Gödel's Incompleteness Theorems Explained Simply
This article tries to explain in an easy to understand manner what Kurt Gödel's famous Incompleteness Theorems are all about. Kurt Gödel was an Austrian mathematician, logician and former child prodigy. He is considered one of the greatest logicians of the 20th century - for a reason.
Written by Claus Volko
Vienna, Austria, Europe
Contact: cdvolko (at) gmail (dot) com
The great mathematician David Hilbert stated at a congress at the beginning of the 20th century that the mathematical guild should endeavour to develop a logically consistent and complete axiom system, from which the entire mathematics can be deduced. Kurt Gödel's achievement was to show that it is impossible to realize this project, because a formal system cannot be logically consistent and at the same time complete (First Incompleteness Theorem).
Computer programs that solve decision problems are formal systems in the sense Gödel uses this term, and each and every formal system can be represented as a computer program. It might therefore be easier to understand Gödel's theorem when you think of a computer program that can process mathematical statements. This computer program can only deliver two possible outputs: "true" or "false". A logically consistent computer program is only allowed to output "true" if the mathematical statement that was given to it as a parameter is actually true and "false" only if the statement is actually false. If the mathematical statement is neither true nor false, but paradoxical, the logically consistent computer program is not allowed to output anything but rather end up in an infinite loop. But such a computer program would not be complete. A complete computer program always terminates, no matter what input you pass to it. Paradoxical statements should therefore also be qualified either as "true" or "false", although neither of the two alternatives applies. A complete computer program would therefore be forced, in some cases, to "lie", and would not be logically consistent.
An example of a paradoxical statement is: "This sentence is wrong." Assuming that the sentence is true, then it says about itself that it is false. So it can't be true. But assuming it's false, then follows, that it must be true. So it can't be wrong. Now, maybe you'd like to say that this is a linguistic statement, not a mathematical one, but in principle linguistic statements of this kind are also mathematical statements. Besides, Kurt Gödel also developed a formalism with which he was able to show that even in mathematics in the narrower sense such paradoxical statements can occur.
That would have been the first Incompleteness Theorem. The second says that a logically consistent system is not able to prove its own logical consistency. How do you prove this statement? Imagine a logically consistent computer program, i. e. one that, if it is not able to is to say whether the statement given to it as a parameter is true or false, is "honest" and draws the consequences, i. e. ends up in an infinite loop. How should such a program prove that it's "honest"? There is only one single possibility: to call itself with a parameter that makes the program end up in an infinite loop. However, the programme is not in a position to establish, that the instance it called has ended up in an infinite loop!
I hope that I have managed to explain Gödel's Incompleteness Theorems in a comprehensible way.
This essay was first published in MATHEMATIQ 30, in 2014.