Hyperarithmetically encodable sets
Author:
Robert M. Solovay
Journal:
Trans. Amer. Math. Soc. 239 (1978), 99122
MSC:
Primary 02F35; Secondary 02F27, 02F30, 02K99
MathSciNet review:
0491103
Fulltext 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 GalvinPrikry 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),
NorthHolland, Amsterdam, 1974, pp. 207–220. Studies in Logic
and the Foundations of Math., Vol. 79. MR 0392571
(52 #13388)
 [2]
P.
Aczel, Representability in some systems of second order
arithmetic, Israel J. Math. 8 (1970), 309–328.
MR
0269501 (42 #4396)
 [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
(51 #96)
 [4]
Fred
Galvin and Karel
Prikry, Borel sets and Ramsey’s theorem, J. Symbolic
Logic 38 (1973), 193–198. MR 0337630
(49 #2399)
 [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
(46 #8834)
 [6]
Carl
G. Jockusch Jr., Uniformly introreducible sets, J. Symbolic
Logic 33 (1968), 521–536. MR 0237330
(38 #5619)
 [7]
Carl
G. Jockusch Jr. and Robert
I. Soare, Encodability of Kleene’s 𝑂, J.
Symbolic Logic 38 (1973), 437–440. MR 0363842
(51 #97)
 [8]
Alexander
S. Kechris, The theory of countable analytical
sets, Trans. Amer. Math. Soc. 202 (1975), 259–297. MR 0419235
(54 #7259), http://dx.doi.org/10.1090/S00029947197504192357
 [9]
Azriel
Lévy, Definability in axiomatic set theory. I, Logic,
Methodology and Philos. Sci. (Proc. 1964 Internat. Congr.), NorthHolland,
Amsterdam, 1965, pp. 127–151. MR 0205827
(34 #5653)
 [10]
A. R. D. Mathias, On a generalization of Ramsey's theorem, Notices Amer. Math. Soc. 15 (1968), 931. Abstract #68TE19; Lecture Notes in Math., SpringerVerlag, Berlin (to appear).
 [11]
Hartley
Rogers Jr., Theory of recursive functions and effective
computability, McGrawHill Book Co., New York, 1967. MR 0224462
(37 #61)
 [12]
G.
E. Sacks and S.
G. Simpson, The 𝛼finite injury method, Ann. Math.
Logic 4 (1972), 343–367. MR 0369041
(51 #5277)
 [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
(43 #6079)
 [14]
Robert
I. Soare, Sets with no subset of higher degree, J. Symbolic
Logic 34 (1969), 53–56. MR 0263627
(41 #8228)
 [15]
Robert
M. Solovay, A model of settheory in which every set of reals is
Lebesgue measurable, Ann. of Math. (2) 92 (1970),
1–56. MR
0265151 (42 #64)
 [1]
 S. Aanderra, Inductive definitions and their closure ordinals, Generalized Recursion Theory (J. E. Fenstad and P. G. Hinman, eds.), NorthHolland, Amsterdam, 1974. MR 0392571 (52:13388)
 [2]
 P. Aczel, Representability in some systems of second order arithmetic, Israel J. Math. 8 (1970), 309328. MR 42 #4396. MR 0269501 (42:4396)
 [3]
 P. Aczel and W. Richter, Inductive definitions and analogues of large cardinals (Conference in Mathematical LogicLondon '70), Lecture Notes in Math., vol. 225, SpringerVerlag, Berlin and New York, 1972, pp. 19. MR 0363841 (51:96)
 [4]
 F. Galvin and K. Prikry, Borel sets and Ramsey's theorem, J. Symbolic Logic 38 (1973), 193198. MR 49 #2399. MR 0337630 (49:2399)
 [5]
 R. B. Jensen, The fine structure of the constructible hierarchy, Ann. Math. Logic 4 (1972), 229308; 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), 521536. 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), 437440. MR 0363842 (51:97)
 [8]
 A. Kechris, The theory of countable analytical sets, Trans. Amer. Math. Soc. 202 (1975), 259297. MR 0419235 (54:7259)
 [9]
 Azriel Lévy, Definability in axiomatic set theory. I, Logic, Methodology, and Philos. Sci. (Proc. 1964 Internat. Congr.), NorthHolland, Amsterdam, 1965, pp. 127151. 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 #68TE19; Lecture Notes in Math., SpringerVerlag, Berlin (to appear).
 [11]
 H. Rogers, Jr., Theory of recursive functions and effective computability, McGrawHill, 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), 343367. 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. 357381. MR 43 #6079. MR 0280359 (43:6079)
 [14]
 R. Soare, Sets with no subset of higher degree, J. Symbolic Logic 34 (1969), 5356. MR 41 #8228. MR 0263627 (41:8228)
 [15]
 R. Solovay, A model of settheory in which every set of reals is Lebesgue measurable, Ann. of Math. (2) 92 (1970), 156. 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:
http://dx.doi.org/10.1090/S00029947197804911037
PII:
S 00029947(1978)04911037
Keywords:
Hyperarithmetically encodable set,
Ramsey set,
selective ultrafilter,
inductive definition,
Mathias forcing,
GalvinPrikry theorem
Article copyright:
© Copyright 1978 American Mathematical Society
