×

zbMATH — the first resource for mathematics

Ramsey’s theorem for singletons and strong computable reducibility. (English) Zbl 1423.03159
Summary: We answer a question posed by D. R. Hirschfeldt and C. G. Jockusch jun. [J. Math. Log. 16, No. 1, Article ID 1650002, 59 p. (2016; Zbl 1373.03068)] by showing that whenever \( k > \ell \), Ramsey’s theorem for singletons and \( k\)-colorings, \( \mathsf {RT}^1_k\), is not strongly computably reducible to the stable Ramsey’s theorem for \( \ell \)-colorings, \( \mathsf {SRT}^2_\ell \). Our proof actually establishes the following considerably stronger fact: given \( k > \ell \), there is a coloring \( c : \omega \rightarrow k\) such that for every stable coloring \( d : [\omega]^2 \rightarrow \ell \) (computable from \( c\) or not), there is an infinite homogeneous set \( H\) for \( d\) that computes no infinite homogeneous set for \( c\). This also answers a separate question of the first author [J. Symb. Log. 81, No. 4, 1405–1431 (2016; Zbl 1368.03044)], as it follows that the cohesive principle, \( \mathsf {COH}\), is not strongly computably reducible to the stable Ramsey’s theorem for all colorings, \( \mathsf {SRT}^2_{<\infty}\). The latter is the strongest partial result to date in the direction of giving a negative answer to the longstanding open question of whether \( \mathsf {COH}\) is implied by the stable Ramsey’s theorem in \( \omega \)-models of \( \mathsf {RCA}_0\).

MSC:
03D80 Applications of computability and recursion theory
03F35 Second- and higher-order arithmetic and fragments
05D10 Ramsey theory
03B30 Foundations of classical theories (including reverse mathematics)
03D30 Other degrees and reducibilities in computability and recursion theory
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] Brattka-bib Vasco Brattka, <span class=”textit”>B</span>ibliography on Weihrauch complexity, website: \tt http://cca-net.de/publications/weibib.php · Zbl 1140.03040
[2] BR-TA Vasco Brattka and Tahina Rakotoniaina, <span class=”textit”>O</span>n the uniform computational content of Ramsey’s theorem, to appear. · Zbl 1422.03132
[3] Cholak, Peter A.; Dzhafarov, Damir D.; Hirst, Jeffry L.; Slaman, Theodore A., Generics for computable Mathias forcing, Ann. Pure Appl. Logic, 165, 9, 1418-1428, (2014) · Zbl 1320.03072
[4] CDS-TA Peter A. Cholak, Damir D. Dzhafarov, and Mariya I. Soskova, <span class=”textit”>G</span>enerics for Mathias forcing over general Turing ideals, Israel J. Math., to appear.
[5] Cholak, Peter A.; Jockusch, Carl G.; Slaman, Theodore A., On the strength of Ramsey’s theorem for pairs, J. Symbolic Logic, 66, 1, 1-55, (2001) · Zbl 0977.03033
[6] Chong, C. T.; Lempp, Steffen; Yang, Yue, On the role of the collection principle for \(Σ ^0_2\)-formulas in second-order reverse mathematics, Proc. Amer. Math. Soc., 138, 3, 1093-1100, (2010) · Zbl 1195.03015
[7] Dorais, Fran\ccois G.; Dzhafarov, Damir D.; Hirst, Jeffry L.; Mileti, Joseph R.; Shafer, Paul, On uniform relationships between combinatorial problems, Trans. Amer. Math. Soc., 368, 2, 1321-1359, (2016) · Zbl 06560459
[8] Dzhafarov, Damir D., Cohesive avoidance and strong reductions, Proc. Amer. Math. Soc., 143, 2, 869-876, (2015) · Zbl 1386.03055
[9] Dzhafarov-TA Damir D. Dzhafarov, <span class=”textit”>S</span>trong reductions between combinatorial principles, J. Symbolic Logic, to appear. · Zbl 1368.03044
[10] GS-TA Marcia J. Groszek and Theodore A. Slaman, <span class=”textit”>M</span>oduli of computation, in preparation.
[11] Hirschfeldt, Denis R., Slicing the truth, Lecture Notes Series. Institute for Mathematical Sciences. National University of Singapore 28, xvi+214 pp., (2015), World Scientific Publishing Co. Pte. Ltd., Hackensack, NJ · Zbl 1304.03001
[12] HJ-TA Denis R. Hirschfeldt and Carl G. Jockusch, Jr., <span class=”textit”>O</span>n notions of computability theoretic reduction between \(Π ^1_2\) principles, to appear. · Zbl 1373.03068
[13] Hirschfeldt, Denis R.; Shore, Richard A., Combinatorial principles weaker than Ramsey’s theorem for pairs, J. Symbolic Logic, 72, 1, 171-206, (2007) · Zbl 1118.03055
[14] Hirst, Jeffry Lynn, COMBINATORICS IN SUBSYSTEMS OF SECOND ORDER ARITHMETIC, 153 pp., (1987), ProQuest LLC, Ann Arbor, MI
[15] Jockusch, Carl; Stephan, Frank, A cohesive set which is not high, Math. Logic Quart., 39, 4, 515-530, (1993) · Zbl 0799.03048
[16] Lerman, Manuel; Solomon, Reed; Towsner, Henry, Separating principles below Ramsey’s theorem for pairs, J. Math. Log., 13, 2, 1350007, 44 pp., (2013) · Zbl 1326.03021
[17] Mileti, Joseph Roy, Partition theorems and computability theory, 76 pp., (2004), ProQuest LLC, Ann Arbor, MI
[18] Patey-TA Ludovic Patey, <span class=”textit”>T</span>he weakness of being cohesive, thin or free in reverse mathematics, Israel J. Math., to appear. · Zbl 1368.03018
[19] Rakotoniaina-2015 Tahina Rakotoniaina, \em The Computational Strength of Ramsey’s Theorem, PhD thesis, University of Cape Town, 2015.
[20] Shore, Richard A., The Turing degrees: an introduction. Forcing, iterated ultrapowers, and Turing degrees, Lect. Notes Ser. Inst. Math. Sci. Natl. Univ. Singap. 29, 39-121, (2016), World Sci. Publ., Hackensack, NJ
[21] Simpson, Stephen G., Subsystems of second order arithmetic, Perspectives in Logic, xvi+444 pp., (2009), Cambridge University Press, Cambridge; Association for Symbolic Logic, Poughkeepsie, NY · Zbl 1181.03001
[22] CSY-TA Theodore A. Slaman and Yue Yang, The metamathematics of stable Ramsey’s theorem for pairs, to appear. · Zbl 1341.03015
[23] Soare-TA Robert I. Soare, \em Computability theory and applications, Theory and Applications of Computability. Springer, New York, to appear. · Zbl 1350.03001
[24] Solovay, Robert M., Hyperarithmetically encodable sets, Trans. Amer. Math. Soc., 239, 99-122, (1978) · Zbl 0411.03039
[25] Weihrauch-1992 K. Weihrauch, <span class=”textit”>T</span>he degrees of discontinuity of some translators between representations of the real numbers, Technical report TR-92-050, International Computer Science Institute, Berkeley, 1992.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.