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

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$.
Keywords No keywords specified (fix it)
Categories (categorize this paper)
DOI 10.1017/jsl.2021.10
Options
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

PhilArchive copy


Upload a copy of this paper     Check publisher's policy     Papers currently archived: 62,268
External links

Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
Through your library

References found in this work BETA

Theory of Recursive Functions and Effective Computability.Hartley Rogers - 1971 - Journal of Symbolic Logic 36 (1):141-146.
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.
Completion of Choice.Vasco Brattka & Guido Gherardi - 2021 - Annals of Pure and Applied Logic 172 (3):102914.
Embeddings Between Well-Orderings: Computability-Theoretic Reductions.Jun Le Goh - 2020 - Annals of Pure and Applied Logic 171 (6):102789.

View all 7 references / Add more references

Citations of this work BETA

No citations found.

Add more citations

Similar books and articles

A Recursion Theoretic Analysis of the Clopen Ramsey Theorem.Peter Clote - 1984 - Journal of Symbolic Logic 49 (2):376-400.
Lattice Representations for Computability Theory.Peter A. Fejer - 1998 - Annals of Pure and Applied Logic 94 (1-3):53-74.
Nondiversity in Substructures.James H. Schmerl - 2008 - Journal of Symbolic Logic 73 (1):193-211.
Nonstandard Combinatorics.Joram Hirshfeld - 1988 - Studia Logica 47 (3):221 - 232.
A Generalization of the Limit Lemma and Clopen Games.Peter Clote - 1986 - Journal of Symbolic Logic 51 (2):273-291.
On the Logical Structure of Quantum Mechanics.G. T. Rüttimann - 1970 - Foundations of Physics 1 (2):173-182.
Phase Transition Results for Three Ramsey-Like Theorems.Florian Pelupessy - 2016 - Notre Dame Journal of Formal Logic 57 (2):195-207.

Analytics

Added to PP index
2021-02-02

Total views
3 ( #1,317,997 of 2,444,923 )

Recent downloads (6 months)
3 ( #232,632 of 2,444,923 )

How can I increase my downloads?

Downloads

My notes