On uniform relationships between combinatorial problems.

*(English)*Zbl 06560459Summary: The enterprise of comparing mathematical theorems according to their logical strength is an active area in mathematical logic, with one of the most common frameworks for doing so being reverse mathematics. In this setting, one investigates which theorems provably imply which others in a weak formal theory roughly corresponding to computable mathematics. Since the proofs of such implications take place in classical logic, they may in principle involve appeals to multiple applications of a particular theorem, or to non-uniform decisions about how to proceed in a given construction. In practice, however, if a theorem \( \mathsf {Q}\) implies a theorem \( \mathsf {P}\), it is usually because there is a direct uniform translation of the problems represented by \( \mathsf {P}\) into the problems represented by \( \mathsf {Q}\), in a precise sense formalized by Weihrauch reducibility.

We study this notion of uniform reducibility in the context of several natural combinatorial problems, and compare and contrast it with the traditional notion of implication in reverse mathematics. We show, for instance, that for all \(n\), \(j\), \(k \geq 1\), if \( j < k\), then Ramsey’s theorem for \( n\)-tuples and \( k\) many colors is not uniformly, or Weihrauch, reducible to Ramsey’s theorem for \( n\)-tuples and \( j\) many colors. The two theorems are classically equivalent, so our analysis gives a genuinely finer metric by which to gauge the relative strength of mathematical propositions.

We also study Weak König’s Lemma, the Thin Set Theorem, and the Rainbow Ramsey’s Theorem, along with a number of their variants investigated in the literature. Weihrauch reducibility turns out to be connected with sequential forms of mathematical principles, where one wishes to solve infinitely many instances of a particular problem simultaneously. We exploit this connection to uncover new points of difference between combinatorial problems previously thought to be more closely related.

We study this notion of uniform reducibility in the context of several natural combinatorial problems, and compare and contrast it with the traditional notion of implication in reverse mathematics. We show, for instance, that for all \(n\), \(j\), \(k \geq 1\), if \( j < k\), then Ramsey’s theorem for \( n\)-tuples and \( k\) many colors is not uniformly, or Weihrauch, reducible to Ramsey’s theorem for \( n\)-tuples and \( j\) many colors. The two theorems are classically equivalent, so our analysis gives a genuinely finer metric by which to gauge the relative strength of mathematical propositions.

We also study Weak König’s Lemma, the Thin Set Theorem, and the Rainbow Ramsey’s Theorem, along with a number of their variants investigated in the literature. Weihrauch reducibility turns out to be connected with sequential forms of mathematical principles, where one wishes to solve infinitely many instances of a particular problem simultaneously. We exploit this connection to uncover new points of difference between combinatorial problems previously thought to be more closely related.

##### MSC:

03B30 | Foundations of classical theories (including reverse mathematics) |

05D10 | Ramsey theory |

05D40 | Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) |

05D15 | Transversal (matching) theory |

03D32 | Algorithmic randomness and dimension |

03D80 | Applications of computability and recursion theory |

03F35 | Second- and higher-order arithmetic and fragments |

PDF
BibTeX
XML
Cite

\textit{F. G. Dorais} et al., Trans. Am. Math. Soc. 368, No. 2, 1321--1359 (2016; Zbl 06560459)

Full Text:
DOI

##### References:

[1] | Ambos-Spies, Klaus; Kjos-Hanssen, Bj\o rn; Lempp, Steffen; Slaman, Theodore A., Comparing DNR and WWKL, J. Symbolic Logic, 69, 4, 1089-1104, (2004) · Zbl 1076.03039 |

[2] | Avigad, Jeremy; Dean, Edward T.; Rute, Jason, Algorithmic randomness, reverse mathematics, and the dominated convergence theorem, Ann. Pure Appl. Logic, 163, 12, 1854-1864, (2012) · Zbl 1259.03021 |

[3] | Blass, Andreas, Questions and answers—a category arising in linear logic, complexity theory, and set theory. Advances in linear logic, Ithaca, NY, 1993, London Math. Soc. Lecture Note Ser. 222, 61-81, (1995), Cambridge Univ. Press, Cambridge · Zbl 0823.03039 |

[4] | Brattka, Vasco; de Brecht, Matthew; Pauly, Arno, Closed choice and a uniform low basis theorem, Ann. Pure Appl. Logic, 163, 8, 986-1008, (2012) · Zbl 1251.03082 |

[5] | Brattka, Vasco; Gherardi, Guido, Weihrauch degrees, omniscience principles and weak computability, J. Symbolic Logic, 76, 1, 143-176, (2011) · Zbl 1222.03071 |

[6] | Brattka, Vasco; Gherardi, Guido; Marcone, Alberto, The Bolzano-Weierstrass theorem is the jump of weak K\H onig’s lemma, Ann. Pure Appl. Logic, 163, 6, 623-655, (2012) · Zbl 1245.03097 |

[7] | [Brattka-Pauly-2010] Vasco Brattka and Arno Pauly, Computation with advice, Electronic Proceedings in Theoretical Computer Science 24 (2010), 41–55. |

[8] | Cholak, Peter A.; Giusto, Mariagnese; Hirst, Jeffry L.; Jockusch, Carl G., Jr., Free sets and reverse mathematics. Reverse mathematics 2001, Lect. Notes Log. 21, 104-119, (2005), Assoc. Symbol. Logic, La Jolla, CA · Zbl 1092.03031 |

