All posts by admin

Finding paths through narrow and wide trees

History of the paper

2006

The paper was written at UConn.

2009

Paper appeared in print:

Finding paths through narrow and wide trees
(with Stephen E. Binns). Journal of Symbolic Logic 74 (2009), no. 1, 349—360.

2012

Laurent Bienvenu and Paul Shafer discovered an apparent error in the proof of Lemma 4.6. There it is stated that A wtt-reduces to B; however, it seems that the reduction of A to B also requires oracle access to f. Corollary 4.7 also seems false (take f to be a ML random of hyperimmune-free degree, and A=f; then A is complex but not f-complex).

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.