Is mathematics a consistent theory? Or, rather, is there a danger of finding a correct mathematical proof for a false statement like “0 = 1″? These questions became quite relevant at the end of the nineteenth century, when some mathematical truths dating back many centuries were shattered and mathematicians started to feel the need for completely rigorous and solid foundations for their discipline.
Gödel’s incompleteness theorem is a famous result in mathematics that shows the limitation of mathematics itself. At the end of the nineteenth century and the beginning of the twentieth, mathematicians tried to find a complete and consistent set of axioms for mathematics. This goal is often referred to as Hilbert’s program, after the mathematician David Hilbert who posed it as the second problem in his famous list of open problems in mathematics. In 1931 Kurt Gödel proved that this goal is impossible to achieve. Gödel proved that for any system of axioms for mathematics there are true results that cannot be proved! This is referred to as Gödel’s first incompleteness result. One startling consequence is that it is impossible to precisely formulate the consistency of mathematics and therefore impossible to prove the consistency of mathematics. This is the content of Gödel’s second incompleteness theorem.
Gödel’s theorem is one of the few results of mathematics that capture the imagination of people well beyond mathematics. The well-known book Gödel, Escher, Bach by Douglas Hofstadter discusses common themes in the works of mathematician Gödel, artist M. C. Escher, and composer Johann Sebastian Bach.
Gödel’s theorem is the climax (and, paradoxically, the end) of the “foundational crisis” in mathematics. Gottlob Frege made an important attempt to reduce all mathematics to a logical formulation. However, Bertrand Russell found a simple paradox that demonstrated a flaw in Frege’s approach. The Dutch mathematician Luitzen E. J. Brouwer proposed an approach to mathematics, called intuitionism, which does not accept the law of excluded middle. This approach does not accept “Reductio ad absurdum,” or, in other words, mathematical proofs “by contradiction.” Most works in mathematics, including Brouwer’s own famous earlier work, do not live up to the intuitionistic standards of mathematical proofs. Brouwer’s ideas were regarded as revolutionary and, while on his lecture tours, he was received with an enthusiasm not usually associated with mathematics.
Hilbert and Brouwer were the main players in a famous controversy in the editorial board of Mathematische Annalen, the most famous mathematical journal of the time. Hilbert, the editor-in-chief, eventually fired Brouwer from the editorial board. There are different accounts regarding the nature of the disagreement. Some scholars have claimed that Brouwer wanted to impose his intuitionistic proof standards. Other scholars strongly reject this story and claim that Hilbert wanted to remove Brouwer in an inappropriate way simply because he felt that Brouwer was becoming too powerful.
Remark: My colleague Ehud (Udi) Hrushovski has a different view on the end of the foundational crisis. According to Udi one reason was the success of the Zermelo-Fraenkel axiomatization (ZFC) for set theory which replaced Frege’s failed axioms and seemed immune against difficulties of the kind discovered by Russell. Another reason was the various positive results, some by Gödel himself, which brought the foundation of mathematics quite close to Hilbert’s dream. Hrushovski’s view is that Hilbert’s main interest was towards completeness and not towards a mathematical proof of the consistency of mathematics.
Update: For a technical discussions of Gödel’s completeness and compactness theorems, see this post by Terry Tao.