Ramsey’s theorem and products in the Weihrauch degrees. (English) Zbl 07271557

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

Computability 9, No. 2, 85-110 (2020).

Summary: 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 Weihrauch-incomparable to the parallel product of the stable Ramsey’s theorem for pairs and the cohesive principle \((\mathsf{SRT}_2^2 \times \mathsf{COH})\).

MSC:

03D	Computability and recursion theory

Keywords:

computable combinatorics; Ramsey theory; computability theory; reverse mathematics