×

zbMATH — the first resource for mathematics

Pigeons do not jump high. (English) Zbl 1441.03013
The authors prove new computability theoretic results related to the pigeonhole principle for two colors. They show that for every set \(A\) there is an infinite non-high set \(H\) with \(H \subseteq A\) or \(H \subseteq \bar A\). Also, they show that for every \(\Delta^0_3\) set \(A\) there is an infinite \(\text{low}_3\) set \(H\) with \(H \subseteq A\) or \(H \subseteq \bar A\). The proofs use a new notion of forcing particularly adapted to the fine analysis of computability theoretic aspects of the pigeonhole principle. This forcing is used to succinctly prove that for every set \(A\) there is an infinite non-PA set \(H\) with \(H \subseteq A\) or \(H \subseteq \bar A\), the main combinatorial lemma of J. Liu [J. Symb. Log. 77, No. 2, 609–620 (2012; Zbl 1245.03095)]. The paper explains the connections between computability theoretic results and a number of open questions in reverse mathematics. Subsequently, the authors announced an answer to Question 1.1 in [“\(\mathsf{SRT}^2_2\) does not imply \(\mathsf{RT}^2_2\) in \(\omega\)-models”, Preprint, arxiv:1905.08427].
MSC:
03B30 Foundations of classical theories (including reverse mathematics)
03F35 Second- and higher-order arithmetic and fragments
03D80 Applications of computability and recursion theory
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] Cholak, P. A.; Dzhafarov, D. D.; Hirst, J. L.; Slaman, T. A., Generics for computable Mathias forcing, Ann. Pure Appl. Logic, 165, 9, 1418-1428 (2014) · Zbl 1320.03072
[2] Cholak, P. A.; Giusto, M.; Hirst, J. L.; Jockusch, C. G., Free sets and reverse mathematics, Reverse Math., 21, 104-119 (2001) · Zbl 1092.03031
[3] Cholak, P. A.; Jockusch, C. G.; Slaman, T. A., On the strength of Ramsey’s theorem for pairs, J. Symbolic Logic, 66, 01, 1-55 (2001) · Zbl 0977.03033
[4] Chong, C.; Lempp, S.; Yang, Y., On the role of the collection principle for \(\Sigma_2^0\)-formulas in second-order reverse mathematics, Proc. Amer. Math. Soc., 138, 3, 1093-1100 (2010) · Zbl 1195.03015
[5] Chong, C.; Slaman, T.; Yang, Y., The metamathematics of stable Ramsey’s theorem for pairs, J. Amer. Math. Soc., 27, 3, 863-892 (2014) · Zbl 1341.03015
[6] Csima, B. F.; Mileti, J. R., The strength of the rainbow Ramsey theorem, J. Symbolic Logic, 74, 04, 1310-1324 (2009) · Zbl 1188.03044
[7] Downey, R.; Hirschfeldt, D. R.; Lempp, S.; Solomon, R., A \(\Delta_2^0\) set with no infinite low subset in either it or its complement, J. Symbolic Logic, 66, 3, 1371-1381 (2001) · Zbl 0990.03046
[8] Dzhafarov, D. D.; Hirst, J. L., The polarized Ramsey’s theorem, Arch. Math. Logic, 48, 2, 141-157 (2009) · Zbl 1172.03007
[9] Dzhafarov, D. D.; Jockusch, C. G., Ramsey’s theorem and cone avoidance, J. Symbolic Logic, 74, 2, 557-578 (2009) · Zbl 1166.03021
[10] Flood, S., Reverse mathematics and a Ramsey-type König’s lemma, J. Symbolic Logic, 77, 4, 1272-1280 (2012) · Zbl 1259.03022
[11] Friedman, H. M., Fom:53:free sets and reverse math and fom:54:recursion theory and dynamics, available at
[12] Hirschfeldt, D. R., Slicing the Truth: On the Computable and Reverse Mathematics of Combinatorial Principles, Lecture Notes Series, Institute for Mathematical Sciences, National University of Singapore, vol. 28 (2015), World Scientific Publishing Co. Pte. Ltd.: World Scientific Publishing Co. Pte. Ltd. Hackensack, NJ, edited and with a foreword by Chitat Chong, Qi Feng, Theodore A. Slaman, W. Hugh Woodin and Yue Yang
[13] Hirschfeldt, D. R.; Jockusch, C. G.; Kjos-Hanssen, B.; Lempp, S.; Slaman, T. A., The strength of some combinatorial principles related to Ramsey’s theorem for pairs, (Computational Prospects of Infinity, Part II: Presented Talks (2008), World Scientific Press: World Scientific Press Singapore), 143-161 · Zbl 1167.03009
[14] Jockusch, C. G., Ramsey’s theorem and recursion theory, J. Symbolic Logic, 37, 2, 268-280 (1972) · Zbl 0262.02042
[15] Jockusch, C. G.; Soare, R. I., \( \Pi_1^0\) classes and degrees of theories, Trans. Amer. Math. Soc., 173, 33-56 (1972) · Zbl 0262.02041
[16] Jockusch, C. G.; Stephan, F., A cohesive set which is not high, MLQ Math. Log. Q., 39, 1, 515-530 (1993) · Zbl 0799.03048
[17] Kang, X., Combinatorial principles between \(RRT_2^2\) and \(RT_2^2\), Front. Math. China, 9, 6, 1309-1323 (2014) · Zbl 1311.03029
[18] Liu, L., \(RT_2^2\) does not imply \(WKL_0\), J. Symbolic Logic, 77, 2, 609-620 (2012) · Zbl 1245.03095
[19] Liu, L., Cone avoiding closed sets, Trans. Amer. Math. Soc., 367, 3, 1609-1630 (2015) · Zbl 1369.03101
[20] Martin, D. A., Classes of recursively enumerable sets and degrees of unsolvability, MLQ Math. Log. Q., 12, 1, 295-310 (1966) · Zbl 0181.30504
[21] Mileti, J. R., Partition Theorems and Computability Theory (2004), ProQuest LLC: ProQuest LLC Ann Arbor, MI, Thesis (Ph.D.) - University of Illinois at Urbana-Champaign · Zbl 1097.03037
[22] Patey, L., Combinatorial weaknesses of Ramseyan principles (2015), in preparation, available at
[23] Patey, L., Somewhere over the rainbow Ramsey theorem for pairs (2015), submitted for publication, available at
[24] Patey, L., Open questions about Ramsey-type statements in reverse mathematics, Bull. Symbolic Logic, 22, 2, 151-169 (2016) · Zbl 1396.03012
[25] Patey, L., The Reverse Mathematics of Ramsey-Type Theorems (2016), Université Paris Diderot, Ph.D. thesis
[26] Patey, L., The weakness of being cohesive, thin or free in reverse mathematics, Israel J. Math., 216, 2, 905-955 (2016) · Zbl 1368.03018
[27] Patey, L., Iterative forcing and hyperimmunity in reverse mathematics, Computability, 6, 3, 209-221 (2017) · Zbl 1420.03028
[28] Rice, B., The thin set theorem for pairs implies DNR, Notre Dame J. Form. Log., 56, 4, 595-601 (2015) · Zbl 1372.03028
[29] Seetapun, D.; Slaman, T. A., On the strength of Ramsey’s theorem, Notre Dame J. Form. Log., 36, 4, 570-582 (1995) · Zbl 0843.03034
[30] Simpson, S. G., Subsystems of Second Order Arithmetic (2009), Cambridge University Press · Zbl 1181.03001
[32] Wang, W., Rainbow Ramsey theorem for triples is strictly weaker than the arithmetical comprehension axiom, J. Symbolic Logic, 78, 3, 824-836 (2013) · Zbl 1300.03013
[33] Wang, W., Cohesive sets and rainbows, Ann. Pure Appl. Logic, 165, 2, 389-408 (2014) · Zbl 1300.03012
[34] Wang, W., The definability strength of combinatorial principles, J. Symb. Log., 81, 4, 1531-1554 (2016) · Zbl 1436.03099
[35] Wang, W., Some logically weak Ramseyan theorems, Adv. Math., 261, 1-25 (2014) · Zbl 1307.03011
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.