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, 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).
- 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
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