The Sentence That Talks About Itself

By 1920 David Hilbert had a programme. Take all of mathematics, set it on a finite list of axioms, and then prove two things about that system using only its own safe, finite methods: that it is consistent, so no contradiction can be derived, and that it is complete, so every true statement of arithmetic can be proved within it.

It was not an unreasonable hope. It was the natural next step after a century of putting analysis and geometry on rigorous foundations. In 1931 a twenty-five-year-old named Kurt Gödel showed it could not be done.

The construction is ingenious and the idea behind it is simple enough to state. Gödel assigned a number to every symbol, then to every formula, then to every sequence of formulas, which is to say to every proof. Once that is done, a statement about proofs becomes a statement about numbers. 'There exists a proof of X' turns into an arithmetical claim about whether some number stands in a certain computable relation to another. And a system that can do arithmetic can make arithmetical claims.

So a formal system can talk about its own proofs. No new machinery is required, and building the coding carefully is most of the paper.

Then the sentence. Gödel constructs a formula G which, decoded, says: G has no proof in this system.

Suppose the system proves G. Then G is provable, and G says it is not, so the system has proved something false and is unsound. Suppose instead the system proves the negation of G. Then it proves that G has a proof, while G in fact has none, and again something has gone wrong.

If the system is consistent, it proves neither. And G, read at face value, is true; it asserts its own unprovability, and it is unprovable. So there is a true statement of arithmetic that the system cannot reach.

The obvious repair does not work. Add G as a new axiom and you have a new system, still consistent, still capable of arithmetic, still with a checkable list of axioms, so the construction runs again and hands you a new unprovable sentence. Incompleteness is not a hole to be patched. It is a property of the entire method.

The second theorem is the one that killed the programme. Among the things the system cannot prove is its own consistency. The guarantee Hilbert wanted was, specifically, the guarantee that could not be had. Gentzen proved arithmetic consistent in 1936 using transfinite induction, from a stronger system, which is a real result and moves the question along rather than settling it, since the stronger system's consistency is now open.

Now the misreadings, because there are more of them attached to this theorem than to almost anything else in mathematics.

It does not show that nothing can be known for certain. It is itself a proved certainty, established by exactly the sort of reasoning the sceptical reading claims is unavailable, and its subject is formal systems of a particular strength rather than knowledge in general.

It does not show that mathematics is unreliable. The sentences Gödel builds are self-referential contrivances, and nothing in ordinary mathematical practice looks like them. Statements genuinely independent of the standard axioms do turn up (the continuum hypothesis is the famous one, shown independent by Gödel and Cohen between them) and the response is to note the independence and study both branches. That is ordinary work, not crisis.

It does not apply to every formal system. The conditions are precise: consistent, capable of expressing arithmetic, with a mechanically checkable list of axioms. Drop any one and the theorem does not bite. Presburger arithmetic, which has addition but no multiplication, is complete and decidable. Euclidean geometry, as Tarski axiomatised it, is complete.

What the theorem does show is that there is no single formal system in which all mathematical truth lives, and that the reliability of arithmetic is not something arithmetic can certify from inside. Those are substantial limits, they are precisely stated, and their precision is exactly what the popular versions throw away.