An effective proof that open sets are Ramsey (Q1128188): Difference between revisions

There are different possibilities to generalize Ramsey's Theorem to infinitary combinatorics. A simple argument employing the axiom of choice shows that \(\omega\not\rightarrow(\omega)^\omega_2\), i.e., not every coloring of the infinite subsets of \(\omega\) into two colors has an infinite homogeneous set [\textit{T. Jech}, Set theory (1978; Zbl 0419.03028), Exercise 29.3]. So to come to a valid generalization one has to take another way. One such way leads to the study of the so-called Ramsey cardinals, i.e., cardinals that satisfy \(\kappa\rightarrow(\kappa)^{<\omega}_2\) [\textit{T. Jech}, loc. cit., p. 328]. Another way is to look for ``well-behaved'' partitions, i.e., subsets of \(\omega\) (giving a two-coloring ``inside''/``outside'' of the infinite subsets of \(\omega\)) that do have an infinite homogeneous set. Such partitions are called Ramsey. The observation that the counterexample used for showing \(\omega\not\rightarrow(\omega)^\omega_2\) is found nonconstructively by AC suggests that the property might hold for ``easily definable'' partitions. A strong result in this direction is ``Every analytic set is Ramsey'' by \textit{J. Silver} [J. Symb. Log. 35, No. 1, 60-64 (1970; Zbl 0216.01304)]. The article under review presents a new proof of Solovay's result: If \(\mathcal O\) is an open set and no infinite set is homogeneous of color ``outside'', then there is an infinite set hyperarithmetic in the code of \(\mathcal O\) that is homogeneous of color ``inside''. As a motivation, first a short proof of the noneffective version ``every open set is Ramsey'' by the use of a nonprincipal ultrafilter is given. Besides being simple and well-presented, the proof in this paper has the advantage that, in contrast to former versions, it has a straightforward formalization in \(ATR_0\). This article is well written, proofs are mainly in prosa using formalism only in so far as it increases comprehensibility and exactness.