Mathematical Logic with Special Reference to the Natural Numbers

Cover......Page 1
Title......Page 4
Untitled......Page 5
Dedication......Page 6
Contents......Page 8
Preface......Page 16
Introduction......Page 18
HISTORICAL REMARKS......Page 25
1.2 The signs and symbols......Page 27
1.3 The formulae......Page 29
1.5 Rules of formation......Page 30
1.6 Parentheses......Page 33
1.8 The rules of consequence......Page 35
1.9 Corresponding and related occurrences......Page 38
1.10 The λ-rules......Page 39
1.11 Definitions and abbreviations......Page 40
1.12 Omission of parentheses......Page 41
1.13 Formal systems......Page 44
1.14 Extensions of formal systems......Page 45
1.16 Negation......Page 46
HISTORICAL REMARKS TO CHAPTER 1......Page 47
EXAMPLES 1......Page 49
2.1 Definition of a propositional calculus......Page 51
2.2 Equivalence of propositional calculi......Page 52
2.4 Models of propositional calculi......Page 53
2.5 Deductions......Page 56
2.6 The classical propositional calculus......Page 59
2.7 Some properties of the remodelling and building schemes......Page 60
2.8 Deduction theorem......Page 65
2.9 Modus Ponens......Page 66
2.10 Regularity......Page 68
2.11 Duality......Page 69
2.12 Independence of symbols, axioms and rules......Page 70
2.13 Consistency and completeness of Pc......Page 72
2.14 Decidability......Page 74
2.15 Truth-tables......Page 75
2.16 Boolean Algebra......Page 78
2.17 Normal forms......Page 81
HISTORICAL REMARKS TO CHAPTER 2......Page 82
EXAMPLES 2......Page 85
3.1 Definition of a predicate calculus......Page 89
3.2 Models......Page 93
3.3 Predicative and impredicative predicate calculi......Page 94
3.4 The classical predicate calculus of the first order......Page 95
3.5 Properties of the system Ŧc......Page 96
3.6 Modus Ponens......Page 101
3.7 Regularity......Page 105
3.8 The system Ŧc......Page 107
3.9 Prenex normal forms......Page 108
3.10 H-disjunctions......Page 116
3.11 Validity and satisfaction......Page 125
3.12 Independence......Page 128
3.13 Consistency......Page 130
3.15 Theories......Page 131
3.16 Many-sorted predicate calculi......Page 132
3.17 Equality......Page 136
3.18 The predicate calculus with equality and functors......Page 140
3.19 Elimination of axiom schemes......Page 143
3.20 Special cases of the decision problem......Page 147
3.21 The reduction problem......Page 153
3.22 Method of semantic tableaux......Page 166
3.23 An application of the method of semantic tableaux......Page 171
3.24 Resolved Ŧc......Page 177
3.25 The system BŦc......Page 183
3.26 Set theory......Page 188
3.27 Ordinals......Page 192
3.28 Transfinite induction......Page 195
3.29 Cardinals......Page 197
3.30 Elimination of the ϵ-symbol......Page 201
3.31 Complete Boolean Algebras......Page 209
3.32 Truth-definitions for set theory......Page 210
3.33 Predicative and impredicative properties......Page 215
3.34 Topology......Page 216
HISTORICAL REMARKS TO CHAPTER 3......Page 218
EXAMPLES 3......Page 222
4.2 The Aₒₒ-rules of formation......Page 230
4.3. The Aₒₒ-rules of consequence......Page 232
4.4 Definition of Aₒₒ-truth......Page 235
4.6 Exclusiveness of Aₒₒ-truth and Aₒₒ-falsity......Page 236
4.7 Consistency of Aₒₒ with respect to Aₒₒ-truth......Page 241
4.8 Completeness and decidability of Aₒₒ with respect to Aₒₒ-truth......Page 242
4.9 Negation in the system Aₒₒ......Page 244
4.10 The system Bₒₒ  (the anti-Aₒₒ-system)......Page 245
HISTORICAL REMARKS TO CHAPTER 4......Page 246
EXAMPLES 4......Page 247
5.1 Calculable functions......Page 249
5.2 Primitive recursive functions......Page 250
5.3 Definitions of particular primitive recursive functions......Page 252
5.4 Characteristic functions......Page 260
5.5 Other schemes for generating calculable functions......Page 263
5.7 Simultaneous recursion......Page 264
5.8 Recursion with substitution in parameter......Page 265
5.9 Double recursion......Page 267
5.10 Simple nested recursion......Page 269
5.11 Alternative definitions of primitive recursive functions......Page 271
5.12 Existence of a calculable function which fails to be primitive recursive......Page 275
5.13 Enumeration of primitive recursive functions......Page 277
5.14 Definition of the proof-predicate for Aₒₒ......Page 282
5.15 The function Val......Page 287
HISTORICAL REMARKS TO CHAPTER 5......Page 290
EXAMPLES 5......Page 292
6.1 The system Aₒ......Page 295
6.2 Aₒ-truth......Page 296
6.3 Undefinability of Aₒ-falsity in Aₒ......Page 300
6.4 Enumeration of Aₒ-theorems......Page 301
EXAMPLES 6......Page 303
7.1 Turing machines and Church\'s Thesis......Page 305
7.2 Some simple tables......Page 317
7.3 Equivalence of partially calculable and partial recursive function......Page 321
7.4 The S-Ɵ-Ɵ\' proposition......Page 330
7.5 The undecidability of the classical predicate calculus Ŧc......Page 331
7.6 Various undecidability results......Page 333
7.7 Lattice points......Page 335
7.9 Simple sets......Page 340
7.10 Hypersimple sets......Page 341
7.11 Creative sets......Page 344
7.12 Productive sets......Page 347
7.13 Isomorphism of creative sets......Page 349
7.14 Fixed point proposition......Page 351
7.15 Completely productive sets......Page 352
7.16 Oracles......Page 353
7.17 Degrees ofunsolvability......Page 360
7.18 Structure of the upper semi-lattice of degrees of unsolvability......Page 363
7.19 Example of the priority method. Solution of Post\'s problem......Page 369
7.20 Complete degrees......Page 373
7.21 Sequences of degrees......Page 378
7.22 Non-recursively separable recursively enumerable sets......Page 381
7.23 Cohesive sets......Page 382
7.24 Maximal sets......Page 383
7.25 Minimal degrees......Page 385
7.26 Degrees of theories......Page 389
7.27 Chains of degrees......Page 391
7.28 Recursive real numbers......Page 392
HISTORICAL REMARKS TO CHAPTER 7......Page 395
EXAMPLES 7......Page 399
8.1 The system A......Page 404
8.2 Definition of A-truth......Page 405
8.3 Incompleteness and undecidability of the system A......Page 407
8.4 Various properties of the system A......Page 408
8.5 Modus Ponens......Page 413
8.6 Consistency......Page 415
8.7 Truth definitions......Page 418
8.8 Axiomatizable sets of statements......Page 420
HISTORICAL REMARKS TO CHAPTER 8......Page 424
EXAMPLES 8......Page 425
9.1 The hierarchy of A-definable sets of lattice points......Page 426
9.2 Δκп-sets......Page 430
9.3 Sets undefinable in A......Page 433
9.4 f-definable sets of lattice points......Page 434
9.5 Computing degrees of unsolvability......Page 436
EXAMPLES 9......Page 438
10.1 Limitations of the system A......Page 440
10.2 Possible ways of extending the system Aₒ......Page 442
10.3 The system E......Page 447
10.4 The system Aɪ......Page 455
10.5 Definition of an Aɪ-proof......Page 457
10.6 Theorem induction......Page 462
10.7 The Aɪ-proof-predicate......Page 465
10.8 An example of an Aɪ-proof......Page 468
10.9 Relations between Aₒ-theorems and E-correctnes......Page 472
10.10 Some properties of the system Aɪ......Page 476
10.11 Reversibility of rules......Page 480
10.12 Deduction theorem......Page 486
10.13 Guts with an Aₒₒ-cut formulae......Page 487
10.14 Cut removal with a weaker form of R 3......Page 501
10.15 Gut removal in general......Page 504
10.16 Further properties of the system Aɪ......Page 514
10.17 The consistency of Aɪ......Page 517
HISTORICAL REMARKS TO CHAPTER 10......Page 524
EXAMPLES 10......Page 526
11.1 The system A\'......Page 528
11.2 Remarks......Page 533
11.4 Properties of the systems A(v)......Page 535
11.5 The system A(v)*......Page 536
11.6 The definition of A-truth in A\'*......Page 538
11.7 Consistency of Aɪ......Page 547
11. 8 Definition ofA(k)-truth......Page 552
11.9 Scheme for an A(k)
-truth-definition......Page 555
11.10 Truth-definitions in impredicative systems......Page 557
11.11 Further extensions of the systems A(k)......Page 558
11. 12 Incompleteness of extended systems......Page 560
11.13 Real numbers......Page 561
11.14 The
 analytical hierarchy......Page 570
11.15 On the length of proofs......Page 575
HISTORICAL REMARKS TO CHAPTER 11......Page 576
EXAMPLES 11......Page 577