An Introduction To Goedel's Theorems

An Introduction to G¨odel’s Theorems Peter Smith Faculty of Philosophy University of Cambridge Version date: March 5, 2006 c Copyright: 2006 Peter Smith Not to be cited or quoted without permission The book’s website is at www.godelbook.net Contents Preface v 1 What G¨ odel’s Theorems say 1.1 Basic arithmetic 1.2 Incompleteness 1.3 More incompleteness 1.4 Some implications? 1.5 The unprovability of consistency 1.6 More implications? 1.7 What’s next? 1 1 3 5 6 6 7 7 2 Decidability and enumerability 2.1 Effective computability, effective decidability 2.2 Enumerable sets 2.3 Effective enumerability 9 9 12 15 3 Axiomatized formal theories 3.1 Formalization as an ideal 3.2 Formalized languages 3.3 Axiomatized formal theories 3.4 More definitions 3.5 The effective enumerability of theorems 3.6 Negation complete theories are decidable 16 16 18 21 23 24 26 4 Capturing numerical properties 4.1 Three remarks on notation 4.2 A remark about extensionality 4.3 The language LA 4.4 Expressing numerical properties and relations 4.5 Capturing numerical properties and relations 4.6 Expressing vs. capturing: keeping the distinction clear 27 27 28 29 32 34 35 5 Sufficiently strong arithmetics 5.1 The idea of a ‘sufficiently strong’ theory 5.2 An undecidability theorem 5.3 An incompleteness theorem 5.4 The truths of arithmetic can’t be axiomatized 37 37 38 39 40 i Contents Interlude: taking stock, looking ahead 42 6 Two 6.1 6.2 6.3 6.4 6.5 45 45 47 49 50 51 7 What Q can prove 7.1 Systems of logic 7.2 Capturing less-than-or-equal-to in Q 7.3 Adding ‘≤’ to LA 7.4 Ten simple facts about what Q can prove 7.5 Defining the ∆0 , Σ1 and Π1 wffs 7.6 Some easy results 7.7 Q is Σ1