Infinite subsets of random sets of integers

Infinite subsets of random sets of integers
Mathematical Research Letters 16 (2009), no. 1, 103—110.

This paper was written in Fall 2007 in Hawaii. It was superseded by a paper in J. Mathematical Logic 2011.

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

Self-embeddings of computable trees

Self-embeddings of computable trees (with Stephen Binns, Manuel Lerman, Jim Schmerl, and Reed Solomon).
Notre Dame Journal of Formal Logic 49 (2008), no. 1, 1—37.

I was probably the least-involved of the five authors of this paper, which was written in 2005-2006 at UConn.

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.

On a conjecture of Dobrinen and Simpson concerning almost everywhere domination

On a conjecture of Dobrinen and Simpson concerning almost everywhere domination (with Stephen Binns, Manuel Lerman, and Reed Solomon). Journal of Symbolic Logic 71 (2006), no. 1, 119—136.

This paper was concerned with the difference between highness and almost everywhere domination in the Turing degrees. This was taken further in later papers.

Lowness for the class of Schnorr random reals

Lowness for the class of Schnorr random reals (with André Nies and Frank Stephan).SIAM Journal on Computing 35 (2005), no. 3, 647—657 (electronic).

In this paper the idea of mixed lowness notions seems to have been born (?). This idea actually occurred to me while unlocking my bicycle in Heidelberg.

Comparing DNR and WWKL

Comparing DNR and WWKL (with Klaus Ambos-Spies, Steffen Lempp, and Theodore A. Slaman).
Journal of Symbolic Logic
69 (2004), no. 4, 1089—1104.

This paper (which is mentioned in Wikipedia under Reverse Mathematics) separated DNR from WWKL. It was mostly written while all four authors were in Heidelberg during 2002-2003.

Local initial segments of the Turing degrees

Local initial segments of the Turing degrees
Bulletin of Symbolic Logic
9 (2003), no. 1, 26—36.

This paper described the results of my doctoral dissertation “Lattice initial segments of the Turing degrees”.