Contents

Preface

Part I: Fundamental theory

1An introduction to higher recursion theory

1.1Projective predicates

1.2Ordinal notations

1.3Effective transfinite induction

1.4Recursive ordinals

1.5-completeness and -boundedness

2Hyperarithmetic theory

2.1H-sets and -singletons

2.2-ness and hyperarithmeticity

2.3Spector’s Uniqueness Theorem

2.4Hyperarithmetic reducibility

2.5Some basis theorems and their applications

2.6More on

2.7Codes for sets

3Admissibility and constructibility

3.1Kripke–Platek set theory

3.2Admissible sets

3.3Constructibility

3.4Projecta and master codes

3.5ω-models

3.6Coding structures

3.7The Spector–Gandy Theorem

4The theory of -sets

4.1A -basis theorem

4.2-uniformization

4.3Characterizing thin -sets

4.4-sets

5Recursion-theoretic forcing

5.1Ramified analytical hierarchy

5.2Cohen forcing

5.3Sacks forcing

5.4Characterizing countable admissible ordinals

6Set theory

6.1Set-theoretic forcing

6.2Some examples of forcing

6.3A cardinality characterization of -sets

6.4Large cardinals

6.5Axiom of determinacy

6.6Recursion-theoretic aspects of determinacy

Part II: The story of Turing degrees

7Classification of jump operators

7.1Uniformly degree invariant functions

7.2Martin’s conjecture for uniformly degree invariant functions

7.3The Posner–Robinson Theorem

7.4Classifying order-preserving functions on 2ω

7.5Pressdown functions

8The construction of -sets

8.1An introduction to inductive definition

8.2Inductively defining -sets of reals

8.3-maximal chains and antichains of Turing degrees

8.4Martin’s conjecture for -functions

9Independence results in recursion theory

9.1Independent sets of Turing degrees

9.2Embedding locally finite upper semilattices into 〈, ≤〉

9.3Cofinal chains in

9.4ω-homogeneity of the Turing degrees

9.5Some general independence results

Part III: Hyperarithmetic degrees and perfect set property

10Rigidity and biinterpretability of hyperdegrees

10.1Embedding lattices into hyperdegrees

10.2The rigidity of hyperdegrees

10.3Biinterpretability

11Basis theorems

11.1A basis theorem for -sets of reals

11.2An antibasis theorem for -sets

11.3Perfect sets in L

Part IV: Higher randomness theory

12Review of classical algorithmic randomness

12.1Randomness via measure theory

12.2Randomness via complexity theory

12.3Lowness for randomness

13More on hyperarithmetic theory

13.1Hyperarithmetic measure theory

13.2Coding sets above Kleene’s

13.3Hyperarithmetic computation

14The theory of higher randomness

14.1Higher Kurtz randomness

14.2 and -Martin-Löf randomness

14.3-randomness

14.4 and -randomness

14.5Kolmogorov complexity and randomness

14.6Lowness for randomness

AOpen problems

A.1Hyperarithmetic theory

A.2Set-theoretic problems in recursion theory

A.3Higher randomness theory

BAn interview with Gerald E. Sacks

CNotations and symbols

Endnotes

Bibliography

Index