The Proof and Paradox of Kurt Gödel

Born in Moravia (now the Czech Republic), Kurt Gödel (April 28, 1906 - January 14, 1978) became one of the most significant mathematicians of the 20th century by the time he turned 25. As a student, an early interest in languages gave way to a passion for mathematics, which he supplemented in his teens with history and philosophy. At 18, he entered the University of Vienna, where his older brother was a medical student. His early courses exposed him to number theory and mathematical logic, and his growing interest in mathematical realism led him to pursue mathematics rather than physics as he'd first intended.

Mathematical realism says that mathematical objects and concepts are real, that they exist outside of human invention and imagination. The distinction may seem trivial, so consider it in terms of food instead: the difference between fruit and meat is "real," it's a difference that is true regardless of human involvement. The difference between dessert and breakfast, on the other hand, exists only in the human mind -- there is no scientific property separating them. Mathematical concepts are discovered, according to realism -- not invented the way recipes are.

Important early influences on Gödel included Immanuel Kant, Bertrand Russell, and David Hilbert. There is a stereotype about mathematicians that they do their most ground-breaking work early in life, even though their mastery over the discipline is greater later. There are many theories about why this might be true, of course, but Kurt Gödel has always been a prime example of the trend. He published his best-known and most important work, his incompleteness theorems, in 1931 -- only a year after graduating from the university, where his completeness theorem had formed his doctoral dissertation. The completeness theorem had proven the completeness of predicate logic -- it had shown, in other words, that within predicate logic (also known as first-order logic), every logically valid formula can be proven through a list of steps. To over-simplify a little, he proved that predicate logic contained all the rules necessary to prove the things it's designed to prove. Like many mathematical advances, this was something which was widely believed to be true but hadn't yet been effectively proven.

The 1931 incompleteness theorems were much more advanced and ground-breaking. Since the nineteenth century, mathematicians had been trying to construct a set of axioms (mathematical rules) which would include all of mathematics. Gödel proved that they would never succeed. To some mathematicians, it was as though he had proven in the middle of the space race that launching a rocket was impossible; few of his colleagues had considered that what they sought was impossible, and had focused more on finding it, whether by brute force or elegant solutions. Gödel proved that for any such system of rules, there would be a valid mathematical formula that it could not prove.

In Gödel's words: "Any effectively generated theory capable of expressing elementary arithmetic cannot be both consistent and complete."

Even aside from the implications of his proof, Gödel had to invent whole new mathematical language in order to achieve it. It took time for those implications to set in, and they continue to unfurl: Gödel's work has been critical in philosophy and cognitive science, and is sometimes brought up in the study of (and quest for) artificial intelligence.

Gödel continued to work in and lecture on this general area of mathematics throughout the 1930s. An often troubled man who suffered a nervous breakdown after the murder of one of his mentors, Gödel avoided politics, and so the only immediate impact on him of the Nazi Party's ascension to power in Germany (which had absorbed Austria) was the abolition of his teaching job. (Not his specifically, but all jobs with his title of Privatdozent.) When his Jewish friends and physical fitness for military duty made it hard for him to find another mathematics job in Vienna, he and his wife left Europe. In 1940, Gödel took a teaching position at the Institute for Advanced Study in Princeton, New Jersey -- where Albert Einstein had emigrated some years earlier. Gödel and Einstein became close friends, both of them brilliant men who saw their early contributions to science unfold wide-spanning consequences during their lives. Einstein later accompanied Gödel when the latter sought U.S. citizenship.

Gödel also published a paper on Einstein's field equations which provided a solution in which time travel would be possible, though his goal was more likely to demonstrate the problems with our understanding of "time" in light of modern physics. Still, it's hard to say. Though he continued to make major contributions to mathematics, especially his work on such advanced topics as the axiom of choice and the continuum hypothesis, in the last years of Gödel's life some of his pursuits became less traditional. He believed there was a way to avoid death, and lamented his inability to discover the mathematics of this escape in his notebooks; when seeking his American citizenship, he went off on a tangent, explaining to the judge that a loophole in the Constitution allowed for the creation of a dictatorship. Straddling the line between the mainstream and the unconventional, he also developed his ontological proof of God, drawing on prior writings by Saint Anselm and Gottfried Leibniz.

