David Hilbert, the great German mathematician (he died in 1943), had a stupendous, dazzling vision. He hoped and believed that some day mathematicians would construct one vast formal deductive system with axioms so powerful that every possible theorem in all of mathematics could be proved true or false. Such a system would have to be both consistent and complete. Consistent means it is impossible to prove both a statement and its negation. Complete means that every statement in the system can be proved true or false.
In 1931, to the astonishment of mathematicians, a shy, reclusive Austrian, Kurt Gödel, aged twenty-five, shattered Hilbert’s magnificent dream. Gödel showed that any formal system rich enough to include arithmetic and elementary logic could not be both consistent and complete. If complete, it would contain an infinity of true statements that could not be proved by the system’s axioms. What is worse, even the consistency of such a system cannot be established by reasoning within the system. “God exists,” a mathematician remarked, “because mathematics is consistent, and the devil exists because we can never prove it.”
I recall a cartoon by Robert Monkoff which shows a man in a restaurant examining his bill. He is saying to the puzzled waiter: “The arithmetic seems correct, yet I find myself haunted by the idea that the basic axioms on which arithmetic is based might give rise to contradictions that would then invalidate these computations.”
Fortunately, arithmetic can be shown consistent, but only by going outside it to a larger system. Alas, the larger system can’t be proved consistent without going to a still larger system. Many formal systems less complex than arithmetic, such as simple logic and even arithmetic without multiplication and division, can be proved consistent and complete without going beyond the system. But on levels that include all of arithmetic, the need for meta-systems to prove completeness and consistency never ends. There is no final system, such as Hilbert longed for, that captures all of mathematics. “Truth,” as the authors of this new book encapsule it, “is larger than proof.”
Statements that are true but unprovable inside a formal system are called “Gödel undecidable.” Like consistency, they can be shown true by a meta-system, but the larger system is sure to contain its own unprovable statements. There is no escape from the endless regress of meta-systems, each with undecidable theorems.
Many books and thousands of technical papers have dealt with Gödel’s epochal bombshell and its implications. Several excellent biographies of Gödel have been published. Gödel: A Life of Logic, by the American science writer John Casti and the mathematician Werner DePauli of the University of Vienna, is a splendid nontechnical account of the Gödelian revolution and at the same time a sketch of Gödel’s eccentric life and its tragic ending.
The authors begin with Gödel’s birth and childhood in Brno, a city now part of the Czech Republic, where he became fluent in German, French, and English. In 1924, he settled in Vienna. There his philosophical interests put him in contact with the famous Vienna Circle of philosophers whose leaders were Moritz Schlick and Rudolf Carnap.
Gödel’s ingenious method of proving undecidability is explained by Casti and DePauli as clearly as possible in a book for general readers. The argument requires attaching a prime number (a number with no divisors except itself and 1) to each symbol in a sentence expressing a theorem. Multiplying the prime numbers gives a product which, because it has a unique set of prime factors, is a unique coding of the sentence. By applying a “diagonal proof” which Georg Cantor had used to show that the infinity of real numbers exceeds the infinity of whole numbers, Gödel was able to construct a number that codes a true sentence which states its own unprovability. In later decades a raft of simpler ways to obtain the same result has been devised, many by the American logician Raymond Smullyan.
In 1940, now world famous, Gödel joined the staff of eminent thinkers at the Institute for Advanced Study, in Princeton, where he and Einstein became good friends. “I used to see them walk to work together,” Murray Gell-Mann recalls in his autobiography. “Did they discuss deep mathematical or physical questions? … or was their conversation mainly about the weather and their health problems?”
Although Gödel continued to make significant contributions to mathematics, as he grew older his speculations became more and more bizarre. In a contribution to Albert Einstein: Philosopher Scientist, an anthology edited by Paul Schlipp, Gödel proposed a model of the universe difficult to take seriously. He conjectured that the universe is rotating in such a peculiar way that it generates closed time-like loops along which a spaceship could travel into the past and future. Following Kant, Gödel believed time to be a subjective illusion. The universe itself is timeless; what William James called a “block universe” in which past and future exist in an eternal now. In such a cosmos, free will obviously is also an illusion, and it is impossible for anyone to alter either the future or the past. How, one wonders, did Gödel avoid the paradoxes of time travel into the past, such as killing yourself, or performing other acts involving your duplicate—acts not in your memory? Gödel’s way out was surprisingly feeble. He argued that travel to the past required such high speeds and long distances that not enough fuel would be available!
Strongly influenced by Leibniz, and by the German philosopher Edmund Husserl, Gödel outlined his own curious version of the ontological argument. This old argument claims to prove that the nonexistence of god, the most perfect of all beings, implies a logical contradiction. Gödel was a philosophical theist who not only believed in a personal god, but also in an afterlife. Because humans have an infinite potential for development, he insisted, it would be absurd for god to create us without allowing for such progress.
As he aged, Gödel became increasingly preoccupied with occultism, reincarnation, and parapsychology. He believed in the reality of ESP and ghosts. He was convinced that his wife Adele, a former nightclub dancer, had strong powers of precognition. He believed that our “self” is more than just the physical brain: “The notion that our ego consists of protein molecules,” he said in a letter, “seems to me one of the most ridiculous ever made.”
Gödel’s philosophy of mathematics, Casti and DePauli make clear, was one of extreme Platonic realism. He thought mathematical objects such as numbers, triangles, and even Cantor’s transfinite sets, are as real and independent of human minds, though in a different way, as pebbles and planets.
Bertrand Russell, in the second volume of his autobiography, speaks of discussions he had at Einstein’s house with Gödel, whom he mistakenly calls Jewish. “Gödel turned out,” Russell writes, “to be an unadulterated Platonist, and apparently believed an eternal ‘not’ was laid up in heaven, where virtuous logicians hope to meet it hereafter.”
Here is how Gödel replied in an unsent letter:
As far as the passage about me [in Russell’s autobiography] is concerned, I have to say first (for the sake of truth) that I am not a Jew (even though I don’t think this question is of any importance), 2) that the passage gives the wrong impression that I had many discussions with Russell, which was by no means the case (I remember only one). 3) Concerning my “unadulterated” Platonism, it is no more “unadulterated” than Russell’s own in 1921 when in the Introduction [to Mathematical Philosophy] he said “[Logic is concerned with the real world just as truly as zoology, though with its more abstract and general features].” At that time evidently Russell had met the “not” even in this world, but later on under the influence of Wittgenstein he chose to overlook it.
As Gödel neared death he became increasingly depressed and paranoid. He began refusing food because he thought he was being poisoned. Somehow Adele managed to keep him alive until his weight dropped to sixty pounds and he stopped eating altogether. His death was a suicide brought on by self-inflicted starvation. He left a vast quantity of unpublished papers, and notes kept in a long forgotten German shorthand called the Gabelsberger method.
Casti and DePauli devote the last half of their book to ramifications of Gödelian undecidablity, including the amazing discoveries of IBM’s Gregory Chaitin about random numbers, too technical to discuss here. In England, Alan Turing translated Gödel’s results into the operation of computers. He showed, using arguments similar to Gödel’s, that it is impossible to build a computer that can decide the truth or falsity of every mathematical question. Given a conjecture and a program for testing it, a computer will stop after a finite number of steps if it finds the theorem true or false. But there are undecidable questions it will keep testing forever. The authors are skillful in explaining the “halting problem” as it applies to an idealized computer known as a Turing machine.
Not all undecidable theorems must be true. They can be true or false, and in some cases can be assumed either true or false. For example, consider Euclid’s notorious parallel postulate: that through a point outside a straight line one and only one parallel to the line can be drawn. The postulate is undecidable in a system based on Euclid’s other axioms. If assumed true, it leads to Euclidean geometry. If assumed false, it leads to systems of non-Euclidean geometry.
Because laws of physics are expressed mathematically, the possibility arises that the universe may also have its undecidable laws. “Some of our colleagues in particle physics,” wrote the physicist Freeman Dyson in Infinite In All Directions,
think that they are coming to a complete understanding of the basic laws of nature… . But I hope [this] … will prove as illusory as the notion of a formal decision for all of mathematics. If it should turn out that the whole of physical reality can be described by a finite set of equations, I would be disappointed. I would feel that the Creator had been uncharacteristically lacking in imagination.
For decades Fermat’s last theorem—the conjecture that an + bn = cn has no solution if n is an integer greater than 2—was thought by some mathematicians to be undecidable until it was proved true. Today the outstanding unsolved problem in number theory is Goldbach’s conjecture. It states that every even number greater than 2 is the sum of two primes in at least one way. All number theorists believe it, partly because it has been tested to monstrously large even numbers, and partly because the larger the number the more ways it can be a sum of two primes. Is it possible that Goldbach’s conjecture is undecidable? Two publishers, England’s Faber and Faber and New York’s Bloomsbury Books, have offered a million dollars for a proof of Goldbach’s conjecture before March 15, 2002. The offer is a promotion for a Greek novel by Apostolos Doxiadis with the English title Uncle Petros and Goldbach’s Conjecture. It tells how Petros Papachristos was driven mad by his vain efforts to prove Goldbach’s conjecture before he decided it was undecidable.
It is easy to show that if Goldbach’s theorem is undecidable it must be true. Assume it is undecidable and false. Then, there will be a counterexample, an even number not the sum of two primes, which a computer could find in a finite number of steps. This makes the theorem undecidable, thus contradicting the assumption that the conjecture is undecidable and false. Therefore it must be undecidable and true.
Casti and DePauli also take up a question which is currently controversial. Does the fact that computers are unable to decide an infinity of conjectures show that our minds are superior to computers because we can often construct meta-systems, with intuitively reasonable axioms, that will decide such questions? This thesis was first strongly defended by the Oxford philosopher J. Anthony Lucas and more recently by Oxford’s mathematical physicist Roger Penrose, among others. Almost all artificial intelligence experts disagree. They are convinced that computers of the kind we know how to build—that is, computers made of wires and switches—are capable in principle of doing as well as humans in finding meta-systems. Indeed, some experts believe that computers will soon cross a threshold of complexity that will enable them to do everything that human minds can do. The physicist Jeremy Bernstein, in one of his books, recalls that as a student he once asked the great Hungarian mathematician John von Neumann, a friend and admirer of Gödel, if computers would ever replace mathematicians. “Sonny,” von Neumann replied, “don’t worry about it.”
- Adele was an attractive, contentious, antisocial, uneducated woman with atrocious taste. She once planted a pink flamingo outside her Princeton home. Gödel’s taste, his biographer John Dawson commented, was no better. He thought the flamingo was “charming.” Go back to the text.