An introduction to Godel's theorems
Choice Reviews Online · 2013
The adequacy theorem Interlude: a very little about Principia 12 The arithmetization of syntax 12.1 Gödel numbering 12.2 Coding sequences 12.3 Prfseq is p.r. 12.4 Some cute notation 12.5 The idea of diagonalization 12.6 Gdl and diag and are p.r. 12.7 Proving that Prfseq is p.r. 13 PA is incomplete 13.1 Constructing G 13.2 Interpreting G 13.3 G is undecidable in PA: the semantic argument 13.4 'G is of Goldbach type' 13.5 G is unprovable in PA: the syntactic argument 13.6 ω-incompleteness, ω-inconsistency 13.7 ¬G is unprovable in PA: the syntactic argument 13.8 Putting things together 14 Gödel's First Theorem 14.1 Generalizing the semantic argument 14.2 Incompletability -a first look 14.3The First Theorem, at last 14.4 Rosser's improvement 14.5 Broadening the scope of the First Theorem 14.6 True Basic Arithmetic can't be axiomatized 14.7 Incompletability -another quick look 15 Using the Diagonalization Lemma 15.1 The provability predicate 15.2 Diagonalization again 15.3The Diagonalization Lemma: a special case 15.4The Diagonalization Lemma generalized 15.5 Incompleteness again 15.6 Capturing provability?15.7 Tarski's Theorem Interlude: about the First Theorem 16 The Second Incompleteness Theorem 16.1 Expressing the Incompleteness Theorem in PA iii Contents 16.2The Formalized First Theorem in PA 16.3The Second Theorem for PA 16.4 How surprising is the Second Theorem? 16.5 How interesting is the Second Theorem? 17 Exploring the Second Theorem 17.1 More notation 17.2The Hilbert-Bernays-Löb derivability conditions 17.3 G, Con, and 'Gödel sentences' 17.4 Löb's Theorem Bibliography 1 I plan, in due course, to put optional exercises (and answers!) on the book's website at www.godelbook.net.v Preface we go along, when needed?Similarly we will also need to call upon some ideas from the general theory of computation -for example, we will make use of both the notion of a 'primitive recursive function' and the more general notion of a 'recursive function'.Again, do we explain these together?Or do we give the explanations many chapters apart, when the respective notions first get used?I've mostly adopted the second policy, introducing new ideas as and when needed.This has its costs, but I think that there is a major compensating benefit, namely that the way the book is organized makes it clearer just what depends on what.It also reflects something of the historical order in which ideas emerged.