Weak Degrees of Pi^0_1 Subsets of 2^omega

Stephen G. Simpson
Department of Mathematics
Pennsylvania State University

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.


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.