[9] | 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 |

[10] | Chong, C. T.; Slaman, Theodore A.; Yang, Yue, The metamathematics of stable Ramsey’s theorem for pairs, J. Amer. Math. Soc., 27, 3, 863-892, (2014) · Zbl 1341.03015 |

[11] | Conidis, Chris J.; Slaman, Theodore A., Random reals, the rainbow Ramsey theorem, and arithmetic conservation, J. Symbolic Logic, 78, 1, 195-206, (2013) · Zbl 1305.03055 |

[12] | Csima, Barbara F.; Mileti, Joseph R., The strength of the rainbow Ramsey theorem, J. Symbolic Logic, 74, 4, 1310-1324, (2009) · Zbl 1188.03044 |

[13] | Downey, Rodney G.; Hirschfeldt, Denis R., Algorithmic randomness and complexity, Theory and Applications of Computability, xxviii+855 pp., (2010), Springer, New York · Zbl 1221.68005 |

[14] | Dzhafarov, Damir D., Cohesive avoidance and strong reductions, Proc. Amer. Math. Soc., 143, 2, 869-876, (2015) · Zbl 1386.03055 |

[15] | Dzhafarov, Damir D.; Jockusch, Carl G., Jr., Ramsey’s theorem and cone avoidance, J. Symbolic Logic, 74, 2, 557-578, (2009) · Zbl 1166.03021 |

[16] | Friedman, Harvey M.; Simpson, Stephen G.; Smith, Rick L., Countable algebra and set existence axioms, Ann. Pure Appl. Logic, 25, 2, 141-181, (1983) · Zbl 0575.03038 |

[17] | [Hirschfeldt-TA] Denis R. Hirschfeldt, Slicing the truth: On the computability theoretic and reverse mathematical analysis of combinatorial principles, to appear. · Zbl 1304.03001 |

[18] | [HJ-TA] Denis R. Hirschfeldt and Carl G. Jockusch, Jr., On notions of computability theoretic reduction between \(Π^1_2\) principles, to appear. · Zbl 1373.03068 |

[19] | 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 |

[20] | Hirst, Jeffry L., Representations of reals in reverse mathematics, Bull. Pol. Acad. Sci. Math., 55, 4, 303-316, (2007) · Zbl 1138.03012 |

[21] | Jockusch, Carl G., Jr., Ramsey’s theorem and recursion theory, J. Symbolic Logic, 37, 268-280, (1972) · Zbl 0262.02042 |

[22] | Jockusch, Carl G., Jr., Degrees of functions with no fixed points. Logic, methodology and philosophy of science, VIII, Moscow, 1987, Stud. Logic Found. Math. 126, 191-201, (1989), North-Holland, Amsterdam |

[23] | Jockusch, Carl G., Jr.; Soare, Robert I., \(Π ^{0}_{1}\) classes and degrees of theories, Trans. Amer. Math. Soc., 173, 33-56, (1972) · Zbl 0262.02041 |

[24] | Kreuzer, Alexander P.; Kohlenbach, Ulrich, Term extraction and Ramsey’s theorem for pairs, J. Symbolic Logic, 77, 3, 853-895, (2012) · Zbl 1254.03112 |

[25] | Kummer, Martin, A proof of Beigel’s cardinality conjecture, J. Symbolic Logic, 57, 2, 677-681, (1992) · Zbl 0763.03025 |

[26] | 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 |

[27] | Mileti, Joseph Roy, Partition theorems and computability theory, 76 pp., (2004), ProQuest LLC, Ann Arbor, MI |

[28] | Pauly, Arno, On the (semi)lattices induced by continuous reducibilities, MLQ Math. Log. Q., 56, 5, 488-502, (2010) · Zbl 1200.03028 |

[29] | 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 |

[30] | Soare, Robert I., Recursively enumerable sets and degrees, Perspectives in Mathematical Logic, xviii+437 pp., (1987), Springer-Verlag, Berlin · Zbl 0623.03042 |

[31] | Wang, Wei, Rainbow Ramsey theorem for triples is strictly weaker than the arithmetical comprehension axiom, J. Symbolic Logic, 78, 3, 824-836, (2013) · Zbl 1300.03013 |

[32] | Wang, Wei, Some logically weak Ramseyan theorems, Adv. Math., 261, 1-25, (2014) · Zbl 1307.03011 |

[33] | [Weihrauch-1992] Klaus Weihrauch, The degrees of discontinuity of some translators between representations of the real numbers, Tech. Report TR-92-050, International Computer Science Institute, Berkeley, July 1992. |

[34] | [Weihrauch-1992a] \bysame, The tte-interpretation of three hierarchies of omniscience principles, Tech. Report (Informatik Berichte) 130, FernUniversit\"at Hagen, Hagen, September 1992. |

[35] | Weihrauch, Klaus, Computable analysis, Texts in Theoretical Computer Science. An EATCS Series, x+285 pp., (2000), Springer-Verlag, Berlin · Zbl 0956.68056 |

[36] | Yu, Xiaokang; Simpson, Stephen G., Measure theory and weak K\"onig’s lemma, Arch. Math. Logic, 30, 3, 171-180, (1990) · 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. 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.