Provability, Computability and Reflection (eBook)

Front Cover 1
A Survey of Mathematical Logic 4
Copyright Page 5
Contents 8
Preface 6
PART ONE GENERAL SKETCHES 14
CHAPTER I. THE AXIOMATIC METHOD 16
$ 1. Geometry and axiomatic systems 16
$ 2. The problem of adequacy 20
$ 3. The problem of evidence 23
$ 4. A very elementary system L 29
$ 5. The theory of non-negative integers 34
$ 6. Gödel’s theorems 38
$ 7. Formal theories as applied elementary logics 43
CHAPTER II. EIGHTY YEARS OF FOUNDATIONAL STUDIES 49
$ 1. Analysis, reduction and formalization 49
$ 2. Anthropologism 54
$ 3. Finitism 56
$ 4. Intuitionism 58
$ 5. Predicativism: standard results on number as being 59
$ 6. Predicativism: predicative analysis and beyond 61
$ 7. Platonism 63
$ 8. Logic in the narrower sense 68
$ 9. Applications 71
CHAPTER III. ON FORMALIZATION 72
$ 1. Systematization 72
$ 2. Communication 73
$ 3. Clarity and consolidation 74
$ 4. Rigour 75
$ 5. Approximation to intuition 76
$ 6. Application to philosophy 78
$ 7. Too many digits 79
$ 8. Ideal language 80
$ 9. How artificial a language? 81
$ 10. The paradoxes 82
CHAPTER IV. THE AXIOMATIZATION OF ARITHMETIC 83
$ 1. Introduction 83
$ 2. Grassmann’s calculus 84
$ 3. Dedekind’s letter 88
$ 4. Dedekind’s essay 89
$ 5. Adequacy of Dedekind’s characterization 92
$ 6. Dedekind and Frege 94
CHAPTER V. COMPUTATION 97
$ 1. The concept of computability 97
$ 2. General recursive functions 104
$ 3. The Friedberg-Mucnik theorem 108
$ 4. Metamathematics 112
$ 5. Symbolic logic and calculating machines 115
$ 6. The control of errors in calculating machines 122
PART TWO CALCULATING MACHINES 142
CHAPTER VI. A VARIANT TO TURING’S THEORY OF CALCULATING MACHINES 144
$ 1. Introduction 144
$ 2. The basic machine B 145
$ 3. All recursive functions are B-computable 150
$ 4. Basic instructions 161
$ 5. Universal Turing machines 167
$ 6. Theorem-proving machines 171
CHAPTER VII. UNIVERSAL TURING MACHINFS: AN EXERCISE IN CODING 177
CHAPTER VIII. THE LOGIC OF AUTOMATA 192
$ 1. Introduction 192
$ 2. Automata and nets 192
$ 3. Transition matrices and matrix form nets 219
$ 4. Cycles, nets, and quantifiers 231
CHAPTER IX. TOWARD MECHANICAL MATHEMATICS 241
$ 1. Introduction 241
$ 2. The propositional calculus (system P) 246
$ 3. Program I: the propositional calculus P 248
$ 4. Program II: selecting theorems in the propositional calculus 251
$ 5. Completeness and consistency of the system P and Ps 253
$ 6. The system Pe : the propositional calculus with equality 254
$ 7. Preliminaries to the predicate calculus 255
$ 8. The system Qp and the AE predicate calculus 257
$ 9. Program III 260
$ 10. Systems Qq and Qr: alternative formulations of the AE predicate calculus 262
$ 11. System Q: the whole predicate calculus with equality 265
$ 12. Conclusions 270
Appendices I—VII 276
CHAPTER X. CIRCUIT SYNTHFSIS BY SOLVING SEQUENTIAL BOOLEAN EQUATIONS 286
$ 1. Summary of problems and results 286
$ 2. Sequential Boolean functionals and equations 287
$ 3. The method of sequential tables 289
$ 4. Deterministic solutions 291
$ 5. Related problems 296
$ 6. An effective criterion of general solvability 298
$ 7. A sufficient condition for effective solvability 303
$ 8. An effective criterion of effective solvability 307
$ 9. The normal form (S) of sequential Boolean equations 311
$ 10. Apparently richer languages 316
$ 11. Turing machines and growing automata 318
PART THREE FORMAL NUMBER THEORY 324
CHAPTER XI. THE PREDICATE CALCULUS 326
$ 1. The propositional calculus 326
$ 2. Formulations of the predicate calculus 328
$ 3. Completeness of the predicate calculus 336
CHAPTER XII. MANY-SORTED PREDICATE CALCULI 341
$ 1. One-sorted and many-sorted theories 341
§ 2. The many-sorted elementary logics Ln 345
$ 3. The theorem (I) and the completeness of Ln 347
$ 4. Proof of the theorem (IV) 348
CHAPTER XIII. THE ARITHMETIZATION OF METAMATHEMATICS 353
$ 1. Gödel numbering 353
$ 2. Recursive functions and the system Z 361
$ 3. Bernays’ lemma 364
$ 4. Arithmetic translations of axiom systems 371
CHAPTER XIV. ACKERMANN’S CONSISTENCY PROOF 381
$ 1. The system Za 381
$ 2. Proof of finiteness 385
$ 3. Estimates of the substituents 389
$ 4. Interpretation of nonfinitist proofs 391
CHAPTER XV. PARTIAL SYSTEMS OF NUMBER THEORY 395
$ 1. Skolem’s non-standard model for number theory 395
$ 2. Some applications of formalized consistency proofs 398
PART FOUR IMPREDICATIVE SET THEORY 402
CHAPTER XVI. DIFFERENT AXIOM SYSTEMS 404
$ 1. The paradoxes 404
$ 2. Zermelo’s set theory 409
$ 3. The Bernays set theory 415
$ 4. The theory of types, negative types, and “new foundations” 423
$ 5. A formal system of logic 436
$ 6. The systems of Ackermann and Frege 444
CHAPTER XVII. RELATIVE STRENGTH AND REDUCIBILITY 453
$ 1. Relation between P and Q 453
$ 2. Finite axiomatization 457
$ 3. Finite sets and natural numbers 460
CHAPTER XVIII. TRUTH DEFINITIONS AND CONSISTENCY PROOFS 464
$ 1. Introduction 464
$ 2. A truth definition for Zermelo set theory 466
$ 3. Remarks on the construction of truth definitions in general 476
$ 4. Consistency proofs via truth definitions 480
$ 5. Relativity of number theory and in particular of induction 487
$ 6. Explanatory remarks 494
CHAPTER XIX. BETWEES NUMBER THEORY AKD SET THEORY 499
$ 1. General set theory 501
$ 2. Predicative set theory 510
$ 3. Impredicative collections and .-consistency 518
CHAPTER XX. SOME PARTIAL SYSTEMS 528
$ 1. Some formal details on class axioms 528
$ 2. A new theory of element and number 536
$ 3. Set-theoretical basis for real numbers 546
$ 4. Functions of real variables 553
PART FIVE PREDICATIVE SET THEORY 556
CHAPTER XXI. CERTAIN PREDICATES DEFINED BY INDUCTION SCHEMATA 558
CHAPTER XXII. UNDECIDABLE SENTENCES SUGGESTED BY SEMANTIC PARADOXES 569
$ 1. Introduction 569
$ 2. Preliminaries 570
$ 3. Conditions which the set theory is to satisfy 572
$ 4. The Epimenides paradox 575
$ 5. The Richard paradox 577
$ 6. Final remarks 580
CHAPTER XXIII. THE FORMALIZATION OF MATHEMATICS 582
$ 1. Original sin of the formal logician 582
$ 2. Historical perspective 582
$ 3. What is a set? 584
$ 4. The indenumerable and the impredicative 585
$ 5. The limitations upon formalization 587
$ 6. A constructive theory 588
$ 7. The denumerability of all sets 590
$ 8. Consistency and adequacy 592
$ 9. The axiom of reducibility 597
$ 10. The vicious-circle principle 599
$ 11. Predicative sets and constructive ordinals 601
$ 12. Concluding remarks 604
CHAPTER XXIV. SOME FORMAL DETAILS ON PREDICATIVE SET THEORIES 608
$ 1. The underlying logic 608
§ 2. The axioms of the theory S 612
§ 3. Preliminary considerations 616
§ 4. The theory of non-negative integers 620
§ 5. The enumerability of all sets 624
§ 6. Consequences of the enumerations 629
§ 7. The theory of real numbers 631
§ 8. Intuitive models 634
§ 9. Proofs of consistency 637
$ 10. The system R 642
CHAPTER XXV. ORDINAL NUMBERS AND PREDICATIVE SET THEORY 647
$ 1. Systems of notation for ordinal numbers 648
$ 2. Strongly effective systems 650
$ 3. The Church-Kleene class B and a new class C 655
$ 4. Partial Herbrand recursive functions 660
$ 5. Predicative set theory 662
§ 6. Two tentative definitions of predicative sets 669
$ 7. System H: the hyperarithmetic set theory 671