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