[FOM] criteria for the existence of infinite models of FO theories

[Rob Arthan]

On 30 Nov 2012, at 03:26, Charlie wrote:

> 	    Is this the same question as before?  I'm not sure.

I can only find the original posting of the question in July:
> On Jul 30, 2012, at 4:22 PM, Andrei Popescu <uuomul at yahoo.com> wrote:
> 
>> Dear FOM subscribers,
>> 
>> I am searching for (preferably lightweight) syntactic criteria for a first-order theory to admit infinite models.  I would appreciate any pointers to results in the literature.
>> 


> 
> If so, one way would be to incorporate these three simple sentences as axioms (or their conjunction):
> 
> 1) Ax~(Fxx);
> 2) AxAyAz(Fxy & Fyz --> Fxz);
> 3) AxEy(Fxy).
> 
> Charlie Silver

I read Andrei as asking about criteria for determining whether a given system of axioms has an infinite model (rather than something you can add to an axiom system to guarantee that all models are infinite). With my reading, the answer is that the problem is undecidable: it is easy to modify Rabin's proof that the theory of a symmetric binary relation is undecidable to give a proof that the theory of a symmetric binary relation with an infinite field is undecidable, but the decision problem for the latter theory reduces to the problem of whether an infinite model of a set of axioms exists.

Regards,

Rob. 


-------------- next part --------------
An HTML attachment was scrubbed...
URL: </pipermail/fom/attachments/20121202/7c5775cd/attachment.html>