Gödel's incompleteness theorem
Created | Updated Jan 28, 2002
Kurt Gödel, brilliant mathematician
and part-time madman
Reality is frequently inaccurate, because Kurt Gödel's law is definitive. This peculiar logician and genius set out to find the answer to the question: 'can every logical proposition be proven?' And in a dramatic break with tradition, he actually found it. The amazing truth is: no, there is no way to prove every proposition.
The implications
If there is no systematic way to solve every possible logical problem, there must be an infinite number of questions that can never be solved - ever. That is, if you assume the world is a deterministic
*
place.
Are you sure?
Quite. The proof of Gödel's theory may be intricate, beautiful, even slightly mystical - it is also strictly logic. The actual proof itself involves some heavy combinatory logic, which is a little beyond the scope of this article. Interested readers may find To Mock a Mocking Bird
*
as well as Gödel, Escher, Bach
*
contain excellent, if technical, elaborations.
Here I will attempt to briefly explain his proof, so you too can evoke glazed looks in your friends and colleagues
If you are more in sight-seeing mode, you can skip to the
intuitive proof, if you so wish.. If not, print the contents of this article, or at least store them somewhere for your relaxed pondering pleasure!
Buckle your brainbelt and don't panic!
Let us first re-formulate our question: 'can every logical proposition be proven?'. This is really saying: 'what function can indicate whether a statement belongs to the collection of true ones or not?'
Because functions often deal in numbers, it would be convenient if we had a way of expressing a statement in numbers. The so-called 'Gödel numbers' are just that: they are a direct translation from statement to numbers. Incidentally, 42 in Gödelian means ') T' or 'closing parenthesis true'. No, I will not debate it's deeper meaning here!
Now we can make a more comfortable
*
'truth-telling' function, which must tell us if a given Gödel number represents a true statement or a lie.
This sought-after function would have to act similarly to the one that, say, determines the parity
*
of a number.
In fact all such collection-calculating functions have something in common; for every one of them, you can make a very interesting statement. What makes it so special, is that if it's a true statement, it's Gödel number belongs to that particular collection. This statement is called a Gödel sentence
*
(are we beginning to see a pattern here?
Another way to put it is that every calculable
*
collection contains a 'true' Gödel number.
For instance, if we take the collection of even numbers, there must be an even number that is also a true statement. Remember, an even number can be a Gödel number, and so can be made to point to a statement like '2 + 1 = 3'!!
So IF there really is a calculable collection of ALL true statements, there must also be a Gödel sentence for it. But of course there should also be a Gödel sentence for the collection of all false statements ('lies')!
And now the conclusion
Now think about this: can there be a statement which, if it is true, belongs to the collection of untrue Gödel-numbers?
If you think that sounds terribly weird, it is. Remember, if a collection can be determined (like we want the collection of false Gödel numbers to be), it will have to have a Gödel sentence. This means there must be a statement like '2 + 1 = 3'
*
that belongs to it. '2 + 1 = 3' is true. So it should belong to the collection involved, in this case the collection of lies. This is clearly impossible, since a statement can not both be true and have a Gödel number that translates to a false statement.
Say what?
Don't panic! Gödel himself got so upset about all of this (or possibly the little gnomes that lived in his pipe), he starved himself to death in fear of being poisoned.
A more right-hemisphere explanation of Gödel's proof goes something like this:
Suppose I say 'the testimony of Bill Clinton is truthful'. Suppose you have god-like powers and are able to find out the truth of any sentence. You might now say: 'no, what you told me about Bill is a lie!'
If Kurt Gödel were to wander by and overhear this conversation, he might ask you to judge this: 'this sentence is a lie.'
What would you do? If you called Gödel a liar
To summarize: in any powerful system (language, mathematics, ..) you can invent a paradox, which undermines the scope of that system.
