Recursion Theory for Metamathematics
1st Edition
Published on 28. January 1993
180 pages
978-0-19-534481-3 (ISBN)
Description
This 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.
More details
Other editions
Additional editions
Raymond M. Smullyan
Recursion Theory for Metamathematics
Book
07/1993
Oxford University Press Inc
€255.50
Shipment within 15-20 days
Content
- Intro
- Contents
- 0 Prerequisites
- I. Some General Incompleteness Theorems
- §0. Preliminaries
- §1. Some Abstract Incompleteness Theorems
- §2. ?-Consistency
- §3. Rosser's Method
- §3.1. Definability and Complete Representability
- II. Arithmetic, S[sub(0)] and R.E. Relations
- §4. Arithmetic, S[sub(0)] and R.E. Relations
- §5. Axiomatizable Systems
- §6. Rosser Systems
- §7. The Systems P.A., (Q) and (R)
- §8. More on Rosser Systems
- §9. The Non-Axiomatizability of N
- Tarski's Theorem
- §10. More on Separation
- §11. Definability of Functions in S
- III. Shepherdson's Theorems
- §12. Shepherdson's Representation Lemma
- §13. Shepherdson's Exact Separation Lemma
- I: Recursive Enumerability and Recursivity
- I. Some Basic Closure Properties
- §1. Some Closure Properties
- §2. Recursive Relations
- §3. Some Consequences
- II. Recursive Pairing Functions
- §4. Recursive Pairing Functions
- §5. The Functions J[sub(n)](x[sub(1)],...,x[sub(n)])
- III. Representability and Recursive Enumerability
- §6.
- II: Undecidability and Recursive Inseparability
- I. Undecidability
- §1. Some Preliminary Theorems
- §2. Undecidable Systems
- §3. Non-Recursivity and Incompleteness
- §4. Essential Undecidability
- II. Recursive Inseparability
- §5. Recursive Inseparability
- §6. Recursive Inseparability and Incompleteness
- III: Indexing
- I. The Enumeration Theorem
- §1. Indexing
- II. The Iteration Theorem
- §2. The Iteration Theorem
- III. Effective Separation
- §3. Uniform Separation
- IV: Generative Sets and Creative Systems
- §1. Productive and Creative Sets
- §2. Many-one Reducibility
- Universal Sets
- §3. Representability and Uniform Representability
- §4. Generativity and Incompleteness
- V: Double Generativity and Complete Effective Inseparability
- I. Complete Effective Inseparability
- §1. Complete Effective Inseparability
- §2. Kleene's Construction
- §3. Kleene's Symmetric Form of Gödel's Theorem
- §4. Reducibility and Semi-Reducibility
- §5. Completely E.I. Systems
- §6. Effective Rosser Systems
- II. Double Universality
- §7. Double Universality
- III. Double Generativity
- §8. Doubly Generative Pairs
- §9. Reducibility
- §10. Sentential Double Generativity
- VI: Universal and Doubly Universal Systems
- I. Universality
- §1. Generativity and Universality
- §2. The Ehrenfeucht-Feferman Theorem
- II. Double Universality
- §3. Double Generativity and Double Universality
- §4. Metamathematical Applications
- VII: Shepherdson Revisited
- §1. Separation Functions
- §2.
- §3. More on the Shepherdson and Putnam-Smullyan Theorems
- VIII: Recursion Theorems
- I. Weak Recursion Theorems
- §1. The Weak Recursion Theorem
- §2. Unsolvable Problems and Rice's Theorem
- II. The Strong Recursion Theorem
- §3. Strong Recursion Theorem
- III. An Extended Recursion Theorem
- §4.
- IX: Symmetric and Double Recursion Theorems
- I. Double Recursion Theorems
- §1. The Weak Double Recursion Theorem
- §2. The Strong Double Recursion Theorem
- II. A Symmetric Recursion Theorem
- §3.
- III. Double Recursion With a Pairing Function
- §4. Double Master Functions
- §5. Theorem D and Theorem 2 Compared
- IV. Further Topics
- §6. Applications of the Extended Recursion Theorem
- §7. The (Strong) Single and Double Recursion Theorems Compared
- §8. A Very Nice Function
- §9. The n-fold Recursion Theorem
- §10. A General Fixed Point Principle
- X: Productivity and Double Productivity
- I. Productivity and Double Productivity
- §1. Weak Productivity
- §2. Weak Double Productivity
- §3. Effective Inseparability
- §4. A Retrospective Look
- XI: Three Special Topics
- I. Uniform Reducibility
- §1. Uniform Reducibility
- §2. Uniform Reducibility for Pairs
- II. Pseudo-Uniform Reducibility
- §3. Pseudo-Uniform Reducibility
- §4. Pseudo-Uniform Reducibility for Pairs
- III. Some Feeble Partial Functions
- §5. Feeble Co-Productive and Generative Functions
- §6. Double Analogues
- XII: Uniform Gödelization
- I. The Sentential Recursion Property
- §1. Effectively Gödelian Systems
- II. DSR and Semi-DSR Systems
- §2. Rosser Systems For Binary Relations
- §3. Effective Rosser Systems for Sets
- §4. Some Stronger Properties
- III. Rosser Fixed-Point Properties and Uniform Incompletability
- §5. Rosser Fixed Point Properties
- §6. Uniform Incompletability
- §7. The Weakened Putnam-Smullyan Conditions
- IV. Finale
- References
- Index
- A
- B
- C
- D
- E
- F
- G
- I
- K
- L
- M
- N
- P
- R
- S
- T
- U
- W
