Diagonalization Lemma

Mathematical Logic · Axiom Academy

The fixed-point theorem enabling self-reference in formal arithmetic Mathematical Logic • Unit 5 - Gödel's Theorems 1. The Liar Paradox and Self-Reference Before formalizing self-reference, let's recall the classic liar paradox: If the sentence is true, then it must be false (as it claims). But if it's false, then the claim is incorrect, making it true. This creates a paradox. The Diagonalization Lemma provides a rigorous, non-paradoxical way to construct self-referential statements in PA. 2. The Diagonal Lemma (Fixed-Point Theorem) The Diagonal Lemma is one of the most important technical results in mathematical logic. Diagonal Lemma (Fixed-Point Theorem) For any formula with one free variable, there exists a sentence (with no free variables) such that: In other words, is a fixed point of : the sentence is provably equivalent to the statement " applied to the Gödel number of ." 3. Gödel Numbering: The Foundation The Diagonal Lemma relies on Gödel numbering , which assigns a unique natural number to every formula and proof in PA. denotes the Gödel number (code) of expression The key technical ingredient is a substitution function that can be represented in PA. Substitution Function sub(m, n) Let be the Gödel number of a formula with one free variable . Then is the Gödel number of the formula obtained by substituting the numeral for the free variable in . 5. Construction of the Fixed Point Now we construct the self-referential sentence for any given formula .

This is the written version of the interactive lesson above. See the full Mathematical Logic course.