### Muchnik and
Medvedev Degrees of Pi^{0}_{1} Subsets of
2^{omega}

### Stephen G. Simpson

### (Penn State University, t20@psu.edu)

### May 2, 2001

*Mathematics
Department, U of MN*

** 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, and this particular Muchnik
degree 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.