Weak Degrees of Pi^0_1 Subsets of 2^omega Stephen G. Simpson Department of Mathematics Pennsylvania State University http://www.personal.psu.edu/t20/ June 16, 2005 Note: This is an abstract of an invited one-hour talk, to be given in a Recursion Theory workshop, part of the program Computational Prospects of Infinity, June 20 to August 15, 2005, at the Institute for Mathematical Sciences, National University of Singapore. Abstract Let P,Q subseteq 2^omega be viewed as mass problems, i.e., "decision problems with more than one solution." We say that the mass problem P is weakly reducible to the mass problem Q if, for every solution Y of Q, there exists a solution X of P such that X is Turing reducible to Y. A weak degree is an equivalence class of mass problems under mutual weak reducibility. (Weak degrees are also known as Muchnik degrees.) Let P_w be the set of weak degrees of nonempty Pi^0_1 subsets of 2^omega, partially ordered by weak reducibility. It is easy to see that P_w is a countable distributive lattice. The speaker and others have studied P_w in a series of publications beginning in 1999. Our principal findings are as follows. 1. There is a natural embedding of R_T, the countable semilattice of recursively enumerable Turing degrees, into P_w. This embedding is one-to-one and preserves the partial ordering leq, the semilattice operation v, and the top and bottom elements 0 and 0'. We identify R_T with its image in P_w under this embedding. 2. Like the semilattice R_T, the lattice P_w is structurally rich. In particular, any countable distributive lattice is lattice embeddable in any nontrivial initial segment of P_w. Also, the P_w analog of the Sacks Splitting Theorem holds. These structural results are proved by means of priority arguments. The P_w analog of the Sacks Density Theorem remains as an open problem. 3. Unlike R_T, the lattice P_w contains a large number of specific, natural degrees other than the top and bottom elements. These specific, natural degrees in P_w are related to foundationally interesting topics such as reverse mathematics, algorithmic randomness, subrecursive hierarchies from Gentzen-style proof theory, and computational complexity. 4. All of these specific, natural degrees in P_w are incomparable with all of the recursively enumerable Turing degrees in R_T. The only exceptions are 0 and 0', the top and bottom elements of R_T, which are the same as the top and bottom elements of P_w.