Stephen G. Simpson Department of Mathematics Pennsylvania State University

                       simpson@math.psu.edu
                 http://www.math.psu.edu/simpson/

Abstract for talk at University of Lisbon July 19, 2001

Muchnik and Medvedev Degrees of Π_{1}^{0} Subsets of 2^{ω}

Let P and Q be nonempty Π_{1}^{0} subsets of 2^{ω}. 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 ω-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 Π_{1}^{0} subsets of 2^{ω} 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 Π_{1}^{0} subsets of 2^{ω}. In this respect, the Muchnik and Medvedev degrees of nonempty Π_{1}^{0} subsets of 2^{ω} are much better than the Turing degrees of recursively enumerable subsets of ω.