7
$\begingroup$

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!

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – russoo Jan 31 '15 at 12:02
  • 1
    $\begingroup$ 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. $\endgroup$ – russoo Jan 31 '15 at 12:45
  • $\begingroup$ @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! $\endgroup$ – Self-teaching worker Jan 31 '15 at 13:25
10
$\begingroup$

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$.

$\endgroup$
  • 2
    $\begingroup$ 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$. $\endgroup$ – HTFB Jan 31 '15 at 12:21
  • 1
    $\begingroup$ @zarathustra: These sentences are the epitome of diagonalization. $\endgroup$ – Asaf Karagila Jan 31 '15 at 12:26
  • 1
    $\begingroup$ My bad, I saw atoms $x_i\neq x_j$ when there were none... You have my upvote :-) $\endgroup$ – zarathustra Jan 31 '15 at 12:33
  • 1
    $\begingroup$ @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$... $\endgroup$ – Asaf Karagila Jan 31 '15 at 12:50
  • $\begingroup$ @AsafKaragila and@HTFB $|\Psi|$ thanks to both! $\endgroup$ – Self-teaching worker Jan 31 '15 at 13:22
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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