Gödel's Incompleteness Theorems

In 1931 a twenty-five-year-old logician proved that mathematics cannot finish itself. The trick he used is one of the most beautiful arguments ever constructed.

For most of human history, mathematics looked like the one place where certainty actually lived. You proved a theorem, and it was true forever, in any galaxy, for any mind. By the late nineteenth century an ambitious project was underway to make this rock-solid foundation explicit: write down a finite list of axioms, fix the rules of inference, and from those starting blocks derive every mathematical truth. Get the foundations right, and the rest is bookkeeping.

In 1931, a quiet Austrian logician named Kurt Gödel — then twenty-five — proved that this is impossible. Not difficult. Impossible. There is no finite axiom system that can capture all the truths of arithmetic. There never will be. And his proof is so clever that even a sketch of it leaves people slightly shaken.

Hilbert's dream

The dream had a name: David Hilbert's program. Hilbert wanted three things from a foundational system for mathematics. It should be consistent — never derive a contradiction. It should be complete — every true statement expressible in the system should be provable inside it. And it should be decidable — there should be a mechanical procedure that takes any statement and tells you whether it is provable.

This wasn't a fringe wish. Russell and Whitehead had spent ten years writing Principia Mathematica, three giant volumes attempting to ground all of mathematics in pure logic. Hilbert's program was the next step: prove, from inside the system, that the system itself was sound. It was a beautiful idea. Gödel showed it was a beautiful, unreachable one.

The trick: a sentence that talks about itself

Here is the move. Consider the liar paradox: this sentence is false. If it's true, it's false. If it's false, it's true. The liar is a paradox in natural language. Gödel's stroke of genius was to build the analogue inside arithmetic itself.

Step one — arithmetisation. Assign every symbol of the formal language a number. Then a string of symbols (a formula, or a proof) becomes a sequence of numbers, which can be folded into a single number using a clever encoding. A formula has a number. A proof has a number. The relation “p is a proof of q” becomes a purely arithmetical relation between two numbers — a relation you can write down inside arithmetic.

Step two — self-reference. Once formulas have numbers, formulas can talk about other formulas. With a careful diagonal construction, Gödel built a sentence — call it G — which, when decoded, says exactly:

“G is not provable in this system.”

That's the whole trick. A sentence inside arithmetic, made of nothing but +, ×, =, ∀, ∃, and so on, that asserts its own unprovability.

The first incompleteness theorem

Now ask: is G true or false?

Suppose G is provable. Then what G says — that G is not provable — must be false. So the system has just proved a false statement. The system is unsound.

Suppose instead G is not provable. Then what G says is exactly the case: G is unprovable. So G is true. But it is, by hypothesis, also not provable inside the system. So the system is incomplete: there is a true statement of arithmetic it cannot prove.

There is no third option. In any consistent formal system rich enough to do basic arithmetic, there exists a statement which is true but unprovable inside the system. This is the first incompleteness theorem. You can patch the hole by adding G as a new axiom, but the same trick generates a new Gödel sentence G′ in the enlarged system. The hole moves. It cannot be closed.

The second theorem — and what it does and doesn't mean

The second theorem is, if anything, more devastating to Hilbert's dream. Gödel showed that “this system is consistent” can itself be encoded as an arithmetical sentence — call it Cons(S). He then proved: if S is consistent, then S cannot prove Cons(S). A system rich enough to do arithmetic cannot prove its own consistency. To establish that arithmetic doesn't contradict itself, you have to step outside arithmetic to a stronger system — whose own consistency you then can't prove without stepping outside that — and so on, forever.

People have made wild claims about the incompleteness theorems for ninety years. Some are reasonable. Most are not. What the theorems do say: there is no single formal system that captures all of mathematical truth. Mathematics is bigger than any of its formalisations. Truth and provability are different things. A finite, mechanical procedure cannot, in general, decide every mathematical question.

What they do not say: that human minds transcend computers, that mathematics is “broken,” that logic is unreliable, that you can't trust calculus or arithmetic in everyday life. The vast majority of working mathematics is provable inside standard systems; Gödel sentences are highly artificial constructions designed to force the issue.

But the philosophical aftermath is still striking. The whole twentieth century thought it knew what a mathematical foundation was supposed to look like — a finished, closed thing, a stone tablet. Gödel demonstrated that any such tablet has a sentence engraved on it that the tablet itself cannot read. It can be read from the next tablet up, but that one has its own unreadable sentence, forever.

Five years later, a young Englishman named Alan Turing translated the same insight into machines. The halting problem — the impossibility of writing a program that decides whether arbitrary programs halt — is a sibling of Gödel's result. Both say the same thing in different dialects: symbols, however carefully arranged, cannot fully grasp themselves.

That is what Gödel handed us in 1931. Not the death of mathematics. Something stranger and more beautiful: the discovery that even mathematics has a horizon, and the horizon recedes as you walk towards it.