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 Free Access

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]**S. Aanderra,*Inductive definitions and their closure ordinals*, Generalized Recursion Theory (J. E. Fenstad and P. G. Hinman, eds.), North-Holland, Amsterdam, 1974. MR**0392571 (52:13388)****[2]**P. Aczel,*Representability in some systems of second order arithmetic*, Israel J. Math.**8**(1970), 309-328. MR**42**#4396. MR**0269501 (42:4396)****[3]**P. Aczel and W. Richter,*Inductive definitions and analogues of large cardinals*(Conference in Mathematical Logic-London '70), Lecture Notes in Math., vol. 225, Springer-Verlag, Berlin and New York, 1972, pp. 1-9. MR**0363841 (51:96)****[4]**F. Galvin and K. Prikry,*Borel sets and Ramsey's theorem*, J. Symbolic Logic**38**(1973), 193-198. MR**49**#2399. MR**0337630 (49:2399)****[5]**R. B. Jensen,*The fine structure of the constructible hierarchy*, Ann. Math. Logic**4**(1972), 229-308; erratum,*ibid*.**4**(1972), 443. MR**46**#8834. MR**0309729 (46:8834)****[6]**C. G. Jockusch, Jr.,*Uniformly introreducible sets*, J. Symbolic Logic**33**(1968), 521-536. MR**38**#5619. MR**0237330 (38:5619)****[7]**C. G. Jockusch, Jr. and R. I. Soare,*Encodability of Kleene's O*, J. Symbolic Logic**38**(1973), 437-440. MR**0363842 (51:97)****[8]**A. Kechris,*The theory of countable analytical sets*, Trans. Amer. Math. Soc.**202**(1975), 259-297. MR**0419235 (54:7259)****[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**34**#5653. MR**0205827 (34:5653)****[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]**H. Rogers, Jr.,*Theory of recursive functions and effective computability*, McGraw-Hill, New York, 1967. MR**37**#61. MR**0224462 (37:61)****[12]**G. Sacks and S. Simpson,*The*-*finite injury method*, Ann. Math. Logic**4**(1972), 343-367. MR**0369041 (51:5277)****[13]**J. R. Shoenfield,*Unramified forcing*, Proc. Sympos. Pure Math., vol. 13, part 1, Amer. Math. Soc., Providence, R. I., 1971, pp. 357-381. MR**43**#6079. MR**0280359 (43:6079)****[14]**R. Soare,*Sets with no subset of higher degree*, J. Symbolic Logic**34**(1969), 53-56. MR**41**#8228. MR**0263627 (41:8228)****[15]**R. Solovay,*A model of set-theory in which every set of reals is Lebesgue measurable*, Ann. of Math. (2)**92**(1970), 1-56. MR**42**#64. MR**0265151 (42:64)**

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