Since their inception, the Perspectives in Logic and Lecture Notes in Logic series have published seminal works by leading logicians. Many of the original books in the series have been unavailable for years, but they are now in print once again. This volume, the second publication in the Perspectives in Logic series, is an almost self-contained introduction to higher recursion theory, in which the reader is only assumed to know the basics of classical recursion theory. The book is divided into four parts: hyperarithmetic sets, metarecursion, α-recursion, and E-recursion. This text is essential reading for all researchers in the field.
Author(s): Gerald E. Sacks
Series: Perspectives in Logic 2
Publisher: Cambridge University Press
Year: 2017
Language: English
Pages: 362
Contents......Page 13
Part A. Hyperarithmetic Sets......Page 18
1. Analytical Predicates......Page 20
2. Notations for Ordinals......Page 25
3. Effective Transfinite Recursion......Page 27
4. Recursive Ordinals......Page 32
5. Ordinal Analysis of ∏ 1 1 Sets......Page 35
1. Hyperarithmetic Implies ∆ 1 1......Page 39
2. ∆ 1 1 Implies Hyperarithmetic......Page 45
3. Selection and Reduction......Page 49
4. ∏ 0 2 Singletons......Page 54
5. Hyperarithmetic Reducibility......Page 59
6. Incomparable Hyperdegrees Via Measure......Page 63
7. The Hyperjump......Page 65
1. Basis Theorems......Page 69
2. Unique Notations for Ordinals......Page 72
3. Hyperarithmetic Quantifiers......Page 76
4. The Ramified Analytic Hierarchy......Page 79
5. Kreisel Compactness......Page 87
6. Perfect Subsets of ∑ 1 1 Sets......Page 88
7. Kreisel's Basis Theorem......Page 91
8. Inductive Definitions......Page 93
9. ∏ 1 1 Singletons......Page 98
1. Measure-Theoretic Uniformity......Page 105
2. Measure-Theoretic Basis Theorems......Page 109
3. Cohen Forcing......Page 111
4. Perfect Forcing......Page 115
5. Minimal Hyperdegrees......Page 120
6. Louveau Separation......Page 124
Part B. Metarecursion......Page 130
1. Fundamentals of Metarecursion......Page 132
2. Metafinite Computations......Page 138
3. Relative Metarecursiveness......Page 141
4. Regularity......Page 146
1. Hyperregular Sets......Page 152
2. Two Priority Arguments......Page 155
3. Simpson's Dichotomy......Page 163
Part C. α-Recursion......Page 166
1. ∑1 Admissibility......Page 168
2. The ∑1 Projectum......Page 174
3. Relative α-Recursiveness......Page 178
4. Existence of Regular Sets......Page 182
5. Hyperregularity......Page 184
1. α-Finite Injury via α*......Page 192
2. α-Finite Injury and Tameness......Page 195
3. Dynamic Versus Fine-Structure......Page 201
4. ∑1 Doing the Work of ∑2......Page 211
1. Shore's Splitting Theorem......Page 221
2. Further Fine Structure......Page 224
3. Density for ω......Page 229
4. Preliminaries to α-Density......Page 233
5. Shore's Density Theorem......Page 235
6. β-Recursion Theory......Page 244
PartD. E-Recursion......Page 248
1. Partial E-Recursive Functions......Page 250
2. Computations......Page 254
3. Reflection......Page 259
4. Gandy Selection......Page 261
5. Moschovakis Witnesses......Page 266
1. Set Forcing over L (k)......Page 276
2. Countably Closed Forcing......Page 282
3. Enumerable Forcing Relations......Page 287
4. Countable-Chain-Condition Forcing......Page 290
5. Normann Selection and Singular Cardinals......Page 296
6. Further Forcing......Page 298
Chapter XII. Selection and k-Sections......Page 300
1. Grilliot Selection......Page 301
2. Moschovakis Selection......Page 304
3. Plus-One Theorems......Page 307
4. Harrington's Plus-Two Theorem......Page 316
5. Selection with Additional Predicates......Page 321
1. Regular Sets......Page 326
2. Projecta and Cofinalities......Page 330
3. van de Wiele's Theorem......Page 342
4. Post's Problem for E-Recursion......Page 345
5. Slaman's Splitting and Density Theorems......Page 350
Bibliography......Page 356
Subject Index......Page 360
