The open and clopen Ramsey theorems in the Weihrauch lattice

Journal of Symbolic Logic 86 (1):316-351 (2021)
  Copy   BIBTEX

Abstract

We investigate the uniform computational content of the open and clopen Ramsey theorems in the Weihrauch lattice. While they are known to be equivalent to $\mathrm {ATR_0}$ from the point of view of reverse mathematics, there is not a canonical way to phrase them as multivalued functions. We identify eight different multivalued functions and study their degree from the point of view of Weihrauch, strong Weihrauch, and arithmetic Weihrauch reducibility. In particular one of our functions turns out to be strictly stronger than any previously studied multivalued functions arising from statements around $\mathrm {ATR}_0$.

Other Versions

No versions found

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 101,394

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

Analytics

Added to PP
2021-02-02

Downloads
21 (#1,006,460)

6 months
4 (#1,249,230)

Historical graph of downloads
How can I increase my downloads?

References found in this work

Theory of Recursive Functions and Effective Computability.Hartley Rogers - 1971 - Journal of Symbolic Logic 36 (1):141-146.
Completion of choice.Vasco Brattka & Guido Gherardi - 2021 - Annals of Pure and Applied Logic 172 (3):102914.
Closed choice and a uniform low basis theorem.Vasco Brattka, Matthew de Brecht & Arno Pauly - 2012 - Annals of Pure and Applied Logic 163 (8):986-1008.
Effective Borel measurability and reducibility of functions.Vasco Brattka - 2005 - Mathematical Logic Quarterly 51 (1):19-44.
How Incomputable Is the Separable Hahn-Banach Theorem?Guido Gherardi & Alberto Marcone - 2009 - Notre Dame Journal of Formal Logic 50 (4):393-425.

View all 8 references / Add more references