## The theory of countable analytical sets

HTML articles powered by AMS MathViewer

- by Alexander S. Kechris
- Trans. Amer. Math. Soc.
**202**(1975), 259-297 - DOI: https://doi.org/10.1090/S0002-9947-1975-0419235-7
- PDF | 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**
D. Guaspari, - 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
—, - 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
—, - 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**
K. Kuratowski, - 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**
M. Lucian, - 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
—, - 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**
—, - 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-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
L. A. Harrington,

*The largest constructible $\Pi _1^1$ set*(to appear). L. Harrington,

*A basis theorem for Borel sets*, Recursive Function Theory: Newsletter, #3, Oct. 1972. J. Harrison, Doctoral dissertation, Stanford University, Stanford, Calif., 1967. A. S. Kechris,

*Projective ordinals and countable analytical sets*, Ph.D. Thesis, UCLA, 1972. —,

*Countable analytical sets and higher-level analogs of*$L$, J. Symbolic Logic

**37**(1972), 776 (abstract).

*Descriptive set theory*, Lecture Notes, M.I.T., Cambridge, Mass., Spring, 1973.

*Notes on the theory of scales*, Circulated multilithed manuscript, 1971.

*Topologie*. Vol. 1, Monografie Mat., Tom 20, PWN, Warsaw, 1948; English transl., Academic Press, New York, 1966. MR

**36**#840.

*Systems of notations and the constructible hierarchy*, Harvard University, Cambridge, Mass., 1972.

*Basis theorems for $\Pi _{2k}^1$ sets of reals*(to appear).

*Elementary induction on abstract structures*, North-Holland, Amsterdam, 1974.

*Contributions to recursion theory on higher types*, Ph.D. Thesis, M.I.T., Cambridge, Mass., 1973.

## Bibliographic Information

- © Copyright 1975 American Mathematical Society
- Journal: Trans. Amer. Math. Soc.
**202**(1975), 259-297 - MSC: Primary 02K30; Secondary 02F35
- DOI: https://doi.org/10.1090/S0002-9947-1975-0419235-7
- MathSciNet review: 0419235