Recursion Theory : Computational Aspects of Definability.
Chong, Chi Tat.
Recursion Theory : Computational Aspects of Definability. - 1st ed. - 1 online resource (322 pages) - De Gruyter Series in Logic and Its Applications Series ; v.8 . - De Gruyter Series in Logic and Its Applications Series .
Intro -- Preface -- Contents -- 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 ?1/1-completeness and S1/1 boundedness -- 2 Hyperarithmetic theory -- 2.1 H-sets and ? -- 2-singletons -- 2.2 ?1/1-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 O -- 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 ?1/1-sets -- 4.1 A ? 1/1-basis theorem -- 4.2 ?1/1-uniformization -- 4.3 Characterizing thin ?1/1-sets -- 4.4 S1/2-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 ?1/1-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 ?1/1-sets -- 8.1 An introduction to inductive definition -- 8.2 Inductively defining ?1/1-sets of reals -- 8.3 ? 1/1-maximal chains and antichains of Turing degrees -- 8.4 Martin's conjecture for ?1/1-functions. 9 Independence results in recursion theory -- 9.1 Independent sets of Turing degrees -- 9.2 Embedding locally finite upper semilattices into ?D, =? -- 9.3 Cofinal chains in D -- 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 ?1/1-sets of reals -- 11.2 An antibasis theorem for ?0/1-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 O -- 13.3 Hyperarithmetic computation -- 14 The theory of higher randomness -- 14.1 Higher Kurtz randomness -- 14.2 ?1/1 and ?1/1-Martin-Löf randomness -- 14.3 ?1/1-randomness -- 14.4 ?1/2 and S1/2-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 -- Bibliography -- Index.
The series is devoted to the publication of high-level monographs on all areas of mathematical logic and its applications. It is addressed to advanced students and research mathematicians, and may also serve as a guide for lectures and for seminars at the graduate level.
9783110275643
Algebra.
Mathematics.
Recursion theory.
Recursive functions.
Electronic books.
QA9.6 .C384 2015
511.3/5
Recursion Theory : Computational Aspects of Definability. - 1st ed. - 1 online resource (322 pages) - De Gruyter Series in Logic and Its Applications Series ; v.8 . - De Gruyter Series in Logic and Its Applications Series .
Intro -- Preface -- Contents -- 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 ?1/1-completeness and S1/1 boundedness -- 2 Hyperarithmetic theory -- 2.1 H-sets and ? -- 2-singletons -- 2.2 ?1/1-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 O -- 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 ?1/1-sets -- 4.1 A ? 1/1-basis theorem -- 4.2 ?1/1-uniformization -- 4.3 Characterizing thin ?1/1-sets -- 4.4 S1/2-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 ?1/1-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 ?1/1-sets -- 8.1 An introduction to inductive definition -- 8.2 Inductively defining ?1/1-sets of reals -- 8.3 ? 1/1-maximal chains and antichains of Turing degrees -- 8.4 Martin's conjecture for ?1/1-functions. 9 Independence results in recursion theory -- 9.1 Independent sets of Turing degrees -- 9.2 Embedding locally finite upper semilattices into ?D, =? -- 9.3 Cofinal chains in D -- 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 ?1/1-sets of reals -- 11.2 An antibasis theorem for ?0/1-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 O -- 13.3 Hyperarithmetic computation -- 14 The theory of higher randomness -- 14.1 Higher Kurtz randomness -- 14.2 ?1/1 and ?1/1-Martin-Löf randomness -- 14.3 ?1/1-randomness -- 14.4 ?1/2 and S1/2-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 -- Bibliography -- Index.
The series is devoted to the publication of high-level monographs on all areas of mathematical logic and its applications. It is addressed to advanced students and research mathematicians, and may also serve as a guide for lectures and for seminars at the graduate level.
9783110275643
Algebra.
Mathematics.
Recursion theory.
Recursive functions.
Electronic books.
QA9.6 .C384 2015
511.3/5