I am trying to understand the basics of computation theory. The Overspill Principle (also at google) basically says if you are cool you can do everything

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

A model is basically a set. The theorem says that if you have a model larger than any model of finite size, you have a model of infinite size. But that is obvious. It is obvious that if, no matter how larger is your finite model, I can always come up with a larger one, this means that my set contains an infinite model. Even the proof of the principle involves expanding Г with $I_1, I_2, \ldots, I_m$ (where $I_m$ says that model size is larger than $m$), applying Complactness theorem to it (which says that such model, larger than $m$, exists) and finally, my common sense is used: the author says that the model must be infinite because it is larger than any finite m. But is clear from the very beginning. What is the point of introducing all these $I_m$s and applying the compactness?

  • 4
    $\begingroup$ Note that antecedent of the compactness theorem is not that $\exists\mathcal{M}\forall n(|\mathcal{M}|\geq n)$, in which case it would be a bit of a triviality. It's "$\forall n\exists\mathcal{M}(|\mathcal{M}|\geq n)$", which only says that you have an endless supply of finite models. It's a pretty substantial result that having enough sizes of finite models means there's an infinite model out there, too. $\endgroup$ – Malice Vidrine May 18 '14 at 9:26
  • $\begingroup$ @MaliceVidrine Can we reaplace $|M|$ with $m$? $\exists m\forall n(m \ge n)$ is not the same as $\forall n\exists m(m \ge n)$. Whereas the first says that there exists a row whose every cell complies to a property (it has 1 in every column), the second is not that strict. It tells just for every column, you'll find a cell (i.e. there is a row), containing 1. First says that the largest is one and the same machine. The other says that we can find a machine larger than every your number n2 but it is not necessary the same machine that is larger than another size n1. How does it break my logic? $\endgroup$ – Val May 18 '14 at 10:15
  • $\begingroup$ @MaliceVidrine I guess that there is a lot of machines larger than 0. There is ten less machines larger than 10. We have a lower triangular matrix, the amount of ones per column is decrementing as we make one step to the right, to the infinity. I guess that in the end of this process, we end up with single row of all ones -- the infinite machine that is larger than any (finite) number. Since, by definition, such model exists, it must be that model satisfies both $\exists M \forall n (|M| \ge n)$ and $\forall n \exists M (|M| \ge n)$. When you satisfy the stronger req, you satisfy the midler. $\endgroup$ – Val May 18 '14 at 10:55
  • 1
    $\begingroup$ Your logic is broken in the case you believe the former, stronger formula is the antecedent of the compactness theorem, which it is not. If you do not believe this, then your logic is still broken for very different reasons :p $\endgroup$ – Malice Vidrine May 18 '14 at 15:17
  • 1
    $\begingroup$ There are not actually any fewer machines greater than 10 than there are greater than 0 if there's an infinite number of them; that might be one problem. It's not generally true that having a lot of different finite sizes of something implies an infinite something; there are arbitrarily large finite proper initial segments of $\mathbb{N}$, but it obviously doesn't follow that there are any infinite ones. $\endgroup$ – Malice Vidrine May 18 '14 at 15:19

To see how this is not obvious, let us see an example out of the grasp of first-order logic.

Consider $\cal L$ the logic obtained by adding $\forall^\infty$ quantifier, whose interpretation is "all but finitely many". This logic is stronger than first-order logic, it can express more things.

In first-order logic we can say something like "The universe has exactly/at most $42$ elements" in order to say that it is finite. The overspill principle says that in a first-order theory, if it cannot prove that some natural number $n$ is an upper bound to the size of models, then there is an infinite model.

But consider a theory in the logic $\cal L$ whose only axiom is this: $$\forall x\forall^\infty y(x=y)$$

This axiom says that every $x$ is equal to all but finitely many elements, that is to say that if $M$ is a model of this axiom, then for every $x\in M$ the set $M\setminus\{x\}$ is finite. Therefore if $M$ satisfies this axiom, it has to be finite since it is the union of $M\setminus\{x\}$ and $\{x\}$ which are two finite sets.

But not only this. Given any finite non-empty set, $M$, then $M$ is a model for this axiom. Because every $x$ is only different from finitely many elements of the universe -- $M$.

So the axiom above has a model of size $1,2,3,4,\ldots$ but no infinite model.

So what goes wrong here? The fact that $\cal L$ does not have a compactness theorem. In first-order logic, however, the overspill principle shows that unless you can specify how large is the universe, there is an infinite model.

  • $\begingroup$ I do not understand what initial segment is finite means. You say like the models are finite but cannot be so in that language/theory. This just means that there are no models. Might be the problem is that I do not understand what the finite linear order is. $\endgroup$ – Val May 18 '14 at 9:36
  • $\begingroup$ Do you understand what a finite set is? Do you understand what a linear order is? This is a logic stronger than first-order logic. It can express more things than what first-order logic can. In particular it can express the statement "The universe is finite" without explicitly expressing how many elements are in the universe. I think that if you don't understand the statement "finite linear order" then you need to go back to the basics, much much before the compactness theorem. In any case, I'll edit with a simpler example. $\endgroup$ – Asaf Karagila May 18 '14 at 9:41
  • $\begingroup$ You say that M is finite because it is infinite otherwise. I see no problem with M infinite. Actually I see that axiom says that our $x$-es are equal to any $y$ from infinity rather than differ from it. Might be you wanted to say that one element cannot equal to everything (including other, distinct elements) or just missed a negation? $\endgroup$ – Val May 18 '14 at 11:24
  • $\begingroup$ If $M$ is infinite, pick any $x$, then the set $M\setminus\{x\}$ is infinite. So the axiom is not true there. $\endgroup$ – Asaf Karagila May 18 '14 at 11:25
  • 1
    $\begingroup$ @Val: If we have compactness, then we can add to the theory the statements "There are at least $k$ elements in the universe", which are expressible in first-order logic. Then by showing that every finite subset of the theory has a model, compactness assures that the entire theory has a model. But in this model there are at least $k$ elements for every finite $k$, and therefore there must be infinitely many elements in the universe of that model, so the model is infinite. And if it satisfies the original theory with more axioms, it certainly satisfies the original theory we cared about. $\endgroup$ – Asaf Karagila May 20 '14 at 11:15

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.