Logic Colloquium 2024


Gian Marco Osso

Dipartimento di Scienze Matematiche, Informatiche e Fisiche - Università di Udine

Talks at this conference:

  Wednesday, 14:50, J335

The Galvin-Prikry theorem in the Weihrauch lattice

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.


  1. 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.
  2. Carl G. Jockush,Ramsey’s Theorem and recursion theory,The Journal of Symbolic Logic,vol. 37 (1972), no. 2, pp. 268–280.
  3. 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.