Some results concerning the \(\mathsf{SRT}_2^2\) vs. \(\mathsf{COH}\) problem. (English) Zbl 07271573

Cholak, Peter A.; Dzhafarov, Damir D.; Hirschfeldt, Denis R.; Patey, Ludovic

Computability 9, No. 3-4, 193-217 (2020).

Summary: The \(\mathsf{SRT}_2^2\) vs. \(\mathsf{COH}\) problem is a central problem in computable combinatorics and reverse mathematics, asking whether every Turing ideal that satisfies the principle \(\mathsf{SRT}_2^2\) also satisfies the principle \(\mathsf{COH}\). This paper is a contribution towards further developing some of the main techniques involved in attacking this problem. We study several principles related to each of \(\mathsf{SRT}_2^2\) and \(\mathsf{COH}\), and prove results that highlight the limits of our current understanding, but also point to new directions ripe for further exploration.

MSC:

03D	Computability and recursion theory

Keywords:

computable combinatorics; Ramsey theory; computability theory; reverse mathematics