Provability, Computability and Reflection (eBook)

Front Cover 1
Combinatory Logic, Volume 22 6
Copyright Page 7
Table of Contents 11
Preface 8
Explanation of Notations 14
Introduction 18
A. The Analysis of Substitution 18
B. The Russell Paradox 21
C. Plan of the Work 22
D. Historical Sketch 25
Chapter 1. Formal Systems 29
A. The Approach to Formal Systems 29
B. Definition of a Formal System 31
C. Philosophy of Formal Systems 36
D. Linguistic Aspects of a Formal System 40
E. Special Forms of Formal Systems 45
S. Supplementary Topics 50
Chapter 2. Epitheory 57
A. The Nature of Epitheory 57
B. Techniques of Induction 61
C. Variables 69
D. Replacement and Monotone Relations 74
E. Theory of Definition 79
S. Supplementary Topics 93
Chapter 3. Lambda-Conversion 97
A. Variables and Functions in Mathematics 97
B. Functional Abstraction 100
C. Morphology of a Formal .-Applicative System 104
D. Theoretical Rules of the Calculuses of Lambda-Conversion 106
E. Substitution Prefixes 111
S. Supplementary Topics 121
Chapter 4. The Church-Rosser Theorem 125
A. General Formulation 125
B. Property (D) 132
C. Property (E) 140
D. Extension to Include .-Conversion 148
E. The Second Church-Rosser Theorem 156
F. Theorems on Order 161
S. Supplementary Topics 166
Chapter 5. Intuitive Theory of Combinators 168
A. Preliminary Discussion 169
B. Interdefinability of Simple Combinators 172
C. Terminology and Notation 177
D. Properties of B 180
E. Combinators Related to S 185
F. Theorems on Order of Combinators 192
G. Paradoxical Combinators 194
H. Definitional Independence of Combinators 196
S. Supplementary Topics 201
Chapter 6. Synthetic Theory of Combinators 203
A. Analysis of Combinatorial Completeness 203
B. Basic Properties of H 211
C. The Combinatory Axioms 214
D. Theory of the Substitution Prefix 222
E. Equivalence of H and Lambda-Conversion 226
F. Theory of Strong Reduction 235
S. Supplementary Topics 253
Chapter 7. Logistic Foundations 256
A. Preliminaries 256
B. The Combinatory Rules 258
C. The Systems 2 262
D. The Systems K 265
E. Modifications and Generalizations 267
S. Supplementary Topics 272
Chapter 8. Introduction to Illative Combinatory Logic 274
A. The Russell Paradox 275
B. Alternative Explanations of the Paradox 277
C. The Notion of Functionality 279
D. Relations to Other Illative Concepts 283
E. Formal Preliminaries 285
S. Supplementary Topics 290
Chapter 9. The Basic Theory of Functionality 294
A. Preliminaries 294
B. The Subject-Construction Theorem 299
C. Thc Subject-Conversion Theorems 310
D. The Stratification Theorem and Its Consequences 321
E. Analogies with Propositional Algebra 329
F. Inferential Forms of Functionality 332
S. Supplementary Topics 361
Chapter 10. The Stronger Theories of Functionality 362
A. Preliminaries 362
B. General Properties of Deductions 370
C. FR-Deductions 377
D. The Restricted Theories 382
E. Finite Formulation 385
Appendix A. List of Basic Constants 394
Appendix B. List of Properties of Relations 397
Bibliography 399
Index 412