
Recursion Theory for Metamathematics
Description
Alles über E-Books | Antworten auf Fragen rund um E-Books, Kopierschutz und Dateiformate finden Sie in unserem Info- & Hilfebereich.
More details
Other editions
Additional editions

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
System requirements
File format: PDF
Copy-Protection: Adobe-DRM (Digital Rights Management)
System requirements:
- Computer (Windows; MacOS X; Linux): Install the free reader Adobe Digital Editions prior to download (see eBook Help).
- Tablet/smartphone (Android; iOS): Install the free app Adobe Digital Editions or the app PocketBook before downloading (see eBook Help).
- E-reader: Bookeen, Kobo, Pocketbook, Sony, Tolino and many more (only limited: Kindle).
The file format PDF always displays a book page identically on any hardware. This makes PDF suitable for complex layouts such as those used in textbooks and reference books (images, tables, columns, footnotes). Unfortunately, on the small screens of e-readers or smartphones, PDFs are rather annoying, requiring too much scrolling.
This eBook uses Adobe-DRM, a „hard” copy protection. If the necessary requirements are not met, unfortunately you will not be able to open the eBook. You will therefore need to prepare your reading hardware before downloading.
Please note: We strongly recommend that you authorise using your personal Adobe ID after installation of any reading software.
For more information, see our eBook Help page.