Gödel's Incompleteness Theorems

Around the beginning of the twentieth century, several paradoxes, such as Russell's paradox, Cantor's Paradox, and the Burali-Forti Paradox were discovered. These paradoxes were quite troubling because they related to the foundations of mathematics; if paradoxes could be found here, it meant that mathematics stood on a rather shaky foundation indeed.

Formal systems (also known as axiom systems) had been quite successful in specific areas of mathematics (see, for example, Peano postulates); perhaps extending them to an axiom system sufficient for all mathematical work might resolve the problem of these paradoxes. This was the solution proposed by David Hilbert, who also proposed attempting to prove that the resulting system is complete (in other words, all true mathematical statements would be able to be proved) and consistent (in other words, no false mathematical statements would be able to be proved, resulting in a contradiction). A significant step towards axiomatizing mathematics was Principia Mathematica, by Alfred North Whitehead and Bertrand Russell, published in three volumes between 1910 and 1913. Meanwhile, others worked on the axiomatization of other areas of mathematics such as set theory. The question of whether a formal system at least rich enough to embrace all of arithmetic could be proven to be complete and consistent was still unresolved, but there was reason to hope that, at least in principle, it could be.

This was the question that Kurt Gödel tackled in his 1931 paper Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I (translated into English, On Formally Undecidable Statements of the Principia Mathematica and Related Systems I). This paper would be one of the greatest mathematical works of the twentieth century. His conclusions, which jolted the mathematical world, were that, first, it is impossible to prove that a system comprehensive enough to include all of arithmetic is consistent (unless the proof uses rules of inference more powerful than those used in the original system, but that would still leave unresolved the issue of whether this more powerful system is itself consistent) and, second, that any system comprehensive enough to include all of arithmetic is incomplete. There must be true arithmetical statements that cannot be derived.

The idea that there are true statements that cannot be proved should not, in itself, be surprising. For example, consider a system that consists of the axioms of arithmetic excluding the axiom of mathematical induction. In this system, it would be impossible to prove the following statement (among others), even though it is true:

However, by adding the axiom of mathematical induction to our system, we can easily prove the above statement. You might intuitively think that, if we added enough axioms, it might be possible to prove all true statements, but Gödel showed that this was not the case.

Gödel's proof is too complex to fully describe here, but a general outline of its main ideas follows. The first challenge is to find a statement that is true but cannot be proven. One possible idea might be to investigate the statements used in vicious circle paradoxes, such as the liar paradox, "This statement is false." This statement won't work though, because it's neither true nor false. What if we modify the statement to read "This statement cannot be proven to be true"? Is it true or false? If it were false, then we could prove it to be true, which means it would be true. That means that the statement must be true; but, if it were true, it cannot be proven. So, "This statement cannot be proven to be true" is a true statement that cannot be proved.

However, this statement is written in the English language, not in the language of an axiom system. The next challenge is to so express this idea. To do this, Gödel translated statements about arithmetic into numbers themselves, referred to as Gödel numbers. There are a few ways of doing this. One way of doing so is to assign a unique number to each symbol in the formal language. For example, "=" might be assigned the number 5, and "0" might be assigned the number 6. To express each formula as a unique integer, Gödel took advantage of the fundamental theorem of arithmetic, which states that a number can be factored into a product of primes in only one way. The Gödel number of a statement was created by taking 2 to the power of the number representing the first symbol, multiplying that by 3 to the power of the number representing the second symbol, multiplying that by 5 to the power of the number representing the third symbol, ..., multiplying that by p_n to the power of the number representing the nth symbol (where p_n is the nth prime number). For example, "0=0" would be encoded as 2⁶ · 3⁵ · 5⁶ = 243,000,000. (These numbers get large very quickly).

Now, if each theorem can be encoded as a Gödel number, each proof of that theorem can also be encoded as a Gödel number. Now, each theorem must have a proof. So, we could define a function that relates a theorem to its proof. Now, while the actual process of doing so is rather complicated, it is possible, using this function, to define a statement, G that, in the language of the formal system, states, "The statement G is not provable." Just as above, G must be true, but that means that it cannot be proved.