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.
Simply Charly: What is the difference between Gödel’s first and second incompleteness theorem?
Gregory Chaitin: 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.
SC: 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?
GC: 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.
SC: What were his peers’ reactions when Gödel’s discovery, dooming to failure the efforts of the world’s greatest mathematicians, was announced?
GC: 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.
SC: 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?
GC: 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.
SC: What are the implications of this discovery in the field of mathematics and logic?
GC: 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 absurdity) of Hilbert’s traditional formalist view that math is based on logical reasoning and the axiomatic method.
SC: To what other areas outside of mathematics and logic (physics, theology, philosophy) did Gödel contribute?
GC: 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 the 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).
SC: Are any renegade mathematicians/logicians disputing the theorem of incompleteness, and if so, on what grounds?
GC: 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 am such a renegade.)
SC: Is anyone today working to further or bring a new dimension to the incompleteness theorem?
GC: 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 to 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.
SC: 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?
GC: 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, 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.
SC: 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?
GC: 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.
SC: How does your own work relate to Gödel’s and what projects are you working on now?
GC: 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 math theory only has finite complexity, hence incompleteness. And the best example of infinite complexity in pure math that I have been able to come up with are the bits in the base-two numerical value of the halting probability Omega, which shows that some math facts are true for no reason, they are true by accident. (For more on this, please see my two books cited below.)
Books for more information (all cited above) In English:
Rebecca Goldstein, Incompleteness: The Proof and Paradox of Kurt Gödel. Palle Yourgrau, A World Without Time: The Forgotten Legacy of Gödel and Einstein. David Bailey et al., Experimental Mathematics in Action. William Byers, How Mathematicians Think. Gregory Chaitin, Meta Math!: The Quest for Omega. Gregory Chaitin, Thinking about Gödel and Turing: Essays on Complexity, 1970-2007.
In French:
Pierre Cassou-Nogues, Les demons de Gödel: Logique et folie (Gödel’s Demons: Logic and Madness).
In Italian:
Kurt Gödel, La prova matematica dell’esistenza di Dio (The mathematical proof of the existence of God) (edited and commented on by Gabriele Lolli and Piergiorgio Odifreddi).
SUGGESTED READING
  |   |   |   |
