In the context of Galvin-Prikry generalization of Ramsey's theorem, I read in a couple of papers ([1],[2]) that Solovay [3] proved that if $P$ is a clopen of $[\mathbb{N}]^{\mathbb{N}}$ then the set of homogeneous solutions for $P$ (i.e. the set of infinite sets $A$ s.t. either $[A]^\mathbb{N}\subset P$ or $[A]^\mathbb{N}\cap P = \emptyset$) always contains a hyperarithmetical set (this is what Clote calls a basis theorem).

I don't see this results being stated explicitly in Solovay's paper, so I guess it follows as a corollary of some other result. Could you please help me in identifying the theorem(s) in [3] from which the "basis theorem" follows?

[1] Simpson, Stephen G., Sets which do not have subsets of every higher degree, J. Symb. Log. 43, 135-138 (1978). ZBL0402.03040.

[2] Clote, Peter, A recursion theoretic analysis of the clopen Ramsey theorem, J. Symb. Log. 49, 376-400 (1984). ZBL0574.03030.

[3] Solovay, Robert M., Hyperarithmetically encodable sets, Trans. Am. Math. Soc. 239, 99-122 (1978). ZBL0411.03039.

  • 1
    $\begingroup$ Am I missing something, or is it Theorem 1.8 in [3] you are looking for? $\endgroup$ – Arno Nov 5 '18 at 21:02
  • $\begingroup$ Maybe...but if there is a solution that lands in $W$ and another one that avoids it I don't see how we could use the theorem 1.8 of [3] to conclude anything on how complicated these solutions are. $\endgroup$ – Manlio Nov 5 '18 at 21:06

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.