Author(s): Raymond M. Smullyan
Series: AM-47 Annals of Mathematics Studies
Publisher: Princeton University Press
Year: 1961
Language: English
Pages: 156
Title ......Page 5
Copyright ......Page 6
Dedication ......Page 7
Preface ......Page 9
Table of Contents ......Page 11
I – Formal Mathematical Systems ......Page 15
§0. Motivation ......Page 16
§1. Definition of an Elementary Formal System ......Page 17
§2. Alternative Formulation of Elementary Formal Systems ......Page 19
§3. Representability ......Page 20
§4. Mathematical Systems ......Page 23
§5. Recursively Enumerable Attributes of Positive Integers ......Page 24
§6. Godel Numbering ......Page 25
§7. The Universal System U ......Page 26
§8. The Recursive Unsolvability of U ......Page 28
Appendix – Formal Representability of T and To ......Page 30
§0. Some Preliminary Principles ......Page 33
#A. Closure Properties ......Page 34
§1. Closure under Existential Definability ......Page 35
§2. Solvability over K ......Page 40
§3. Recursive Enumerability of Some Basic Arithmetical Attributes ......Page 42
§5. Finite Quantification; Constructive Definability ......Page 43
§6. Extension of Alphabets ......Page 45
§7. Dyadic Godel Numbering ......Page 46
§8. Solvability ......Page 47
§9. Lexicographical Ordering; n-Adic Representation of Numbers ......Page 48
§11. Further Facts about Admissibility (optional) ......Page 51
#D. A Brief Summary ......Page 52
III – Incompleteness and Undecidability ......Page 53
§1. Representation Systems ......Page 55
§2. First Diagonalization Lemma; Tarski's Theorem ......Page 56
§3. Consistency and Completeness; Godel's Theorem ......Page 59
§4. Complete Representability and Definability in Z ......Page 60
§5. Separability within Z; Rosser's Theorems ......Page 61
§6. Symmetric Systems ......Page 63
§7. Extensions ......Page 64
#B. Undecidability ......Page 65
§8. Systems with an "Effective" Representation Function ......Page 66
§9. Undecidability ......Page 67
§11. Additional Theorems ......Page 69
§13. Undecidability and Incompleteness ......Page 70
§16. Recursive Inseparability ......Page 72
§17. Separation of R.I. Sets within Systems ......Page 73
§18. Rosser Systems ......Page 74
§19. Recursive Inseparability of the Diagonal Sets T*, R* ......Page 75
§1. Enumeration Theorem ......Page 79
§3. Iteration Theorems for r.e. Relations ......Page 81
§4. Effective Operations ......Page 84
§5. Fixed Point Theorems ......Page 86
§6. Double Recursion Theorems ......Page 89
#B. Construcive Arithmetic and Rudimentary Attributes ......Page 91
§7. Some Preliminaries ......Page 92
§8. Dyadic Concatenation ......Page 93
§9. Rudimentary Attributes ......Page 95
§10. Pure Elementary Formal Systems ......Page 98
§11. Arithmetization of Elementary Dyadic Arithmetics ......Page 99
§12. Kleene Enumeration Theorem ......Page 103
§14. Partial Recursive Functions ......Page 104
§15. Functional Indexing ......Page 105
§1. Productive and Creative Sets; Recursive and Effective Inseparability ......Page 107
§2. Many-One and One-One Reducibility ......Page 109
§3. Creative Systems ......Page 111
§4. Effective Inseparability ......Page 112
§5. Effective Rosser Systems ......Page 113
§6. Weakly Productive Functions ......Page 114
§7. Uniform Reducibility ......Page 116
§9. On Uniform Reducibility ......Page 118
§11. Bi-Uniformity ......Page 120
§12. Doubly Productive Pairs ......Page 121
§13. Reducibility of Pairs to Pairs ......Page 124
§15. Uniform Reducibility ......Page 126
§16. Weakly Doubly Productive Pairs ......Page 127
§17. On Doubly Productive Pairs ......Page 128
§19. Uniform Reducibility ......Page 131
§20. A Generalization of Effective Inseparability ......Page 133
§21. Total Double Universality ......Page 134
§22. Double Isomorphism ......Page 137
§23. 1-1 Equivalence and Double Isomorphism ......Page 139
§24. Double Isomorphism of Rosser Systems ......Page 140
§1. Theories ......Page 141
§2. Calculability of Functions; Normality ......Page 144
§3. omega-Consistency; Enumerability within (T); Godel's Theorem ......Page 145
§4. Rosser's Construction ......Page 146
§5. Godel Theories and Rosser Theories ......Page 148
§6. Theories in which Plus and Times are Definable ......Page 150
§8. Essential Undecidability ......Page 151
§9. Essential Creativity ......Page 152
§10. Exact Rosser Theories ......Page 153
Reference and Brief Bibliography ......Page 155
