The Diagonal Lemma and the Gödel-Tarski Theorem

  • Thread starter nomadreid
  • Start date
  • Tags
    Theorem
This distinction is important in understanding the diagonal lemma and its applications in proving the Gödel-Tarski Theorem. In summary, the diagonal lemma is a powerful tool used in mathematical logic to prove the Gödel-Tarski Theorem and other theorems. It involves defining a 2-place relation and using it to construct a formula, which is then used to define another formula. This construction highlights the difference between a particular sentence and a formula applied to the code of that sentence, which is crucial in understanding the diagonal lemma and its applications.
  • #1
nomadreid
Gold Member
1,704
220
The diagonal lemma (which can be used to prove the Gödel-Tarski Theorem, among others) apparently goes, in a nutshell,

suppose you have a one-place formula A(.) with domain the set of codes of sentences.
I use quotation marks in this way : "M" is the code of M.
Define the 2-place relation sub:
If x ="f(.)", then sub(x,x) = "f(x)"
Define B(x) as A(sub (x,x))
Define S as B("B(x)")
retracing, S is true iff A("S") is.

Nice. What I do not understand is that the proof notes that S and A("S") are equivalent but not the same. It appears to me from the construction that they are the same. What am I missing?
Thanks.
 
Physics news on Phys.org
  • #2
The key thing to note here is that S and A("S") are different expressions, even though they may have the same truth value. S is a particular sentence, while A("S") is a formula applied to the code of S. This means that S and A("S") are syntactically different, even if they are semantically equivalent.
 

Related to The Diagonal Lemma and the Gödel-Tarski Theorem

1. What is the Diagonal Lemma?

The Diagonal Lemma, also known as the Diagonalization Lemma, is a fundamental result in mathematical logic that was first proved by logician Kurt Gödel in 1931. It states that for any consistent and sufficiently expressive formal system, there exists a statement that is true but unprovable within that system. This result has important implications for the foundations of mathematics and computability theory.

2. What is the Gödel-Tarski Theorem?

The Gödel-Tarski Theorem, also known as the Incompleteness Theorem, is a result that was jointly proved by Kurt Gödel and Alfred Tarski in 1936. It states that any formal system that is powerful enough to capture basic arithmetic cannot prove its own consistency. This theorem has significant implications for the limits of mathematical knowledge and the foundations of logic.

3. How are the Diagonal Lemma and the Gödel-Tarski Theorem related?

The Diagonal Lemma is a key component in the proof of the Gödel-Tarski Theorem. In fact, the first step in Gödel's proof of the Incompleteness Theorem is to use the Diagonal Lemma to construct a statement that is true but unprovable in the formal system under consideration. This statement is known as the Gödel sentence, and its existence demonstrates the incompleteness of the system.

4. Can the Diagonal Lemma and the Gödel-Tarski Theorem be applied to all formal systems?

No, the Diagonal Lemma and the Gödel-Tarski Theorem only apply to formal systems that are consistent and sufficiently expressive. This means that there must be a way to express basic arithmetic within the system, and that the system cannot prove both a statement and its negation. If these conditions are not met, then the results do not hold.

5. What are the practical implications of the Diagonal Lemma and the Gödel-Tarski Theorem?

The Diagonal Lemma and the Gödel-Tarski Theorem have significant implications for the foundations of mathematics and logic. They demonstrate the inherent limitations of any formal system and the impossibility of creating a complete and consistent axiom system. These results also have practical applications in computer science and artificial intelligence, as they provide insight into the types of problems that computers cannot solve.

Similar threads

A Karhunen–Loève theorem expansion random variables
    • Set Theory, Logic, Probability, Statistics
Replies
1
Views
651
I On sub and super solutions: Teschl and others
    • Differential Equations
Replies
5
Views
984
MHB Algorithm to answer existential questions - Reduction
    • Set Theory, Logic, Probability, Statistics
Replies
1
Views
1K
Q.E.D.Undecidability of Q: Proving Godel's First Incompleteness Theorem
    • Set Theory, Logic, Probability, Statistics
Replies
1
Views
1K
Decoding Gödel Numbers for Sequences: A Constructive Approach
    • Set Theory, Logic, Probability, Statistics
Replies
2
Views
1K
A confusion about Godel theorem and real numbers
    • Set Theory, Logic, Probability, Statistics
Replies
7
Views
2K
I Are Time-Travel and Logical Paradoxes Connected?
    • Set Theory, Logic, Probability, Statistics
Replies
5
Views
1K
I Question Regarding Binary PR Predicates
    • Set Theory, Logic, Probability, Statistics
Replies
2
Views
1K
Proof of Godel's 1st Theorem missing ω-consistency requirement. What's wrong?
    • Set Theory, Logic, Probability, Statistics
Replies
2
Views
2K
Help me Prove that such a set does NOT exist
    • Calculus and Beyond Homework Help
Replies
1
Views
1K

Hot Threads

Recent Insights

Back
Top