Incompleteness
A Socratic walk-through of incompleteness — reasoned out one step at a time, not lectured.
The question we started with
THE QUESTION #Can a system of arithmetic prove every true statement about numbers?
Here is a hope that seemed reasonable for a long time: write down the right axioms for arithmetic, fix the rules of inference, and every true statement about the whole numbers turns up at the end of some proof. Not quickly, perhaps, but in principle reachable. The hope is not naive — it is exactly what had been achieved for smaller systems. So what would have to be true of a system for it to fail?
Reasoning it through
REASONING #Start with the demands we would place on such a system. We want it consistent — never proving both a statement and its negation, since a system that does proves everything and is worthless. We want its axioms effectively given: a machine should be able to check whether a line is a legitimate axiom, or "proof" means nothing checkable. And we want it strong enough to actually be arithmetic — addition and multiplication of the naturals.
Notice what that third demand quietly buys. A system that can talk about numbers can, once you assign a number to every symbol, formula and proof, talk about its own sentences. Gödel numbering is a bookkeeping device, not a philosophical claim: statements about proofs become statements about arithmetic, a subject the system already discusses.
What can we build with that? Gödel constructed a sentence G that the system itself proves equivalent to "G is not provable in this system." Suppose the system proves G. Then G is provable — but G asserts it is not, so the system proves a falsehood about its own proofs and, followed through, contradicts itself. Consistency forbids it. And if the system proves not-G? Gödel originally needed a slightly stronger hypothesis than bare consistency to close that half; Rosser later modified the sentence so plain consistency suffices.
So G is neither provable nor refutable. Is G true? Yes — true of the natural numbers, in the ordinary sense, because it says it has no proof and demonstrably has none. That is the first theorem: any consistent, effectively axiomatised system capable of a modest amount of arithmetic leaves some arithmetical truth undecided.
Could we add G as a new axiom? We could — and the new system, still consistent, still effectively axiomatised, still arithmetical, satisfies the hypotheses again, so it has a fresh unprovable sentence of its own. The gap is not a hole to be patched; it reappears wherever you stand.
The second theorem twists the knife. Formalise "this system is consistent" inside the system, and it cannot prove it. Its own consistency is exactly what it cannot vouch for — which is why Gentzen's later proof that Peano arithmetic is consistent had to reach for a principle Peano arithmetic does not contain.
The analogy
THE ANALOGY #Imagine a rulebook thick enough to describe its own procedures — so that "produce page 40 by the rules" is itself a thing the book can express. In such a book you can write the line: no procedure in this book produces this line. If the book produces it, the book has produced a falsehood. If the book is honest, it never produces it — and the line stands there, correct and unreachable.
This is not the liar paradox. "This sentence is false" is contradictory and yields nothing; Gödel's sentence says only "I am unprovable", which resolves cleanly — it is simply true, and unproved — so the result is a limitation, not a contradiction.
Clarifying the model
THE MODEL #The theorems are narrower than their reputation, and the narrowness is the interesting part.
Every hypothesis is load-bearing. Drop the arithmetic and the conclusion evaporates: Presburger arithmetic, which has addition but no multiplication, is complete and decidable, as is the first-order theory of real closed fields that Tarski settled — and with it, remarkably, elementary Euclidean geometry. Drop effectiveness and it also fails: the set of all true arithmetic sentences is a complete axiom system, but no machine can recognise its members, which is precisely why it is useless. And first-order logic itself is complete — Gödel proved that too, four years earlier, and the collision of names causes endless confusion.
So the theorems say nothing about "systems" in the loose sense — not physics, law, ethics or organisations, none of which are consistent effectively axiomatised theories of arithmetic. They do not say truth is relative, that nothing can be known, or that mathematics is unreliable. Nor do they establish that human minds exceed machines: that argument needs us to know our own axioms and be certain of our own consistency, which assumes precisely what the theorem denies any formal system.
What they do establish is sharp. No fixed, checkable axiom set captures all arithmetical truth; provability and truth are different properties, and the difference is not a matter of effort; consistency proofs must come from outside. Nor is this confined to artificial sentences — Goodstein's theorem and the Paris-Harrington principle are ordinary combinatorial statements, true of the naturals and unprovable in Peano arithmetic.
A picture of it
THE PICTURE #How to readH1, H2 and H3 are the theorem's hypotheses, and the arrows out of G1 point back at them — read "derives" as derived from, so G1 holds only where all three do. G2 refines G1 as its second, sharper half. The two elements below are candidate systems: Peano arithmetic satisfies all three hypotheses, so both theorems bite. Presburger arithmetic satisfies only two, and the arrow that is missing, to H3, is the whole point — without multiplication it is complete and decidable, and Gödel's result does not reach it.
What became clearer
WHAT CLEARED #Incompleteness is a precise statement with three conditions attached, not a slogan about the limits of knowledge. Any consistent, mechanically checkable system that can do ordinary arithmetic can be turned to describe its own proofs — and once it can, it can be handed a true sentence it cannot reach, and cannot even certify its own consistency. Weaken any one condition and the limitation lifts.
Where to go next
ONWARD #- How Turing recast the same limit as the undecidability of the halting problem.
- Why proving Peano arithmetic consistent requires transfinite induction, and what that buys.
Key terms
TERMS #| Term | What it means |
|---|---|
| Effectively axiomatised | having an axiom set a machine can recognise, so proofs are mechanically checkable. |
| Gödel numbering | an encoding of symbols, formulas and proofs as numbers, letting arithmetic describe its own syntax. |
| Complete (of a theory) | proving or refuting every sentence in its language; distinct from Gödel's completeness theorem about first-order logic. |
| Independent statement | one neither provable nor refutable from a given set of axioms. |
Every term the collection defines is gathered in the glossary.