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.