2
$\begingroup$

The principle (called a Löwenheim–Skolem theorem by Huth and Ryan) states

Let $\phi$ be a sentence of predicate logic such that for any natural number $n \geq 1$, there is a model of $\phi$ with at least $n$ elements. Then $\phi$ has a model with infinitely many elements.

IMO, it basically states that if you can always name a number larger than mine arbitrary natural number then your model is infinite. What needs to be proven here? There are no other options obviously for any school kid.

PS The answers state that there is a difference between having infinite amount of models and single infinite model. But this is similarly stupid. At first, I do not see whether I claim that I have a single infinite model or approach it by having all denumerable models. Secondly, it does not matter since in any case you should have an infinite model in order to respond to any natural number.

Nevertheless, I started to understand why people (mistakenly) ask me to differentiate between infinite amount of models and models of infinite size. They fail to recognize that principle "The fact that I can always name a number larger than yours implies that we have an infinite model/set", which is intuitive and used to prove the overspill theorem, also implies that the model of infinite size exists. The set of models $A = \{M_k, M_l, M_m \ldots\}$ has sizes $S = \{k, l, m, \ldots\}$ correspondingly. When you speak about size of models, you basically speak of the numbers in $S$. When you say "a model of size n" you just say "n". Thus, we can forget about set of models and speak only about S. Now, you say that "whatever integer you have, set S contains a larger one." This basically means that S contains an infinite number (i.e. $A$ contains infinite models). What to be proven here?

In other words, what is the point of expanding $\phi$ with infinite set $\{I_1, I_2, \ldots\}$ in the proof and applying the Compactness theorem? This says that there is an infinite model. But this is obvious without even without it, right from the the premise of the overspill principle.

$\endgroup$
  • $\begingroup$ @Louis I can always name a number larger than yours. My model is infinite. What have to be proven here and what do I confuse here? $\endgroup$ – Val May 10 '14 at 14:31
  • 1
    $\begingroup$ "But this is obvious without even without it, right from the the premise of the overspill principle." False. $\endgroup$ – Louis May 13 '14 at 12:23
  • 1
    $\begingroup$ Why is this question on CS.SE, rather than on Mathematics.SE? What's the context where this question arose? $\endgroup$ – D.W. May 13 '14 at 17:26
  • $\begingroup$ @D.W. I read a book on Logic in computer science. I am also sure for some unknown reason that logic and such computability stuff as Turing and Compactness is more a subject of computing than basis of math. I would be happy if sombody could draw a line between CS and math. $\endgroup$ – Val May 13 '14 at 17:49
  • $\begingroup$ @Val $S$ does not contain an infinite number; it contains an infinite number of finite numbers. By your analogy, this means $A$ contains infinitely many, finite models. I think it's good that you made your analogy explicit, because it shows what I think is the fundamental thing that you're misunderstanding: $S$ does not contain an infinite number. Besides, an "infinite number" does not make sense; only an "infinite number of things" makes sense. $\endgroup$ – sjmc May 13 '14 at 18:49
6
$\begingroup$

The theorem says that when a sentence has arbitrarily large (finite) models, then it also has infinite models.

The antecedent of the theorem:

$\phi$ is a sentence of predicate logic such that for any natural number $n \geq 1$, there is a model of $\phi$ with at least $n$ elements.

is equivalent to saying that there are infinitely many different models, but it does not state that any of these models are infinite in size.

In fact, it would be clearer to use:

$\phi$ is a sentence of predicate logic such that for any natural number $n \geq 1$, there is a finite model of $\phi$ with at least $n$ elements.

This is not exactly the same statement, but as an antecedent within this theorem, it is equivalent.

The consequent:

$\phi$ has a model with infinitely many elements.

does not say anything about how many different models there are - it just says something about the size of at least one of them.

To see that the truth of this theorem doesn't simply follow from its structure, consider the following statement, which has the same structure:

Let $\phi$ be a sentence of predicate logic such that for any natural number $n \geq 1$, there is an equivalent sentence of predicate logic with at least $n$ elements. Then there is an equivalent sentence with infinitely many elements.

Is this a theorem, too? No, this statement is false, for the simple reason that all sentences of predicate logic have finitely many elements by definition.

$\endgroup$
  • $\begingroup$ 1. You contradict to yourself when say that there are inifinite models but none of them are infinite. 2. When I say that there are infinitely many elements I say exactly that. I do not say that there are many models instead of that. 3. I do not get why my analogy with the infinite set is wrong. When you say that you can come up with a number larger than mine in your model then you say that your model is infinite. I see no other options here. Here is nothing to be proven. $\endgroup$ – Val Apr 21 '14 at 14:04
  • 3
    $\begingroup$ Saying that there are infinitely many models is different from saying that there are infinite models. It's the same difference as between saying that a bag of apples is big and saying that it contains a big apple. $\endgroup$ – reinierpost Apr 21 '14 at 19:11
  • $\begingroup$ You keep askribing this nonsense to me for the 2nd time. Point me where do I say that there are infinitly many models. Why when I talk about initinite models and that I do not I do not speak about infinitly many models you keep informing me that inifinite amount is different from infinite size? $\endgroup$ – Val Apr 23 '14 at 18:00
  • $\begingroup$ I'm sorry, apparently I do not understand what you don't understand. $\endgroup$ – reinierpost Apr 24 '14 at 9:10
  • 1
    $\begingroup$ No, you don't say anything about them, and that is exactly the problem, for those are the two things the theorem is about. It says: if there are infinitely many models, there must be an infinite model. Clearly this is a special property of such models, that requires proof: in general, it is not true that whenever there are infinitely many X, there must be an infinite X. $\endgroup$ – reinierpost May 13 '14 at 13:20
