Compactness and the Löwenheim–Skolem Theorems

The completeness theorem equates deduction and truth for first-order logic: $\Gamma ⊢\phi$ exactly when $\Gamma \models \phi$. Read at the level of a whole set of sentences, that equivalence converts a finiteness fact about deductions — every deduction is a finite object using only finitely many hypotheses — into a theorem about models.

Compactness for first-order logic

A deduction of $\phi$ from $\Gamma$ is a finite sequence of formulas. It can therefore invoke only finitely many members of $\Gamma$ as hypotheses. Combined with the equivalence of consistency and satisfiability from the completeness proof, this yields the semantic form of compactness.

The forward direction is immediate: a model of $\Gamma$ is a model of each finite subset. The content is the converse. Suppose $\Gamma$ is unsatisfiable. By completeness it is inconsistent, so $\Gamma ⊢\phi$ and $\Gamma ⊢\neg \phi$ for some $\phi$. Each of those two deductions is finite and uses finitely many members of $\Gamma$; collect them into a finite ${\Gamma }_0\subseteq \Gamma$. Then ${\Gamma }_0$ proves both $\phi$ and $\neg \phi$, so ${\Gamma }_0$ is inconsistent, hence unsatisfiable. Contrapositively, if every finite subset is satisfiable then so is $\Gamma$.

The sentential version was proved directly from König's lemma; here the first-order version is a corollary of completeness.¹

Finite and infinite models

Some sentences constrain the size of their models. Every model of $\forall x\forall yx=y$ has exactly one element. Others admit only infinite models: the sentence asserting that $<$ is an ordering with no largest element is true in $(\mathbb{N},<)$ but in no finite ordering. Compactness forbids the intermediate case where a set of sentences has arbitrarily large finite models but no infinite one.

For each integer $k\ge 2$ there is a sentence ${\lambda }_k$ saying there are at least $k$ distinct things, built by asserting the existence of $k$ pairwise distinct elements:

The theorem rules out subtle finite/infinite dividing lines. No equation of group theory can be true in every finite group and false in every infinite one: if it held in arbitrarily large finite groups it would hold in an infinite group too.

Elementary classes

The infinite-model theorem is best phrased through the notion of an elementary class. A class $K$ of structures is $\mathrm{EC}$ if $K=\text{Mod }\tau$ for a single sentence $\tau$, and ${\mathrm{EC}}_{\Delta }$ if $K=\text{Mod }\Sigma$ for a set $\Sigma$ of sentences.

The infinite structures do form an ${\mathrm{EC}}_{\Delta }$ class, namely $\text{Mod }\{{\lambda }_2,{\lambda }_3,\dots \}$. But no single sentence captures them: were $\text{Mod }\tau$ to contain the infinite structures and nothing else, then $\text{Mod }\neg \tau$ would contain the finite ones and nothing else, and by the infinite-model theorem that class is not even ${\mathrm{EC}}_{\Delta }$. First-order logic can require infinity (with infinitely many sentences) but cannot forbid it with a finite axiom, and cannot express finite at all.

This limitation extends to decidability. For a finite structure $\mathfrak{A}$ in a finite language, $\text{Th }\mathfrak{A}$ is decidable: replace $\mathfrak{A}$ by an isomorphic copy on the universe $\{1,\dots ,n\}$, then evaluate any sentence by a finite tree search, each quantifier triggering a sweep of the $n$ elements. One might hope the sentences true in every finite structure form a decidable set. They do not. Trakhtenbrot's theorem (1950) states that $\{\sigma \mid \sigma \text{ is true in every finite structure}\}$ is not decidable and not even effectively enumerable, so the enumerability results that hold for validity over all structures fail when attention is restricted to finite ones.

The size of a model

The completeness proof built a model out of syntax. Its size can be read off the construction. Starting from a consistent set $\Gamma$ in a countable language, one adjoins countably many new constant symbols and takes the universe of the term model to be equivalence classes of terms. A countable language has countably many terms, so the term model is countable.²

