Muchnik and Medvedev Degrees of Pi⁰₁ Subsets of 2^omega
Stephen G. Simpson (Penn State University, t20@psu.edu)
July 19, 2001, University of Lisbon

Let P and Q be nonempty Pi⁰₁ subsets of 2^omega. We say that P is Muchnik (respectively Medvedev) reducible to Q if every element of Q computes an element of P (uniformly). Muchnik reducibility is closely related to the study of omega-models of subsystems of WKL₀. Medvedev reducibility is equivalent by Stone duality to the existence of recursive homomorphisms of recursively presented Boolean algebras, as studied by Pour-El/Kripke and Martin/Pour-El. Of course we can also study these reducibilities for their own sake. The Muchnik (respectively Medvedev) degrees form a countable distributive lattice with 0 and 1. Every countable distributive lattice is lattice-embeddable in every nontrivial initial segment of the Muchnik degrees. For the Medvedev degrees, we have strong partial results in the same direction. These embedding results are due to Stephen Binns and myself. The Muchnik (respectively Medvedev) degree of P is 1 if and only if P is degree isomorphic (respectively recursively homeomorphic) to the set of complete extensions of PA. We have natural examples of Muchnik and Medvedev degrees other than 0 and 1. In particular, the set of Muchnik degrees of Pi⁰₁ subsets of 2^omega of positive Lebesgue measure has a maximum element. This particular Muchnik degree does not join to 1, and is incomparable with the Muchnik degrees of all thin perfect Pi⁰₁ subsets of 2^omega. In this respect, the Muchnik and Medvedev degrees of nonempty Pi⁰₁ subsets of 2^omega are much better than the Turing degrees of recursively enumerable subsets of omega.