What is "Seetapun Enigma"?

2012-03-25T07:12:37Z

A friend of mine just asked me this very question. While I had some training in combinatorics, I have never heard of the "Seetapun Enigma", which, supposedly, is related to the Ramsey's theorem. A quick Google search provides nothing useful, nor was Math.StackExchange of any help. Does anyone know what it is, and what is the significance of its solution/proof/refutation.

Answer by Carl Mummert for What is "Seetapun Enigma"?

2012-03-25T17:50:26Z

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 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.

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)

Answer by Brian for What is "Seetapun Enigma"?

2012-03-29T21:27:32Z

it's been solved (proved wrong) by a Chinese undergraduate student. You may want to check his paper coming in http://www.aslonline.org/journals-journal.html

What is "Seetapun Enigma"? - MathOverflow

What is "Seetapun Enigma"?

Answer by Carl Mummert for What is "Seetapun Enigma"?

Answer by Brian for What is "Seetapun Enigma"?