Wednesday, April 16, 2008

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.


Jego said...

Great summary. I saw Hofstadter's GED at Booksale but it was missing the first 60 or so pages. I have a poorly scanned soft-copy which is a pain to read.

Jego said...

GED? I meant GEB -- Godel Escher Bach.

cvj said...

Thanks Jeg. It's good that understanding what Godel proved is easier than understanding how he went about proving it.

I have a copy of GEB but haven't gotten around to reading it in depth.

Brian Brotarlo said...

What the common tao has always known, Godel has taken to the scientific mainstream.

His method, known as Godel numbering, is a breakthrough.

CVJ, the great thing about mathematicians and philosophers is that unlike novelist, you do not have to read the original.

cvj said...

Hi Brian, i agree. Mathematical and philosophical (as well as scientific) concepts once introduced, break free of its author.

Kang Li Xin ace said...

we are a group of secondary school students working on a project related to Godel's first theorem. We found that your diagrams are of great help to us and would like to obtain your permission to use these diagrams for our project. Regarding figure 4, we are not clear what the assertion of the man means. Could you further explain on it?
Thank you.

cvj said...

Hi, yes please go ahead and use the diagrams. 'Assertion' is just a synonym for 'statement'. In diagram #4, it is drawn as free floating i.e. not connected to any axiom or theorem to show that its truth is not derived from any axiom or theorem. (In that way, the assertion is similar to an axiom, rather than a theorem.)

Kang Li Xin ace said...

Thank you for allowing us to use your diagrams! As our project would be submitted into the Singapore Mathematics Festival competition, we need to know your name for acknowledgement. Please feel free to drop us an email at if there are any inquiries. Please reply ASAP! Thanks:)

cvj said...

You're welcome. My name is Carlos Villamil Jugo. Good luck on the competition.