What Gödel Proved

As explained by Nagel and Newman in their classic introduction to Kurt Gödel's landmark Incompleteness Theorem,

"...given any consistent set of arithmetical axioms, there are true arithmetical statements that cannot be derived from the set."

A Mathematical System is based on a limited set of axioms, i.e. assertions or statements that are assumed to be true without the need for any proof.

Figure 1: Axioms as Self-evident Truths
Using the internal rules of the Mathematical System, these axioms can then be used as basis to determine whether other assertions within such a system are true or false. Assertions that are proven to be true are accorded the status of Theorems.

Figure 2: Proving Assertions
These theorems can in turn be used (together with axioms or other theorems) to prove or disprove other assertions via the same method of Deductive Reasoning. One would therefore expect that such an ongoing process of generating assertions and proving them would result in a mathematical system that is able to extend itself by uncovering or constructing more mathematical truths while, at the same time, avoiding false assertions that would allow inconsistency(-ies) to creep into the System. Gödel found out that this is not the case.

Figure 3: Consistent and Complete Mathematical System
(Click on image to enlarge)
What Gödel proved in 1931 was that avoiding inconsistency within the system comes at the expense of completeness, i.e. the system's characteristic of being self-contained (in other words, 'complete in itself'). In a mathematical system based on axioms, there will always be assertions that are true, but whose truth cannot be proven from within the system on the basis of its axioms (or by way of the system's theorems). The truth of these assertions can be determined from outside the system [aka the 'Environment'], but not from within.

Figure 4: Consistent but Incomplete Mathematical System
(Click on image to enlarge)
Gödel's Incompleteness Theorem has a number of implications that have been explored at length, but i believe that one of the most significant, as explained by Douglas Hofstadter* is that:

"...provability is a weaker notion than truth** no matter what axiomatic system is involved."

A timely reminder to those who count on a given system to always come up with evidence to establish truth. There are situations when lack of evidence does not negate the truth of an assertion. Sometimes, you just have to step outside the system to see that this is indeed the case.

Update April-16-2008: Here's an excellent discussion on Douglas Hofstadter's book Gödel, Escher, Bach (also known by its shortname GEB).

Update April-25-2008: It is also important to emphasize what Gödel does not prove, i.e. Gödel does not prove the romantic and anti-rationalist notion that "There are true things which cannot be proved".

*in his book Gödel, Escher, Bach: an Eternal Golden Braid
**Emphasis mine.