COH, SRT22, and multiple functionals

Article type: Research Article

Authors: Dzhafarov, Damir D.^{a; *} | Patey, Ludovic^b

Affiliations: [a] Department of Mathematics, University of Connecticut, CT, U.S.A.. damir@math.uconn.edu | [b] Institut Camille Jordan, Université Claude Bernard Lyon 1, France. ludovic.patey@computability.fr

Correspondence: [*] Corresponding author. damir@math.uconn.edu.

Abstract: We prove the following result: there is a family R=⟨R0,R1,…⟩ of subsets of ω such that for every stable coloring c:[ω]2→k hyperarithmetical in R and every finite collection of Turing functionals, there is an infinite homogeneous set H for c such that none of the finitely many functionals map R⊕H to an infinite cohesive set for R. This provides a partial answer to a question in computable combinatorics, whether COH is omnisciently computably reducible to SRT22.

Keywords: Ramsey’s theorem, computability theory, computable combinatorics, reverse mathematis

DOI: 10.3233/COM-190261

Journal: Computability, vol. 10, no. 2, pp. 111-121, 2021