An introduction to Goedel's theorems

Preface......Page 7
1.1 Basic arithmetic......Page 9
1.2 Incompleteness......Page 11
1.3 More incompleteness......Page 13
1.5 The unprovability of consistency......Page 14
1.7 What\'s next?......Page 15
2.1 Effective computability, effective decidability......Page 17
2.2 Enumerable sets......Page 20
2.3 Effective enumerability......Page 23
3.1 Formalization as an ideal......Page 24
3.2 Formalized languages......Page 26
3.3 Axiomatized formal theories......Page 29
3.4 More definitions......Page 31
3.5 The effective enumerability of theorems......Page 32
3.6 Negation complete theories are decidable......Page 34
4.1 Three remarks on notation......Page 35
4.2 A remark about extensionality......Page 36
4.3 The language LA......Page 37
4.4 Expressing numerical properties and relations......Page 40
4.5 Capturing numerical properties and relations......Page 42
4.6 Expressing vs. capturing: keeping the distinction clear......Page 43
5.1 The idea of a `sufficiently strong\' theory......Page 45
5.2 An undecidability theorem......Page 46
5.3 An incompleteness theorem......Page 47
5.4 The truths of arithmetic can\'t be axiomatized......Page 48
Interlude: taking stock, looking ahead......Page 50
6.1 BA -- Baby Arithmetic......Page 53
6.2 BA is complete......Page 55
6.3 Q -- Robinson Arithmetic......Page 57
6.4 Q is not complete......Page 58
6.5 Why Q is interesting......Page 59
7 What Q can prove......Page 60
7.1 Systems of logic......Page 61
7.2 Capturing less-than-or-equal-to in Q......Page 62
7.4 Ten simple facts about what Q can prove......Page 63
7.5 Defining the 0, 1 and 1 wffs......Page 66
7.6 Some easy results......Page 68
7.7 Q is 1-complete......Page 69
7.8 Intriguing corollaries......Page 71
8.1 Induction and the Induction Schema......Page 73
8.2 Arguing using 0 induction......Page 75
8.3 PA -- First-order Peano Arithmetic......Page 78
8.4 Summary overview of PA......Page 79
8.5 A very brief aside: Presburger Arithmetic......Page 80
8.6 Is PA consistent?......Page 81
9.1 Introducing the primitive recursive functions......Page 84
9.2 Defining the p.r. functions more carefully......Page 86
9.3 An aside about extensionality......Page 88
9.4 The p.r. functions are computable......Page 89
9.5 Not all computable numerical functions are p.r.......Page 91
9.6 Defining p.r. properties and relations......Page 93
9.7 Building p.r. functions and relations......Page 94
9.8 Some more examples......Page 97
10.1 Three ways of capturing a function......Page 100
10.2 Relating our definitions......Page 103
10.3 The idea of p.r. adequacy......Page 104
11.1 More definitions......Page 107
11.2 Q can capture all 1 functions......Page 108
11.3 LA can express all p.r. functions: starting the proof......Page 110
11.4 The idea of a -function......Page 111
11.5 LA can express all p.r. functions: finishing the proof......Page 114
11.6 The p.r. functions are 1......Page 115
11.7 The adequacy theorem......Page 117
11.8 Canonically capturing......Page 118
Interlude: a very little about Principia......Page 119
Bibliography......Page 125