He starved to death in 1978 while his wife was too sick to cook for him -- in a bout of paranoia, he refused to eat anything else lest he be poisoned. His work continues to be as important to many branches of mathematics and logic as his friend Einstein's was to physics.

"In any non-trivial axiomatic system," stated Austrian mathematician and logician Kurt Gödel (1906 - 1978), "there are true theorems which cannot be proven."

This finding forms the basis of Gödel's groundbreaking Incompleteness Theorem, demonstrating that the establishment of a set of axioms encompassing all of mathematics would never succeed.

When it was first made public in 1931, the theorem revolutionized the field of mathematics and logic, disproving the prevailing belief that mathematics could be explained with the correct set of axioms.

Gregory Chaitin is at the IBM Thomas J. Watson Research Center in Yorktown Heights, New York. He is the discoverer of the celebrated Omega number, and has devoted his life to developing a complexity-based view of incompleteness. He calls this subject "algorithmic information theory," and has published eleven books and numerous papers, some of which may be found on his website at http://www.cs.umaine.edu/~chaitin.
Q. What is the difference between Gödel's first and second incompleteness theorem?

A: Gödel's first incompleteness theorem shows that no axiomatic theory can prove all mathematical truths, while Godel's second incompleteness theorem shows that a specific mathematical result is unprovable. A famous mathematician of the time, David Hilbert, had asked for a proof that an important axiomatic theory was consistent, and Gödel showed that such a proof could not be carried out within the axiomatic theory itself, and presumably could therefore not be established in a convincing way outside of the theory either.

At the time, Gödel's second incompleteness theorem had the greatest impact, because Hilbert had argued that a proof of consistency was an extremely important part of his so-called "formalist" program.

In my opinion, however, the second incompleteness theorem is now only of historical interest, since Hilbert and his formalist project are fading into history. What is still extremely shocking is Gödel's first incompleteness theorem, since here we have logic and mathematics showing that logic and mathematics have serious limitations, surprisingly enough.

Q. David Hilbert believed that eventually all mathematical things would be defined. Gödel's theorem disproves that. Are there any other commonly held beliefs / theories that the incompleteness theorem puts into doubt?

A: Incompleteness shows that mathematics, logic and axiomatic reasoning do not furnish us with absolute truth. It shows that the truth is not totally black or white, not even in pure math, not even in the domain of pure reason. This is very difficult emotionally for mathematicians to accept.

Q. What was his peers' reaction when Gödel's discovery, dooming to failure the efforts of the world's greatest mathematicians, was announced?

A: The initial reaction was surprise and dismay, and a feeling that Godel had pulled the rug out from under mathematics. But human beings have wonderful psychological defense mechanisms. The crisis has passed, and the mathematical community now has forgotten about incompleteness. They continue to work as before and believe in absolute truth, logic, and the axiomatic method. They dismiss incompleteness as a theoretical possibility but having no impact in practice on the everyday work of mathematicians. They do not think incompleteness applies to "real" mathematics, but only in extremely artificial circumstances.

Q. Within the context of how mathematics was perceived at the time, what was the impact of Gödel's work on other mathematicians of his era, and on science and philosophy in general?

A. At that time, it seemed to destroy the conventional notion of what math is all about. It left the foundations of math in total disarray. Now, as I said, incompleteness is actually ignored and everything proceeds as if Gödel had never existed. However, my own very controversial and very much a minority view, is that incompleteness shows that math and physics are not that different, that neither gives absolute truth. Following Imre Lakatos, I refer to this as a "quasi-empirical" view of mathematics.

Q. What are the implications of this discovery on the field of mathematics and logic?

