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

DOI10.3233/COM-190251zbMATH Open1485.03024arXiv1901.10326OpenAlexW3016913989MaRDI QIDQ5131650FDOQ5131650

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)

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.

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

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

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)

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)