The canonical model (how completeness is actually proved)

Parent: soundness-and-completeness

Completeness (⊨ φ ⟹ ⊢ φ) hinges on one lemma: every consistent theory has a model. The beautiful trick is that you don't go searching for a model — you build the canonical one straight out of the syntax: the theory's own sentences become a structure. That structure is the canonical model (a.k.a. the term model / Henkin model).

What has to be shown

Prove the contrapositive of completeness: Γ ⊬ φ ⟹ Γ ⊭ φ. Since Γ ⊬ φ, the set Γ ∪ {¬φ} is consistent (no proof of a contradiction). So it's enough to show:

consistent ⟹ satisfiable — any consistent set of sentences has a model.

Then that model satisfies Γ and ¬φ, witnessing Γ ⊭ φ.

Build the model from the words

Start with a consistent set Δ (here Γ ∪ {¬φ}) and turn it into a structure in three moves:

1. Complete it (Lindenbaum). Extend Δ to a maximal consistent set Δ*: run through every sentence ψ and toss in ψ or ¬ψ — whichever keeps consistency. Now Δ* decides every sentence (for each ψ, exactly one of ψ, ¬ψ is in).
2. Add witnesses (Henkin). For every ∃x. ψ in Δ*, make sure some constant c has ψ[c/x] in Δ* too (introduce fresh witnessing constants). Every "there exists" now has a named example.
3. Read off the structure M. Take the domain to be the terms themselves (closed terms, with t ~ s whenever t = s ∈ Δ*); interpret each function and relation symbol by whatever Δ* asserts. The elements of the model literally are the syntax.

The truth lemma — syntax turns into truth

Truth lemma

In this M, for every sentence: M ⊨ ψ ⟺ ψ ∈ Δ*. (By induction on ψ: the connectives work because Δ* is maximal-consistent, the quantifiers because of the Henkin witnesses.)

So M makes true exactly the sentences of Δ* ⊇ Γ ∪ {¬φ}. That's a model of Γ in which φ fails → Γ ⊭ φ. ∎

See it work — the syllogism

We prove the hypothetical syllogism — from P→Q and Q→R, conclude P→R:

    P → Q        (premise)
    Q → R        (premise)
  ───────────
  ∴ P → R        (conclusion)

That's the transitivity of implication (chaining P⇒Q⇒R, so P⇒R) — the backbone of every multi-step argument. It's an ideal demo precisely because you already know it's true: watch the construction reproduce it, and you learn to trust the method (which you can then aim at claims whose answer you don't know).

Now the semantic way. By completeness it's enough to show Γ ⊨ P→R, and the canonical-model theorem hands us that: Γ ⊢ P→R fails only if Γ ∪ {¬(P→R)} is consistent (then it would have a canonical model — a countermodel). So try to build that model and watch it collapse.

The set is (using ¬(P→R) ≡ P ∧ ¬R):

   P → Q ,   Q → R ,   P ,   ¬R

Complete it (Lindenbaum) — throw in what's forced:

• P is in, and P→Q is in ⟹ Q must go in (adding ¬Q is inconsistent);
• Q is in, and Q→R is in ⟹ R must go in;
• but ¬R is already in — contradiction.

So there is no maximal consistent extension → no canonical model → the set is unsatisfiable → Γ ⊨ P→R, hence (completeness) Γ ⊢ P→R. ∎

Read what happened: the construction tried to build a world where the premises hold but the conclusion fails, and couldn't — the syntax forced R both true and false. (Had the set been consistent, the completion would instead have succeeded and handed you a genuine model, exactly as in the general construction above. In full first-order logic that success also uses Henkin witnesses — a constant c with ψ[c/x] for each ∃x.ψ — and takes the terms as the domain.)

Why it's called canonical

You didn't discover a model out in the mathematical wild — you manufactured the one canonical model the theory describes about itself: its objects are the terms, its truths are "whatever the maximal consistent theory says." The syntax is the semantics. That's the real content of completeness: a merely consistent pile of symbols is already forced to describe a world — which is why provability and truth end up coinciding.

(Different sense of "canonical" from a normal form like CNF/DNF: here the canonical object is a model, not a formula. The construction also gives compactness for free — if every finite part of Γ is satisfiable, Γ is consistent, so it has a canonical model.)