Table of Contents
Preface ix
Introduction 1
1 The Problem of Consistency 1
2 Completeness and Decidability 3
3 The Historical Setting 5
1 Consistency, Decidability, Completeness for the Arithmetic of Order with Successor 10
1 Examples of simple Consistency Proofs 10
2 The Arithmetic C1 of Older with Successor 14
3 Reductions and Quantifier Elimination for C1 16
4 The Main Theorems of the Arithmetic C1 31
2 Consistency, Decidability, Completeness for the Arithmetic of Addition and Order 34
1 The Arithmetic C2 of Addition and Order 34
2 Reductions and Quantifier Elimination for C2* 41
3 The Main Theorems for the Arithmetic C2* and C2 50
4 C2 and Induction 53
Introduction to Chapters 3 - 9 56
3 Antinomies, Pseudomenos, and their Analysis 58
1 Antinomies 58
2 More Examples and the Liar 59
3 Analysis: The Undefinability of Truth 61
4 Analysis: Incompleteness 67
4 Undefinability and Incompleteness, General Theory 71
1 A Combinatorial Frame 71
2 Basic Notions on Definability and Representability 73
3 Undefinability 80
4 Incompleteness 84
5 Incompleteness, continued 90
6 Set Theory - an Example 94
5 Elementary and Primitive Recursive Functions 99
1 Basic Constructions 100
2 Simple Functions 107
3 Elementary Functions 111
4 Primitive Recursive Functions 117
5 Elementary Arithmetization 120
6 Simple Arithmetization 125
6 Recursive Relations and-Recursive Functions 132
1 Bounded Arithmetical Relations 133
2 Projections 137
3 P-closed Classes and their Core 140
4 Recursively Enumerable Relations 143
5 Recursive Relations and Recursive Functions 145
6 Recursivity and Minimization 148
7 The Arithmetization of Syntax 155
8 Consequences of Arithmetization 165
1 Recursively Enumerable Axiom Systems 166
2 Undefinability and Incompleteness 169
3 Radical Undecidability 174
4 Uniformization 178
9 Axioms for Arithmetic 190
1 The Arithmetic PC 191
2 The Arithmetic PB 196
3 Representability of Recursive Relations I 202
4 Representability of Recursive Relations II 205
5 Formal Definability of Recursive Relations 210
6 The Arithmetic PQ 212
7 Application: The Undecidability of Elementary Logic 216
10 Peano Arithmetic PA and its Expansion PR 219
1 Development of Basic Arithmetic 222
2 Extensions by Recursive Terms 231
3 A First Look at PR 240
11 Unprovability of Consistency 255
1 Introduction: Gödel's Theorem and Provability Conditions 255
Plan of the Remaining Sections of this Chapter 259
2 Free Variable Formalization of Syntax 262
PR-Terms for Terms 262
PR-Terms for Formulas 263
PR-Terms for Deductions and the Proof Predicate 266
3 Internalization 271
The Internal Copy 271
Internalization and Codification 274
Internalization of Constants 277
Internal Forms 278
4 Sentences Which Imply Their Provability 283
Epilogue 292
Index of concepts and names 296
Index of symbolic notations 299
