In 1929, at the age of twenty-three, Kurt Gödel published his doctoral dissertation establishing the crowning achievement of early mathematical logic: the Completeness Theorem for First-Order Logic. Gödel proved that the purely syntactic, mechanical deduction rules formulated by Frege, Russell, and Hilbert are universally capable of proving every first-order mathematical truth. Its immediate corollary, the Compactness Theorem, became the foundational sledgehammer of modern model theory.
1. The Completeness Statement
Let $Sigma$ be a set of first-order sentences and $phi$ a sentence in a first-order language $mathcal{L}$.
[
Sigma vDash phi implies Sigma vdash phi
]
Semantic validity ($Sigma vDash phi$—in every mathematical universe where the axioms of $Sigma$ hold, $phi$ must also hold) guarantees syntactic provability ($Sigma vdash phi$—there exists a finite, step-by-step mechanical proof of $phi$).
Equivalently formulated via consistency:
The Model Existence Theorem
A first-order theory $Sigma$ is syntactically consistent ($Sigma notvdash bot$) if and only if $Sigma$ has a model ($exists mathcal{M} vDash Sigma$).
2. The Henkin Construction (1949)
While Gödel’s original 1929 proof used normal forms and projection, Leon Henkin introduced in 1949 an immensely elegant proof technique that constructs the model directly out of the typographical symbols of the language itself. The proof consists of four monumental steps:
Step 1: Adding Henkin Witness Constants
Extend the language $mathcal{L}$ to $mathcal{L}^*$ by adding a countably infinite reservoir of witness constants $c_phi$. For every formula $phi(x)$ with one free variable, add the axiom:
[
exists x , phi(x) to phi(c_phi)
]
Henkin proved that this extension preserves syntactic consistency: if $Sigma$ was consistent, $Sigma^*$ remains consistent.
Step 2: Maximal Consistent Extension (Lindenbaum’s Lemma)
By Zorn’s Lemma (or an inductive enumeration of all formulas $phi_1, phi_2, dots$), extend $Sigma^*$ to a maximally consistent theory $T^*$. For every sentence $psi$, either $psi in T^*$ or $neg psi in T^*$, but never both.
Step 3: Defining the Equivalence Relation on Terms
Define an equivalence relation $sim$ on the closed terms of $mathcal{L}^*$ based on provable equality in $T^*$:
[
t_1 sim t_2 iff (t_1 = t_2) in T^*
]
Because the axioms of equality ($x=x$, $x=y to y=x$, $x=y land y=z to x=z$) are in $T^*$, $sim$ is a genuine congruence relation.
Step 4: The Canonical Term Model
Construct the structure $mathcal{M}$ where the universe $M$ is the set of equivalence classes of closed terms: $M = { [t] mid t text{ is a closed term} }$. Interpret functions and relations by:
[
f^mathcal{M}([t_1], dots, [t_n]) = [f(t_1, dots, t_n)]
]
[
([t_1], dots, [t_n]) in R^mathcal{M} iff R(t_1, dots, t_n) in T^*
]
By the Truth Lemma, for every sentence $psi$:
[
mathcal{M} vDash psi iff psi in T^*
]
Since $Sigma subseteq T^*$, $mathcal{M}$ is a genuine model of $Sigma$! Mathematical reality has been forged purely out of syntax.
3. The Compactness Theorem
The most consequential byproduct of Completeness is the Compactness Theorem:
The Compactness Theorem
A set of first-order sentences $Sigma$ has a model if and only if every finite subset $Sigma_0 subseteq Sigma$ has a model.
Proof: Suppose $Sigma$ has no model. By Completeness, $Sigma$ is inconsistent ($Sigma vdash bot$). But any formal derivation consists of a finite sequence of formulas, meaning it can only invoke a finite number of premises $Sigma_0 subseteq Sigma$. Thus $Sigma_0 vdash bot$. By Soundness, $Sigma_0$ has no model. By contraposition, if every finite subset $Sigma_0$ has a model, $Sigma$ must have a model. $blacksquare$
4. The Power of Compactness: Non-Standard Arithmetic
Compactness demonstrates that first-order logic cannot enforce finiteness. Let $text{Th}(mathbb{N})$ be the set of all true first-order sentences about natural numbers. Introduce a new constant $c$ and define the infinite theory:
[
Sigma = text{Th}(mathbb{N}) cup { c > 0, c > 1, c > 2, c > 3, dots }
]
Any finite subset $Sigma_0$ mentions only finitely many inequalities $c > k$. We can satisfy $Sigma_0$ in the standard natural numbers simply by setting $c = k + 1$. Thus, every finite subset has a model!
By Compactness, the entire infinite theory $Sigma$ must have a model $mathcal{N}^*$! In $mathcal{N}^*$, all standard arithmetic truths hold, yet the element $c$ is an “infinite integer” strictly greater than every standard number $0, 1, 2, 3, dots$. First-order logic is structurally incapable of preventing the existence of transfinite, non-standard universes.
