Hyperarithmetic theory is the first step beyond classical recursion theory. It is the primary source of ideas and examples in higher recursion theory. It is also a crossroad for several areas of mathematical logic: in set theory it is an initial segment of Godel's L; in model theory, the least admissible set after ; in descriptive set theory, the setting for effective arguments. In this book, hyperarithmetic theory is developed at length and used to lift classical recursion theory from integers to recursive ordinals (metarecursion). Two further liftings are then made, first ordinals ( -recursion) and then to sets (E-recursion). Techniques such as finite and infinite injury, forcing and fine structure and extended and combined Dynamic and syntactical methods are contrasted. Several notions of reducibility and computation are compared. Post's problem is answere affirmatively in all three settings. This long-awaited volume of the -series will be a "Must" for all working in the field.
Author(s): Gerald E. Sacks
Series: Perspectives in Mathematical Logic
Edition: 1
Publisher: Springer
Year: 1990
Language: English
Pages: 359
Preface......Page 11
Contents......Page 15
Part A. Hyperarithmetic Sets......Page 19
1. Analytical predicates......Page 21
2. Notations for ordinals......Page 26
3. Effective transfinite recursion......Page 28
4. Recursive ordinals......Page 33
5. Ordinal analysis of Π^1_1 sets......Page 36
1. Hyperarithmetic implies Δ^1_1......Page 40
2. Δ^1_1 implies hyperarithmetic......Page 46
3. Selection and reduction......Page 50
4. Π^0_2 singletons......Page 55
5. Hyperarithmetic reducibility......Page 60
6. Incomparable hyperdegrees via measure......Page 64
7. The hyperjump......Page 66
1. Basis theorems......Page 70
2. Unique notations for ordinals......Page 73
3. Hyperarithmetic quantifiers......Page 77
4. The ramified analytic hierachy......Page 80
5. Kreisel compactness......Page 88
6. Perfect subsets of Σ^1_1 sets......Page 89
7. Kreisel's basis theorem......Page 92
8. Inductive definitions......Page 94
9. Π^1_1 singletons......Page 99
1. Measure-theoretic uniformity......Page 106
2. Measure-theoretic basis theorems......Page 110
3. Cohen forcing......Page 112
4. Perfect forcing......Page 116
5. Minimal hyperdegrees......Page 121
6. Louveau separation......Page 125
Part B. Metarecursion......Page 131
1. Fundamentals of metarecursion......Page 133
2. Metafinite computations......Page 139
3. Relative metarecursiveness......Page 142
4. Regularity......Page 147
1. Hyperregular sets......Page 153
2. Two priority arguments......Page 156
3. Simpson's dichotomy......Page 164
Part C. α-Recursion......Page 167
1. Σ_1 admissibility......Page 169
2. The Σ_1 projectum......Page 175
3. Relative α-recursiveness......Page 179
4. Existence of regular sets......Page 183
5. Hyperregularity......Page 185
1. α-finite injury via α*......Page 193
2. α-finite injury and tameness......Page 196
3. Dynamic versus fine-structure......Page 202
4. Σ_1 doing the work of Σ_2......Page 212
1. Shore's splitting theorem......Page 222
2. Further fine structure......Page 225
3. Density for ω......Page 230
4. Preliminaries to α-density......Page 234
5. Shore's density theorem......Page 236
6. β-recursion theory......Page 245
Part D. E-Recursion......Page 249
1. Partial E-recursive functions......Page 251
2. Computations......Page 255
3. Reflection......Page 260
4. Gandy selection......Page 262
5. Moschovakis witnesses......Page 267
1. Set forcing over L(κ)......Page 277
2. Countably closed forcing......Page 283
3. Enumerable forcing relations......Page 288
4. Countable chain-condition forcing......Page 291
5. Normann selection and singular cardinals......Page 297
6. Further forcing......Page 299
XII. Selection and k-Sections......Page 301
1. Grilliot selection......Page 302
2. Moschovakis selection......Page 305
3. Plus-one theorems......Page 308
4. Harrington's plus-two theorem......Page 317
5. Selection with additional predicates......Page 322
1. Regular sets......Page 327
2. Projecta and cofinalities......Page 331
3. van de Wiele's Theorem......Page 343
4. Post's problem for E-recursion......Page 346
5. Slaman's splitting and density theorems......Page 351
Bibliography......Page 357
Subject Index......Page 361
