The Information (29 page)

One was Berry’s paradox, first suggested to Russell by G. G. Berry, a librarian at the Bodleian. It has to do with counting the syllables needed to specify each integer. Generally, of course, the larger the number the more syllables are required. In English, the smallest integer requiring two syllables is seven. The smallest requiring three syllables is eleven. The number 121 seems to require six syllables (“one hundred twenty-one”),
but actually four will do the job, with some cleverness: “eleven squared.” Still, even with cleverness, there are only a finite number of possible syllables and therefore a finite number of names, and, as Russell put it, “Hence the names of some integers must consist of at least nineteen syllables, and among these there must be a least. Hence
the least integer not nameable in fewer than nineteen syllables
must denote a definite integer.”
^♦
♦
Now comes the paradox. This phrase,
the least integer not nameable in fewer than nineteen syllables
, contains only eighteen syllables. So the least integer not nameable in fewer than nineteen syllables has just been named in fewer than nineteen syllables.

Another paradox of Russell’s is the Barber paradox. The barber is the man (let us say) who shaves all the men, and only those, who do not shave themselves. Does the barber shave himself? If he does he does not, and if he does not he does. Few people are troubled by such puzzles, because in real life the barber does as he likes and the world goes on. We tend to feel, as Russell put it, that “the whole form of words is just a noise without meaning.”
^♦
But the paradox cannot be dismissed so easily when a mathematician examines the subject known as set theory, or the theory of classes. Sets are groups of things—for example, integers. The set 0, 2, 4 has integers as its members. A set can also be a member of other sets. For example, the set 0, 2, 4 belongs to the set of
sets of integers
and the set of
sets with three members
but not the set of
sets of prime numbers
. So Russell defined a certain set this way:

This version is known as Russell’s paradox. It cannot be dismissed as noise.

To eliminate Russell’s paradox Russell took drastic measures. The enabling factor seemed to be the peculiar recursion within the offending
statement: the idea of sets belonging to sets. Recursion was the oxygen feeding the flame. In the same way, the liar paradox relies on statements about statements. “This statement is false” is meta-language: language about language. Russell’s paradoxical set relies on a meta-set: a set of sets. So the problem was a crossing of levels, or, as Russell termed it, a mixing of types. His solution: declare it illegal, taboo, out of bounds. No mixing different levels of abstraction. No self-reference; no self-containment. The rules of symbolism in
Principia Mathematica
would not allow the reaching-back-around, snake-eating-its-tail feedback loop that seemed to turn on the possibility of self-contradiction. This was his firewall.

Enter Kurt Gödel.

He was born in 1906 in Brno, at the center of the Czech province of Moravia. He studied physics at the University of Vienna, seventy-five miles south, and as a twenty-year-old became part of the Vienna Circle, a group of philosophers and mathematicians who met regularly in smoky coffeehouses like the Café Josephinum and the Café Reichsrat to propound logic and realism as a bulwark against metaphysics—by which they meant spiritualism, phenomenology, irrationality. Gödel talked to them about the New Logic (this term was in the air) and before long about metamathematics—
der Metamathematik
. Metamathematics was not to mathematics what metaphysics was to physics. It was mathematics once removed—mathematics about mathematics—a formal system “looked at from the outside” (“
äußerlich betrachtet
”).
^♦
He was about to make the most important statement, prove the most important theorem about knowledge in the twentieth century. He was going to kill Russell’s dream of a perfect logical system. He was going to show that the paradoxes were not excrescences; they were fundamental.

Gödel praised the Russell and Whitehead project before he buried it: mathematical logic was, he wrote, “a science prior to all others, which contains the ideas and principles underlying all sciences.”
^♦
Principia Mathematica
, the great opus, embodied a formal system that had become, in its brief lifetime, so comprehensive and so dominant that
Gödel referred to it in shorthand: PM. By PM he meant the system, as opposed to the book. In PM, mathematics had been contained—a ship in a bottle, no longer buffeted and turned by the vast unruly seas. By 1930, when mathematicians proved something, they did it according to PM. In PM, as Gödel said, “one can prove any theorem using nothing but a few mechanical rules.”
^♦

Any
theorem: for the system was, or claimed to be, complete.
Mechanical
rules: for the logic operated inexorably, with no room for varying human interpretation. Its symbols were drained of meaning. Anyone could verify a proof step by step, by following the rules, without understanding it. Calling this quality mechanical invoked the dreams of Charles Babbage and Ada Lovelace, machines grinding through numbers, and numbers standing for anything at all.