5
$\begingroup$

Your interpretation isn't faithful to the theorem: if within a model you can always find a larger number, then the model is infinite. But the theorem says that if there is an infinite number of finite models, there is also an infinite model (which is not an obvious consequence).

The statement you quote appears in a book I have (Computability and Logic by Boolos and Burgess) as the "Overspill Principle."

Overspill Principle: If a set of sentences has arbitrarily large finite models, then it has a denumerable model.

To prove this, let $\Gamma$ be a set of sentences with arbitrary large finite models. For each $m$ let $I_m$ be a sentence with no nonlogical symbols true in a model iff the model has size $m$ or larger. Let $\Gamma^*=\Gamma\cup\{I_1,I_2,\ldots\}$ be the result of adding every $I_m$ to $\Gamma$. Every finite subset of $\Gamma^*$ has a model, because every such subset is also a subset of $\Gamma\cup\{I_1,I_2,\ldots I_m\}$ for some $m$, and $\Gamma$ has arbitrarily large finite models. By compactness, $\Gamma^*$ itself has a model $M$. Then $M$ is a model of $\Gamma$, but also a model of $I_m$ for every $m$, meaning $M$ has size at least $m$ for every $m$, i.e. $M$ is infinite.

$\endgroup$
  • $\begingroup$ Is there any textbook that explains this slowly? $\endgroup$ – Val May 8 '14 at 22:11
  • $\begingroup$ @Val Yes, here is a pdf of the textbook I mention in the answer. See Corollary 12.16 and the surrounding text. f3.tiera.ru/2/M_Mathematics/MA_Algebra/… $\endgroup$ – sjmc May 9 '14 at 20:26
  • $\begingroup$ Thanks for the correction. Logic in Computer science by Huth and Ryan have misinformed me. But what is the answer? You basically say what I say: if you have a set with arbitrary large number then your set is infinite. What is to prove here? Why do you need to apply the compactness theorem if infinite size model follows directly from the premise? $\endgroup$ – Val May 13 '14 at 8:37
  • $\begingroup$ @Val No. Given that there are arbitrarily large finite models, then there exists an infinite model. Each of the given models is finite. There are many of them, and their size is unbounded. Given that, we want to construct one model which is infinite. $\endgroup$ – Yuval Filmus May 13 '14 at 13:55
  • $\begingroup$ @Yuval Filmus What no? $\endgroup$ – Val May 13 '14 at 14:53
3
$\begingroup$

The other answers are really quite good, but here is basically another variant. Let's start with the logical mistake you're making, just to get it out of the way. Consider the statement:

Let $\mathcal{C} = \{A_1,A_2,\ldots\}$ be a sequence of sets with $\#A_i \ge i$. Then one of the $A_i$ is infinite.

This is not, in general, true. Why? Just take $A_i = [i]$. These are all clearly finite. That $\mathcal{C}$ is infinite doesn't make the statement true.

Here, the idea is that we want $\mathcal{C}$ to be the set of models for $\phi$ and we want to somehow use the infinite sequence of finite models $A_i$ to find a single infinite model $A$.

Since we've seen that this kind of statement isn't always true, clearly something about $\phi$ and things that are true about models of FO sentences that aren't true of arbitrary sets needs to come in.

This is where your second mistake comes in. What you want to prove doesn't say what you think it does. You say:

"it basically states that if you can always name a number larger than mine arbitrary natural number then your model is infinite."

This is not what it says at all. You are imagining a game played within one model. That's wrong.

If you want to give the intuition as a game, it's like this: if for every number $n$ that I give you, you will be able to come back with a (different) finite model $A_n$ of size at least $n$, then there is an infinite model of $\phi$.

Now, we start to see why this might be difficult. Nowhere was it said that any of these $A_n$ are related to each other in a way that lets you combine them into a larger model. This is the crux of the matter. To get around it, as in the other answer, the compactness theorem comes up, as does the hypothesis about $\phi$.

As a meta point, it is not bad to start with some intuition. But when that either trivializes or clashes with the statement, it's a good idea to try and write a formal proof, using the definitions. Usually, this will make clear what went wrong with the intuition, even if it seemed obvious.

$\endgroup$
  • $\begingroup$ Do you mean that $A_n$ contains ${1,2,\ldots,n}$? So, what you say is just despite the set of integers in infinite, every number is finite. This was my misunderstanding (and I still do not see any argument for that). Regarding the game with models, all models are related by their sizes. I say that if I can always come up with a larger model then I have arbitrary large models (there is no largerst model in my list, the size of largest model is unlimited, it is inifinte). How can you say that there is a size limit? $\endgroup$ – Val May 12 '14 at 10:27
  • 1
    $\begingroup$ It will really, really help you to try and write a formal proof for the thing you don't see an argument for. Start with "A set $A$ is infinite if ..." and go from there. $\endgroup$ – Louis May 12 '14 at 10:52
1
$\begingroup$

In order to see why the theorem is not obvious, let us take $\phi$ to be a second-order sentence saying 'my model is finite'. For all $n$, there is a model of $\phi$ with $\geq n$ elements. Yet there is no infinite model.

Hence the theorem fails for second-order logic. The reason it holds for first-order logic is compactness.

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