Theory of Formal Systems. (AM-47), Volume 47 (Annals of Mathematics Studies, 47)

This book serves both as a completely self-contained introduction and as an exposition of new results in the field of recursive function theory and its application to formal systems. Front Cover......Page scandjvutmpd3c_0001.djvu Back Cover......Page scandjvutmpd3d_0001.djvu Title Page......Page scandjvutmpd36_0001.djvu Copyright Page......Page scandjvutmpd37_0001.djvu Preface......Page scandjvutmpd39_0001.djvu Table of Contents......Page scandjvutmpd3f_0001.djvu I – Formal Mathematical Systems......Page scandjvutmpd42_0001.djvu #A. Elementary Formal Systems......Page scandjvutmpd43_0001.djvu §0. Motivation......Page 18 §1. Definition of an Elementary Formal System......Page scandjvutmpd44_0001.djvu §2. Alternative Formulation of Elementary Formal Systems......Page scandjvutmpd46_0001.djvu §3. Representability......Page scandjvutmpd47_0001.djvu §4. Mathematical Systems......Page scandjvutmpd4a_0001.djvu #B. Recursive Enumerability......Page scandjvutmpd4b_0001.djvu §5. Recursively Enumerable Attributes of Positive Integers......Page 26 §6. Gödel Numbering......Page scandjvutmpd4c_0001.djvu §7. The Universal System U......Page scandjvutmpd4d_0001.djvu §8. The Recursive Unsolvability of U......Page scandjvutmpd4f_0001.djvu Appendix – Formal Representability of T and T0......Page scandjvutmpd51_0001.djvu II – Formal Representability and Recursive Enumerability......Page scandjvutmpd54_0001.djvu §0. Some Preliminary Principles......Page 35 #A. Closure Properties......Page scandjvutmpd55_0001.djvu §1. Closure under Existential Definability......Page scandjvutmpd56_0001.djvu §2. Solvability over K......Page scandjvutmpd5b_0001.djvu #B. Recursive Enumerability......Page 44 §3. Recursive Enumerability of Some Basic Arithmetical Attributes......Page scandjvutmpd5d_0001.djvu §4. Recursive and Partial Recursive Functions......Page scandjvutmpd5e_0001.djvu §5. Finite Quantification; Constructive Definability......Page 45 #C. Transformations on Alphabets; Gödel Numbering......Page 47 §6. Extension of Alphabets......Page scandjvutmpd60_0001.djvu §7. Dyadic Gödel Numbering......Page scandjvutmpd61_0001.djvu §8. Solvability......Page scandjvutmpd62_0001.djvu §9. Lexicographical Ordering; n-Adic Representation of Numbers......Page scandjvutmpd63_0001.djvu §10. Admissible Gödel Correspondences......Page scandjvutmpd66_0001.djvu §11. Further Facts about Admissibility (optional)......Page 53 #D. A Brief Summary......Page scandjvutmpd67_0001.djvu III – Incompleteness and Undecidability......Page scandjvutmpd68_0001.djvu #A. Incompleteness......Page scandjvutmpd6a_0001.djvu §1. Representation Systems......Page 57 §2. First Diagonalization Lemma; Tarski's Theorem......Page scandjvutmpd6b_0001.djvu §3. Consistency and Completeness; Gödel's Theorem......Page scandjvutmpd6e_0001.djvu §4. Complete Representability and Definability in Z......Page scandjvutmpd6f_0001.djvu §5. Separability within Z; Rosser's Theorems......Page scandjvutmpd70_0001.djvu §6. Symmetric Systems......Page scandjvutmpd72_0001.djvu §7. Extensions......Page scandjvutmpd73_0001.djvu #B. Undecidability......Page scandjvutmpd74_0001.djvu §8. Systems with an "Effective" Representation Function......Page scandjvutmpd75_0001.djvu §9. Undecidability......Page scandjvutmpd76_0001.djvu §10. Normality......Page scandjvutmpd79_0001.djvu §11. Additional Theorems......Page 71 §12. Universal Systems......Page scandjvutmpd7a_0001.djvu §13. Undecidability and Incompleteness......Page 72 §16. Recursive Inseparability......Page 74 §14. Definability in Formal Systems......Page scandjvutmpd7c_0001.djvu §17. Separation of R.I. Sets within Systems......Page scandjvutmpd7d_0001.djvu §18. Rosser Systems......Page scandjvutmpd7e_0001.djvu §19. Recursive Inseparability of the Diagonal Sets T*, R*......Page scandjvutmpd7f_0001.djvu §1. Enumeration Theorem......Page 81 #A. Effective Operations and Fixed Point Theorems......Page scandjvutmpd83_0001.djvu §2. Indexing......Page scandjvutmpd85_0001.djvu §3. Iteration Theorems for r.e. Relations......Page 83 §4. Effective Operations......Page scandjvutmpd88_0001.djvu §5. Fixed Point Theorems......Page scandjvutmpd8a_0001.djvu §6. Double Recursion Theorems......Page scandjvutmpd8d_0001.djvu #B. Construcive Arithmetic and Rudimentary Attributes......Page scandjvutmpd8f_0001.djvu §7. Some Preliminaries......Page scandjvutmpd90_0001.djvu §8. Dyadic Concatenation......Page scandjvutmpd91_0001.djvu §9. Rudimentary Attributes......Page scandjvutmpd98_0001.djvu §10. Pure Elementary Formal Systems......Page scandjvutmpd9b_0001.djvu §11. Arithmetization of Elementary Dyadic Arithmetics......Page scandjvutmpd9c_0001.djvu #C. Enumeration and Normal Form Theorems......Page scandjvutmpda0_0001.djvu §12. Kleene Enumeration Theorem......Page 105 §13. Separation of Differences of r.e. Sets......Page scandjvutmpda1_0001.djvu §14. Partial Recursive Functions......Page 106 §15. Functional Indexing......Page scandjvutmpda3_0001.djvu V – Creativity and Effective Inseparability......Page scandjvutmpda5_0001.djvu §1. Productive and Creative Sets; Recursive and Effective Inseparability......Page 109 §2. Many-One and One-One Reducibility......Page scandjvutmpda7_0001.djvu §3. Creative Systems......Page scandjvutmpda9_0001.djvu §4. Effective Inseparability......Page scandjvutmpdaa_0001.djvu §5. Effective Rosser Systems......Page scandjvutmpdab_0001.djvu §6. Weakly Productive Functions......Page scandjvutmpdac_0001.djvu §7. Uniform Reducibility......Page scandjvutmpdae_0001.djvu §8. Universal Sets......Page scandjvutmpdb0_0001.djvu §9. On Uniform Reducibility......Page 120 §10. Uniform Representability......Page scandjvutmpdb2_0001.djvu §11. Bi-Uniformity......Page 122 #C. Effective Inseparability and Double Productivity......Page scandjvutmpdb3_0001.djvu §12. Doubly Productive Pairs......Page 123 §13. Reducibility of Pairs to Pairs......Page scandjvutmpdb6_0001.djvu #D. Double Universality......Page scandjvutmpdb8_0001.djvu §15. Uniform Reducibility......Page 128 §16. Weakly Doubly Productive Pairs......Page scandjvutmpdb9_0001.djvu §17. On Doubly Productive Pairs......Page scandjvutmpdba_0001.djvu §18. Application to Rosser Systems......Page scandjvutmpdbd_0001.djvu §19. Uniform Reducibility......Page 133 §20. A Generalization of Effective Inseparability......Page scandjvutmpdbf_0001.djvu §21. Total Double Universality......Page scandjvutmpdc0_0001.djvu #E. Double Isomorphism......Page scandjvutmpdc3_0001.djvu §22. Double Isomorphism......Page 139 §23. 1-1 Equivalence and Double Isomorphism......Page scandjvutmpdc5_0001.djvu §24. Double Isomorphism of Rosser Systems......Page scandjvutmpdc6_0001.djvu Supplement – Applications to Mathematical Logic......Page scandjvutmpdc7_0001.djvu §1. Theories......Page 143 §2. Calculability of Functions; Normality......Page scandjvutmpdca_0001.djvu §3. ω-Consistency; Enumerability within (T); Gödel's Theorem......Page scandjvutmpdcb_0001.djvu §4. Rosser's Construction......Page scandjvutmpdcc_0001.djvu §5. Gödel Theories and Rosser Theories......Page scandjvutmpdce_0001.djvu §6. Theories in which Plus and Times are Definable......Page scandjvutmpdd0_0001.djvu §7. Some Special Theories......Page scandjvutmpdd1_0001.djvu §8. Essential Undecidability......Page 153 §9. Essential Creativity......Page scandjvutmpdd2_0001.djvu §10. Exact Rosser Theories......Page scandjvutmpdd3_0001.djvu Reference and Brief Bibliography......Page scandjvutmpdd5_0001.djvu