The Incompleteness Theorem

The Incompleteness Theorem

In 1931 and while still in Vienna, Gödel published his famous incompleteness theorems in "Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme" (called in English "On formally undecidable propositions of Principia Mathematica and related systems"). In that article, he proved for any computable axiomatic system that is powerful enough to describe the arithmetic of the natural numbers (e.g. the Peano axioms or ZFC), that:

If the system is consistent, it cannot be complete.

The consistency of the axioms cannot be proven within the system.

These theorems ended a half-century of attempts, beginning with the work of Frege and culminating in Principia Mathematica and Hilbert's formalism, to find a set of axioms sufficient for all mathematics. The incompleteness theorems also imply that not all mathematical questions are computable.

In hindsight, the basic idea at the heart of the incompleteness theorem is rather simple. Gödel essentially constructed a formula that claims that it is unprovable in a given formal system. If it were provable, it would be false, which contradicts the idea that in a consistent system, provable statements are always true. Thus there will always be at least one true but unprovable statement. That is, for any computably enumerable set of axioms for arithmetic (that is, a set that can in principle be printed out by an idealized computer with unlimited resources), there is a formula that obtains in arithmetic, but which is not provable in that system. To make this precise, however, Gödel needed to solve several technical issues, such as encoding statements, proofs, and the very concept of provability into the natural numbers. He did this using a process known as Gödel numbering.