Haim Gaifman

This short sketch of Gödel’s incompleteness proof shows how it arises naturally from Cantor’s diagonalization method [1891]. It renders the proof of the so–called fixed point theorem transparent. We also point out various historical details and make some observations on circularity and some comparisons with natural language. The sketch does not include the messy details of the arithmetization of the language, but the motive for arithmetization and what it should accomplish are made obvious. We suggest this as a way to teach the incompleteness results to students that have had a basic course in logic, which is more efficient than the standard textbooks. For the sake of self–containment Cantor’s original diagonalization is included. A broader and more technical perspective on diagonalization is given in [Gaifman 2005]. Motivated partly by didactic considerations, the present paper presents things somewhat differently. It also includes various points concerning natural language and circularity that appear only here

The semantic paradoxes, whose paradigm is the Liar, played a crucial role at a crucial juncture in the development of modern logic. In his 1908 seminal paper, Russell outlined a system, soon to become that of the Principia Mathematicae, whose main goal was the solution of the logical paradoxes, both semantic and settheoretic. Russell did not distinguish between the two and his theory of types was designed to solve both kinds in the same uniform way. Set theoreticians, however, were content to treat only the set-theoretic paradoxes, putting aside the semantic ones as a non-mathematical concern. This separation was explicitly proposed, eighteen years after Russell’s paper, by Ramsey, though he, like Russell, advocated a system that addresses both kinds. Since then, the semantic paradoxes have been viewed within the perspective of the theory of truth, where they have occupied a respectable niche, but one of rather specialized interest.