The density theorem for the Muchnik lattice

Stephen G. Simpson Department of Mathematics Pennsylvania State University http://www.math.psu.edu/simpson/ simpson@math.psu.edu

June 24, 2015

This is my abstract for a Workshop on Computability Theory, Bucharest, June 27–28, 2015.

Let E_{T} be the upper semilattice of recursively enumerable Turing degrees. There is a strong analogy between E_{T} and E_{w}, the lattice of Muchnik degrees of nonempty Π_{1}^{0} subsets of {0, 1}^{ℕ}. The most famous structural theorems concerning E_{T} are the Splitting Theorem (Sacks 1962) and the Density Theorem (Sacks 1964). The analogous Splitting Theorem for E_{w} was proved by Stephen Binns and published in 2003. The analogous Density Theorem for E_{w} has been a long-standing open question, but it was recently proved by Binns, Shore, and Simpson and will appear in a forthcoming paper. In this talk I shall sketch the proof of the Density Theorem for E_{w}. The proof involves a small amount of hyperarithmetical theory.