Ramsey's theorem and products in the Weihrauch degrees

DOI10.3233/COM-180203MaRDI QIDQ5131643zbMATH OpenFDO

Authors Damir D. Dzhafarov, Jun Le Goh, Denis R. Hirschfeldt, Ludovic Patey, Arno Pauly

Publication date 9 November 2020

Published in Computability (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1804.10968

zbMATH Keywords

computability theorycomputable combinatoricsRamsey theoryreverse mathematics

Mathematics Subject Classification ID

Foundations of classical theories (including reverse mathematics) (03B30) Other degrees and reducibilities in computability and recursion theory (03D30) Computation over the reals, computable analysis (03D78) Constructive and recursive analysis (03F60) Ramsey theory (05D10)

Abstract: We study the positions in the Weihrauch lattice of parallel products of various combinatorial principles related to Ramsey's theorem. Among other results, we obtain an answer to a question of Brattka, by showing that Ramsey's theorem for pairs ($mathsf{RT}_2^2$) is strictly Weihrauch below the parallel product of the stable Ramsey's theorem for pairs and the cohesive principle ($mathsf{SRT}_2^{2}imesmathsfCOH$).

Recommendations

• On the uniform computational content of Ramsey's theorem
• Strong reductions between combinatorial principles
• On the strength of Ramsey's theorem
• An inside/outside Ramsey theorem and recursion theory
• scientific article; zbMATH DE number 7377981

Cited in

(17)

• Ramsey's theorem for sums, products, and arithmetic progressions
• Book review of: P. Dodos and V. Kanellopoulos, Ramsey theory for product spaces
• On the Weihrauch degree of the additive Ramsey theorem over the rationals
• On the uniform computational content of Ramsey's theorem
• A note on the diamond operator
• COH, SRT 2 2 , and multiple functionals
• THE OPEN AND CLOPEN RAMSEY THEOREMS IN THE WEIHRAUCH LATTICE
• Compositions of multivalued functions
• FINDING DESCENDING SEQUENCES THROUGH ILL-FOUNDED LINEAR ORDERS
• Searching for an analogue of \(\text{ATR}_0\) in the Weihrauch lattice
• Algebraic properties of the first-order part of a problem
• On the Weihrauch degree of the additive Ramsey theorem
• Hilbert's tenth problem for term algebras with a substitution operator
• Complemented subsets and Boolean-valued, partial functions
• Defining long words succinctly in FO and MSO
• On the first-order parts of problems in the Weihrauch degrees
• The weakness of finding descending sequences in ill-founded linear orders

This page was built for publication: Ramsey's theorem and products in the Weihrauch degrees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5131643)