Ramsey’s theorem and products in the Weihrauch degrees

Article type: Research Article

Authors: Dzhafarov, Damir D.^{a; *} | Goh, Jun Le^b | Hirschfeldt, Denis R.^c | Patey, Ludovic^d | Pauly, Arno^e

Affiliations: [a] Department of Mathematics, University of Wisconsin-Madison, WI, U.S.A. [email protected] | [b] Department of Mathematics, University of Connecticut, CT, U.S.A.. [email protected] | [c] Department of Mathematics, University of Chicago, IL, U.S.A.. [email protected] | [d] Institut Camille Jordan, Université Claude Bernard Lyon 1, France. [email protected] | [e] Department of Computer Science, Swansea University, U.K.. [email protected]

Correspondence: [*] Corresponding author. [email protected].

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 (RT22) is Weihrauch-incomparable to the parallel product of the stable Ramsey’s theorem for pairs and the cohesive principle (SRT22×COH).

Keywords: Computable combinatorics, Ramsey theory, computability theory, reverse mathematics

DOI: 10.3233/COM-180203

Journal: Computability, vol. 9, no. 2, pp. 85-110, 2020