10
$\begingroup$

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.

$\endgroup$
4
  • 1
    $\begingroup$ Your $\Gamma$ works fine. $\endgroup$
    – Brian M. Scott
    Nov 15, 2012 at 20:53
  • 1
    $\begingroup$ 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. $\endgroup$
    – Deven Ware
    Nov 15, 2012 at 20:59
  • $\begingroup$ @DevenWare This question remains unanswered, you should make your comment an answer! $\endgroup$
    – Rustyn
    Jan 14, 2013 at 17:55
  • $\begingroup$ @DevenWare, would you consider posting your comment as an answer so the question becomes answered? $\endgroup$
    – Kaveh
    Feb 7, 2013 at 1:01

1 Answer 1

Reset to default
1
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .