Recursion Theory for MetamathematicsThis work is a sequel to the author's Gödel's Incompleteness Theorems, though it can be read independently by anyone familiar with Gödel's incompleteness theorem for Peano arithmetic. The book deals mainly with those aspects of recursion theory that have applications to the metamathematics of incompleteness, undecidability, and related topics. It is both an introduction to the theory and a presentation of new results in the field. |
Contents
| 1 | |
Recursive Enumerability and Recursivity | 24 |
Undecidability and Recursive Inseparability | 38 |
Indexing | 48 |
Generative Sets and Creative Systems | 58 |
Double Generativity and Complete Effective Inseparability | 67 |
Universal and Doubly Universal Systems | 82 |
Shepherdson Revisited | 89 |
Recursion Theorems | 94 |
Symmetric and Double Recursion Theorems | 105 |
Productivity and Double Productivity | 120 |
Three Special Topics | 128 |
Uniform Gödelization | 141 |
References | 159 |
Index | 161 |
Other editions - View all
Common terms and phrases
a e w A1 and A2 argument arithmetic arithmetic set Assume hypothesis binary relations Chapter Corollary D.G. function disjoint pair double recursion theorem effective inseparability effectively a Rosser exact Rosser system exactly separates Exercise existential quantification first-order logic fixed point property formula H(v1 function for A1 Gödel number Gödel sentence Hence iteration theorem iterative function Kleene function Kleene pair Lemma metamathematical n-tuple natural numbers number h number n ordered pairs pair of r.e. Peano Arithmetic proof of Theorem Proposition provable formulas prove Theorem r.e. relation M(a r.e. sets recursive function f(z recursive function tſy recursive sets recursively inseparable refutable represents Rosser function semi-DSR sentential recursion property sets are representable Shepherdson strongly definable strongly separates superset Suppose system for binary system for sets Theorem 2.1 tion undecidable w-consistent weakly
Popular passages
Page 43 - from A, so the condition is symmetric]. A and B are called recursively inseparable (abbreviated RI) iff they are
Page 63 - if there is a recursive function g(x] such that for every number i,
Page viii - theorems of 1960 can be proved without appeal to the recursion theorem or any other fixed point argument.
Page 134 - the collection of all recursive sets is pseudo-uniformly reducible to a, then a is
Page 86 - consider the following three conditions which may or may not hold for a
Page 41 - axiomatizable system in which some non-recursive set is representable, then S is incomplete.
Page ix - sentential and double sentential recursion properties, Rosser fixed point properties, uniform incompleteness) and
Page 136 - to be recursively inseparable is that for every recursive set A, there
References to this book
Subrecursive Programming Systems: Complexity & Succinctness James S. Royer,John Case Limited preview - 1994 |