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

### Steve Simpson

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

### TIME AND LOCATION
TBA

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