×

On the logical strengths of partial solutions to mathematical problems. (English) Zbl 1453.03002

Summary: We use the framework of reverse mathematics to address the question of, given a mathematical problem, whether or not it is easier to find an infinite partial solution than it is to find a complete solution. Following S. Flood [J. Symb. Log. 77, No. 4, 1272–1280 (2012; Zbl 1259.03022)], we say that a Ramsey-type variant of a problem is the problem with the same instances but whose solutions are the infinite partial solutions to the original problem. We study Ramsey-type variants of problems related to König’s lemma, such as restrictions of König’s lemma, Boolean satisfiability problems and graph coloring problems. We find that sometimes the Ramsey-type variant of a problem is strictly easier than the original problem (as Flood showed with weak König’s lemma) and that sometimes the Ramsey-type variant of a problem is equivalent to the original problem. We show that the Ramsey-type variant of weak König’s lemma is robust in the sense of A. Montalbán [Bull. Symb. Log. 17, No. 3, 431–454 (2011; Zbl 1233.03023)]: it is equivalent to several perturbations. We also clarify the relationship between Ramsey-type weak König’s lemma and algorithmic randomness by showing that Ramsey-type weak weak König’s lemma is equivalent to the problem of finding diagonally non-recursive functions and that these problems are strictly easier than Ramsey-type weak König’s lemma. This answers a question of Flood.

MSC:

