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.



What is "Seetapun Enigma"?
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](http://www.math.uchicago.edu/~antonio/RM11/schedule.html) at University of Chicago in September 2011. The [slides from that talk](http://www.math.uchicago.edu/~antonio/RM11/RM%20talks/jiayi.pdf) 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)


