Now Obvious
№ 19 · mathematics

Gödel: a true statement that cannot be proved

Take any fixed set of rules for proving facts about whole numbers, as long as the rules are precise enough for a machine to check and never prove a falsehood. There is a true statement about whole numbers that those rules cannot prove. Add it as a new rule, and another appears.

Why it matters

At the start of the twentieth century the hope was to write down one complete rulebook for mathematics: every true statement provable, every proof mechanically checkable. Gödel showed in 1931 that no such rulebook exists. Truth and provability are different things, and the gap is not a failure of cleverness. It is built into any system strong enough to talk about arithmetic.

The mechanism

Three ingredients. First, numbering. Every statement in the rulebook is a finite string of symbols, and any finite string can be encoded as a whole number — the way a text file is a number on a disk. So statements about numbers can, through the code, be statements about statements. A proof is also a finite string, so "p is the code of a proof of statement s" is a checkable fact about two numbers.

Second, self-reference. Because statements have numbers, a statement can contain its own code number. Gödel built a statement G that says, in coded form: no number is the code of a proof of G. In plain words, G says "I am not provable."

Third, the squeeze. Suppose the rules prove G. Then there is a proof, so some number codes it, so G is false — the rules proved a falsehood, which we assumed they never do. So the rules do not prove G. But that is exactly what G asserts. So G is true, and unprovable in the rulebook.

Adding G as a new axiom does not help. The larger rulebook has its own code numbers, and the same construction produces a new G′ for it.

Interactive Press either button to try to prove G from the rules. Whichever you choose, the argument breaks.

code =
② let G = "no number is the code of a proof of the statement whose code is …" — and arrange that number to be G’s own.
③ suppose the rules are consistent (never prove a falsehood). Which is it?
Type any sentence; it becomes one number and decodes back, so statements about numbers can refer to statements. Then walk both branches. The "prove G" branch forces the rules to prove a falsehood, so it is closed. The only open branch is "unprovable" — which is what G says, so G is true.

In one breath

Statements can be numbered, so a statement can talk about its own provability. The statement "I am not provable" cannot be proved without the rules proving something false, so it is unprovable — and therefore true. Every consistent, mechanically checkable rulebook for arithmetic has one.

Where this comes from

  1. Gödel for Goldilocks: A Rigorous, Streamlined Proof of (a variant of) Gödel's First Incompleteness Theorem linked only, not reproduced
    Dan Gusfield · arXiv:1409.5944 · 2014
    arxiv.org/abs/1409.5944
  2. A Simple Character String Proof of the "True but Unprovable" Version of Gödel's First Incompleteness Theorem linked only, not reproduced
    Antti Valmari (Tampere University of Technology) · arXiv:1402.7253 · 2014
    arxiv.org/abs/1402.7253