Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I am doing an exercise on the compactness theorem of first order logic. The task is to prove that there is no singe first order sentence which is satisfied in exactly the infinite graphs (thereby, a graph interpretation is an interpretation over a language with a single predicate symbol $\rho(x, y)$ and equality; $\rho(x, y)$ stands for 'there is some edge from $x$ to $y$').

This is easily proved by assuming that there is such a sentence $F$ and by considering $\neg F$ (that is the sentence satisfied by exactly the finite graph interpretations). However, I am wondering whether there is an infinite set of first order sentences which has as its models exactly the infinite graphs. After all a graph can only be infinite if it has an infinite set of vertices (which is the domain of the interpretation). So this reduces to the problem of finding an infinite set of first-order sentences which has as models exactly the infinite sets.

Such a set can be constructed by letting $\Gamma = \{I_n\,|\,n > 0\}$ where $I_n$ denotes a sentence stating that there are at least $n$ elements in the domain. Is this statement right? Note that this is homework, so I'd appreciate if you just gave me some feedback and hints if I am wrong.

share|improve this question
1  
Your $\Gamma$ works fine. –  Brian M. Scott Nov 15 '12 at 20:53
1  
Your set $\Gamma$ certainly is one that gives infinite graphs. So if $F$ is your sentence, then by completeness $\Gamma\cup Graph \vdash F$ where $Graph$ is the graph axioms, so then you can use the finiteness of proof. –  Deven Ware Nov 15 '12 at 20:59
    
@DevenWare This question remains unanswered, you should make your comment an answer! –  Rustyn Jan 14 '13 at 17:55
    
@DevenWare, would you consider posting your comment as an answer so the question becomes answered? –  Kaveh Feb 7 '13 at 1:01

1 Answer 1

The set $\Gamma$ from the question works perfectly well. This is a community wiki answer so that the question does not show up as unanswered.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.