The Compactness Theorem is one of the most powerful results in mathematical logic, and I want to prove it for you. Fair warning, the proof is not a walk in the park, and you probably won’t comprehend it if you speed through. Take your time! This is the easiest proof of Compactness that I know of which doesn’t rely on the Completeness Theorem, which is itself not easy to prove.

First, some background concepts:

Interpretation An interpretation of a set of sentences Σ is a consistent assignment of truth values to all well-formed-formulas such that every sentence in Σ is assigned true.

Logical Entailment Σ logically entails α (Σ ⊧ α) iff in every interpretation v of Σ, v(α) = True.

Completeness A set of sentences Σ is complete iff for every well-formed-formula α, Σ ⊧ α or Σ ⊧ ¬α.

Satisfiability A set of sentences Σ is satisfiable iff there is at least one interpretation under which all sentences in Σ are true.

Finite Satisfiability A set of sentences Σ is finitely satisfiable iff every finite subset of Σ is satisfiable.

Compactness Theorem Σ is satisfiable iff every finite subset of Σ is satisfiable.

With that aside, here’s an outline of the proof. I’ve adapted the outline from this lecture series, and added in some minor improvements.

There are five steps, and most of the work is in the middle three.

1. Establish that there is an ordering on the set of well-formed-formulas.
2. Prove that if Σ is finitely satisfiable, then so is either Σ ∪ {α} or Σ ∪ {¬α}.
3. Construct Δ, an extension of Σ, which is complete and finitely satisfiable.
4. Prove that Δ is satisfiable.
5. Prove that Σ is satisfiable.

This will prove that Σ is satisfiable if it’s finitely satisfiable. The other direction (if it’s satisfiable then it’s finitely satisfiable) is trivial, as any subset of a satisfiable set is also satisfiable.

So let’s dive in!

1. There is an ordering on the set of well-formed-formulas.

This is a fun fact that is basically established by Gödel numbering. Assign numbers to all the symbols of your language. An example assignment for propositional logic:

“(” assigned 0
“)” assigned 1
“¬” assigned 2
“∧” assigned 3
“∨” assigned 4
“→” assigned 5
“P₀” assigned 6
“P₁” assigned 7
“P₂” assigned 8
And so on…

Now we translate a string by going through symbol by symbol and making the number assigned to the nth symbol in the string the exponent of the nth prime. Here are a few translations to illustrate:

Initial string: “(¬P₀)”
Codes for each character: [0, 2, 6, 1]
Gödel number: 2⁰ 3² 5⁶ 7¹ = 984,375

Initial string: “(P₀ → P₂)”
Codes for each character: [0, 6, 5, 8, 1]
Gödel number: 2⁰ 3⁶ 5⁵ 7⁸ 11¹ = 144,462,310,059,375

Initial string: “((P₀ ∨ P₂) → (¬P₁))”
Codes for each character: [0, 0, 6, 4, 8, 1, 5, 0, 2, 7, 1]
Gödel number: 2⁰ 3⁰ 5⁶ 7⁴ 11⁸ 13¹ 17⁵ 19⁰ 23² 29⁷ 31¹ ≈ 4.2 × 10³⁷

Since the prime factorization of a number is unique, we have a unique number for every possible string, which means we can go backwards from any number to its corresponding string. Now to construct our order, we just start from 2 and work our way up, discarding any sentences we get that are not well-formed-formulas. This will give us an ordered list of all well-formed formulas!

2. If Σ is finitely satisfiable, then so is either Σ ∪ {α} or Σ ∪ {¬α}.

Suppose not. Then neither Σ ∪ {α} nor Σ ∪ {¬α} are finitely satisfiable. So there must exist some finite sets Σ₀ and Σ₁ such that Σ₀ ⊆ Σ ∪ {α} and Σ₁ ⊆ Σ ∪ {¬α}, where neither Σ₀ and Σ₁ are satisfiable.

