Weak Degrees of Π_{1}^{0} Subsets of 2^{ω}

Stephen G. Simpson Department of Mathematics Pennsylvania State University

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

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 ⊆ 2^{ω} 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 Π_{1}^{0} subsets of 2^{ω}, 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 ≤, the semilattice operation ∨, 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}.