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.

**Bibliography**

*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*