Medvedev Degrees, Muchnik Degrees, Subsystems of Z_{2}, and Reverse Mathematics

Stephen G. Simpson Pennsylvania State University

                  simpson@math.psu.edu

April 18, 2001

Foundations of mathematics (f.o.m.) is the study of the most basic concepts and logical structure of mathematics as a whole. An important f.o.m. research program is reverse mathematics, where one discovers which subsystems of second order arithmetic are necessary and sufficient to prove specific theorems in core mathematical areas: analysis, algebra, geometry, countable combinatorics. One of the most important subsystems for reverse mathematics is WKL_{0}, consisting of RCA_{0} plus Weak König’s Lemma.

Let P be the set of nonempty Π_{1}^{0} subsets of 2^{ω}. Forcing with P is known as Jockusch/Soare forcing. I have used iterated Jockusch/Soare forcing to obtain an ω-model M of WKL_{0} with the following property: for all X, Y ∈ M, X is definable over M from Y if and only if X ≤_{T} Y. The proof is based on a homogeneity argument involving the Recursion Theorem, and a factorization lemma. I discuss the foundational significance of M and its hyperarithmetical analog.

For P, Q ∈ P one says that P is Muchnik reducible to Q if for all Y ∈ Q there exists X ∈ P such that X ≤_{T} Y. One says that P is Medvedev reducible to Q if there exists a recursive functional Φ : Q → P. I introduce the countable distributive lattices P_{w} (P_{M}) consisting of the Muchnik (Medvedev) degrees of members of P. I have shown that P ∈ P is Muchnik (Medvedev) complete if and only if P is degree isomorphic (recursively homeomorphic) to the set of complete extensions of PA.

Structural aspects of P_{w} and P_{M} present a rich problem area for recursion theorists. Stephen Binns and I have shown that every countable distributive lattice is lattice-embeddable below any nonzero degree in P_{w}. We have also obtained partial results in this direction for P_{M}.

The lattices P_{w} and P_{M} are in some respects similar to the upper semilattice of Turing degrees of recursively enumerable subsets of ω. However, P_{w} and P_{M} are much better in that they contain specific, known, natural examples of degrees ≠ 0, 1. Such examples are especially relevant for f.o.m. In P_{w} there is the maximum Muchnik degree of Π_{1}^{0} subsets of 2^{ω} of positive measure. This is of interest for the reverse mathematics of measure theory. In P_{M} there are the Medvedev degrees of {X : X is k-valued DNR}, k ≥ 3. This is of interest for the reverse mathematics of graph coloring.

   For references see http://www.math.psu.edu/simpson/talks/obwf0101/.