Skip to main content
MathOverflow

Return to Answer

added 5 characters in body
Source Link
Carl Mummert
Carl Mummert
  • 9.7k
  • 1
  • 46
  • 68

The results I have mentioned left the question open whether $\mathsf{RT}^2_2$ implies $\mathsf{WKL}_0$. This was recently solved by Liu in 2011. Liu showed in a still-unpublished paper that $\mathsf{RT}^2_2$ does not imply $\mathsf{WWKL}_0$, which is the restriction of $\mathsf{WKL}_0$ to trees of positive measure $1$, and which is strictly weaker than $\mathsf{WKL}_0$. Thus, combining results, $\mathsf{RT}^2_2$ and $\mathsf{WKL}_0$ are mutually independent.

The results I have mentioned left the question open whether $\mathsf{RT}^2_2$ implies $\mathsf{WKL}_0$. This was recently solved by Liu in 2011. Liu showed in a still-unpublished paper that $\mathsf{RT}^2_2$ does not imply $\mathsf{WWKL}_0$, which is the restriction of $\mathsf{WKL}_0$ to trees of measure $1$, and which is strictly weaker than $\mathsf{WKL}_0$. Thus, combining results, $\mathsf{RT}^2_2$ and $\mathsf{WKL}_0$ are mutually independent.

The results I have mentioned left the question open whether $\mathsf{RT}^2_2$ implies $\mathsf{WKL}_0$. This was recently solved by Liu in 2011. Liu showed in a still-unpublished paper that $\mathsf{RT}^2_2$ does not imply $\mathsf{WWKL}_0$, which is the restriction of $\mathsf{WKL}_0$ to trees of positive measure, and which is strictly weaker than $\mathsf{WKL}_0$. Thus, combining results, $\mathsf{RT}^2_2$ and $\mathsf{WKL}_0$ are mutually independent.

Source Link
Carl Mummert
Carl Mummert
  • 9.7k
  • 1
  • 46
  • 68

The question seems to be about the following special form of Ramsey's Theorem:

$\mathsf{RT}^2_2$: for every $2$-coloring of the unordered pairs from $\mathbb{N}$ there is an infinite subset of $\mathbb{N}$ for which all unordered pairs receive the same color.

which is a special case of

$\mathsf{RT}^n_k$: for every $k$-coloring of the unordered $n$-tuples from $\mathbb{N}$ there is an infinite subset of $\mathbb{N}$ for which all unordered $n$-tuples receive the same color.

The computability strength of infinite Ramsey's theorem was first studied by Jockusch (1972). When interpreted in modern terminology that didn't exist then, Jockusch's result is that $\mathsf{RT}^n_k$ is equivalent to $\mathsf{ACA}_0$ whenever $n \geq 3$ and $k \geq 2$. The equivalence is over the standard base system $\mathsf{RCA}_0$ which is assumed in the rest of this post. As a corollary, $\mathsf{ACA}_0$ proves $\mathsf{RT}^2_k$ for all $k \geq 2$.

Later, Hirst (1987) characterized the strength of principles of the form $\mathsf{RT}^1_k$. The separate results of Jockusch and Hirst leave a gap for exponent $2$, and in particular for $\mathsf{RT}^2_2$. The exact reverse mathematics strength of $\mathsf{RT}^2_2$ is somewhat mysterious, although I don't know that anyone calls it an "enigma". It has proven to be a particularly difficult open problem.

The first result was due to Seetapun (published as Seetapun and Slaman (1995)), who showed that $\mathsf{RT}^2_2$ does not imply $\mathsf{ACA}_0$. The fact that this seemingly weak result was all that could be obtained hints at the difficulty of finding the exact strength of $\mathsf{RT}^2_2$ with known methods. Seetapun's proof used an intricate forcing argument. The ideas behind this argument have been progressively clarified and extended, and are now well understood; the most recent paper on this is by Dzhafarov and Jockusch (2009).

The principle $\mathsf{WKL}_0$ says that every infinite subtree of $2^{<\mathbb{N}}$ has an infinite path. $\mathsf{WKL}_0$ is one of the "big five" systems of reverse mathematics, and is the natural comparison point for principles weaker than $\mathsf{ACA}_0$ such as $\mathsf{RT}^2_2$.

Cholak, Jockusch, and Slaman (2001) made the next significant progress on $\mathsf{RT}^2_2$. Among many other new results they showed that $\mathsf{RT}^2_2$ is not provable in $\mathsf{WKL}_0$, because $\mathsf{WKL}_0$ does not prove the principle $\mathsf{COH}$ which is provable from $\mathsf{RT}^2_2$. The principle $\mathsf{COH}$ is a formalized statement of a theorem from recursion theory about the existence of $r$-cohesive sets.

The results I have mentioned left the question open whether $\mathsf{RT}^2_2$ implies $\mathsf{WKL}_0$. This was recently solved by Liu in 2011. Liu showed in a still-unpublished paper that $\mathsf{RT}^2_2$ does not imply $\mathsf{WWKL}_0$, which is the restriction of $\mathsf{WKL}_0$ to trees of measure $1$, and which is strictly weaker than $\mathsf{WKL}_0$. Thus, combining results, $\mathsf{RT}^2_2$ and $\mathsf{WKL}_0$ are mutually independent.

As I understand it, Liu proved this independently while a student at Central South University (China), without an advisor in logic or any graduate training in logic. Liu presented his result at the Reverse Mathematics workshop at University of Chicago in September 2011. The slides from that talk are available online, but they are quite technical. The proof uses another intricate forcing argument.

As I understand it, Liu's paper was submitted to a journal some time before the workshop, the results have been verified by referees, and the paper will be published once it is in final form.

Citations

  • Cholak, Peter A.; Jockusch, Carl G.; Slaman, Theodore A. On the strength of Ramsey's theorem for pairs. J. Symbolic Logic 66 (2001), no. 1, 1–55. MR1825173 (2002c:03094)

  • Dzhafarov, Damir D.; Jockusch, Carl G., Jr. Ramsey's theorem and cone avoidance. J. Symbolic Logic 74 (2009), no. 2, 557–578. MR2518811 (2010e:03052)

  • Hirst, Jeffry Lynn. Combinatorics in subsystems of second-order arithmetic. PhD Thesis, The Pennsylvania State University. 1987. 153 pp.

  • Jockusch, Carl G., Jr. Ramsey's theorem and recursion theory. J. Symbolic Logic 37 (1972), 268–280. MR0376319 (51 #12495)

  • Seetapun, David; Slaman, Theodore A. On the strength of Ramsey's theorem. Special Issue: Models of arithmetic. Notre Dame J. Formal Logic 36 (1995), no. 4, 570–582. MR1368468 (96k:03136)