Re: The IDS, the EDS and the DBMS
From: Jan Hidders <jan.hidders_at_REMOVETHIS.pandora.be>
Date: Wed, 15 Sep 2004 16:06:08 GMT
Message-Id: <pan.2004.09.15.16.09.04.217597_at_REMOVETHIS.pandora.be>
>
> This is because that kind of symbolic representation is base-1 system:
>
> 5=1+1+1+1+1
>
>
> Finitely axiomatisable or not?
Date: Wed, 15 Sep 2004 16:06:08 GMT
Message-Id: <pan.2004.09.15.16.09.04.217597_at_REMOVETHIS.pandora.be>
On Tue, 14 Sep 2004 17:17:27 -0700, Mikito Harakiri wrote:
> "Jan Hidders" <jan.hidders_at_REMOVETHIS.pandora.be> wrote in message
> news:pan.2004.09.14.21.10.13.654821_at_REMOVETHIS.pandora.be...
>> On Tue, 14 Sep 2004 13:29:11 -0700, Mikito Harakiri wrote:
>> > The complexity of finite object can't be specified in absolute terms.
>>
>> Quite interestingly if you consider the operations over unnormalized
>> formulas (so no normalization at all and x + y is straightforwardly
>> represented as "(" x "+" y ")") then for both operations you also have an
>> upperbound of O(|x|+|y|).
>
> This is because that kind of symbolic representation is base-1 system:
>
> 5=1+1+1+1+1
>
>> The question about the complexity of normalization is also interesting. >> From Tarksi we know that the reals are axiomatisable
>
> Finitely axiomatisable or not?
Yes, the first order theory of reals is finitely axiomatisable and in fact decidable. Ten points if you know why this not contradicts Goedel's incompleteness theorems. ;-)
- Jan Hidders