On the role of diagonalization in Gödel's incompleteness and Tarski's theorems

Abstract

Three major theorems of arithmetics from early 1930s delineate the enterprise of formalization in mathematics: Gödel's First Incompleteness Theorem, Diagonalization Lemma and Tarski's Theorem. We begin the thesis with a statement and exposition of these theorems. Then we examine their proofs and observe the following structural stratification: The first layer consists in a certain purely syntactical mechanism which constructs self-referential sentences with arithmetical means. Gödel's own proof of his First Completeness Theorem is based on a specific use of this mechanism. Diagonalization Lemma is a generalization of the same mechanism and Tarski's theorem is a direct consequence, almost a corollary, of the Diagonalization Lemma. The actual chronology approximates this logical stratification too: Gödel's First is published in 1931, Diagonalization Lemma in 1934 and Tarski's Theorem in 1933. After completing the exposition of the theorems and their proofs we focus our attention mainly on the rst layer. There we observe that the mentioned self-referential mechanism is achieved using twice a method called diagonalization; abstract this mechanism to general languages; try to generalize a similar method to obtain a couple of other famous theorems like the non-capturability of provability in formal arithmetics; show the intrinsic a finity of Tarski's Theorem with the Liar Paradox and close the thesis discussing the mathematical relevance of the three major theorems.