## The thin set theorem for pairs implies DNR.(English)Zbl 1372.03028

Summary: Answering a question in the reverse mathematics of combinatorial principles, we prove that the thin set theorem for pairs (TS(2)) implies the diagonally noncomputable set principle (DNR) over the base axiom system $$\mathrm{RCA}_0$$.

### MSC:

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

### Keywords:

reverse mathematics; thin set; Ramsey’s theorem
Full Text:

### References:

 [1] Cholak, P. A., M. Giusto, J. L. Hirst, and C. G. Jockusch, Jr., “Free sets and reverse mathematics,” pp. 104-19 in Reverse Mathematics 2001 , vol. 21 of Lecture Notes in Logic , Association for Symbolic Logic, La Jolla, Calif., 2005. · Zbl 1092.03031 [2] Cholak, P. A., C. G. Jockusch, Jr., and T. A. Slaman, “On the strength of Ramsey’s theorem for pairs,” Journal of Symbolic Logic , vol. 66 (2001), pp. 1-55. · Zbl 0977.03033 [3] Chong, C. T., T. A. Slaman, and Y. Yang, “$$\Pi^{1}_{1}$$-conservation of combinatorial principles weaker than Ramsey’s theorem for pairs,” Advances in Mathematics , vol. 230 (2012), pp. 1060-77. · Zbl 1255.03025 [4] Hirschfeldt, D. R., C. G. Jockusch, Jr., B. Kjos-Hanssen, S. Lempp, and T. A. Slaman, “The strength of some combinatorial principles related to Ramsey’s theorem for pairs,” pp. 143-61 in Computational Prospects of Infinity, Part II: Presented Talks , vol. 15 of Lecture Notes Series, Institute for Mathematical Sciences, National University of Singapore , World Science, Hackensack, N.J., 2008. · Zbl 1167.03009 [5] Hirschfeldt, D. R., and R. A. Shore, “Combinatorial principles weaker than Ramsey’s theorem for pairs,” Journal of Symbolic Logic , vol. 72 (2007), pp. 171-206. · Zbl 1118.03055 [6] Hirschfeldt, D. R., R. A. Shore, and T. A. Slaman, “The atomic model theorem and type omitting,” Transactions of the American Mathematical Society , vol. 361 (2009), pp. 5805-37. · Zbl 1184.03005 [7] Jockusch, C. G., Jr., “Ramsey’s theorem and recursion theory,” Journal of Symbolic Logic , vol. 37 (1972), pp. 268-80. · Zbl 0248.05005 [8] Liu, J., “$$\mathrm{RT}^{2}_{2}$$ does not imply $$\mathrm{WKL}_{0}$$,” Journal of Symbolic Logic , vol. 77 (2012), pp. 609-20. · Zbl 1245.03095 [9] Seetapun, D., and T. A. Slaman, “On the strength of Ramsey’s theorem,” Notre Dame Journal of Formal Logic , vol. 36 (1995), pp. 570-82. · Zbl 0843.03034 [10] Wang, W., “Some logically weak Ramseyan theorems,” Advances in Mathematics , vol. 261 (2014), pp. 1-25. · 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.