The Galvin-Prikry theorem in the Weihrauch lattice
Gian Marco Osso
I will address the classification of different fragments of the Galvin-Prikry theorem, an infinite dimensional generalization of Ramsey’s theorem, in terms of their uniform computational content (Weihrauch degree). This work can be seen as a continuation of [1], which focused on the Weihrauch classification of functions related to the Nash-Williams theorem, i.e., the restriction of the Galvin-Prikry theorem to open sets. We have shown that functions related to the Galvin-Prikry theorem for Borel sets of rank \(n\) are strictly between the \((n+1)\)-th and \(n\)-th iterate of the hyperjump operator \(\mathsf{HJ}\), which corresponds to \(\Pi^1_1\)-\(\mathsf{CA}_0\) in the Weihrauch lattice. To establish this classification we obtain the following computability theoretic result (along the lines of [2] and [3]): a Turing jump ideal containing homogeneous sets for all \(\Delta^0_{n+1}(X)\) sets must also contain \(\mathsf{HJ}^n(X)\). Similar results also hold for Borel sets of transfinite rank. This is joint work with Alberto Marcone.
Bibliography
- Alberto Marcone, Manlio Valenti,The open and clopen Ramsey theorem in the Weihrauch lattice,The Journal of Symbolic Logic,vol. 86 (2021), no. 1, pp. 316–351.
- Carl G. Jockush,Ramsey’s Theorem and recursion theory,The Journal of Symbolic Logic,vol. 37 (1972), no. 2, pp. 268–280.
- Stephen G. Simpson,Sets which do not have subsets of every higher degree,The Journal of Symbolic Logic,vol. 43 (1978), no. 1, pp. 135–138.