Re: deductive databases

Hi,

"Jan Hidders" <jan.hidders_at_REMOVETHIS.pandora.be> wrote in message news:Avqke.99355$Rk1.5615685_at_phobos.telenet-ops.be...
> Torkel Franzen wrote:
>> Jan Hidders <jan.hidders_at_REMOVETHIS.pandora.be> writes:
>>
>>>Since we are doing PA they have to satisfy PA's axioms.
>>
>> You haven't specified that the structure contains + and *
>> operations. Let's skip ahead a bit. Let L be the language of PA
>> extended with two binary predicates p and q. By compactness, it is not
>> the case that there is any set M of sentences in the language of L
>> such that for every structure I obtained by adding to a model of PA
>> two binary relations R and S interpreting p and q, I satisfies the
>> sentences in M if and only if S is the transitive closure of R.
>
> I don't understand how compactness applies if all models that we consider
> are infinite. Can you explain this?

?

Ths FOL compactness theorem says that a set, possibly *infinite*, of first-order sentences has a model (or is satisfiable) , iff every finite subset of it has a model. Also, you are talking, if I understand you correctly, about first-order Peano which is a language, not a model. First-order Peano axioms are statisfied by natural numbers as well as by other (non-standard) structures.

TC inexpressibility in a first-order language was a motivation for least/inflationary fixedpoint/etc. FOL extensions.

> -- Jan Hidders
Received on Wed May 25 2005 - 00:38:52 CEST