The Completeness Theorem

Soundness gave the easy inclusion $⊢ \subseteq ⊨$ . The reverse is the deep theorem of first-order logic: the syntactic calculus is strong enough to derive every semantic consequence.

Parts (a) and (b) are equivalent, so it suffices to prove (b). For (b) $\Rightarrow$ (a), $Γ ⊨ φ$ makes $Γ \cup {\neg φ}$ unsatisfiable, hence inconsistent by (b), so $Γ ⊢ φ$ by reductio. For (a) $\Rightarrow$ (b), an unsatisfiable set logically implies every formula, in particular some $β$ and $\neg β$ , so by (a) it is inconsistent. We prove (b) for a countable language and indicate the changes for larger cardinalities at the end. The construction is due to Henkin, and unlike Gödel's original proof it scales to any cardinality.¹

Consistency versus satisfiability

Consistency is a syntactic property (no formula and its negation are both provable); satisfiability is semantic (some structure makes everything true). Completeness asserts they coincide. Soundness already gave satisfiable $\Rightarrow$ consistent. The hard direction builds a structure from nothing but the formulas, so the model's elements must be syntax. The plan extends $Γ$ to a set $Δ$ so saturated that a structure can be read directly off it.

The completeness proof as a pipeline: enrich the language and the set until a model can be read off the formulas, then quotient by equality.

Fix a consistent set $Γ$ in a countable language. The target is a set $Δ \supseteq Γ$ with two properties:

maximal consistent: consistent, and for every $α$ , either $α \in Δ$ or $\neg α \in Δ$ ;
witnessing (Henkin): for every $φ$ and $x$ , some constant $c$ has $(\neg\forall x φ \to \neg φ_{c}^{x}) \in Δ$ .

Maximality decides every formula; the witnessing property ensures that whenever $Δ$ denies a universal, it names a specific counterexample. Those two features supply what the satisfaction recursion needs.

Step 1: witnessing constants

Expand the language with a countably infinite set of new constant symbols. As a set of wffs in the larger language, $Γ$ stays consistent.

If not, some $β$ has a deduction of $β \land \neg β$ from $Γ$ in the expanded language. A deduction is finite, so it uses only finitely many new constants; by generalization on constants each may be replaced by a variable, yielding a deduction of $β^{'} \land \neg β^{'}$ from $Γ$ in the original language. That contradicts the consistency of $Γ$ .

Step 2: Henkin axioms

For each pair $φ, x$ we want to add the sentence

θ : \neg\forall x φ \to \neg φ_{c}^{x},

where $c$ is a new constant. The reading: $c$ names a counterexample to $φ$ , should one exist. Enumerate all pairs $⟨ φ_{1}, x_{1} ⟩, ⟨ φ_{2}, x_{2} ⟩, \dots$ (possible since the language is countable). Define $θ_{n} = (\neg\forall x_{n} φ_{n} \to \neg (φ_{n})_{c_{n}}^{x_{n}})$ , taking $c_{n}$ to be the first new constant occurring in neither $φ_{n}$ nor any earlier $θ_{k}$ . Let $Θ = {θ_{1}, θ_{2}, \dots}$ . Then $Γ \cup Θ$ is consistent.

Suppose not. Deductions are finite, so $Γ \cup {θ_{1}, \dots, θ_{m + 1}}$ is inconsistent for a least $m$ . By reductio,

Γ \cup {θ_{1}, \dots, θ_{m}} ⊢ \neg θ_{m + 1} .

Now $θ_{m + 1}$ is $\neg\forall x φ \to \neg φ_{c}^{x}$ , so rule T extracts both $Γ \cup {θ_{1}, \dots, θ_{m}} ⊢ \neg\forall x φ$ and $Γ \cup {θ_{1}, \dots, θ_{m}} ⊢ φ_{c}^{x}$ . The constant $c$ occurs in none of the formulas on the left, so the corollary to generalization on constants turns the second into $Γ \cup {θ_{1}, \dots, θ_{m}} ⊢ \forall x φ$ . That contradicts the first, and the leastness of $m$ (or the consistency of $Γ$ when $m = 0$ ). So $Γ \cup Θ$ is consistent.

The Henkin axiom in force: whenever the saturated set denies a universal, its witnessing constant names a specific counterexample inside it.

Step 3: a maximal consistent extension

Extend the consistent $Γ \cup Θ$ to a set $Δ$ that is maximal: consistent, with $α \in Δ$ or $\neg α \in Δ$ for every wff $α$ . One route imitates the sentential compactness construction. A cleaner route uses the tautological-implication characterization of deducibility: since $Γ \cup Θ$ is consistent, $Γ \cup Θ \cup Λ$ does not tautologically imply any $β \land \neg β$ , so some truth assignment $v$ on the prime formulas satisfies $Γ \cup Θ \cup Λ$ . Set

Δ = {φ : v (φ) = T} .

For every $φ$ , exactly one of $φ, \neg φ$ lies in $Δ$ . Moreover $Δ$ is deductively closed: if $Δ ⊢ φ$ , then by consistency $Δ ⊬ \neg φ$ , so $\neg φ \in / Δ$ , so $φ \in Δ$ by maximality.

A maximal consistent set decides every formula. Extending the given set, each formula or its negation is admitted, never both, climbing to a set that is deductively closed.

At this point $Δ$ decides every sentence and, thanks to $Θ$ , names a witness against every denied universal. It remains to turn $Δ$ into a structure.

Step 4: the term model

Build a preliminary structure $A$ whose universe is the syntax itself. If the language has equality, first replace $=$ by a fresh two-place predicate symbol $E$ ; write $φ^{*}$ for the result of that replacement in $φ$ .

