Kurt Godel is one of my heroes (along with Norman Borlaug – but that is for another blog entry). In the early 1900’s Bertrand Russell and Hilbert were trying to prove that for certain number systems that all true statements could be proven by axioms WITHIN the system (completeness). Tying up number systems with a nice neat, consistent, complete bow was very attractive to these mathematicians. Unfortunately, Godel came along and showed that for any computable axiomatic system that is powerful enough to describe the arithmetic of the natural numbers that:
1. If the system is consistent, it cannot be complete (If the system has only statements that can be proven, then there are others outside of the system that are true, but cannot be proven).
2. The consistency of the axioms cannot be proven with the system. (There may be external proofs that exist, but not ones within the system)
Some great explanations of the theorem and it’s philosophical ramifications are here:
There are many ramifications of Godel’s Incompleteness theory, but the one’s I particularly like are:
1) As Douglas Hofstadter says “Provability is a weaker notion than truth”. True but not provable!
2) Led to the birth of computer science and showed Alan Turing the way. The
“Godel-numbering” system took syntax and represented it by numbers, effectively showing the how to take 0’s and 1’s and represent logic (arithmetization of syntax). http://link.springer.com/chapter/10.1007%2F11780342_14#page-1
3) Established bounds on what is and what is not computable. Does the “human mind infinitely surpass the powers of any finite machine?” Godel believed that this was a highly likely conclusion based on his theorem.
Godel uses logic to play the beautiful music of mathematics and computer science by showing that Truth may not be Provable.