22f4
Kurt Godel was born in 1906 in Brunn, then part of the Austro-Hungarian Empire and now part of the Czech Republic, to a father who owned a textile factory and had a fondness for logic and reason and a mother who believed in starting her son’s education early. By age 10, Godel was studying math, religion and several languages. By 25 he had produced what many consider the most important result of 20th century mathematics: his famous “incompleteness theorem.” Godel’s astonishing and disorienting discovery, published in 1931, proved that nearly a century of effort by the world’s greatest mathematicians was doomed to failure.
To appreciate Godel’s theorem, it is crucial to understand how mathematics was perceived at the time. After many centuries of being a typically sloppy human mishmash in which vague intuitions and precise logic coexisted on equal terms, mathematics at the end of the 19th century was finally being shaped up. So-called formal systems were devised (the prime example being Russell and Whitehead’s Principia Mathematica) in which theorems, following strict rules of inference, sprout from axioms like limbs from a tree. This process of theorem sprouting had to start somewhere, and that is where the axioms came in: they were the primordial seeds, the Ur-theorems from which all others sprang.
The beauty of this mechanistic vision of mathematics was that it eliminated all need for thought or judgment. As long as the axioms were true statements and as long as the rules of inference were truth preserving, mathematics could not be derailed; falsehoods simply could never creep in. Truth was an automatic hereditary property of theoremhood.
The set of symbols in which statements in formal systems were written generally included, for the sake of clarity, standard numerals, plus signs, parentheses and so forth, but they were not a necessary feature; statements could equally well be built out of icons representing plums, bananas, apples and oranges, or any utterly arbitrary set of chicken scratches, as long as a given chicken scratch always turned up in the proper places and only in such proper places. Mathematical statements in such systems were, it then became apparent, merely precisely structured patterns made up of arbitrary symbols.
Soon it dawned on a few insightful souls, Godel foremost among them, that this way of looking at things opened up a brand-new branch of mathematics - namely, metamathematics. The familiar methods of mathematical analysis could be brought to bear on the very pattern-sprouting processes that formed the essence of formal systems - of which mathematics itself was supposed to be the primary example. Thus mathematics twists back on itself, like a self-eating snake.
Bizarre consequences, Godel showed, come from focusing the lens of mathematics on mathematics itself. One way to make this concrete is to imagine that on some far planet (Mars, let’s say) all the symbols used to write math books happen - by some amazing coincidence - to look like our numerals 0 through 9. Thus when Martians discuss in their textbooks a certain famous discovery that we on Earth attribute to Euclid and that we would express as follows: “There are infinitely many prime numbers,” what they write down turns out to look like this: “84453298445087 87863070005766619463864545067111.” To us it looks like one big 46-digit number. To Martians, however, it is not a number at all but a statement; indeed, to them it declares the infinitude of primes as transparently as that set of 34 letters constituting six words a few lines back does to you and me.
Now imagine that we wanted to talk about the general nature of all theorems of mathematics. If we look in the Martians’ textbooks, all such theorems will look to our eyes like mere numbers. And so we might develop an elaborate theory about which numbers could turn up in Martian textbooks and which numbers would never turn up there. Of course we would not really be talking about numbers, but rather about strings of symbols that to us look like numbers. And yet, might it not be easier for us to forget about what these strings of symbols mean to the Martians and just to look at them as plain old numerals?
By such a simple shift of perspective, Godel wrought deep magic. The Gšdelian trick is to imagine studying what might be called “Martian-producible numbers” (those numbers that are in fact theorems in the Martian textbooks), and to ask questions such as, “Is or is not the number 8030974 Martian-producible (M.P., for short)?” This question means, Will the statement ‘8030974′ ever turn up in a Martian textbook?
Gšdel, in thinking very carefully about this rather surreal scenario, soon realized that the property of being M.P. was not all that different from such familiar notions as “prime number,” “odd number” and so forth. Thus earthbound number theorists could, with their standard tools, tackle such questions as, “Which numbers are M.P. numbers, and which are not?” for example, or “Are there infinitely many non-M.P. numbers?” Advanced math textbooks - on Earth, and in principle on Mars as well - might have whole chapters about M.P. numbers.
And thus, in one of the keenest insights in the history of mathematics, Godel devised a remarkable statement that said simply, “X is not an M.P. number” where X is the exact number we read when the statement “X is not an M.P. number” is translated into Martian math notation. Think about this for a little while until you get it. Translated into Martian notation, the statement “X is not an M.P. number” will look to us like just some huge string of digits - a very big numeral. But that string of Martian writing is our numeral for the number X (about which the statement itself talks). Talk about twisty; this is really twisty! But twists were Gšdel’s specialty - twists in the fabric of space-time, twists in reasoning, twists of all sorts.
By thinking of theorems as patterns of symbols, Gšdel discovered that it is possible for a statement in a formal system not only to talk about itself, but also to deny its own theoremhood. The consequences of this unexpected tangle lurking inside mathematics were rich, mind-boggling and - rather oddly - very sad for the Martians. Why sad? Because the Martians–like Russell and Whitehead - had hoped with all their hearts that their formal system would capture all true statements of mathematics. If Gšdel’s statement is true, it is not a theorem in their textbooks and will never, ever show up - because it says it won’t! If it did show up in their textbooks, then what it says about itself would be wrong, and who - even on Mars - wants math textbooks that preach falsehoods as if they were true?
The upshot of all this is that the cherished goal of formalization is revealed as chimerical. All formal systems - at least ones that are powerful enough to be of interest - turn out to be incomplete because they are able to express statements that say of themselves that they are unprovable. And that, in a nutshell, is what is meant when it is said that Godel in 1931 demonstrated the “incompleteness of mathematics.” It’s not really math itself that is incomplete, but any formal system that attempts to capture all the truths of mathematics in its finite set of axioms and rules. To you that may not come as a shock, but to mathematicians in the 1930s, it upended their entire world view, and math has never been the same since.
Godel’s 1931 article did something else: it invented the theory of recursive functions, which today is the basis of a powerful theory of computing. Indeed, at the heart of Godel’s article lies what can be seen as an elaborate computer program for producing M.P. numbers, and this “program” is written in a formalism that strongly resembles the programming language Lisp, which wasn’t invented until nearly 30 years later.
Godel the man was every bit as eccentric as his theories. He and his wife Adele, a dancer, fled the Nazis in 1939 and settled at the Institute for Advanced Study in Princeton, where he worked with Einstein. In his later years Godel grew paranoid about the spread of germs, and he became notorious for compulsively cleaning his eating utensils and wearing ski masks with eye holes wherever he went. He died at age 72 in a Princeton hospital, essentially because he refused to eat. Much as formal systems, thanks to their very power, are doomed to incompleteness, so living beings, thanks to their complexity, are doomed to perish, each in its own unique manner.
680