Some results concerning the SRT₂^2 vs. COH problem

DOI10.3233/COM-190251MaRDI QIDQ5131650zbMATH OpenOpenAlexFDO

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

Publication date 9 November 2020

Published in Computability (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1901.10326

zbMATH Keywords

Ramsey theorycomputability theoryreverse mathematicscomputable combinatorics

Mathematics Subject Classification ID

Foundations of classical theories (including reverse mathematics) (03B30) Ramsey theory (05D10) Second- and higher-order arithmetic and fragments (03F35)

Abstract: The $mathsf{SRT}_2^2$ vs. $mathsfCOH$ 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 $mathsfCOH$. 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 $mathsfCOH$, and prove results that highlight the limits of our current understanding, but also point to new directions ripe for further exploration.

Recommendations

• The Strength of Some Combinatorial Principles Related to Ramsey's Theorem for Pairs
• Strong reductions between combinatorial principles
• \(\varPi^1_1\)-conservation of combinatorial principles weaker than Ramsey's theorem for pairs
• Cohesive avoidance and strong reductions
• scientific article; zbMATH DE number 7377981

Cited in

(2)

• \( \mathsf{SRT}_2^2\) does not imply \(\mathsf{RT}_2^2\) in \(\omega \)-models
• The coding power of a product of partitions

This page was built for publication: Some results concerning the \(\mathsf{SRT}_2^2\) vs. \(\mathsf{COH}\) problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5131650)