Stephen G. Simpson (simpson@math.psu.edu), Department of Mathematics, Pennsylvania State University, University Park, State College PA 16802. Muchnik Degrees of Π_{1}^{0} Subsets of 2^{ω}.

Let P be the set of nonempty Π_{1}^{0} subsets of 2^{ω}. For P, Q ∈ P say that P is Muchnik reducible to Q, abbreviated P ≤_{w} Q, if for all Y ∈ Q there exists X ∈ P such that X is Turing reducible to Y. The Muchnik degree of P is the equivalence class of P under the equivalence relation P ≡_{w} Q, i.e., P ≤_{w} Q and Q ≤_{w} P. The Muchnik degrees of members of P form a countable distributive lattice with 0 and 1. Call this lattice P_{w}. By Binns/Simpson 2000, every countable distributive lattice is lattice embeddable in every nontrivial initial segment of P_{w}. We prove that P ∈ P is of Muchnik degree 1 if and only if the Turing degrees of members of P are precisely the Turing degrees of completions of Peano Arithmetic. We prove that, among Muchnik degrees of members of P of positive measure, there is a largest one, call it r_{1}. We prove that r_{1} ∈ P_{w} is meet-irreducible and does not join to 1. Call P ∈ P thin if P \ Q ∈ P for all Q ∈ P. By Martin/Pour-El 1970, there exists a thin P ∈ P such that the Muchnik degree of P is not 0. By Downey 1982/1987 and Downey/Jockusch/Stob 1990/1996, many such Muchnik degrees exist. We prove that all such Muchnik degree are incomparable with r_{1}.