Amid the doomed culture of 1930 Vienna, listening to his new friends debate the New Logic, his manner reticent, his eyes magnified by black-framed round spectacles, the twenty-four-year-old Gödel believed in the perfection of the bottle that was PM but doubted whether mathematics could truly be contained. This slight young man turned his doubt into a great and horrifying discovery. He found that lurking within PM—and within any consistent system of logic—there must be monsters of a kind hitherto unconceived: statements that can never be proved, and yet can never be disproved. There must be
truths
, that is, that cannot be proved—and Gödel could prove it.

He accomplished this with iron rigor disguised as sleight of hand. He employed the formal rules of PM and, as he employed them, also approached them metamathematically—viewed them, that is, from the outside. As he explained, all the symbols of PM—numbers, operations of arithmetic, logical connectors, and punctuation—constituted a limited alphabet. Every statement or formula of PM was written in this alphabet. Likewise every proof comprised a finite sequence of formulas—just a longer passage written in the same alphabet. This is where metamathematics came in. Metamathematically, Gödel pointed out, one sign is
as good as another; the choice of a particular alphabet is arbitrary. One could use the traditional assortment of numerals and glyphs (from arithmetic: +, −, =, ×; from logic: ¬, ∨, ⊃, ∃), or one could use letters, or one could use dots and dashes. It was a matter of encoding, slipping from one symbol set to another.

Gödel proposed to use numbers for all his signs. Numbers were his alphabet. And because numbers can be combined using arithmetic, any sequence of numbers amounts to one (possibly very large) number. So every statement, every formula of PM can be expressed as a single number, and so can every proof. Gödel outlined a rigorous scheme for doing the encoding—an algorithm, mechanical, just rules to follow, no intelligence necessary. It works forward and backward: given any formula, following the rules generates one number, and given any number, following the rules produces the corresponding formula.

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—

—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),

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:

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.

Gödel’s first public mention of his discovery, on the third and last day of a philosophical conference in Königsberg in 1930, drew no response; only one person seems to have heard him at all, a Hungarian named Neumann János. This young mathematician was in the process of moving to the United States, where he would soon and for the rest of his life be called John von Neumann. He understood Gödel’s import at once; it stunned him, but he studied it and was persuaded. No sooner did Gödel’s paper appear than von Neumann was presenting it to the mathematics colloquium at Princeton. Incompleteness was real. It meant that mathematics could never be proved free of self-contradiction. And “the important point,” von Neumann said, “is that this is not a philosophical principle or a plausible intellectual attitude, but the result of a rigorous mathematical proof of an extremely sophisticated kind.”
^♦
Either you believed in mathematics or you did not.

Bertrand Russell (who, of course,
did
) had moved on to more gentle sorts of philosophy. Much later, as an old man, he admitted that Gödel had troubled him: “It made me glad that I was no longer working at mathematical logic. If a given set of axioms leads to a contradiction, it is clear that at least one of the axioms must be false.”
^♦
On the other hand, Vienna’s most famous philosopher, Ludwig Wittgenstein (who, fundamentally,
did not
), dismissed the incompleteness theorem as trickery (“
Kunststücken
”) and boasted that rather than try to refute it, he would simply pass it by:

Gödel’s retort took care of them both. “Russell evidently misinterprets my result; however, he does so in a very interesting manner,” he wrote. “In contradistinction Wittgenstein … advances a completely trivial and uninteresting misinterpretation.”
^♦

In 1933 the newly formed Institute for Advanced Study, with John von Neumann and Albert Einstein among its first faculty members, invited Gödel to Princeton for the year. He crossed the Atlantic several more times that decade, as fascism rose and the brief glory of Vienna began to fade. Gödel, ignorant of politics and naïve about history, suffered depressive breakdowns and bouts of hypochondria that forced him into sanatoria. Princeton beckoned but Gödel vacillated. He stayed in Vienna in 1938, through the
Anschluss
, as the Vienna Circle ceased to be, its members murdered or exiled, and even in 1939, when Hitler’s army occupied his native Czechoslovakia. He was not a Jew, but mathematics was
verjudet
enough. He finally managed to leave in January 1940 by way of the Trans-Siberian Railway, Japan, and a ship to San Francisco. His name was recoded by the telephone company as “K. Goedel” when he arrived in Princeton, this time to stay.
^♦