Show that Γ has an infinite model.

Question

Suppose that Γ is a set of sentences with arbitrarily large finite models (that is, for every natural number n, there is some interpretation whose domain has more than n members such that every member of Γ is true in that interpretation). Show that Γ has an infinite model.

Answer 1

This is a corollary of the compactness theorem for first-order logic which in turn is a corollary of the strong completeness theorem for first-order logic.

---

Let $\Gamma$ be a set of sentences with arbitary large finite models, i.e. for every $n\geq 1$, there is a structure $\mathcal A$ in the signature of $\Gamma$ s.t. $|A|>n$ where $A$ is the domain of $\mathcal A$.

Take $$\Gamma^*=\Gamma\cup\{\phi_{>n}\mid n\geq 0\}$$ where $$\phi_{>n}=\exists x_0\dots\exists x_n\bigwedge_{i,j\leq n, i\neq j}\neg x_i=x_j$$

Note, that $\phi_{>n}$ is a sentence for every $n\geq 0$. Then, if $\mathcal A$ is a structure in the signature of $\Gamma$, then $\mathcal A\models \phi_{>n}$ iff $|A|>n$.

---

Now, we show that every finite subset of $\Gamma^*$ has a model. For this, let $\Gamma_0\subseteq\Gamma^*$ be finite. Then $\Gamma_0\subseteq \Gamma\cup\{\phi_{>n}\mid n\leq m\}$ for some $m$.

As $\Gamma$ has arbitrary large finite models, take a model $\mathcal A$ of $\Gamma$ which satisfies $|A|>m$. Then $\mathcal A\models\Gamma\cup\{\phi_{>n}\mid n\leq m\}$ and thus $\mathcal A\models\Gamma_0$.

---

By the compactness theorem, we have that $\Gamma^*$ has a model $\mathcal B$ and now $|B|$ is infinite, as suppose it is finite, then $|B|=n$ for some $n\geq 1$ but $\mathcal B\models\phi_{>n}$. Contradiction.