Ramsey's theorem and products in the Weihrauch degrees

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\times \mathsf{COH}$).

arXiv comment30 pages

References in corpus (8)

• The Bolzano-Weierstrass Theorem is the Jump of Weak König's Lemma
• The Strength of Some Combinatorial Principles Related to Ramsey's Theorem for Pairs
• On the algebraic structure of Weihrauch degrees
• The degree structure of Weihrauch-reducibility
• Connected Choice and the Brouwer Fixed Point Theorem
• Weihrauch-completeness for layerwise computability
• Partial orders and immunity in reverse mathematics
• Strong Reductions between Relatives of the Stable Ramsey's Theorem