On uniform relationships between combinatorial problems
HTML articles powered by AMS MathViewer
- by François G. Dorais, Damir D. Dzhafarov, Jeffry L. Hirst, Joseph R. Mileti and Paul Shafer PDF
- Trans. Amer. Math. Soc. 368 (2016), 1321-1359 Request permission
Abstract:
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.
References
- Klaus Ambos-Spies, Bjørn Kjos-Hanssen, Steffen Lempp, and Theodore A. Slaman, Comparing DNR and WWKL, J. Symbolic Logic 69 (2004), no. 4, 1089–1104. MR 2135656, DOI 10.2178/jsl/1102022212
- Jeremy Avigad, Edward T. Dean, and Jason Rute, Algorithmic randomness, reverse mathematics, and the dominated convergence theorem, Ann. Pure Appl. Logic 163 (2012), no. 12, 1854–1864. MR 2964874, DOI 10.1016/j.apal.2012.05.010
- Andreas Blass, 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., vol. 222, Cambridge Univ. Press, Cambridge, 1995, pp. 61–81. MR 1356008, DOI 10.1017/CBO9780511629150.004
- Vasco Brattka, Matthew de Brecht, and Arno Pauly, Closed choice and a uniform low basis theorem, Ann. Pure Appl. Logic 163 (2012), no. 8, 986–1008. MR 2915694, DOI 10.1016/j.apal.2011.12.020
- Vasco Brattka and Guido Gherardi, Weihrauch degrees, omniscience principles and weak computability, J. Symbolic Logic 76 (2011), no. 1, 143–176. MR 2791341, DOI 10.2178/jsl/1294170993
- Vasco Brattka, Guido Gherardi, and Alberto Marcone, The Bolzano-Weierstrass theorem is the jump of weak Kőnig’s lemma, Ann. Pure Appl. Logic 163 (2012), no. 6, 623–655. MR 2889550, DOI 10.1016/j.apal.2011.10.006
- Vasco Brattka and Arno Pauly, Computation with advice, Electronic Proceedings in Theoretical Computer Science 24 (2010), 41–55.
- Peter A. Cholak, Mariagnese Giusto, Jeffry L. Hirst, and Carl G. Jockusch Jr., Free sets and reverse mathematics, Reverse mathematics 2001, Lect. Notes Log., vol. 21, Assoc. Symbol. Logic, La Jolla, CA, 2005, pp. 104–119. MR 2185429
- Peter A. Cholak, Carl G. Jockusch, and Theodore A. Slaman, On the strength of Ramsey’s theorem for pairs, J. Symbolic Logic 66 (2001), no. 1, 1–55. MR 1825173, DOI 10.2307/2694910
- C. T. Chong, Theodore A. Slaman, and Yue Yang, The metamathematics of stable Ramsey’s theorem for pairs, J. Amer. Math. Soc. 27 (2014), no. 3, 863–892. MR 3194495, DOI 10.1090/S0894-0347-2014-00789-X
- Chris J. Conidis and Theodore A. Slaman, Random reals, the rainbow Ramsey theorem, and arithmetic conservation, J. Symbolic Logic 78 (2013), no. 1, 195–206. MR 3087070, DOI 10.2178/jsl.7801130
- Barbara F. Csima and Joseph R. Mileti, The strength of the rainbow Ramsey theorem, J. Symbolic Logic 74 (2009), no. 4, 1310–1324. MR 2583822, DOI 10.2178/jsl/1254748693
- Rodney G. Downey and Denis R. Hirschfeldt, Algorithmic randomness and complexity, Theory and Applications of Computability, Springer, New York, 2010. MR 2732288, DOI 10.1007/978-0-387-68441-3
- Damir D. Dzhafarov, Cohesive avoidance and strong reductions, Proc. Amer. Math. Soc. 143 (2015), no. 2, 869–876. MR 3283673, DOI 10.1090/S0002-9939-2014-12261-1
- Damir D. Dzhafarov and Carl G. Jockusch Jr., Ramsey’s theorem and cone avoidance, J. Symbolic Logic 74 (2009), no. 2, 557–578. MR 2518811, DOI 10.2178/jsl/1243948327
- Harvey M. Friedman, Stephen G. Simpson, and Rick L. Smith, Countable algebra and set existence axioms, Ann. Pure Appl. Logic 25 (1983), no. 2, 141–181. MR 725732, DOI 10.1016/0168-0072(83)90012-X
- Denis R. Hirschfeldt, Slicing the truth: On the computability theoretic and reverse mathematical analysis of combinatorial principles, to appear.
- Denis R. Hirschfeldt and Carl G. Jockusch, Jr., On notions of computability theoretic reduction between ${\Pi }^1_2$ principles, to appear.
- Denis R. Hirschfeldt and Richard A. Shore, Combinatorial principles weaker than Ramsey’s theorem for pairs, J. Symbolic Logic 72 (2007), no. 1, 171–206. MR 2298478, DOI 10.2178/jsl/1174668391
- Jeffry L. Hirst, Representations of reals in reverse mathematics, Bull. Pol. Acad. Sci. Math. 55 (2007), no. 4, 303–316. MR 2369116, DOI 10.4064/ba55-4-2
- Carl G. Jockusch Jr., Ramsey’s theorem and recursion theory, J. Symbolic Logic 37 (1972), 268–280. MR 376319, DOI 10.2307/2272972
- Carl G. Jockusch Jr., Degrees of functions with no fixed points, Logic, methodology and philosophy of science, VIII (Moscow, 1987) Stud. Logic Found. Math., vol. 126, North-Holland, Amsterdam, 1989, pp. 191–201. MR 1034562, DOI 10.1016/S0049-237X(08)70045-4
- Carl G. Jockusch Jr. and Robert I. Soare, $\Pi ^{0}_{1}$ classes and degrees of theories, Trans. Amer. Math. Soc. 173 (1972), 33–56. MR 316227, DOI 10.1090/S0002-9947-1972-0316227-0
- Alexander P. Kreuzer and Ulrich Kohlenbach, Term extraction and Ramsey’s theorem for pairs, J. Symbolic Logic 77 (2012), no. 3, 853–895. MR 2987141, DOI 10.2178/jsl/1344862165
- Martin Kummer, A proof of Beigel’s cardinality conjecture, J. Symbolic Logic 57 (1992), no. 2, 677–681. MR 1169201, DOI 10.2307/2275299
- Manuel Lerman, Reed Solomon, and Henry Towsner, Separating principles below Ramsey’s theorem for pairs, J. Math. Log. 13 (2013), no. 2, 1350007, 44. MR 3125903, DOI 10.1142/S0219061313500074
- Joseph Roy Mileti, Partition theorems and computability theory, ProQuest LLC, Ann Arbor, MI, 2004. Thesis (Ph.D.)–University of Illinois at Urbana-Champaign. MR 2706695
- Arno Pauly, On the (semi)lattices induced by continuous reducibilities, MLQ Math. Log. Q. 56 (2010), no. 5, 488–502. MR 2742884, DOI 10.1002/malq.200910104
- Stephen G. Simpson, Subsystems of second order arithmetic, 2nd ed., Perspectives in Logic, Cambridge University Press, Cambridge; Association for Symbolic Logic, Poughkeepsie, NY, 2009. MR 2517689, DOI 10.1017/CBO9780511581007
- Robert I. Soare, Recursively enumerable sets and degrees, Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1987. A study of computable functions and computably generated sets. MR 882921, DOI 10.1007/978-3-662-02460-7
- Wei Wang, Rainbow Ramsey theorem for triples is strictly weaker than the arithmetical comprehension axiom, J. Symbolic Logic 78 (2013), no. 3, 824–836. MR 3135500, DOI 10.2178/jsl.7803070
- Wei Wang, Some logically weak Ramseyan theorems, Adv. Math. 261 (2014), 1–25. MR 3213294, DOI 10.1016/j.aim.2014.05.003
- 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.
- —, The tte-interpretation of three hierarchies of omniscience principles, Tech. Report (Informatik Berichte) 130, FernUniversität Hagen, Hagen, September 1992.
- Klaus Weihrauch, Computable analysis, Texts in Theoretical Computer Science. An EATCS Series, Springer-Verlag, Berlin, 2000. An introduction. MR 1795407, DOI 10.1007/978-3-642-56999-9
- Xiaokang Yu and Stephen G. Simpson, Measure theory and weak König’s lemma, Arch. Math. Logic 30 (1990), no. 3, 171–180. MR 1080236, DOI 10.1007/BF01621469
Additional Information
- François G. Dorais
- Affiliation: Department of Mathematics, Dartmouth College, Hanover, New Hampshire 03755-3551
- Email: francois.g.dorais@dartmouth.edu
- Damir D. Dzhafarov
- Affiliation: Department of Mathematics, University of Connecticut, Storrs, Connecticut 06269
- MR Author ID: 781680
- ORCID: 0000-0003-4921-7561
- Email: damir@math.uconn.edu
- Jeffry L. Hirst
- Affiliation: Department of Mathematical Sciences, Appalachian State University, Boone, North Carolina 28608-2092
- MR Author ID: 242430
- ORCID: 0000-0002-8273-8951
- Email: jlh@math.appstate.edu
- Joseph R. Mileti
- Affiliation: Department of Mathematics and Statistics, Grinnell College, Grinnell, Iowa 50112
- Email: miletijo@grinnell.edu
- Paul Shafer
- Affiliation: Department of Mathematics, Ghent University, Ghent, Belgium
- MR Author ID: 920651
- ORCID: 0000-0001-5386-9218
- Email: paul.shafer@ugent.be
- Received by editor(s): October 30, 2012
- Received by editor(s) in revised form: December 2, 2013, and March 16, 2014
- Published electronically: April 9, 2015
- Additional Notes: The second author was partially supported by an NSF Postdoctoral Fellowship
The third author was partially supported by grant ID#20800 from the John Templeton Foundation. The opinions expressed in this publication are those of the authors and do not necessarily reflect the views of the John Templeton Foundation
The fifth author was supported by the Fondation Sciences Mathématiques de Paris and is also an FWO Pegasus Long Postdoctoral researcher - © Copyright 2015 American Mathematical Society
- Journal: Trans. Amer. Math. Soc. 368 (2016), 1321-1359
- MSC (2010): Primary 03B30, 05D10; Secondary 05D40, 05D15, 03D32, 03D80, 03F35
- DOI: https://doi.org/10.1090/tran/6465
- MathSciNet review: 3430365