Roads to Infinity: The Mathematics of Truth and Proof

Cover page......Page 1
Title page......Page 4
Contents......Page 7
Preface......Page 9
1  The Diagonal Argument......Page 12
1.1  Counting and Countability......Page 13
1.2  Does One Infinite Size Fit All?......Page 15
1.3  Cantor\'s Diagonal Argument......Page 17
1.4  Transcendental Numbers......Page 21
1.5  Other Uncountability Proofs......Page 23
1.6  Rates of Growth......Page 25
1.7  The Cardinality of the Continuum......Page 27
1.8  Historical Background......Page 30
2  Ordinals......Page 40
2.1  Counting Past Infinity......Page 41
2.2  The Countable Ordinals......Page 44
2.3  The Axiom of Choice......Page 48
2.4  The Continuum Hypothesis......Page 51
2.5  Induction......Page 53
2.6  Cantor Normal Form......Page 57
2.7  Goodstein\'s Theorem......Page 58
2.8  Hercules and the Hydra......Page 62
2.9  Historical Background......Page 65
3  Computability and Proof......Page 78
3.1  Formal Systems......Page 79
3.2  Post\'s Approach to Incompleteness......Page 83
3.3  Godel\'s First Incompleteness Theorem......Page 86
3.4  Godel\'s Second Incompleteness Theorem......Page 91
3.5  Formalization of Computability......Page 93
3.6  The Halting Problem......Page 96
3.7  The Entscheidungsproblem......Page 98
3.8  Historical Background......Page 100
4  Logic......Page 108
4.1  Propositional Logic......Page 109
4.2  A Classical System......Page 111
4.3  A Cut-Free System for Propositional Logic......Page 113
4.4  Happy Endings......Page 116
4.5  Predicate Logic......Page 117
4.6  Completeness, Consistency, Happy Endings......Page 121
4.7  Historical Background......Page 123
5  Arithmetic......Page 130
5.1  How Might We Prove Consistency?......Page 131
5.2  Formal Arithmetic......Page 132
5.3  The Systems PA and PA_w......Page 133
5.4  Embedding PA in PA_w......Page 135
5.5  Cut Elimination in PA_w......Page 138
5.6  The Height of This Great Argument......Page 141
5.7  Roads to Infinity......Page 144
5.8  Historical Background......Page 146
6  Natural Unprovable Sentences......Page 150
6.1  A Generalized Goodstein Theorem......Page 151
6.2  Countable Ordinals via Natural Numbers......Page 152
6.3  From Generalized Goodstein to Well-Ordering......Page 155
6.4  Generalized and Ordinary Goodstein......Page 157
6.5  Provably Computable Functions......Page 158
6.6  Complete Disorder Is Impossible......Page 162
6.7  The Hardest Theorem in Graph Theory......Page 165
6.8  Historical Background......Page 168
7.1  Set Theory without Infinity......Page 176
7.2  Inaccessible Cardinals......Page 179
7.3  The Axiom of Determinacy......Page 181
7.4  Largeness Axioms for Arithmetic......Page 183
7.5  Large Cardinals and Finite Mathematics......Page 184
7.6  Historical Background......Page 188
Bibliography......Page 194
Index......Page 200