Donate to arXiv
Please join the Simons Foundation and our generous member organizations in supporting arXiv during our giving campaign September 23-27. 100% of your contribution will fund improvements and new initiatives to benefit arXiv's global scientific community.
[secure site, no need to create account]
dev.arxiv.org > math > arXiv:1212.0157
Mathematics > Logic
arXiv:1212.0157 (math)
[Submitted on 1 Dec 2012 (v1), last revised 16 Apr 2015 (this version, v5)]
Title:On uniform relationships between combinatorial problems
Authors:François G. Dorais, Damir D. Dzhafarov, Jeffry L. Hirst, Joseph R. Mileti, Paul Shafer
Abstract: The enterprise of comparing mathematical theorems according to their logical strength is an active area in mathematical logic. In this setting, called reverse mathematics, 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. 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 does not uniformly reduce to Ramsey's theorem for $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. Uniform 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.
Subjects: Logic (math.LO)
Cite as: arXiv:1212.0157 [math.LO]
(or arXiv:1212.0157v5 [math.LO] for this version)
From: François G. Dorais [view email]
[v1] Sat, 1 Dec 2012 20:42:03 UTC (35 KB)
[v2] Tue, 3 Dec 2013 14:20:18 UTC (44 KB)
[v3] Tue, 18 Mar 2014 14:54:35 UTC (44 KB)
[v4] Tue, 22 Apr 2014 11:19:47 UTC (44 KB)
[v5] Thu, 16 Apr 2015 13:37:51 UTC (44 KB)
math.LO