Speaker
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 HJ, which corresponds to Π11-CA0 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 Δ0n+1(X) sets must also contain HJn(X). Similar results also hold for Borel sets of transfinite rank. This is joint work with Alberto Marcone. Bibliography
|