The Diagonalization Lemma — Demystified Hopefully
Saeed Salehi (University of Tabriz):
Slides
The diagonal lemma says that when a computable and injective Gödel coding # is available from the formulas to the closed terms of a fixed language, then for every formula F(x), with x as the only free variable, there exists a sentence S such that S ↔ F(#S) holds. Holding may mean that the above equivalence is true in the standard model of natural numbers (the semantic diagonal lemma) or may mean that the equivalence is provable in a sufficiently strong theory such as Robinson's Arithmetic (the syntactic diagonal lemma).
The so-called lemma, first proved by Gödel (1931) for a particular formula F(x), that of unprovability, and explicated by Carnap (1934) for every formula F, has a (couple of) very short but extremely tricky and easy-to-forget proof(s). The (classical) proof is mysterious and a kind
of magical (pulling a rabbit out of a hat), which adds to the confusion on and about the lemma. It can be even said that once this lemma has been mastered and grasped, then the proofs of the theorems of Gödel's first incompleteness, Tarski's undefinability of truth, and Rosser's (strengthening of Gödel's) incompleteness can be easily understood.
In this talk we will give some alternative proofs for the semantic form of this lemma and for its weak syntactic forms. We will see that the lemma is actually equivalent, in a sense, to the above mentioned theorems of Gödel, Tarski, and Rosser. These new results, we hope, will help us in demystifying this wonderful and prolific lemma; though its classic proof may remain in shadow, our new proofs will hopefully shed some light on the true nature of the diagonal lemma.
Video of the talk
References
· SAEED SALEHI, On the Diagonal Lemma of Gödel and Carnap, The
Bulletin of Symbolic Logic 26:1 (2020) 80—88.
· SAEED SALEHI, Tarski’s Undefinability Theorem and the Diagonal
Lemma, Logic Journal of the IGPL (forthcoming).