On uniform relationships between combinatorial problems
 Author
 François G Dorais, Damir D Dzhafarov, Jeffry L Hirst, Joseph R Mileti and Paul Shafer (UGent)
 Organization
 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 nonuniform decisions about how to proceed in a given construction. In practice, however, if a theorem Q implies a theorem P, it is usually because there is a direct uniform translation of the problems represented by P into the problems represented by 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 >= 1, if j < k, then Ramsey's theorem for ntuples and k many colors is not uniformly, or Weihrauch, reducible to Ramsey's theorem for ntuples 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 Konig'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.
 Keywords
 PAIRS, RAINBOW RAMSEY THEOREM, PRINCIPLES, AVOIDANCE, STRENGTH
Downloads

DoraisDzhafarovHirstMiletiShaferUniformRelations.pdf
 full text
 
 open access
 
 
 508.32 KB
Citation
Please use this url to cite or link to this publication: http://hdl.handle.net/1854/LU7175617
 MLA
 Dorais, François G et al. “On Uniform Relationships Between Combinatorial Problems.” TRANSACTIONS OF THE AMERICAN MATHEMATICAL SOCIETY 368.2 (2016): 1321–1359. Print.
 APA
 Dorais, F. G., Dzhafarov, D. D., Hirst, J. L., Mileti, J. R., & Shafer, P. (2016). On uniform relationships between combinatorial problems. TRANSACTIONS OF THE AMERICAN MATHEMATICAL SOCIETY, 368(2), 1321–1359.
 Chicago authordate
 Dorais, François G, Damir D Dzhafarov, Jeffry L Hirst, Joseph R Mileti, and Paul Shafer. 2016. “On Uniform Relationships Between Combinatorial Problems.” Transactions of the American Mathematical Society 368 (2): 1321–1359.
 Chicago authordate (all authors)
 Dorais, François G, Damir D Dzhafarov, Jeffry L Hirst, Joseph R Mileti, and Paul Shafer. 2016. “On Uniform Relationships Between Combinatorial Problems.” Transactions of the American Mathematical Society 368 (2): 1321–1359.
 Vancouver
 1.Dorais FG, Dzhafarov DD, Hirst JL, Mileti JR, Shafer P. On uniform relationships between combinatorial problems. TRANSACTIONS OF THE AMERICAN MATHEMATICAL SOCIETY. 2016;368(2):1321–59.
 IEEE
 [1]F. G. Dorais, D. D. Dzhafarov, J. L. Hirst, J. R. Mileti, and P. Shafer, “On uniform relationships between combinatorial problems,” TRANSACTIONS OF THE AMERICAN MATHEMATICAL SOCIETY, vol. 368, no. 2, pp. 1321–1359, 2016.
@article{7175617, 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 nonuniform decisions about how to proceed in a given construction. In practice, however, if a theorem Q implies a theorem P, it is usually because there is a direct uniform translation of the problems represented by P into the problems represented by 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 >= 1, if j < k, then Ramsey's theorem for ntuples and k many colors is not uniformly, or Weihrauch, reducible to Ramsey's theorem for ntuples 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 Konig'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.}, author = {Dorais, François G and Dzhafarov, Damir D and Hirst, Jeffry L and Mileti, Joseph R and Shafer, Paul}, issn = {00029947}, journal = {TRANSACTIONS OF THE AMERICAN MATHEMATICAL SOCIETY}, keywords = {PAIRS,RAINBOW RAMSEY THEOREM,PRINCIPLES,AVOIDANCE,STRENGTH}, language = {eng}, number = {2}, pages = {13211359}, title = {On uniform relationships between combinatorial problems}, url = {http://dx.doi.org/10.1090/tran/6465}, volume = {368}, year = {2016}, }
 Altmetric
 View in Altmetric
 Web of Science
 Times cited: