Tuesday, April 22, 2008

Non completeness

This statement is not provable.

Let 's call the above statement S. So what S says is that

S is not provable

If this statement is false (meaning S is false) then the opposite statement must be true. The opposite statement is

S is provable

and it must be true. But wait a minute. If S is provable, meaning that there exists a proof of its truth, then S is true. But wait a minute again. We started by assuming that S is false. A contradiction... This means that our initial assumption was wrong and therefore S is true. But what does this mean ? This means that what it says is true, S is actually not provable. So S is true but non-provable. This is non-completeness. Our inability to reach every existing truth. Simple, elegant and yet so deep.


adamo said...

Excellent explanation! But what triggered you to write about it?

chstath said...

I was certain that especially you would like it. I 'm glad I was right. Actually, this post is not an explanation. It is an (over)simplification of the actual proof that Goedel constructed. I 'm reading a book about Goedel 's theorems these days and I liked so much the part about the proof to the first theorem that I felt I had to share.

adamo said...

If it is Nagel's "Goedel's proof" then you should also read Goedel, Nagel, minds and machines.

chstath said...

I should also try and at last finish "Goedel, Escher, Bach"

Nick Palladinos said...

A good book is also "Infinity and the mind" by Rudy Rucker