Muchnik and Medvedev Degrees of Pi01 Subsets of 2omega

Steve Simpson

(Penn State University,



 Let P and Q be nonempty Pi01 subsets of 2omega. 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 WKL0. 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 Pi01 subsets of 2omega of positive Lebesgue measure has a maximum element, and this particular Muchnik degree is incomparable with the Muchnik degrees of all thin perfect Pi01 subsets of 2omega. In this respect, the Muchnik and Medvedev degrees of nonempty Pi01 subsets of 2omega are much better than the Turing degrees of recursively enumerable subsets of omega.