Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)

 
 

 

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 $ \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 [Enhancements On Off] (What's this?)

  • [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 $ \alpha $-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)

Similar Articles

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

American Mathematical Society