Take $s : V \to ∣ A ∣$ to be the identity, $s (x) = x$ . Then $s (t) = t$ for every term $t$ (induction on $t$ ). The core claim links satisfaction to membership.

Proof. Induction on the number of connective and quantifier symbols in $φ$ .

Atomic. By construction. For $P t$ : $⊨_{A} P t [s]$ iff $s (t) \in P^{A}$ iff $t \in P^{A}$ iff $P t \in Δ$ . For $u = t$ : $⊨_{A} u E t [s]$ iff $⟨ u, t ⟩ \in E^{A}$ iff $(u = t) \in Δ$ .
Negation. $⊨_{A} (\neg φ)^{*} [s]$ iff not $⊨_{A} φ^{*} [s]$ iff $φ \in / Δ$ (inductive hypothesis) iff $\neg φ \in Δ$ (maximality).
Conditional. $⊨_{A} (φ \to ψ)^{*} [s]$ iff $φ \in / Δ$ or $ψ \in Δ$ , which, since $Δ$ is maximal and deductively closed, holds iff $(φ \to ψ) \in Δ$ .
Quantifier. The forward direction of $⊨_{A} \forall x φ^{*} [s]$ iff $\forall x φ \in Δ$ is where $Θ$ is used: if $φ^{*}$ is true of everything it is true of the witness $c$ , so $φ_{c}^{x} \in Δ$ ; the Henkin axiom $\neg\forall x φ \to \neg φ_{c}^{x}$ then forces $\forall x φ \in Δ$ . The converse uses the substitution lemma, repaired with an alphabetic variant when the witness term is not substitutable. $■$

If the language has no equality, we are done: restricting $A$ to the original language gives a structure satisfying every member of $Γ$ with the identity assignment.

Steps 5 and 6: quotient by equality

With equality present, $A$ is wrong: it may contain distinct terms $c, d$ with $(c = d) \in Δ$ , yet $c^{A} = c \neq = d = d^{A}$ . The fix collapses $E$ -equivalent terms. By the equality facts Eq1–Eq5, $E^{A}$ is a congruence: an equivalence relation (Eq1–Eq3) compatible with every predicate (Eq4) and function (Eq5).

Congruence makes these definitions independent of representatives, so $A / E$ is well defined, and $E^{A / E}$ is the genuine equality relation on the classes.

By the homomorphism theorem, for every $φ$ ,

φ \in Δ \leftrightarrow ⊨_{A} φ^{*} [s] \leftrightarrow ⊨_{A / E} φ^{*} [h \circ s] \leftrightarrow ⊨_{A / E} φ [h \circ s] .

The term model, then its quotient. Distinct terms that the set forces equal are merged into one element, so the interpreted equality symbol becomes real identity.

Restricting $A / E$ to the original language gives a structure satisfying every member of $Γ$ with $h \circ s$ . So the consistent $Γ$ is satisfiable, proving part (b) and with it the completeness theorem.

Step	Action	Property secured
1	add new constants	room for witnesses; consistency preserved
2	add Henkin axioms $\neg\forall x φ \to \neg φ_{c}^{x}$	a named counterexample for every denied universal
3	extend to $Δ$ maximal consistent	every formula decided; deductively closed
4	build the term model $A$	satisfaction equals membership in $Δ$
5	quotient by the congruence $E$	interpreted $=$ becomes real identity
6	restrict to the original language	a model of $Γ$ itself

For an uncountable language of cardinality $λ$ , three changes suffice: add $λ$ new constants in step 1; index the pairs by ordinals below $λ$ in step 2 (at each stage only $ℵ_{0} \cdot card (α)$ constants are excluded, leaving some free); and obtain the maximal set in step 3 by Zorn's lemma. Everything else is unchanged.²

Consistency equals satisfiability

Completeness (b) with the soundness corollary gives the full equivalence.

The model-theoretic consequences rest on this equivalence. Consistency is syntactic and finitary (deductions are finite); satisfiability is semantic. The equivalence transports finiteness from one side to the other.

The two theorems close a loop. Soundness runs one way, completeness the other, so the syntactic and semantic consequence relations coincide.

Compactness and enumerability

Two further theorems, provable independently, are immediate from completeness. They underpin the model theory built on first-order logic.

Compactness mentions only semantics, yet the shortest route runs through the deductive calculus. The finiteness it asserts comes entirely from the finiteness of deductions.

The second theorem needs a mild effectiveness assumption. A language is reasonable if its parameters can be effectively enumerated and the arity relations for predicate and function symbols are decidable; every finite language qualifies, and a reasonable language is necessarily countable.

Algorithm:

\textsc{EnumerateValidities}

— list every valid wff of a reasonable language

1
for each finite sequence $\alpha_0, \dots, \alpha_n$ of wffs, in order of increasing code do
2
if the sequence is a deduction from $\varnothing$ then
3
output $\alpha_n$

The same argument relativizes to any decidable set of nonlogical axioms.

A complete decidable theory is therefore decidable, the link to categoricity and the Łoś–Vaught test. Enumerability does not in general upgrade to decidability of validity itself: for almost all languages the valid wffs are undecidable, which is Church's theorem in the incompleteness chapter.

Enderton, §2.5, Historical Notes. The completeness theorem for countable languages is Gödel's 1930 dissertation, with compactness as a corollary; the Henkin-style proof given here is from Henkin's 1949 dissertation and generalizes to any cardinality. ↩
Enderton, §2.5, the paragraph on uncountable languages; $λ$ is taken as an initial ordinal and the language well-ordered. ↩

Consistency versus satisfiability

Step 1: witnessing constants

Step 2: Henkin axioms

Step 3: a maximal consistent extension

Step 4: the term model

Steps 5 and 6: quotient by equality

Consistency equals satisfiability

Compactness and enumerability

Footnotes