Muchnik and Medvedev Degrees of Pi^{0}_{1} 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^{0}_{1} 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_{0}. 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^{0}_{1} 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^{0}_{1} subsets
of 2^{omega}. In this respect, the Muchnik and Medvedev
degrees of nonempty Pi^{0}_{1} subsets of
2^{omega} are much better than the Turing degrees of
recursively enumerable subsets of omega.