Applied with $\Gamma =\text{Th }\mathfrak{A}$, this gives a countable structure elementarily equivalent to any structure for a countable language. If $\mathfrak{B}\models \text{Th }\mathfrak{A}$ then $\mathfrak{A}\equiv \mathfrak{B}$, since every sentence true in $\mathfrak{A}$ lies in $\text{Th }\mathfrak{A}$ and so holds in $\mathfrak{B}$, and the same runs through negations. The real field $(\mathbb{R};0,1,+,\cdot )$ is uncountable, yet some countable field satisfies exactly the same first-order sentences; the field of real algebraic numbers is one such.

Skolem's paradox

Take a consistent set $A_{ST}$ of axioms for set theory. It has a model, so by the downward theorem it has a countable model $\mathfrak{S}$. Among the consequences of $A_{ST}$ is a sentence asserting the existence of uncountably many sets. That sentence holds in the countable $\mathfrak{S}$. The apparent conflict, Skolem's paradox, dissolves on inspection. Within $\mathfrak{S}$ there is no element coding a bijection between the naturals and the universe. The uncountability sentence asserts precisely that no such internal bijection exists. That a genuine bijection exists outside $\mathfrak{S}$, in the ambient set theory, is no contradiction, because it is not an element of the model.

Larger models and nonstandard arithmetic

Compactness runs the other way as well: it manufactures elements that no standard model contains. Consider the standard structure of arithmetic

Add a fresh constant symbol $c$ and the sentences

each saying that $c$ exceeds a particular standard numeral. Any finite subset of $\Sigma \cup \text{Th }\mathfrak{N}$ mentions finitely many of these, so it is satisfied in $\mathfrak{N}$ with $c$ interpreted as a large enough natural number. By compactness the whole set has a model, and by the downward theorem a countable model $\mathfrak{M}$. Restricting $\mathfrak{M}$ to the original language gives ${\mathfrak{M}}_0\equiv \mathfrak{N}$: it satisfies every sentence of $\text{Th }\mathfrak{N}$, hence exactly the same sentences as $\mathfrak{N}$. Yet it is not isomorphic to $\mathfrak{N}$, because the element interpreting $c$ is larger than every standard numeral.

The element interpreting $c$ is a nonstandard, infinite natural number. Every first-order sentence true of $\mathbb{N}$ remains true of ${\mathfrak{M}}_0$, so no first-order property distinguishes the two structures; the difference lives entirely in the isomorphism type, which first-order logic cannot detect. The same construction on $(\mathbb{N},<)$ shows that there is no infinite descending chain is not first-order expressible: a nonstandard model has descending chains below its infinite elements yet agrees with $\mathbb{N}$ on every sentence.

Upward Löwenheim–Skolem

The nonstandard construction generalizes to any cardinality. The upward part is due to Tarski, giving the combined theorem its LST label.³

The failure of first-order categoricity

Call a set $\Sigma$ of sentences categorical if any two of its models are isomorphic. The Löwenheim–Skolem–Tarski theorem forces a verdict: a set of first-order sentences with an infinite model is never categorical, because it has non-isomorphic models of different cardinalities. In particular no set of first-order sentences has exactly the structures isomorphic to $(\mathbb{N};0,S,+,\cdot )$ as its models. The natural numbers are not first-order categorical.

Categoricity remains only in restricted forms. A theory can be categorical in a cardinality — all its models of a fixed size isomorphic — even though it has non-isomorphic models across sizes. This weaker notion, $\kappa$-categoricity, still forces completeness through the Łoś–Vaught test. Full categoricity returns only in second-order logic, where the induction axiom quantifies over subsets and pins $\mathbb{N}$ to a single isomorphism type, at the cost of compactness and completeness.

The recurring technique in every construction is the same: write down the sentences describing the structure wanted, argue that each finite subset is satisfiable in a structure already at hand, and let compactness supply the rest.