## 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. |

### What people are saying - Write a review

We haven't found any reviews in the usual places.

### Contents

0 Prerequisites | 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 |

159 | |

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

### References to this book

Subrecursive Programming Systems: Complexity & Succinctness James S. Royer,John Case Limited preview - 1994 |