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

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

A journey through computability, topology and analysis.Manlio Valenti - 2022 - Bulletin of Symbolic Logic 28 (2):266-267.
Weihrauch Goes Brouwerian.Vasco Brattka & Guido Gherardi - 2020 - Journal of Symbolic Logic 85 (4):1614-1653.
Embeddings between well-orderings: Computability-theoretic reductions.Jun Le Goh - 2020 - Annals of Pure and Applied Logic 171 (6):102789.

Analytics

Added to PP
2021-02-02

Downloads
60 (#1,002,355)

6 months
17 (#698,773)

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.
Higher recursion theory.Gerald E. Sacks - 1990 - New York, NY, USA: Cambridge University Press.
Completion of choice.Vasco Brattka & Guido Gherardi - 2021 - Annals of Pure and Applied Logic 172 (3):102914.

View all 17 references / Add more references