Where proof and truth coincide
The corpus now stands on two pillars. The diagonal, in seven volumes, traced the syntactic limit — a system reasoning about itself, forcing a fixed point it cannot prove. The multitude traced the semantic limit — a theory reasoning about its models, unable to single one out. And the claim was made, but not yet earned, that these are one gap seen from two sides: that incompleteness is the splitting of the multitude, that the unprovable is the unsatisfied. That claim rests entirely on a theorem the corpus has leaned on at every turn and never once proved — Gödel's completeness theorem, which says that for first‑order logic, what can be proved and what is true in every model are exactly the same. It is the keystone of the arch: the stone that locks the two faces into one structure. This volume proves it, by the astonishing device of building a model out of pure syntax; shows that it is what makes both limits precise; and finds, at its edge, that strengthening the logic to escape the limit does not destroy the limit but only moves it — from the theory into the logic itself.
the hinge of the corpus · the completeness theorem as the bridge between proof and truth — soundness, the trustworthy half; Henkin's construction of a model from a maximal consistent theory; the truth lemma and the identity ⊢ = ⊨; the reframing of incompleteness as the theory's failure, not the logic's; the duality of Henkin and the ultraproduct, two roads to one model; and the failure of completeness for second‑order logic, where the diagonal's limit migrates into the logic and the conservation law returns
Two faces of the limit have been drawn, and a bridge between them assumed. It is time to lay the bridge — and the first step is to see precisely what it must connect.
two relations, one identity A formal system carries two notions of "follows," and the whole of logic lives in the space between them. There is provability, T ⊢ φ — a finite derivation of φ from T by fixed rules, a syntactic, mechanical, checkable thing. And there is logical consequence, T ⊨ φ — that φ holds in every model of T, a semantic claim ranging over all the worlds the theory permits. The diagonal corpus was the study of ⊢; the multitude was the study of ⊨. Nothing guarantees, in advance, that these two should agree. A logic could prove too little — leaving consequences underivable — or, were its rules unsound, prove too much. The completeness theorem is the discovery that for first‑order logic they agree exactly: T ⊢ φ if and only if T ⊨ φ. The mechanical and the meaningful are one relation wearing two names.
why this is the keystone The identity ⊢ = ⊨ is what makes the corpus's central claim true rather than merely poetic. The multitude said a sentence is independent of a theory exactly when the theory's models disagree about it — and that "exactly when" is the completeness theorem, for it is completeness that turns "no model decides it uniformly" into "no proof decides it." Incompleteness, the diagonal's signature, becomes a fact about models only because the bridge is in place: G is unprovable from PA precisely because G fails in some model of PA, and we know this because provability and consequence coincide. Remove the keystone and the two faces fall apart into unrelated stories; set it, and they lock into a single arch. This volume lays the stone in three movements: the easy direction, soundness, that proof never outruns truth; the deep direction, completeness, that truth never outruns proof — proved by conjuring a model from syntax alone; and the consequences, which reframe everything the corpus has said and, at the last, reveal that the limit cannot be escaped, only relocated.
It is worth naming the strangeness of the deep direction in advance, because it is one of the most beautiful arguments in logic. To prove that every logical consequence is provable, one proves the contrapositive: that anything unprovable can be made false — that if T ⊬ φ, there is a genuine model of T in which φ fails. This requires building a world to order, a structure satisfying T and refuting φ, and the device — Henkin's — is to build that world out of the words of the language itself: to take the very symbols and let them be the elements of the model. Syntax, asked whether it captures semantics, answers by becoming a semantics. The multitude built models by blending other models under an ultrafilter; the keystone builds a model from a consistent theory, with nothing but its own terms for bricks. Two constructions, two directions, and between them the bridge on which the whole corpus stands.
The easy half of the bridge, and the half that makes proof worth trusting. Its statement is modest, its proof a routine induction — and it converts the hard half into a single, sharper question.
the question that remains Soundness is why a proof is a guarantee: a derivation cannot lead from true premises to a false conclusion, because each step is truth‑preserving. Proof never outruns truth. The whole difficulty of the completeness theorem is the converse — that truth never outruns proof, that every consequence is reachable by some finite derivation — and soundness lets us sharpen exactly what that requires. For completeness says T ⊨ φ ⟹ T ⊢ φ; contrapose it, and it says: if T ⊬ φ, then T ⊭ φ — there is a model of T where φ fails. Now T ⊬ φ means, by soundness's contrapositive, that T ∪ {¬φ} is consistent — no contradiction is derivable from it. So the entire completeness theorem reduces to a single existence claim, the model existence theorem:
If that holds, completeness follows: an unprovable φ leaves T ∪ {¬φ} consistent, hence satisfiable, hence φ fails somewhere, hence φ is not a consequence. The bridge is built the moment we can turn consistency — a syntactic property, the mere absence of a derivable contradiction — into an actual world. That is what the next section does, and it does it with breathtaking economy: it makes the world out of the syntax itself.
The centerpiece. To prove every consistent theory has a model, Henkin builds one — and the bricks are the terms of the language. The structure that satisfies the theory is assembled from the theory's own symbols.
three moves Begin with a consistent theory T. First, extend it to a maximal consistent theory T* — go through the sentences one by one, adding each, or its negation, whichever keeps consistency; by Lindenbaum's lemma a maximal consistent extension always exists. T* now decides every sentence: for each φ, exactly one of φ, ¬φ belongs to it. Second, ensure witnesses: whenever T* asserts ∃x φ(x), it should contain an actual term naming the witness. Expand the language with new constants and add the Henkin axioms (∃x φ(x)) → φ(cφ), then re‑maximise; the result still decides everything, and now every existential it proves has a constant to witness it. Third, build the term model: let the elements be the closed terms of the language — quotient by t ~ s when t = s ∈ T* — and read every function and relation straight off T*. The domain of the model is the syntax, lightly folded.
the truth lemma, in miniature The heart of the construction is the truth lemma's claim that membership in the maximal consistent theory and truth in the built model are the same. Its essence is already visible at the propositional level, where a maximal consistent set is nothing but a complete, coherent verdict on the atoms — a valuation — and the model it defines makes a formula true exactly when the set contains it. Set the verdict on the atoms below and watch the lemma hold: every compound formula's membership is forced by the atoms, and forced to agree, line for line, with its truth in the model. The first‑order construction adds the machinery of terms and witnesses, but this is the engine inside it — consistency, completed, is a world.
the truth lemma — a maximal consistent set is a model
Soundness and model existence, set end to end, are the completeness theorem. The two notions of consequence collapse into one — and a mechanical proof system is shown to reach, in principle, every truth it ought to.
closing the loop The pieces assemble in a line. Suppose T ⊨ φ but T ⊬ φ. Then T ∪ {¬φ} is consistent, so by the model existence theorem it has a model M. But M ⊨ T and M ⊨ ¬φ contradict T ⊨ φ. So T ⊨ φ forces T ⊢ φ — completeness. Joined to soundness, which gives the reverse, the two relations are identical.
first‑order logic is complete The phrase deserves care, because it is the exact word that "incompleteness" will seem to contradict. To say first‑order logic is complete is to say its proof system is adequate to its semantics: every logically valid sentence — every sentence true in all structures whatsoever — has a proof, and every consequence of a theory is derivable from it. The logic leaves no semantic truth unreachable. This is a property of the logic, of the apparatus of quantifiers and connectives and rules. It says nothing yet about any particular theory's power to describe its intended subject, and the next section turns on keeping those two things — the completeness of the logic and the incompleteness of a theory — rigorously apart. They are not in tension. They are about different things, and the keystone is what lets us see that.
With the bridge in place, the corpus's two great limits change character. Incompleteness becomes a fact about a theory, not a flaw in the logic; the multitude becomes the bridge's own construction; and the gap between them is, at last, exactly stated.
incompleteness belongs to the theory Here is the reframing the keystone forces, and it dissolves a confusion as old as the theorems themselves. Gödel's incompleteness theorem and Gödel's completeness theorem are felt to be in tension only by those who have not separated the logic from the theory. The logic is complete: every logical consequence of PA is provable from PA. The Gödel sentence G is unprovable from PA not because some consequence escaped the proof system — none can — but because G is not a consequence of PA at all: by completeness, its unprovability means it fails in some model of PA. G is true in the standard model ℕ and false in some nonstandard one, and so it is true‑in‑the‑intended‑model without being true‑in‑all‑models. Incompleteness is not the logic falling short of its semantics; it is a theory falling short of pinning down its intended structure among the many that satisfy it. The diagonal's limit, read through the keystone, is a limit on theories, not on proof.
the multitude is the keystone's own work And the other face is reframed just as sharply. The model existence theorem — every consistent theory has a model — is not a remote cousin of the multitude; it is its source. Henkin's construction is a model‑building machine: feed it any consistent theory and it returns a world. Feed it PA together with "there is a number larger than every numeral," consistent because every finite part is, and it returns a nonstandard model. The completeness theorem, in the form of model existence, is precisely the engine that manufactures the multitude — the same engine the ultraproduct provided from the other direction. So the two faces are not merely connected; each is the other's mechanism. Incompleteness produces the multitude (independent sentences split the models), and the multitude's existence theorem produces incompleteness (a model where G fails is a witness to its unprovability). They generate each other through the bridge.
Now the corpus's central claim can be made with full precision, no longer a metaphor but an equation. By the completeness theorem, "provable from T" and "true in every model of T" are the same. The limits of the foundations are therefore not in the gap between proof and consequence — there is no such gap; the keystone closed it. The limits live one level out, in the gap between true in every model and true in the intended model. The diagonal measures this gap from the syntactic side: a sentence true in the intended model but not in all of them is true‑but‑unprovable. The multitude measures it from the semantic side: the models that disagree with the intended one are the nonstandard shadows. And the keystone is what identifies the two measurements, because it is what makes "provable" and "true in all models" interchangeable. The single gap of the whole corpus — between what a formal system can establish and what is so of the thing it means — is the gap between all models and the model; the diagonal and the multitude are its two profiles; and the completeness theorem is the plane in which they are seen to be one. Strengthen the logic to close even this gap — to force the intended model to be the only model — and the limit does not vanish. It moves. That is the last section.
The keystone and the multitude each manufacture models, and the corpus now holds both machines. They take opposite inputs and meet at the same theorem — and seeing them side by side is seeing the bridge built from both banks.
one bridge, two derivations The completeness theorem and the compactness theorem are, it turns out, equivalent — each follows from the other. Compactness from completeness is immediate: if every finite part of T is satisfiable then, by soundness and completeness, every finite part is consistent; and since any derivation of contradiction would use only finitely many sentences, T itself is consistent, hence has a model. The converse holds too, model existence flowing from compactness applied to a maximal witnessed theory. So the two great theorems are one fact approached from two sides — and they are proved from two sides, by two model‑building machines that take exactly opposite raw materials.
two constructions of a model
The completeness theorem is a property of first‑order logic, and a fragile one. Strengthen the logic to control its models — to kill the multitude outright — and the bridge collapses, the diagonal's limit reappearing in a new and deeper place.
second‑order logic kills the multitude First‑order logic could not pin down ℕ; its induction was a schema, one instance per definable property, and the nonstandard models slipped through the gaps between instances. Second‑order logic closes those gaps by brute force: its induction axiom quantifies over all subsets at once — ∀P [ (P(0) ∧ ∀n(P(n) → P(n+1))) → ∀n P(n) ] — and that single axiom is categorical. The set of standard numbers is itself a subset P containing zero and closed under successor; second‑order induction then forces it to be everything, so no nonstandard element can survive. Second‑order Peano arithmetic has, up to isomorphism, exactly one model: ℕ. The multitude is annihilated; the intended structure is captured uniquely; the gap between "all models" and "the model" is closed. It looks like total victory.
second-order induction annihilates the nonstandard model
The victory is an illusion, and the way it fails is the conservation law of The Law, now operating across logics themselves. Buy categoricity, and you forfeit the keystone: second‑order logic, under its full semantics, has no completeness theorem. Its consequence relation ⊨₂ is not recursively axiomatizable — there is no sound, effective proof system deriving all second‑order validities. The reason is the diagonal, returning. Because PA₂ is categorical, "⊨₂ φ" for an arithmetical φ means simply "ℕ ⊨ φ" — second‑order validity encodes truth in the standard model, and truth in the standard model is not even arithmetically definable, let alone effectively provable, by Tarski's theorem from the diagonal corpus. So the incompleteness does not disappear when the multitude is killed. In first‑order logic the limit lived in the theory: PA was incomplete, but the logic was complete and the proof system reached all consequences. In second‑order logic the limit lives in the logic: the intended model is captured, but no proof system reaches the logic's own truths. The gap was moved from theory to logic; it was not closed. This is the conservation law in its widest form — the forced fixed point of the whole enterprise, relocating from sentence to model to logic, surrendering one stronghold only to occupy the next. A formal system may grasp itself, or grasp its models, or prove its consequences — but never all three, and the price of taking one is always the loss of another. The diagonal forced a fixed point; the multitude forced a plurality of worlds; the keystone bridged them; and here, at the edge of the bridge, the two faces and their conservation are revealed as a single law, governing not just theories and models but the logics that frame them. The corpus is complete, and its subject was always one thing: the unbridgeable gap between a formal system and the reality it reaches for, conserved under every attempt to close it.
The corpus stood on two pillars — the diagonal's syntactic limit, the multitude's semantic one — and claimed they were one gap. The keystone is the theorem that makes the claim true: Gödel's completeness theorem, that for first‑order logic, provable and true‑in‑all‑models coincide. It is proved by the most elegant of devices, building a world out of the words of the language — a consistent theory, maximised and witnessed, is a model, its terms read as things. Soundness gives the easy direction; Henkin's construction gives the deep one; together they identify ⊢ with ⊨ and lock the two faces into one arch. The reframing is total: incompleteness belongs to the theory, not the logic; the multitude is the model‑existence theorem's own offspring; and the real gap of the foundations is between all models and the intended model, measured by the diagonal from one side and the multitude from the other. And at the bridge's edge, the deepest fact of all: strengthen the logic to close even that gap — second‑order logic, categorical, the multitude annihilated — and completeness collapses, the diagonal's limit migrating from theory into logic, conserved exactly as The Law foretold. ⊢ φ ⟺ ⊨ φ — the mechanical and the meaningful, one relation, for just so long as the logic is weak enough to let them be.