Cobra Effect · Maths and proof
The limits of proof
How Kurt Godel found limits that no system of proof can escape.
7 cards, read aloud in 2:45, with a test and sources.
Early in the twentieth century, David Hilbert hoped to make mathematics completely secure.
He hoped for a system of rules strong enough to settle every mathematical statement. And he wanted a proof, using simple and safe methods, that the system could never contradict itself. In 1930 he declared, we must know, and we will know.
At a meeting in Konigsberg in 1930, a young mathematician quietly raised a problem.
Kurt Godel, from Vienna, was twenty four. He mentioned, almost in passing, that he had found a limit to what such systems can prove. John von Neumann was one of the few who immediately saw its importance.
His first theorem showed that such systems must always be incomplete.
Take any consistent system whose rules can be checked mechanically, and which is strong enough for basic arithmetic. There will always be statements in the system’s own language that it can neither prove nor disprove. Godel built such a statement, one that in effect says that it cannot be proved within the system. If the system could prove it, the system would be proving something false.
His second theorem went further.
A consistent system of that kind cannot prove its own consistency. Von Neumann worked this out independently, but Godel’s paper, already submitted, contained it. The paper was published in 1931.
Hilbert’s hope, in its original form, could not be achieved.
Many, including von Neumann, concluded that Hilbert’s programme, as first planned, could not be carried out. Mathematicians went on working toward modified versions of the goal. Mathematics itself did not collapse. Proofs remained proofs.
The theorems are often stretched far beyond what they say.
They do not show that some truths can never be proved at all, only that each such system has limits. A statement unprovable in one system may be provable in a stronger one, which then has limits of its own. Claims that Godel proved something about minds, gods or laws go far beyond his mathematics.
So when a system claims to capture everything, ask what it cannot say about itself.
Godel turned mathematics back on itself, and found a boundary. The boundary did not make mathematics weaker. Knowing the limits of a method is part of using it well.
Sources
- Godel’s Incompleteness Theorems, Stanford Encyclopedia of Philosophy. What the theorems say, and the common ways they are misread.
- Hilbert’s Program, Stanford Encyclopedia of Philosophy. Hilbert’s goal, and what incompleteness did to it.
- Kurt Godel, MacTutor History of Mathematics. A biography of Godel.
Nearby ideas
- The question no machine can answer. How Alan Turing imagined the computer, and proved some questions have no answer.
- Some infinities are bigger than others. How Georg Cantor showed that some infinities are larger than others.
- The margin that was too small. How Andrew Wiles proved Fermat's three hundred year old claim.
- The primes never run out. How a proof over two thousand years old shows the primes never run out.
- The long journey of zero. How zero grew from a gap in a number into a number in its own right.
- Seven bridges and a walk that could not be done. How Euler proved a walk impossible without trying a single route.