# zbMATH — the first resource for mathematics

On uniform relationships between combinatorial problems. (English) Zbl 06560459
Summary: 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.

##### 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
Full Text:
##### References:
  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  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  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  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  Brattka, Vasco; Gherardi, Guido, Weihrauch degrees, omniscience principles and weak computability, J. Symbolic Logic, 76, 1, 143-176, (2011) · Zbl 1222.03071  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  [Brattka-Pauly-2010] Vasco Brattka and Arno Pauly, Computation with advice, Electronic Proceedings in Theoretical Computer Science 24 (2010), 41–55.  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  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  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  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  Csima, Barbara F.; Mileti, Joseph R., The strength of the rainbow Ramsey theorem, J. Symbolic Logic, 74, 4, 1310-1324, (2009) · Zbl 1188.03044  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  Dzhafarov, Damir D., Cohesive avoidance and strong reductions, Proc. Amer. Math. Soc., 143, 2, 869-876, (2015) · Zbl 1386.03055  Dzhafarov, Damir D.; Jockusch, Carl G., Jr., Ramsey’s theorem and cone avoidance, J. Symbolic Logic, 74, 2, 557-578, (2009) · Zbl 1166.03021  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  [Hirschfeldt-TA] Denis R. Hirschfeldt, Slicing the truth: On the computability theoretic and reverse mathematical analysis of combinatorial principles, to appear. · Zbl 1304.03001  [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  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  Hirst, Jeffry L., Representations of reals in reverse mathematics, Bull. Pol. Acad. Sci. Math., 55, 4, 303-316, (2007) · Zbl 1138.03012  Jockusch, Carl G., Jr., Ramsey’s theorem and recursion theory, J. Symbolic Logic, 37, 268-280, (1972) · Zbl 0262.02042  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  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  Kreuzer, Alexander P.; Kohlenbach, Ulrich, Term extraction and Ramsey’s theorem for pairs, J. Symbolic Logic, 77, 3, 853-895, (2012) · Zbl 1254.03112  Kummer, Martin, A proof of Beigel’s cardinality conjecture, J. Symbolic Logic, 57, 2, 677-681, (1992) · Zbl 0763.03025  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  Mileti, Joseph Roy, Partition theorems and computability theory, 76 pp., (2004), ProQuest LLC, Ann Arbor, MI  Pauly, Arno, On the (semi)lattices induced by continuous reducibilities, MLQ Math. Log. Q., 56, 5, 488-502, (2010) · Zbl 1200.03028  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  Soare, Robert I., Recursively enumerable sets and degrees, Perspectives in Mathematical Logic, xviii+437 pp., (1987), Springer-Verlag, Berlin · Zbl 0623.03042  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  Wang, Wei, Some logically weak Ramseyan theorems, Adv. Math., 261, 1-25, (2014) · Zbl 1307.03011  [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.  [Weihrauch-1992a] \bysame, The tte-interpretation of three hierarchies of omniscience principles, Tech. Report (Informatik Berichte) 130, FernUniversit\"at Hagen, Hagen, September 1992.  Weihrauch, Klaus, Computable analysis, Texts in Theoretical Computer Science. An EATCS Series, x+285 pp., (2000), Springer-Verlag, Berlin · Zbl 0956.68056  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.