The Information - James Gleick [87]
Not every number translates into a correct formula, however. Some numbers decode back into gibberish, or formulas that are false within the rules of the system. The string of symbols “0 0 0 = = =” does not make a formula at all, though it translates to some number. The statement “0 = 1” is a recognizable formula, but it is false. The formula “0 + x = x + 0” is true, and it is provable.
This last quality—the property of being provable according to PM—was not meant to be expressible in the language of PM. It seems to be a statement from outside the system, a metamathematical statement. But Gödel’s encoding reeled it in. In the framework he constructed, the natural numbers led a double life, as numbers and also as statements. A statement could assert that a given number is even, or prime, or a perfect square, and a statement could also assert that a given number is a provable formula. Given the number 1,044,045,317,700, for example, one could make various statements and test their truth or falsity: this number is even, it is not a prime, it is not a perfect square, it is greater than 5, it is divisible by 121, and (when decoded according to the official rules) it is a provable formula.
Gödel laid all this out in a little paper in 1931. Making his proof watertight required complex logic, but the basic argument was simple and elegant. Gödel showed how to construct a formula that said A certain number, x, is not provable. That was easy: there were infinitely many such formulas. He then demonstrated that, in at least some cases, the number x would happen to represent that very formula. This was just the looping self-reference that Russell had tried to forbid in the rules of PM—
This statement is not provable
—and now Gödel showed that such statements must exist anyway. The Liar returned, and it could not be locked out by changing the rules. As Gödel explained (in one of history’s most pregnant footnotes),
Contrary to appearances, such a proposition involves no faulty circularity, for it only asserts that a certain well-defined formula … is unprovable. Only subsequently (and so to speak by chance) does it turn out that this formula is precisely the one by which the proposition itself was expressed.♦
Within PM, and within any consistent logical system capable of elementary arithmetic, there must always be such accursed statements, true but unprovable. Thus Gödel showed that a consistent formal system must be incomplete; no complete and consistent system can exist.
The paradoxes were back, nor were they mere quirks. Now they struck at the core of the enterprise. It was, as Gödel said afterward, an “amazing fact”—“that our logical intuitions (i.e., intuitions concerning such notions as: truth, concept, being, class, etc.) are self-contradictory.”♦ It was, as Douglas Hofstadter says, “a sudden thunderbolt from the bluest of skies,”♦ its power arising not from the edifice it struck down but the lesson it contained about numbers, about symbolism, about encoding:
Gödel’s conclusion sprang not from a weakness in PM but from a strength. That strength is the fact that numbers are so flexible or “chameleonic” that their patterns can mimic patterns of reasoning.… PM’s expressive power is what gives rise to its incompleteness.
The long-sought universal language, the characteristica universalis Leibniz had pretended to invent, had been there all along, in the numbers. Numbers could encode all of reasoning. They could represent any form of knowledge.