Back to Search Start Over

The open and clopen Ramsey theorems in the Weihrauch lattice

Authors :
Marcone, Alberto
Valenti, Manlio
Source :
J. symb. log. 86 (2021) 316-351
Publication Year :
2020

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 8 different multivalued functions (5 corresponding to the open Ramsey theorem and 3 corresponding to the clopen Ramsey theorem) 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$.<br />Comment: Improved the presentation of lemmas 4.3 and 4.13. To appear in The Journal of Symbolic Logic

Details

Database :
arXiv
Journal :
J. symb. log. 86 (2021) 316-351
Publication Type :
Report
Accession number :
edsarx.2003.04245
Document Type :
Working Paper
Full Text :
https://doi.org/10.1017/jsl.2021.10