A: Gödel's own belief was that in spite of his incompleteness theorem, there is in fact no limit to what mathematicians can achieve by using their intuition and creativity, instead of depending only on logic and the axiomatic method. He believed that any important mathematical question could eventually be settled, if necessary by adding new fundamental principles to math, that is, new axioms or postulates. This implies, however, that the concept of mathematical truth becomes something dynamic that evolves, that changes with time, as opposed to the traditional view that mathematical truth is static and eternal. Though this seemed like an obvious consequence of his work to Gödel himself, these ideas of Gödel's about the meaning and the implications of his work were not accepted by the mathematical community. Still now, more than 75 years after Gödel published his incompleteness theorem, it remains controversial. My own view is that Godel uses logic to refute logic, and that Gödel's incompleteness theorem is a reductio ad absurdum (reduction to an absurdity) of Hilbert's traditional formalist view that math is based on logical reasoning and the axiomatic method.

Q. To what other areas outside of mathematics and logic (physics, theology, philosophy) did Gödel contribute?

A: Gödel used Einstein's theory of general relativity to construct a rotating universe in which the future and the past form a loop, arguing that this showed that time was an illusion. For more on this, see the book by Palle Yourgrau (listed below). In theology, Gödel gave a logical proof of the existence of God. There is a book in Italian presenting Gödel's proof and discussing it (see the list of books below). Godel also did a considerable amount of work on philosophy, which is unfortunately generally ignored since it goes against current zeitgeist, against the current spirit of the time. He is closest to the rationalist philosophy of the 17th century philosopher and mathematician Leibniz. Gödel the philosopher is discussed in two excellent books, one in English by Rebecca Goldstein, and one in French by Pierre Cassou-Nogues (see below).

Q. Are any renegade mathematicians / logicians disputing the theorem of incompleteness, and if so, on what grounds?

A: The exact opposite is the case. No one disputes Gödel's theorem, but people insist that it has no philosophical impact, no bearing on how math should actually be done, and does not change the traditional formalist mathematical stance believing in static black-and-white absolute truth attained through logic and the axiomatic method. So now, in a reversal of fortune, it requires daring to claim that incompleteness is significant. (I myself am such a renegade.)

Q. Is anyone today working to further or bring a new dimension to the incompleteness theorem?

A: The first such work was done by Alan Turing and Emil Post already in the 1930s and 1940s, who brought the computer into the discussion and showed that incompleteness was a corollary, an immediate consequence, of a much more fundamental difficulty, the existence of mathematical questions whose answers are uncomputable (and therefore also unprovable).

And a few people are still trying to digest Gödel. Two recent examples are given in books by Byers and by Bailey, et al. (see below). Byers argues about the important role of intuition, ambiguity and paradox in mathematical creativity, and against formalism, logic and the axiomatic method, which he claims have a stultifying effect. Bailey et al. champion experimental math in which conjectures based on computer experiments are used to supplement traditional mathematical reasoning. In other words, they propose that sometimes it pays to treat math as an experimental science
rather than as a traditional deductive discipline.

Q. Since the 19th century, mathematicians have been trying to construct a set of axioms that would include all of mathematics. Gödel proved that they would never succeed. Have we gained any knowledge / insight since then that could eventually lead mathematicians to construct such a set of axioms?

A: Well, we know that such a set of axioms could never be complete. In other words, for math to progress it would have to evolve over time, adding new concepts and new fundamental principles (axioms or postulates). In practice, however, most contemporary mathematicians seem to think that ZFC, the formal axiomatic version of Zermelo-Fraenkel set theory using first-order logic, is adequate for all existing mathematics. ZFC is currently fashionable even though Godel's incompleteness theorem applies to it just as much as to the axiomatic theory that Hilbert was interested in.

Q. By all accounts, Gödel and Albert Einstein were close friends and they had many discussions during the walks they took together to and from the Princeton Institute for Advanced Study. Do we know what they talked about, and also what each thought of the other's work?

A: Gödel and Einstein were respectively a mathematician and a physicist, but they shared an interest in philosophy and fundamental ideas, as well as a belief that the universe can be rationally comprehended. Neither believed in quantum randomness or contingent truths. Einstein late in life used to say that he no longer had much interest in his own work but went to the Institute mostly for the privilege of talking with Gödel.

Q. How does your own work relate to Gödel's and what projects are you working on now?

A: My work attempts to go further in the direction pioneered by Turing and Post. They deduce incompleteness from uncomputability, I deduce incompleteness by using arguments involving information, complexity and randomness. In a nutshell, I argue that the world of pure math is infinitely complex, but any