The theory of countable analytical sets

Kechris, Alexander S.

doi:10.1090/S0002-9947-1975-0419235-7

The theory of countable analytical sets
HTML articles powered by AMS MathViewer

by Alexander S. Kechris PDF

Trans. Amer. Math. Soc. 202 (1975), 259-297 Request permission

Abstract:

The purpose of this paper is the study of the structure of countable sets in the various levels of the analytical hierarchy of sets of reals. It is first shown that, assuming projective determinacy, there is for each odd $n$ a largest countable $\Pi _n^1$ set of reals, ${\mathcal {C}_n}$ (this is also true for $n$ even, replacing $\Pi _n^1$ by $\Sigma _n^1$ and has been established earlier by Solovay for $n = 2$ and by Moschovakis and the author for all even $n > 2$). The internal structure of the sets ${\mathcal {C}_n}$ is then investigated in detail, the point of departure being the fact that each ${\mathcal {C}_n}$ is a set of $\Delta _n^1$-degrees, wellordered under their usual partial ordering. Finally, a number of applications of the preceding theory is presented, covering a variety of topics such as specification of bases, $\omega$-models of analysis, higher-level analogs of the constructible universe, inductive definability, etc.

References

Stȧl Aanderaa, Inductive definitions and their closure ordinals, Generalized recursion theory (Proc. Sympos., Univ. Oslo, Oslo, 1972) Studies in Logic and the Foundations of Math., Vol. 79, North-Holland, Amsterdam, 1974, pp. 207–220. MR 0392571
Peter Aczel, Infinitary logic and the Barwise compactness theorem, The Proceedings of the Bertrand Russell Memorial Conference (Uldum, 1971), Bertrand Russell Memorial Logic Conf., Leeds, 1973, pp. 234–277. MR 0363795
Peter Aczel and Wayne Richter, Inductive definitions and analogues of large cardinals, Conference in Mathematical Logic—London ’70 (Proc. Conf., Bedford Coll., London, 1970) Lecture Notes in Math., Vol. 255, Springer, Berlin, 1972, pp. 1–9. MR 0363841
J. W. Addison and Yiannis N. Moschovakis, Some consequences of the axiom of definable determinateness, Proc. Nat. Acad. Sci. U.S.A. 59 (1968), 708–712. MR 221927, DOI 10.1073/pnas.59.3.708
Jon Barwise, Infinitary logic and admissible sets, J. Symbolic Logic 34 (1969), no. 2, 226–252. MR 406760, DOI 10.2307/2271099
Jon Barwise and Edward Fisher, The Shoenfield absoluteness lemma, Israel J. Math. 8 (1970), 329–339. MR 278934, DOI 10.1007/BF02798679
K. J. Barwise, R. O. Gandy, and Y. N. Moschovakis, The next admissible set, J. Symbolic Logic 36 (1971), 108–120. MR 300876, DOI 10.2307/2271519
George Boolos and Hilary Putnam, Degrees of unsolvability of constructible sets of integers, J. Symbolic Logic 33 (1968), 497–513. MR 239977, DOI 10.2307/2271357
Morton Davis, Infinite games of perfect information, Advances in Game Theory, Princeton Univ. Press, Princeton, N.J., 1964, pp. 85–101. MR 0170727
Jens Erik Fenstad, The axiom of determinateness, Proceedings of the Second Scandinavian Logic Symposium (Univ. Oslo, Oslo, 1970) Studies in Logic and the Foundations of Mathematics, Vol. 63, North-Holland, Amsterdam, 1971, pp. 41–61. MR 0332479
R. O. Gandy, G. Kreisel, and W. W. Tait, Set existence, Bull. Acad. Polon. Sci. Sér. Sci. Math. Astronom. Phys. 8 (1960), 577–582. MR 159747

The largest constructible $\Pi _1^1$ set

A basis theorem for Borel sets

Projective ordinals and countable analytical sets

Countable analytical sets and higher-level analogs of

37

Alexander S. Kechris, Measure and category in effective descriptive set theory, Ann. Math. Logic 5 (1972/73), 337–384. MR 369072, DOI 10.1016/0003-4843(73)90012-0

Descriptive set theory

Alexander S. Kechris and Yiannis N. Moschovakis, Two theorems about projective sets, Israel J. Math. 12 (1972), 391–399. MR 323544, DOI 10.1007/BF02764630

Notes on the theory of scales

H. Jerome Keisler, Model theory for infinitary logic. Logic with countable conjunctions and finite quantifiers, Studies in Logic and the Foundations of Mathematics, Vol. 62, North-Holland Publishing Co., Amsterdam-London, 1971. MR 0344115