03B30 Foundations of classical theories (including reverse mathematics)
03F35 Second- and higher-order arithmetic and fragments
05D10 Ramsey theory
03D32 Algorithmic randomness and dimension
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] 1 K. Ambos‐Spies, B. Kjos‐Hanssen, S. Lempp and T. A. Slaman, ‘Comparing DNR and WWKL’, J. Symb. Log.69 (2004) 1089-1104. · Zbl 1076.03039
[2] 2 J. Avigad, E. T. Dean and J. Rute, ‘Algorithmic randomness, reverse mathematics, and the dominated convergence theorem’, Ann. Pure Appl. Logic 163 (2012) 1854-1864. · Zbl 1259.03021
[3] 3 A. Bovykin and A. Weiermann, ‘The strength of infinitary Ramseyan principles can be accessed by their densities’, Ann. Pure Appl. Logic (2005), to appear. · Zbl 1422.03127
[4] 4 P. A. Cholak, C. G. Jockusch and T. A. Slaman, ‘On the strength of Ramsey’s theorem for pairs’, J. Symb. Log.66 (2001) 1-55. · Zbl 0977.03033
[5] 5 C. T. Chong, T. A. Slaman and Y. Yang, ‘The metamathematics of stable Ramsey’s theorem for pairs’, J. Amer. Math. Soc.27 (2014) 863-892. · Zbl 1341.03015
[6] 6 R. G. Downey and D. R. Hirschfeldt, Algorithmic randomness and complexity, Theory and Applications of Computability (Springer, New York, 2010). · Zbl 1221.68005
[7] 7 D. D. Dzhafarov and C. Mummert, ‘On the strength of the finite intersection principle’, Israel J. Math.196 (2013) 345-361. · Zbl 1302.03035
[8] 8 P. Erdős and F. Galvin, ‘Some Ramsey‐type theorems’, Discrete Math.87 (1991) 261-269. · Zbl 0759.05095
[9] 9 S. Flood, ‘Reverse mathematics and a Ramsey‐type König’s lemma’, J. Symb. Log.77 (2012) 1272-1280. · Zbl 1259.03022
[10] 10 S. Flood, ‘A packed Ramsey’s theorem and computability theory’, Trans. Amer. Math. Soc.367 (2015) 4957-4982. · Zbl 1371.03095
[11] 11 S. Flood and H. Towsner, ‘Separating principles below W K L 0’ (2014), to appear. · Zbl 1373.03017
[12] 12 H. Friedman, ‘Some systems of second order arithmetic and their use’, Proceedings of the International Congress of Mathematicians 1, Vancouver, B.C., 1974 (Canadian Mathematical Congress, Montreal, Quebek, 1975) 235-242. · Zbl 0344.02022
[13] 13 N. Greenberg and J. Miller, ‘Lowness for Kurtz randomness’, J. Symb. Log.74 (2009) 665-678. · Zbl 1168.03033
[14] 14 P. Hájek and P. Pudlák, Metamathematics of first‐order arithmetic, Perspectives in Mathematical Logic (Springer, Berlin, 1998). · Zbl 0889.03053
[15] 15 D. R. Hirschfeldt and R. A. Shore, ‘Combinatorial principles weaker than Ramsey’s theorem for pairs’, J. Symb. Log.72 (2007) 171-206. · Zbl 1118.03055
[16] 16 D. R. Hirschfeldt, R. A. Shore and T. A. Slaman, ‘The atomic model theorem and type omitting’, Trans. Amer. Math. Soc.361 (2009) 5805-5837. · Zbl 1184.03005
[17] 17 J. L. Hirst, ‘Combinatorics in subsystems of second order arithmetic’, PhD Thesis, Pennsylvania State University, 1987.
[18] 18 J. L. Hirst, Marriage theorems and reverse mathematics, Logic and Computation, Contemporary Mathematics 106 (ed. W. Sieg; American Mathematical Society, Providence, RI, 1990) 181-196. · Zbl 0701.03032
[19] 19 C. Jockusch, ‘Π1 0 classes and Boolean combinations of recursively enumerable sets’, J. Symb. Log.39 (1974) 95-96. · Zbl 0286.02045
[20] 20 B. Kjos‐Hanssen, ‘Infinite subsets of random sets of integers’, Math. Res. Lett.16 (2009) 103-110. · Zbl 1179.03061
[21] 21 A. Kučera, Measure, Π1 0 classes, and complete extensions of PA, Lecture Notes in Mathematics 1141 (1985) 245-259. · Zbl 0622.03031
[22] 22 M. Lerman, R. Solomon and H. Towsner, ‘Separating principles below Ramsey’s theorem for pairs’, J. Math. Log.13 (2013) 1350007-1350044. · Zbl 1326.03021
[23] 23 J. Liu, ‘R T 2 2 does not imply W K L 0’, J. Symb. Log.77 (2012) 609-620. · Zbl 1245.03095
[24] 24 L. Liu, ‘Cone avoiding closed sets’, Trans. Amer. Math. Soc.367 (2015) 1609-1630. · Zbl 1369.03101
[25] 25 J. R. Mileti, ‘Partition theorems and computability theory’, PhD Thesis, University of Illinois, 2004. · Zbl 1097.03037
[26] 26 A. Montalbán, ‘Open questions in reverse mathematics’, Bull. Symb. Log.17 (2011) 431-454. · Zbl 1233.03023
[27] 27 A. Nies, Computability and randomness, Oxford Logic Guides 51 (Oxford University Press, Oxford, 2009).
[28] 28 L. Patey, ‘Somewhere over the rainbow Ramsey theorem for pairs’, Preprint, 2014.
[29] 29 L. Patey, ‘Iterative forcing and hyperimmunity in reverse mathematics’, Evolving computability, Lecture Notes in Computer Science 9136 (Springer, Cham, 2015) 291-301. · Zbl 1461.03011
[30] 30 L. Patey, ‘Ramsey‐type graph coloring and diagonal non‐computability’, Arch. Math. Logic 54 (2015) 899-914. · Zbl 1342.03015
[31] 31 L. Patey, ‘The strength of the tree theorem for pairs in reverse mathematics’, J. Symb. Log. (4) 81 (2016) 1481-1499. · Zbl 1368.03019
[32] 32 L. Patey, ‘The weakness of being cohesive, thin or free in reverse mathematics’, Israel J. Math. (2) 216 (2016) 905-955. · Zbl 1368.03018
[33] 33 D. Seetapun and T. A. Slaman, ‘On the strength of Ramsey’s theorem’, Notre Dame J. Form. Log.36 (1995) 570-582. · Zbl 0843.03034
[34] 34 S. G. Simpson, Subsystems of second order arithmetic (Cambridge University Press, Cambridge, 2009). · Zbl 1181.03001
[35] 35 T. Slaman, ‘The first‐order fragments of second‐order theories’, 2011. http://cie2011.fmi.uni-sofia.bg/files/slides/Slaman.pdf.
[36] 36 W. Wang, ‘Some logically weak Ramseyan theorems’, Adv. Math.261 (2014) 1-25. · Zbl 1307.03011
[37] 37 X. Yu and S. G. Simpson, ‘Measure theory and weak König’s lemma’, Arch. Math. Logic 30 (1990) 171-180. · Zbl 0718.03043
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.