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$.

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 91,122

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 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
2021-02-02

Downloads
11 (#1,022,695)

6 months
5 (#366,001)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

Algebraic properties of the first-order part of a problem.Giovanni Soldà & Manlio Valenti - 2023 - Annals of Pure and Applied Logic 174 (7):103270.

Add more citations

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