## Hyperarithmetically encodable sets

HTML articles powered by AMS MathViewer

- by Robert M. Solovay PDF
- Trans. Amer. Math. Soc.
**239**(1978), 99-122 Request permission

## Abstract:

We say that a set of integers,*A*, is hyperarithmetically (recursively) encodable, if every infinite set of integers

*X*contains an infinite subset

*Y*in which

*A*is hyperarithmetical (recursive). We show that the recursively encodable sets are precisely the hyperarithmetic sets. Let $\sigma$ be the closure ordinal of a universal $\Sigma _1^1$ inductive definition. Then

*A*is hyperarithmetically encodable iff it is constructible before stage $\sigma$. We also prove an effective version of the Galvin-Prikry results that open sets, and more generally Borel sets, are Ramsey, and in the case of open sets prove that our improvement is optimal.

## 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** - P. Aczel,
*Representability in some systems of second order arithmetic*, Israel J. Math.**8**(1970), 309–328. MR**269501**, DOI 10.1007/BF02798678 - 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** - Fred Galvin and Karel Prikry,
*Borel sets and Ramsey’s theorem*, J. Symbolic Logic**38**(1973), 193–198. MR**337630**, DOI 10.2307/2272055 - R. Björn Jensen,
*The fine structure of the constructible hierarchy*, Ann. Math. Logic**4**(1972), 229–308; erratum, ibid. 4 (1972), 443. With a section by Jack Silver. MR**309729**, DOI 10.1016/0003-4843(72)90001-0 - Carl G. Jockusch Jr.,
*Uniformly introreducible sets*, J. Symbolic Logic**33**(1968), 521–536. MR**237330**, DOI 10.2307/2271359 - Carl G. Jockusch Jr. and Robert I. Soare,
*Encodability of Kleene’s $O$*, J. Symbolic Logic**38**(1973), 437–440. MR**363842**, DOI 10.2307/2273040 - Alexander S. Kechris,
*The theory of countable analytical sets*, Trans. Amer. Math. Soc.**202**(1975), 259–297. MR**419235**, DOI 10.1090/S0002-9947-1975-0419235-7 - Azriel Lévy,
*Definability in axiomatic set theory. I*, Logic, Methodology and Philos. Sci. (Proc. 1964 Internat. Congr.), North-Holland, Amsterdam, 1965, pp. 127–151. MR**0205827**
A. R. D. Mathias, - Hartley Rogers Jr.,
*Theory of recursive functions and effective computability*, McGraw-Hill Book Co., New York-Toronto, Ont.-London, 1967. MR**0224462** - G. E. Sacks and S. G. Simpson,
*The $\alpha$-finite injury method*, Ann. Math. Logic**4**(1972), 343–367. MR**369041**, DOI 10.1016/0003-4843(72)90004-6 - J. R. Shoenfield,
*Unramified forcing*, Axiomatic Set Theory (Proc. Sympos. Pure Math., Vol. XIII, Part I, Univ. California, Los Angeles, Calif., 1967) Amer. Math. Soc., Providence, R.I., 1971, pp. 357–381. MR**0280359** - Robert I. Soare,
*Sets with no subset of higher degree*, J. Symbolic Logic**34**(1969), 53–56. MR**263627**, DOI 10.2307/2270981 - Robert M. Solovay,
*A model of set-theory in which every set of reals is Lebesgue measurable*, Ann. of Math. (2)**92**(1970), 1–56. MR**265151**, DOI 10.2307/1970696

*On a generalization of Ramsey’s theorem*, Notices Amer. Math. Soc.

**15**(1968), 931. Abstract #68T-E19; Lecture Notes in Math., Springer-Verlag, Berlin (to appear).

## Additional Information

- © Copyright 1978 American Mathematical Society
- Journal: Trans. Amer. Math. Soc.
**239**(1978), 99-122 - MSC: Primary 02F35; Secondary 02F27, 02F30, 02K99
- DOI: https://doi.org/10.1090/S0002-9947-1978-0491103-7
- MathSciNet review: 0491103