Gödel's Incompleteness Theorem (1931)

Kurt Gödel (1906 - 1978) was a talented Austrian mathematician specializing in logic who emigrated to the United States to escape Nazi rule. He spent many years at the Institute for Advanced Learning at Princeton, where he was a very good friend of Albert Einstein. He died in old age by gradually starving himself.

To give a more complete explanation and background to Gödel's theorem it is necessary to discuss what inspired it. In 1911, Bertrand Russell and Alfred North Whitehead completed a monumental work, Principia Mathematica, which sought to provide a solid foundation to all mathematics. The ancient Greek geometer Euclid provided a foundation for the study of geometry with The Elements, but there were modern concerns by the great German mathematician, David Hilbert, and others that our language might not be entirely consistent for this purpose.

An axiom is a mathematical statement or property considered to be self-evidently true, but yet cannot be proven. All attempts to form a mathematical system must begin from the ground up with a set of axioms. For example, Euclid wrote The Elements with a foundation of just five axioms. One of these is the axiom that exactly one (unique) line can be drawn through any two different points. This can't be proven, but no one doubts its veracity. Likewise, an axiom of our real number system is that addition is commutative; i. e., it doesn't matter in which order you add two numbers, you always get the same sum. Clearly, no one doubts this axiom either, but it cannot be proven for all real numbers.

Hilbert and others expressed concern that an axiomatic basis for a mathematical system might contain subtle inconsistencies. In other words, one axiom might conflict with another in a way that the conflict could manifest itself in a theorem such that the theorem could be proven both true and false, a paradox. In a very famous address to the International Congress of Mathematicians in Paris, 1900, Hilbert laid out twenty-three problems he considered to be of the highest priority. Number two on his list was "The compatibility of the arithmetical axioms." Here is an excerpt from his address on the topic:

But above all I wish to designate the following as the most important among the numerous questions which can be asked with regard to the axioms: To prove that they are not contradictory, that is, that a definite number of logical steps based upon them can never lead to contradictory results.

Thus Russell and Whitehead took up this challenge. Their solution was to recast the foundations of mathematics in the terse language of logic and sets. By driving out language and using just symbols their intention was to create an entirely consistent system for mathematics without the risk of subtle ambiguity that the words of a spoken language might entail. Attaching meaning to these symbols was called, by Hilbert and others, "meta-mathematics." Here is an illustrative example I have come up with:

Mathematics: ( (p --> q) ^ (q --> r) ) --> (p --> r).

Meta-mathematics: The above proposition can be called the Transitive Law, one of three which apply to equivalence relations. For example, if A = B and B = C, then we can say that A = C.

By using symbols and strict rules Russell and Whitehead were able to generate "formulas," theorems stated in a form resembling mathematical equations or computations. With their tight control of the language Principia Mathematica was regarded as the purest expression of mathematical formalism. In fact, it was believed that Russell and Whitehead had put in place a system by which new mathematical theorems could be generated as automatically as multiplying new sets of numbers together. In our times, one could imagine computers generating nearly countless numbers of mathematical theorems.

But there was a monster growling in the closet.

Logic is the mathematical process of turning statements into symbolic expressions or equations in order to determine whether these statements are true or false. We adopt the Law of the Excluded Middle, which means that logically, any statement, if not true, must be false. There is no middle ground of both true and false, or neither true nor false. But logic has its Achilles Heel: self-reference. The Law of the Excluded Middle can fail when a statement refers back to itself, producing a paradox. The simplest paradox takes the logical form of this statement:

This statement is false.

The statement cannot be true, because then it would be false. But if it was false, then it must be a true statement. Such a bizarre logical problem can arise through self-reference, or circular reasoning. The statement refers to itself to prove an assertion about itself.

It was thought that Russell and Whitehead had avoided all possibility of self-reference, and thus had a logical foundation for mathematics that was entirely consistent, i. e., no contradictory results.

While studying Principia, Gödel had a brilliant insight. In looking at the mass of logical statements he began to imagine that each logical symbol could be assigned a unique number--we call them Gödel numbers--and that each logical statement could be represented by a unique number formed by multiplying the Gödel numbers therein. Thus he saw that Principia was a book about numbers which used numbers to prove itself. It was a subtle form of self-reference, which meant that there might be trouble. Gödel then set about to see if he could find an example of inconsistency. But he end up going much deeper than this.

Gödel found a theorem that could be stated within the confines of Russell & Whitehead's system that was impossible to prove within that system. Outside of Russell & Whitehead's system, using meta-mathematics, he was able to prove a statement similar to "This formula is unprovable by the rules of Principia Mathematica." But this statement could exist within the framework of Principia Mathematica, thus creating a paradox in their system akin to the paradox, "This statement is false." Gödel numbers played a role in this.

Thus, Russell & Whitehead's system had at least one undecidable proposition and thus was incomplete. This is why Gödel's theorem is often called the "Incompleteness Theorem."

For reasons too deep to consider here, the fact that Gödel found a theorem unprovable under the framework of Principia established, oddly enough, the consistency of Principia, meeting Hilbert's criteria. For if Principia was an inconsistent system then any theorem stated within the framework could be proven but would contain paradoxes.

Gödel hammered the final nail home by being able to demonstrate that any consistent system of axioms would contain theorems which could not be proven. Even if new axioms were created to handle these situations this would, of necessity, create new theorems which could not be proven. There's just no way to beat the system. Thus he not only demolished the basis for Russell and Whitehead's work--that all mathematical theorems can be proven with a consistent set of axioms--but he also showed that no such system could be created.

Gödel published his paper, "On Formally Undecidable Propositions of Principia Mathematica and Related Systems," in 1931. Here, then, is a summary of his results:

Any consistent axiomatic system of mathematics will contain theorems which cannot be proven.

If all the theorems of an axiomatic system can be proven then the system is inconsistent, and thus has theorems which can be proven both true and false.

The ramifications of Gödel's result are profound. For one, it means that mathematics cannot attain the total purity of language which mathematicians both desired and believed to exist. In 1950 the British computer pioneer, Alan Turing, showed how this translates to computing. Since any computer operates off a set of instructions, not unlike axioms, there will inevitably be problems (not unlike theorems) which computers will be unable to compute. Any logical system, if open-ended like the numbers and tied to numbers, will contain problems of the sort Gödel outlined.

In the early 1960's an important theorem was demonstrated to be unprovable, just as Gödel predicted. There are many theorems in mathematics which have defied all attempts at proof, so one wonders if some of these are further examples of the incompleteness of our axiomatic systems.

Because of its total impact on all of mathematics Gödel's theorem is considered by most mathematicians to be the most important mathematical result of the 20th century.



Gödel's Proof, Nagel & Newmann, New York University Press, 2001.

On Formally Undecidable Propositions of Principia Mathematica and Related Systems, Kurt Gödel, Dover, New York, 1992.

David Hilbert's 1900 Address: http://aleph0.clarku.edu/~djoyce/hilbert/problems.html

To contact the author by e-mail click on this link: Jon Davidson