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

Rice, Brian

Notre Dame J. Formal Logic 56, No. 4, 595-601 (2015).

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

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