O'Reilly logo

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

Recursion Theory

Book Description

This monograph presents recursion theory from a generalized point of view centered on the computational aspects of definability. A major theme is the study of the structures of degrees arising from two key notions of reducibility, the Turing degrees and the hyperdegrees, using techniques and ideas from recursion theory, hyperarithmetic theory, and descriptive set theory.
The emphasis is on the interplay between recursion theory and set theory, anchored on the notion of definability. The monograph covers a number of fundamental results in hyperarithmetic theory as well as some recent results on the structure theory of Turing and hyperdegrees. It also features a chapter on the applications of these investigations to higher randomness.

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