15 highlights
-
Mathematicians of the era sought a solid foundation for mathematics: a set of basic mathematical facts, or axioms, that was both consistent — never leading to contradictions — and complete, serving as the building blocks of all mathematical truths.
-
But Gödel’s shocking incompleteness theorems, published when he was just 25, crushed that dream.
-
He also showed that no candidate set of axioms can ever prove its own consistency.
-
His incompleteness theorems meant there can be no mathematical theory of everything, no unification of what’s provable and what’s true.
-
Undecidable questions have even arisen in physics, suggesting that Gödelian incompleteness afflicts not just math, but — in some ill-understood way — reality.
-
He proved that any set of axioms you could posit as a possible foundation for math will inevitably be incomplete; there will always be true facts about numbers that cannot be proved by those axioms.
-
Gödel’s main maneuver was to map statements about a system of axioms onto statements within the system — that is, onto statements about numbers.
-
The first step in this process is to map any possible mathematical statement, or series of statements, to a unique number called a Gödel number.
-
For example, consider 0 = 0. The formula’s three symbols correspond to Gödel numbers 6, 5 and 6. Gödel needs to change this three-number sequence into a single, unique number — a number that no other sequence of symbols will generate. To do this, he takes the first three primes (2, 3 and 5), raises each to the Gödel number of the symbol in the same position in the sequence, and multiplies them together. Thus 0 = 0 becomes 26 × 35 × 56, or 243,000,000.
-
Because we can generate Gödel numbers for all formulas, even false ones, we can talk sensibly about these formulas by talking about their Gödel numbers.
-
Gödel’s extra insight was that he could substitute a formula’s own Gödel number in the formula itself, leading to no end of trouble.
-
Substitution forms the crux of Gödel’s proof.
-
There are three pieces of information to convey: We started with the formula that has Gödel number m. In it, we substituted m for the symbol y. And according to the mapping scheme introduced earlier, the symbol y has the Gödel number 17. So let’s designate the new formula’s Gödel number sub(m, m, 17)
-
You might think you could just posit some extra axiom, use it to prove G, and resolve the paradox. But you can’t. Gödel showed that the augmented axiomatic system will allow the construction of a new, true formula Gʹ (according to a similar blueprint as before) that can’t be proved within the new, augmented system. In striving for a complete mathematical system, you can never catch your own tail.
-
We’ve learned that if a set of axioms is consistent, then it is incomplete. That’s Gödel’s first incompleteness theorem. The second — that no set of axioms can prove its own consistency — easily follows.