What is the Incompleteness Theorem and how does it relate to Gödel's proof?

  • Thread starter heman
  • Start date
  • Tags
    Theorem
In summary, Gödel's Incompleteness Theorem states that there are statements in any formal system that cannot be proven or disproven within that system. This is demonstrated through Gödel's sneaky procedure involving a Universal Truth Machine and a sentence that the machine can never say is true. This shows that the Universal Truth Machine is not truly universal and there is always something it cannot answer.
  • #1
heman
361
0
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:

1. 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.
2. 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.
3. 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."
4. Now Gödel laughs his high laugh and asks UTM whether G is true or not.
5. 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.
6. 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").
7. "I know a truth that UTM can never utter," Gödel says. "I know that G is true. UTM is not truly universal."

Think about it - it grows on you ...

i really don't get it...i get lost understanding it..
 
Mathematics news on Phys.org
  • #2
heman said:
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:

1. 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.
2. 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.
3. 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."
4. Now Gödel laughs his high laugh and asks UTM whether G is true or not.
5. 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.
6. 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").
7. "I know a truth that UTM can never utter," Gödel says. "I know that G is true. UTM is not truly universal."

Think about it - it grows on you ...

i really don't get it...i get lost understanding it..

I see nothing in the statement that says that UTM can't opt to say nothing...

-Dan
 
  • #3
Then it wouldn't be a "Universal Truth Machine, capable of correctly answering any question at all".

It would instead be a partial truth machine that answers some questions correctly, and doesn't answer other the other questions.
 
  • #4
heman said:
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:

1. 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.
2. 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.
3. 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."
4. Now Gödel laughs his high laugh and asks UTM whether G is true or not.
5. 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.
6. 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").
7. "I know a truth that UTM can never utter," Gödel says. "I know that G is true. UTM is not truly universal."

Think about it - it grows on you ...

i really don't get it...i get lost understanding it..


Think about a liar's type paradox- If I write "The following sentence is false. The preceeding sentence is true" Now is that system of sentences consistent? Can you determine truth or falseness from them? No-it is a paradox. This is "essentially" what Godel did, although a Godel statement G is a paradox due to (dis)provability rather than truth/falseness.
 

FAQ: What is the Incompleteness Theorem and how does it relate to Gödel's proof?

What is the Incompleteness theorem?

The Incompleteness theorem, also known as Gödel's Incompleteness theorem, is a mathematical theorem that states that in any consistent and sufficiently powerful formal system, there will always be statements that cannot be proven or disproven within that system.

Who discovered the Incompleteness theorem?

The Incompleteness theorem was discovered by Austrian mathematician Kurt Gödel in 1931. It was one of his most significant contributions to the field of mathematical logic.

What are the implications of the Incompleteness theorem?

The Incompleteness theorem has significant implications for mathematics and philosophy. It shows that there are inherent limitations in any formal system, and that there will always be statements that are true but cannot be proven. This challenges the idea of a complete and consistent mathematical theory.

How is the Incompleteness theorem relevant to other fields of study?

The Incompleteness theorem has been applied to other disciplines, such as computer science and physics. It has also sparked discussions in philosophy and theology, as it raises questions about the limits of human knowledge and the nature of truth.

What is the difference between the first and second Incompleteness theorem?

The first Incompleteness theorem states that a formal system cannot prove its own consistency, while the second Incompleteness theorem states that a formal system cannot prove its own completeness. In other words, there will always be statements that cannot be proven or disproven within a formal system, and a formal system cannot prove that it is free from contradictions.

Similar threads

Replies
12
Views
7K
Replies
14
Views
2K
Replies
2
Views
3K
Replies
32
Views
4K
Replies
15
Views
5K
Back
Top