But now consider Σ’ = (Σ₀ ∪ Σ₁) \ {α, ¬α}. Σ’ is a finite subset of Σ, so it must be satisfiable (remember, Σ is finitely satisfiable by assumption). This means that there is some interpretation which satisfies Σ’. But this interpretation must assign to α either T or F.

If it assigns T to α, then Σ’ ∪ {α} is satisfiable. But Σ’ ∪ {α} is a superset of Σ₀! So Σ₀ must also be satisfiable. But this contradicts our assumption!

But if it assigns F to α, then Σ’ ∪ {¬α} is satisfiable. And Σ’ ∪ {¬α} is a superset of Σ₁! So Σ₁ must also be satisfiable. Contradiction!

Either way we get a contradiction, so this proves our theorem.

3. Extend Σ to Δ, which is complete and finitely satisfiable.

We inductively define Δ as follows:

Δ₀ = Σ
Δ_n+1 = Δ_n ∪ {α_n} if Δ_n ∪ {α_n} is finitely satisfiable, otherwise Δ_n ∪ {¬α_n}
Δ = ∪ Δ_n

Here we’re using our ordering that we constructed in Step 1 to go through every well-formed-formula in order. This establishes that Δ is complete, as we construct it by appending to Σ either α or ¬α for every well-formed-formula. I.e. we construct it by taking Σ and adding to it an explicit “opinion” on every possible sentence, ensuring at each stage that we remain finitely satisfiable.

How do we know that the final result Δ is also finitely satisfiable? This is due to our proof in Step 2, which allows us to say that Δ_n is always finitely satisfiable for any n. But any finite subset of Δ is also a subset of Δ_n for some n! So any finite subset of Δ is satisfiable. Thus Δ is finitely satisfiable.

4. Δ is satisfiable.

To prove this, we’ll hand-make a truth assignment for our purposes. First we define a truth assignment v over atomic propositions as follows:

v(p) = T if p ∈ Δ, otherwise F

Now we extend v to the rest of the set of well-formed-formulas in the usual way, ensuring consistency of the truth-assignment.

We’ll prove now that under this extension, v(α) = T if and only if α ∈ Δ. The proof is by structural induction.

Base case

• α is an atomic proposition. Then v(α) = T iff α ∈ Δ, by definition of v.

Inductive step(s)

• If α = ¬β, then v(α) = v(¬β) = T iff ¬β ∈ Δ iff α ∈ Δ.
• If α = (β ∧ γ), then v(α) = v(β ∧ γ) = T iff (v(β) = T and v(γ) = T) iff (β ∈ Δ and γ ∈ Δ) iff (β ∧ γ) ∈ Δ iff α ∈ Δ
  • If β ∈ Δ and γ ∈ Δ, then (β ∧ γ) ∈ Δ, since Δ is complete and finitely satisfiable.
    • If (β ∧ γ) ∉ Δ, then ¬(β ∧ γ) ∈ Δ by completeness. But then {β, γ, ¬(β ∧ γ)} is a finite subset of Δ that’s not satisfiable, so Δ isn’t finitely satisfiable. Proof by contradiction.
  • If β ∉ Δ or γ ∉ Δ, then (β ∧ γ) ∉ Δ, since Δ is complete and finitely satisfiable.
    • Suppose (β ∧ γ) ∈ Δ. Since β ∉ Δ or γ ∉ Δ, at least one of ¬β and ¬γ must be in Δ. Without loss of generality, assume ¬β ∈ Δ. Then {¬β, (β ∧ γ)} is a finite subset of Δ that’s not satisfiable, so Δ isn’t finitely satisfiable. Proof by contradiction.

Since ¬ and ∧ are a complete set of truth functions (all other well-formed formulas can be converted into a form that uses only ¬ and ∧), this proves the proposition for all well-formed formulas.

We’ve shown that v(α) = T if and only if α ∈ Δ. This proves that v satisfies Δ!

5. Σ is satisfiable.

The final step is the easiest one. Δ is satisfied by v, and Δ is a superset of Σ, so Σ must also be satisfied by v. So we’re done!