Overflow Theorem

Theorem

Let $A$ be a set of first-order formulas which has finite models of arbitrarily large size.

Then $A$ has an infinite model.

Corollary

The class of finite models is not $\Delta$-Elementary.

That is, there is no set of formulas $F$ such that $F$ is satisfied by a model $\mathcal M$ iff $\mathcal M$ is finite.

Proof

For each $n$, let $A_n$ be the formula:

$\exists x_1 \exists x_2 \ldots \exists x_i: \left({x_1 \ne x_2 \land x_1 \ne x_3 \land \ldots \land x_n \ne x_{n-1} }\right)$

Then $A_i$ is true in an interpretation $I$ iff $I$ has at least $i$ elements.

Now, take $\displaystyle \Gamma \equiv A \cup \bigcup_{i=1}^\infty A_i$.

Since $A$ has models of arbitrarily large size, every finite subset of $\Gamma$ is satisfiable, from Compactness of First-Order Logic.

So $\Gamma$ is satisfiable in some model $\mathcal M$.

But since $\mathcal M \models A_i$ for each $i$, $\mathcal M$ must be infinite.

So $A$ has an infinite model.

$\blacksquare$

Proof of Corollary

Follows directly from the Overflow Theorem above.

$\blacksquare$