General Recursion Theory: An Axiomatic Approach

✍ Scribed by Jens E. Fenstad

• Publisher: Cambridge University Press
• Year: 2017
• Tongue: English
• Leaves: 238
• Series: Perspectives in Logic, Band 10
• Category: Library

✦ Synopsis

Since their inception, the Perspectives in Logic and Lecture Notes in Logic series have published seminal works by leading logicians. Many of the original books in the series have been unavailable for years, but they are now in print once again. In this volume, the tenth publication in the Perspectives in Logic series, Jens E. Fenstad takes an axiomatic approach to present a unified and coherent account of the many and various parts of general recursion theory. The main core of the book gives an account of the general theory of computations. The author then moves on to show how computation theories connect with and unify other parts of general recursion theory. Some mathematical maturity is required of the reader, who is assumed to have some acquaintance with recursion theory. This book is ideal for a second course in the subject.

✦ Table of Contents

Contents
Pons Asinorum
Chapter 0. On the Choice of Correct Notions for the General Theory
0.1 Finite Algorithmic Procedures
0.2 FAP and Inductive Definability
0.3 FAP and Computation Theories
0.4 Platek's Thesis
0.5 Recent Developments in Inductive Definability
Part A. General Theory
Chapter 1. General Theory: Combinatorial Part
1.1 Basic Definitions
1.2 Some Computable Functions
1.3 Semicomputable Relations
1.4 Computing Over the Integers
1.5 Inductively Defined Theories
1.6 A Simple Representation Theorem
1.7 The First Recursion Theorem
Chapter 2. General Theory: Subcomputations
2.1 Subcomputations
2.2 Inductively Defined Theories
2.3 The First Recursion Theorem
2.4 Semicomputable Relations
2.5 Finiteness
2.6 Extension of Theories
2.7 Faithful Representation
Part B. Finite Theories
Chapter 3. Finite Theories on One Type
3.1 The Prewellordering Property
3.2 Spector Theories
3.3 Spector Theories and Inductive Definability
Chapter 4. Finite Theories on Two Types
4.1 Computation Theories on Two Types
4.2 Recursion in a Normal List
4.3 Selection in Higher Types
4.4 Computation Theories and Second Order Definability
Part C. Infinite Theories
Chapter 5. Admissible Prewellorderings
5.1 Admissible Prewellorderings and Infinite Theories
5.2 The Characterization Theorem
5.3 The Imbedding Theorem
5.4 Spector Theories Over ω
Chapter 6. Degree Structure
6.1 Basic Notions
6.2 The Splitting Theorem
6.3 The Theory Extended
Part D. Higher Types
Chapter 7. Computations Over Two Types
7.1 Computations and Reflection
7.2 The General Plus-2 and Plus-1 Theorem
7.3 Characterization in Higher Types
Chapter 8. Set Recursion and Higher Types
8.1 Basic Definitions
8.2 Companion Theory
8.3 Set Recursion and Kleene-recursion in Higher Types
8.4 Degrees of Functional
8.5 Epilogue
References
Notation
Author Index
Subject Index