Self-Reference and the Diagonal Lemma
Master the crucial technique of mathematical self-reference that makes Gödel's construction possible
Listen to summary
Self-Reference and the Diagonal Lemma
Introduction to Mathematical Self-Reference
One of the most profound insights in Gödel's incompleteness theorems is the ability to construct mathematical statements that refer to themselves. This might seem impossible at first – how can a mathematical formula talk about itself? The key lies in a technique called Gödel numbering, which allows us to encode mathematical statements as numbers, and then use arithmetic to manipulate these codes.
The Concept of Self-Reference
In everyday language, self-reference is common. Consider the sentence: "This sentence contains five words." The sentence refers to itself and makes a claim about its own properties. In mathematics, we want to construct formulas that can similarly make statements about themselves.
The crucial insight is that once we have a way to encode mathematical statements as numbers (Gödel numbering), we can write arithmetic statements about these numbers. Since the statements themselves are also encoded as numbers, we can potentially have statements that refer to their own Gödel numbers.
The Diagonal Lemma
The Diagonal Lemma is the technical tool that makes mathematical self-reference possible. It's named after Cantor's diagonal argument, which uses a similar self-referential construction.
Diagonal Lemma Statement: For any formula φ(x) with one free variable, there exists a sentence ψ such that:
ψ ↔ φ(⌜ψ⌝)
Here, ⌜ψ⌝ represents the Gödel number of the sentence ψ.
Understanding the Lemma
This might look abstract, so let's break it down:
- φ(x) is some property we want to express about Gödel numbers
- The lemma guarantees we can find a sentence ψ that says: "φ is true of my own Gödel number"
- In other words, ψ is equivalent to applying φ to ψ's own code number
Construction Sketch
The proof of the Diagonal Lemma uses a clever substitution technique:
-
Start with a formula template: Consider a formula σ(x,y) that says "the formula with Gödel number x, when we substitute the numeral for x into its free variable, satisfies property φ"
-
Apply substitution: Let n be the Gödel number of σ(x,y). Define ψ as σ(n,n) – that is, substitute n for both free variables in σ.
-
Self-reference emerges: The sentence ψ now says "the formula with Gödel number n, when we substitute n into it, satisfies φ." But ψ itself is exactly what we get when we substitute n into the formula with Gödel number n!
Example: The Liar Sentence
Consider φ(x) meaning "the sentence with Gödel number x is not provable." The Diagonal Lemma gives us a sentence G such that:
G ↔ "G is not provable"
This is essentially Gödel's incompleteness sentence! It says of itself that it cannot be proven.
Why This Matters
The Diagonal Lemma is the engine behind both of Gödel's incompleteness theorems:
- First theorem: Uses it to construct a true but unprovable sentence
- Second theorem: Uses it to construct a sentence that expresses the consistency of the system
Without this technique of mathematical self-reference, Gödel's revolutionary results would not be possible. The lemma shows that sufficiently powerful mathematical systems cannot avoid self-referential statements, leading to the fundamental limitations that Gödel discovered.
Technical Notes
The Diagonal Lemma works in any theory that can:
- Express basic arithmetic
- Prove certain elementary facts about Gödel numbering
- Handle substitution of numerals into formulas
This includes Peano arithmetic and stronger systems, making the incompleteness results very general.
Resources
Practice
Explain in your own words why the Diagonal Lemma is called 'diagonal.' What connection does it have to Cantor's diagonal argument? Provide a concrete analogy that helps illustrate the self-referential nature of the construction.
💡 Think about how Cantor's diagonal method creates a new object that differs from all objects in a list by referring to their position in that same list.
Which of the following best describes what the Diagonal Lemma guarantees? A) Every mathematical statement can be proven or disproven B) For any property φ, we can construct a statement that applies φ to its own Gödel number C) All self-referential statements lead to paradoxes D) Gödel numbering is unique for each formula
💡 Focus on the technical statement of the lemma: ψ ↔ φ(⌜ψ⌝)
Consider the property φ(x): 'the sentence with Gödel number x contains more than 10 symbols.' Using the Diagonal Lemma, describe what kind of self-referential sentence we could construct. What would this sentence be saying about itself?
💡 The resulting sentence would be equivalent to applying φ to its own Gödel number - so it would be making a claim about its own length.