Ramsey's theorem and products in the Weihrauch degrees

2018/04/29 by Damir D. Dzhafarov, Jun Le Goh, Dzhafarov, Damir D. +7 · 1 citation
Computer Science · Mathematics · #Advanced Topology and Set Theory #Computability, Logic, AI Algorithms #FOS: Mathematics #Logic (math.LO) #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.1804.10968

openalex publication_date 2018/04/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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 (RT²₂) is strictly Weihrauch below the parallel product of the stable Ramsey's theorem for pairs and the cohesive principle (SRT²₂ × COH).

Cited by

• The weakness of finding descending sequences in ill-founded linear orders

Related

• On the Weihrauch degree of the additive Ramsey theorem
• Weihrauch reducibility between Ramsey-type theorems and well-ordering principles at the level of Σ⁰₂-induction: A pilot study
• Joins in the strong Weihrauch degrees
• An inside/outside Ramsey theorem and recursion theory
• Weaker cousins of Ramsey's theorem over a weak base theory