Some results concerning the SRT22 vs. COH problem

Issue title: Dagstuhl Seminar on Measuring the Complexity of Computational Content 2018

Guest editors: Vasco Brattka, Damir D. Dzhafarov, Alberto Marcone and Arno Pauly

Article type: Research Article

Authors: Cholak, Peter A.^{a; *} | Dzhafarov, Damir D.^b | Hirschfeldt, Denis R.^c | Patey, Ludovic^d

Affiliations: [a] Department of Mathematics, University of Notre Dame, IN, USA. Peter.Cholak.1@nd.edu | [b] Department of Mathematics, University of Connecticut, CT, USA. damir@math.uconn.edu | [c] Department of Mathematics, University of Chicago, IL, USA. drh@math.uchicago.edu | [d] Institut Camille Jordan, Université Claude Bernard Lyon 1, France. ludovic.patey@computability.fr

Correspondence: [*] Corresponding author. Peter.Cholak.1@nd.edu.

Abstract: The SRT22 vs. COH problem is a central problem in computable combinatorics and reverse mathematics, asking whether every Turing ideal that satisfies the principle SRT22 also satisfies the principle 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 SRT22 and COH, and prove results that highlight the limits of our current understanding, but also point to new directions ripe for further exploration.

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

DOI: 10.3233/COM-190251

Journal: Computability, vol. 9, no. 3-4, pp. 193-217, 2020