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. The theory set out in this volume, the ninth publication in the Perspectives in Logic series, is the result of the meeting and common development of two currents of mathematical research: descriptive set theory and recursion theory. Both are concerned with notions of definability and with the classification of mathematical objects according to their complexity. These are the common themes which run through the topics discussed here. The author develops a general theory from which the results of both areas can be derived, making these common threads clear.
Author(s): Peter G. Hinman
Series: Perspectives in Logic 9
Publisher: Cambridge University Press
Year: 2017
Language: English
Pages: 494
Contents......Page 12
Introduction......Page 14
Part A. Basic Notions of Definability......Page 18
1. Logic and Set Theory......Page 20
2. Topology and Measure......Page 28
3. Inductive Definitions......Page 35
Chapter II. Ordinary Recursion Theory......Page 40
1. Primitive Recursion......Page 41
2. Recursive Functionals and Relations......Page 50
3. Normal Forms......Page 59
4. Semi-Recursive Relations......Page 65
5. Relativization......Page 75
1. The Arithmetical Hierarchy......Page 82
2. The Analytical Hierarchy......Page 93
3. Inductive Definability......Page 102
4. Implicit Definability and Bases......Page 119
5. Definability in Formal Languages for Arithmetic......Page 127
6. Arithmetical Forcing......Page 137
PartB. The Analytical and Projective Hierarchies......Page 146
1. ∏ 1 1 and Well-Orderings......Page 148
2. The Boundedness Principle and Other Applications......Page 156
3. The Borel Hierarchy......Page 169
4. The Effective Borel and Hyperarithmetical Hierarchies......Page 176
5. Cardinality, Measurability and Category......Page 193
6. Continuous Images......Page 201
7. Uniformization......Page 207
Chapter V. ∆ 1 2 and Beyond......Page 214
1. The Pre-Wellordering Property......Page 215
2. The Hypothesis of Constructibility......Page 227
3. The Hypothesis of Projective Determinacy......Page 234
4. Classical Hierarchies in ∆ 1 r......Page 249
5. Effective Hierarchies in ∆ 1 r......Page 259
6. A Hierarchy for ∆ 1 2......Page 264
Part C. Generalized Recursion Theories......Page 270
1. Basic Properties......Page 272
2. Substitution Theorems......Page 284
3. Ordinal Comparison......Page 297
4. Relations Semi-Recursive in a Type-2 Functional......Page 304
5. Hierarchies of Relations Recursive in a Type-2 Functional......Page 320
6. Extended Functional......Page 328
7. Recursive Type-3 Functional and Relations......Page 348
1. Basic Properties......Page 356
2. Relations Semi-Recursive in a Type-3 Functional......Page 363
3. Hierarchies of Relations Recursive in a Type-3 Functional......Page 373
4. Higher Types......Page 376
Chapter. VIII. Recursion on Ordinals......Page 384
1. Recursive Ordinal Functions......Page 385
2. Recursively Regular Ordinals......Page 396
3. Ordinal Recursion and the Analytical Hierarchy......Page 406
4. Ordinal Recursion and Type-2 Functionals......Page 416
5. Stability......Page 425
6. Recursively Large Ordinals......Page 432
7. Ordinal Recursion and Constructible Sets......Page 443
Epilogue......Page 458
References......Page 472
Global Notational Conventions......Page 480
Special Notations......Page 482
Index......Page 486
