# No proposition $\chi$ such that $\mathscr{M}\models\chi\iff\mathscr{M}$ is infinite

Let notation "$\models$" be used for the two following case:

• let $\mathscr{M}\models\varphi$, where $\mathscr{M}$ is an interpretation model and $\varphi$ is a proposition, mean that $\varphi$ holds in model $\mathscr{M}$;
• let $\Phi\models\varphi$, where $\Phi$ is a set of propositions and $\varphi$ is a proposition, mean that $\varphi$ is a logical consequence of $\Phi$, i.e. that it holds in all models where the propositions belonging to $\Phi$ hold.

I read the following interesting theorem (V. Manca, Logica matematica, 2001), whose proof I cannot understand:

There is no proposition $\chi$ such that $$\mathscr{M}\models\chi\iff\mathscr{M}\text{ is infinite}.$$ Proof: Let us suppose that such a proposition $\chi$ exists. Let us consider theory $\Psi$ of the countable domain:$$\mathscr{M}\models\Psi\Rightarrow\mathscr{M}\models\chi$$therefore$$\Psi\models\chi$$and this is absurd because of the finiteness theorem.

There are two main things obscure to me: what a theory of the countable domain [teoria del dominio numerabile in the book's original Italian language] is and how the finiteness theorem makes the last formula absurd. By finiteness theorem I suppose that the only one theorem bearing that name shown in the book is intended, which says that, given a set of propositions $\Phi$ and a proposition $\varphi$, $\Phi\models\varphi\iff\Delta\models\varphi$ for some finite subset $\Delta\subseteq\Phi$. Does anybody understand this proof? I heartily thank you for any answer!

• This is indeed a strange proof of this well-known theorem and like you, I do not understand it. All what I can do in order to help you is to show you the "standard" proof of the theorem in question. – russoo Jan 31 '15 at 12:02
• If you would like to see the standard proof, just let me know and answer to my comments. I will then write this as an answer to your post. – russoo Jan 31 '15 at 12:45
• @russoo I desired to be able to understand the book's proof. Failing to understand a proof is always frustrating for mathematics' lovers. But if you like to explain another more "usual" proof, I'll be grateful to you and glad to study it! – Self-teaching worker Jan 31 '15 at 13:25

It would make sense if the "theory of the countable domain" $\Psi$ is the theory containing the sentences "there are at least $n$ objects" for each $n$, i.e. the sentences $\forall x_1, \ldots, x_{n-1}\, \exists x_n\, \bigwedge_{i<n} x_n \neq x_i$.

Any finite subset of this theory has a finite model. By the finiteness theorem (more usually known as the compactness theorem for first-order logic), if $\Phi \models \chi$ then there is a finite subset of $\Phi$ that models $\chi$; so $\chi$ is true in the finite model of that particular finite subset. This contradicts the assumption on $\chi$.

• No. If $n>2$ and $\mathcal{M}$ is a model with two elements ${a,b}$, then we can choose $x_1 = a$ and $x_2 = b$; then the formula (actually a sentence; I'll edit the answer) says we are able to find an $x_n$ which is different from both $a$ and $b$. – HTFB Jan 31 '15 at 12:21
• @zarathustra: These sentences are the epitome of diagonalization. – Asaf Karagila Jan 31 '15 at 12:26
• My bad, I saw atoms $x_i\neq x_j$ when there were none... You have my upvote :-) – zarathustra Jan 31 '15 at 12:33
• @Self-teachingDavide: Note that $\Psi$ is the theory of infinite sets, so it must hold in all infinite models; and since $\chi$ holds in all infinite models, $\Psi\models\chi$. Therefore (by compactness) there is a finite subset $\Phi$ such that $\Phi\models\chi$. And now we find a finite model of $\Phi$... – Asaf Karagila Jan 31 '15 at 12:50
• @AsafKaragila and@HTFB $|\Psi|$ thanks to both! – Self-teaching worker Jan 31 '15 at 13:22

Here is a sketch for a more "conventional" proof for the theorem.

First of all, you have to proof the following:

$\textbf{Lemma.}$ There is no theory $T$ such that the class of of models of $T$ consists exactly of all the finite models.

The above lemma may already be known to you. It's proof is a typical example for the application of the compactness theorem.

Now, to proof the theorem which is the subject of your post, let us assume there is a sentence $\chi$ with

$\phantom{assssssssssssssssssssasaaaaaaaaa}$$M \models \chi$ iff $M$ is infinite

Then, the class of models of $\neg \chi$ is exactly the class of all finite models - a contradiction to our lemma from above.