All posts by admin

The strength of some combinatorial principles related to Ramsey’s theorem

The strength of some combinatorial principles related to Ramsey’s theorem
(with Denis R. Hirschfeldt, Carl G. Jockusch, Steffen Lempp, and Theodore A. Slaman.) Computational Prospects of Infinity. Part II: Presented Talks, Lecture Notes Series, Institute of Mathematical Sciences, National University of Singapore, vol. 15, World Scientific Publishing, Hackensack, NJ, 2008, pp. 143—162.

This paper established that Stable Ramsey’s Theorem for pairs implies DNR, which is a weak form of WKL.
It was later shown by Liu in 2011 that Ramsey’s theorem for pairs does not imply WKL (which is what we really wanted to know!).

This paper was written while all authors were participating in the Computational Prospects of Infinity workshop in Singapore in 2005.