Proof of Godel's incompleteness theorem for a layman

[immortal]

Well i am a layman not a mathematician so i found a link which gives the proof of the godel's incompleteness theorem from a layman's

perspective.

 

Here's the link

My link

 

I quote a paragraph from this website

"The proof of Gödel's Incompleteness Theorem is so simple, and so sneaky, that it is almost embarassing to relate. His basic procedure is as follows:

 

Someone introduces Gödel to a UTM, a machine that is supposed to be a Universal Truth Machine, capable of correctly answering any question at all.

Gödel asks for the program and the circuit design of the UTM. The program may be complicated, but it can only be finitely long. Call the program P(UTM) for Program of the Universal Truth Machine.

Smiling a little, Gödel writes out the following sentence: "The machine constructed on the basis of the program P(UTM) will never say that this sentence is true." Call this sentence G for Gödel. Note that G is equivalent to: "UTM will never say G is true."

Now Gödel laughs his high laugh and asks UTM whether G is true or not.

If UTM says G is true, then "UTM will never say G is true" is false. If "UTM will never say G is true" is false, then G is false (since G = "UTM will never say G is true"). So if UTM says G is true, then G is in fact false, and UTM has made a false statement. So UTM will never say that G is true, since UTM makes only true statements.

We have established that UTM will never say G is true. So "UTM will never say G is true" is in fact a true statement. So G is true (since G = "UTM will never say G is true").

"I know a truth that UTM can never utter," Gödel says. "I know that G is true. UTM is not truly universal."

 

 

If we put a little bit effort we can know or understand that G is true. Now if we apply the same argument on ourselves for example,

let G = " I will never say G is true". NOW if someone asks me whether G is true or not.

if I say that G is true then the statement which I made earlier is false and hence G is false. Therefore I know that G is true provided that I can not make false statements. What's the difference?

 

Even though both humans and machines can't say that G is true when we can not make false statements. We has humans know or understand that G is true but the machine does not know that G is true as there is no systematic procedure to obtain the result that G is true. So the way humans think and understand is very different from the machines. Don't you think that this argument opens up the world of plato. I know that this is metaphysics but when there is a strong and valid argument we may have to withdraw our hypothesis. Ofcourse an another argument would be that there may be other axiomatic systems which helps us to prove that G is true which we don't know yet

Edited October 29, 2010 by immortal

[Mr Skeptic]

If that is the case, would he not have proved that a UTM must be capable of lying or refusing to answer a question (as otherwise it could not be a UTM)?

[immortal]

If that is the case, would he not have proved that a UTM must be capable of lying or refusing to answer a question (as otherwise it could not be a UTM)?

 

Of course a UTM which speaks a lie is not a UTM. But Godel's incompleteness theorem proved that a UTM is not truly universal. Godel's incompleteness theorem did not speak anything about the correctness of UTM. We have to believe in the UTM that it always says correct answers. It is same as how you believe in a theory the more we fail to disprove the theory the more we are going to believe in that. In the same way we are going to believe in a axiomatic system if it continues to give consistent answers. As you know we are not going to completely eliminate the theory as we progress in science, we may just add something to the theory or the theory itself may become a sub-case for a whole new larger theory for example -the Newton's law of gravity is a sub-case in Einstein's general theory of relativity. If this was'nt the case then no one would have had belief in science.

 

Now if we apply the same argument of yours to humans, even though we are capable of making false statements (i.e. a lie) and say that "G is true" we know that we are lying and understand that G is true even though we know that it will become a lie if we say it provided that we can not make false statements. Now the question is can a UTM understand that when it says that "G is true" which makes 'G' a false statement, then G turns out to be a true statement provided that the UTM can not make false statements and we firmly believe in it.

 

 

So the statement "G is true" is a fundamental truth which we humans somehow can grasp. Godel proved that not all parts or systems in mathematics is complete.

Edited October 29, 2010 by immortal

[D H]

Have you stopped beating your wife? Answer yes or no only, please.

 

 

Godel's theorems are not so much about lying as undecidability. That somewhat simplistic description skips right over some of the key aspects of the theorems. Two things must come into play for Godel's theorems to apply.

 

 

"Have you stopped beating your wife?" is a loaded question. Godel showed that it is possible to construct loaded questions in any mathematical system that is as strong as Peano arithmetic. The basic problem is that Peano arithmetic has addition and multiplication. Get rid of multiplication and the problems are gone.

 

The correct response to "have you stopped beating your wife?" is "Neither." Requiring that the answer be either yes or no and nothing else is the law of the excluded middle / principal of bivalence. Some mathematicians reject the law of the excluded middle because it, along with multiplication, is at the heart of the undecidability issue.

 

Suppose you are asked to prove that there exists two irrational numbers α and β such that α^β is rational. This is easy with the law of the excluded middle. √2 is irrational. By the law of the excluded middle, √2^√2 is either rational or irrational. If it is rational, game over: We have found the requisite α and β. If it is irrational we have also proven the conjecture because [math]\left(\surd 2^{\surd 2}\right)^{\surd 2} = 2[/math]. This is an invalid proof to a constructivist. A constructivist would demand a proof that √2^√2 is irrational (which it is, thanks to the Gelfond-Schneider theorem).

[wright496]

This is an oversimplified proof. You seem to present the UTM as a thing that answers questions but then you hit it with a statement. I don't doubt the theorem because the original proof was good, but this proof isn't very convincing.