Gödel's incompleteness theorem

2 Conversations


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
, then his sentence would make perfect sense. But the one thing a liar can't do, is make sense! So is he telling the truth? No can do, because he claims to be telling a lie, which he is unable to!



To summarize: in any powerful system (language, mathematics, ..) you can invent a paradox, which undermines the scope of that system.


Bookmark on your Personal Space


Entry

A256439

Infinite Improbability Drive

Infinite Improbability Drive

Read a random Edited Entry


Written and Edited by

Disclaimer

h2g2 is created by h2g2's users, who are members of the public. The views expressed are theirs and unless specifically stated are not those of the Not Panicking Ltd. Unlike Edited Entries, Entries have not been checked by an Editor. If you consider any Entry to be in breach of the site's House Rules, please register a complaint. For any other comments, please visit the Feedback page.

Write an Entry

"The Hitchhiker's Guide to the Galaxy is a wholly remarkable book. It has been compiled and recompiled many times and under many different editorships. It contains contributions from countless numbers of travellers and researchers."

Write an entry
Read more