Hyperarithmetically encodable sets

Author:
Robert M. Solovay

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

Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 be the closure ordinal of a universal inductive definition. Then *A* is hyperarithmetically encodable iff it is constructible before stage .

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.

**[1]**StÈ§l Aanderaa,*Inductive definitions and their closure ordinals*, Generalized recursion theory (Proc. Sympos., Univ. Oslo, Oslo, 1972), North-Holland, Amsterdam, 1974, pp. 207–220. Studies in Logic and the Foundations of Math., Vol. 79. MR**0392571****[2]**P. Aczel,*Representability in some systems of second order arithmetic*, Israel J. Math.**8**(1970), 309–328. MR**0269501**, https://doi.org/10.1007/BF02798678**[3]**Peter Aczel and Wayne Richter,*Inductive definitions and analogues of large cardinals*, Conference in Mathematical Logic—London ’70 (Proc. Conf., Bedford Coll., London, 1970) Springer, Berlin, 1972, pp. 1–9. Lecture Notes in Math., Vol. 255. MR**0363841****[4]**Fred Galvin and Karel Prikry,*Borel sets and Ramsey’s theorem*, J. Symbolic Logic**38**(1973), 193–198. MR**0337630**, https://doi.org/10.2307/2272055**[5]**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**0309729**, https://doi.org/10.1016/0003-4843(72)90001-0**[6]**Carl G. Jockusch Jr.,*Uniformly introreducible sets*, J. Symbolic Logic**33**(1968), 521–536. MR**0237330**, https://doi.org/10.2307/2271359**[7]**Carl G. Jockusch Jr. and Robert I. Soare,*Encodability of Kleene’s 𝑂*, J. Symbolic Logic**38**(1973), 437–440. MR**0363842**, https://doi.org/10.2307/2273040**[8]**Alexander S. Kechris,*The theory of countable analytical sets*, Trans. Amer. Math. Soc.**202**(1975), 259–297. MR**0419235**, https://doi.org/10.1090/S0002-9947-1975-0419235-7**[9]**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****[10]**A. R. D. Mathias,*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).**[11]**Hartley Rogers Jr.,*Theory of recursive functions and effective computability*, McGraw-Hill Book Co., New York-Toronto, Ont.-London, 1967. MR**0224462****[12]**G. E. Sacks and S. G. Simpson,*The 𝛼-finite injury method*, Ann. Math. Logic**4**(1972), 343–367. MR**0369041**, https://doi.org/10.1016/0003-4843(72)90004-6**[13]**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****[14]**Robert I. Soare,*Sets with no subset of higher degree*, J. Symbolic Logic**34**(1969), 53–56. MR**0263627**, https://doi.org/10.2307/2270981**[15]**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**0265151**, https://doi.org/10.2307/1970696

Retrieve articles in *Transactions of the American Mathematical Society*
with MSC:
02F35,
02F27,
02F30,
02K99

Retrieve articles in all journals with MSC: 02F35, 02F27, 02F30, 02K99

Additional Information

DOI:
https://doi.org/10.1090/S0002-9947-1978-0491103-7

Keywords:
Hyperarithmetically encodable set,
Ramsey set,
selective ultrafilter,
inductive definition,
Mathias forcing,
Galvin-Prikry theorem

Article copyright:
© Copyright 1978
American Mathematical Society