Recursion Theory

Table of contents

1. Cover
2. Title
3. Copyright
4. Preface
5. Contents
6. Preface
7. Part I: Fundamental theory
   1. 1 An introduction to higher recursion theory
      1. 1.1 Projective predicates
      2. 1.2 Ordinal notations
      3. 1.3 Effective transfinite induction
      4. 1.4 Recursive ordinals
      5. 1.5 -completeness and -boundedness
   2. 2 Hyperarithmetic theory
      1. 2.1 H-sets and -singletons
      2. 2.2 -ness and hyperarithmeticity
      3. 2.3 Spector’s Uniqueness Theorem
      4. 2.4 Hyperarithmetic reducibility
      5. 2.5 Some basis theorems and their applications
      6. 2.6 More on
      7. 2.7 Codes for sets
   3. 3 Admissibility and constructibility
      1. 3.1 Kripke–Platek set theory
      2. 3.2 Admissible sets
      3. 3.3 Constructibility
      4. 3.4 Projecta and master codes
      5. 3.5 ω-models
      6. 3.6 Coding structures
      7. 3.7 The Spector–Gandy Theorem
   4. 4 The theory of -sets
      1. 4.1 A -basis theorem
      2. 4.2 -uniformization
      3. 4.3 Characterizing thin -sets
      4. 4.4 -sets
   5. 5 Recursion-theoretic forcing
      1. 5.1 Ramified analytical hierarchy
      2. 5.2 Cohen forcing
      3. 5.3 Sacks forcing
      4. 5.4 Characterizing countable admissible ordinals
   6. 6 Set theory
      1. 6.1 Set-theoretic forcing
      2. 6.2 Some examples of forcing
      3. 6.3 A cardinality characterization of -sets
      4. 6.4 Large cardinals
      5. 6.5 Axiom of determinacy
      6. 6.6 Recursion-theoretic aspects of determinacy
8. Part II: The story of Turing degrees
   1. 7 Classification of jump operators
      1. 7.1 Uniformly degree invariant functions
      2. 7.2 Martin’s conjecture for uniformly degree invariant functions
      3. 7.3 The Posner–Robinson Theorem
      4. 7.4 Classifying order-preserving functions on 2ω
      5. 7.5 Pressdown functions
   2. 8 The construction of -sets
      1. 8.1 An introduction to inductive definition
      2. 8.2 Inductively defining -sets of reals
      3. 8.3 -maximal chains and antichains of Turing degrees
      4. 8.4 Martin’s conjecture for -functions
   3. 9 Independence results in recursion theory
      1. 9.1 Independent sets of Turing degrees
      2. 9.2 Embedding locally finite upper semilattices into 〈, ≤〉
      3. 9.3 Cofinal chains in
      4. 9.4 ω-homogeneity of the Turing degrees
      5. 9.5 Some general independence results
9. Part III: Hyperarithmetic degrees and perfect set property
   1. 10 Rigidity and biinterpretability of hyperdegrees
      1. 10.1 Embedding lattices into hyperdegrees
      2. 10.2 The rigidity of hyperdegrees
      3. 10.3 Biinterpretability
   2. 11 Basis theorems
      1. 11.1 A basis theorem for -sets of reals
      2. 11.2 An antibasis theorem for -sets
      3. 11.3 Perfect sets in L
10. Part IV: Higher randomness theory
    1. 12 Review of classical algorithmic randomness
       1. 12.1 Randomness via measure theory
       2. 12.2 Randomness via complexity theory
       3. 12.3 Lowness for randomness
    2. 13 More on hyperarithmetic theory
       1. 13.1 Hyperarithmetic measure theory
       2. 13.2 Coding sets above Kleene’s
       3. 13.3 Hyperarithmetic computation
    3. 14 The theory of higher randomness
       1. 14.1 Higher Kurtz randomness
       2. 14.2 and -Martin-Löf randomness
       3. 14.3 -randomness
       4. 14.4 and -randomness
       5. 14.5 Kolmogorov complexity and randomness
       6. 14.6 Lowness for randomness
11. A Open problems
    1. A.1 Hyperarithmetic theory
    2. A.2 Set-theoretic problems in recursion theory
    3. A.3 Higher randomness theory
12. B An interview with Gerald E. Sacks
13. C Notations and symbols
14. Endnotes
15. Bibliography
16. Index