Home Page Icon
Home Page
Table of Contents for
Part I: Fundamental theory
Close
Part I: Fundamental theory
by Liang Yu, Chi Tat Chong
Recursion Theory
Cover
Title
Copyright
Preface
Contents
Preface
Part I: Fundamental theory
1 An introduction to higher recursion theory
1.1 Projective predicates
1.2 Ordinal notations
1.3 Effective transfinite induction
1.4 Recursive ordinals
1.5 -completeness and -boundedness
2 Hyperarithmetic theory
2.1 H-sets and -singletons
2.2 -ness and hyperarithmeticity
2.3 Spector’s Uniqueness Theorem
2.4 Hyperarithmetic reducibility
2.5 Some basis theorems and their applications
2.6 More on
2.7 Codes for sets
3 Admissibility and constructibility
3.1 Kripke–Platek set theory
3.2 Admissible sets
3.3 Constructibility
3.4 Projecta and master codes
3.5 ω-models
3.6 Coding structures
3.7 The Spector–Gandy Theorem
4 The theory of -sets
4.1 A -basis theorem
4.2 -uniformization
4.3 Characterizing thin -sets
4.4 -sets
5 Recursion-theoretic forcing
5.1 Ramified analytical hierarchy
5.2 Cohen forcing
5.3 Sacks forcing
5.4 Characterizing countable admissible ordinals
6 Set theory
6.1 Set-theoretic forcing
6.2 Some examples of forcing
6.3 A cardinality characterization of -sets
6.4 Large cardinals
6.5 Axiom of determinacy
6.6 Recursion-theoretic aspects of determinacy
Part II: The story of Turing degrees
7 Classification of jump operators
7.1 Uniformly degree invariant functions
7.2 Martin’s conjecture for uniformly degree invariant functions
7.3 The Posner–Robinson Theorem
7.4 Classifying order-preserving functions on 2ω
7.5 Pressdown functions
8 The construction of -sets
8.1 An introduction to inductive definition
8.2 Inductively defining -sets of reals
8.3 -maximal chains and antichains of Turing degrees
8.4 Martin’s conjecture for -functions
9 Independence results in recursion theory
9.1 Independent sets of Turing degrees
9.2 Embedding locally finite upper semilattices into 〈, ≤〉, ≤〉
9.3 Cofinal chains in
9.4 ω-homogeneity of the Turing degrees
9.5 Some general independence results
Part III: Hyperarithmetic degrees and perfect set property
10 Rigidity and biinterpretability of hyperdegrees
10.1 Embedding lattices into hyperdegrees
10.2 The rigidity of hyperdegrees
10.3 Biinterpretability
11 Basis theorems
11.1 A basis theorem for -sets of reals
11.2 An antibasis theorem for -sets
11.3 Perfect sets in L
Part IV: Higher randomness theory
12 Review of classical algorithmic randomness
12.1 Randomness via measure theory
12.2 Randomness via complexity theory
12.3 Lowness for randomness
13 More on hyperarithmetic theory
13.1 Hyperarithmetic measure theory
13.2 Coding sets above Kleene’s
13.3 Hyperarithmetic computation
14 The theory of higher randomness
14.1 Higher Kurtz randomness
14.2 and -Martin-Löf randomness-Martin-Löf randomness
14.3 -randomness
14.4 and -randomness
14.5 Kolmogorov complexity and randomness
14.6 Lowness for randomness
A Open problems
A.1 Hyperarithmetic theory
A.2 Set-theoretic problems in recursion theory
A.3 Higher randomness theory
B An interview with Gerald E. Sacks
C Notations and symbols
Endnotes
Bibliography
Index
Search in book...
Toggle Font Controls
Playlists
Add To
Create new playlist
Name your new playlist
Playlist description (optional)
Cancel
Create playlist
Sign In
Email address
Password
Forgot Password?
Create account
Login
or
Continue with Facebook
Continue with Google
Sign Up
Full Name
Email address
Confirm Email Address
Password
Login
Create account
or
Continue with Facebook
Continue with Google
Prev
Previous Chapter
Contents
Next
Next Chapter
1 An introduction to higher recursion theory
Part I:
Fundamental theory
Add Highlight
No Comment
..................Content has been hidden....................
You can't read the all page of ebook, please click
here
login for view all page.
Day Mode
Cloud Mode
Night Mode
Reset