Topologie

36

Stephen Leeds and Hilary Putnam, An intrinsic characterization of the hierarchy of constructible sets of integers, Logic Colloquium ’69 (Proc. Summer School and Colloq., Manchester, 1969), North-Holland, Amsterdam, 1971, pp. 311–350. MR 0419200

Systems of notations and the constructible hierarchy

Richard Mansfield, Perfect subsets of definable sets of real numbers, Pacific J. Math. 35 (1970), 451–457. MR 280380, DOI 10.2140/pjm.1970.35.451
Richard Mansfield, A Souslin operation for $\Pi ^{1}_{2}$, Israel J. Math. 9 (1971), 367–379. MR 297575, DOI 10.1007/BF02771687
Donald A. Martin, The axiom of determinateness and reduction principles in the analytical hierarchy, Bull. Amer. Math. Soc. 74 (1968), 687–689. MR 227022, DOI 10.1090/S0002-9904-1968-11995-0
D. A. Martin and R. M. Solovay, A basis theorem for $\sum _3^1$ sets of reals, Ann. of Math. (2) 89 (1969), 138–159. MR 255391, DOI 10.2307/1970813

Basis theorems for $\Pi _{2k}^1$ sets of reals

Yiannis N. Moschovakis, Determinacy and prewellorderings of the continuum, Mathematical Logic and Foundations of Set Theory (Proc. Internat. Colloq., Jerusalem, 1968) North-Holland, Amsterdam, 1970, pp. 24–62. MR 0280362
Yiannis N. Moschovakis, Uniformization in a playful universe, Bull. Amer. Math. Soc. 77 (1971), 731–736. MR 285390, DOI 10.1090/S0002-9904-1971-12789-1
Y. N. Moschovakis, Analytical definability in a playful universe, Logic, methodology and philosophy of science, IV (Proc. Fourth Internat. Congress, Bucharest, 1971) Studies in Logic and Foundations of Math., Vol. 74, North-Holland, Amsterdam, 1973, pp. 77–85. MR 0540769

Elementary induction on abstract structures

Yiannis N. Moschovakis, Structural characterizations of classes of relations, Generalized recursion theory (Proc. Sympos., Univ. Oslo, Oslo, 1972) Studies in Logic and the Foundations of Math., Vol. 79, North-Holland, Amsterdam, 1974, pp. 53–79. MR 0411953
Jan Mycielski, On the axiom of determinateness, Fund. Math. 53 (1963/64), 205–224. MR 161787, DOI 10.4064/fm-53-2-205-224
Wayne Richter, Constructive transfinite number classes, Bull. Amer. Math. Soc. 73 (1967), 261–265. MR 207557, DOI 10.1090/S0002-9904-1967-11710-5
Hartley Rogers Jr., Theory of recursive functions and effective computability, McGraw-Hill Book Co., New York-Toronto, Ont.-London, 1967. MR 0224462
Gerald E. Sacks, Countable admissible ordinals and hyperdegrees, Advances in Math. 20 (1976), no. 2, 213–262. MR 429523, DOI 10.1016/0001-8708(76)90187-0
Joseph R. Shoenfield, Mathematical logic, Addison-Wesley Publishing Co., Reading, Mass.-London-Don Mills, Ont., 1967. MR 0225631
Jack H. Silver, Measurable cardinals and $\Delta ^{1}_{3}$ well-orderings, Ann. of Math. (2) 94 (1971), 414–446. MR 299469, DOI 10.2307/1970765
Robert M. Solovay, On the cardinality of $\sum _{2}^{1}$ sets of reals, Foundations of Mathematics (Symposium Commemorating Kurt Gödel, Columbus, Ohio, 1966) Springer, New York, 1969, pp. 58–73. MR 0277382
Yoshindo Suzuki, A complete classification of the $\Delta _{2}^{1}$-functions, Bull. Amer. Math. Soc. 70 (1964), 246–253. MR 158819, DOI 10.1090/S0002-9904-1964-11104-6
Hisao Tanaka, A property of arithmetic sets, Proc. Amer. Math. Soc. 31 (1972), 521–524. MR 286661, DOI 10.1090/S0002-9939-1972-0286661-1
Yiannis N. Moschovakis, On nonmonotone inductive definability, Fund. Math. 82 (1974/75), 39–83. MR 354373, DOI 10.4064/fm-82-1-39-83

Contributions to recursion theory on higher types