Medvedev Degrees, Muchnik Degrees,
Subsystems of $\mathsf{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 $\mathsf{WKL}_0$, consisting of $\mathsf{RCA}_0$ plus Weak König's Lemma.

Let $\mathcal{P}$ be the set of nonempty $\Pi^0_1$ subsets of $2^\omega$. Forcing with $\mathcal{P}$ is known as Jockusch/Soare forcing. I have used iterated Jockusch/Soare forcing to obtain an $\omega$-model M of $\mathsf{WKL}_0$ with the following property: for all $X,Y\in M$, X is definable over M from Y if and only if $X\le_TY$. 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\in\mathcal{P}$ one says that P is Muchnik reducible to Qif for all $Y\in Q$ there exists $X\in P$ such that $X\le_TY$. One says that P is Medvedev reducible to Q if there exists a recursive functional $\Phi:Q\to P$. I introduce the countable distributive lattices $\mathcal{P}_w$ ( $\mathcal{P}_M$) consisting of the Muchnik (Medvedev) degrees of members of $\mathcal{P}$. I have shown that $P\in\mathcal{P}$ is Muchnik (Medvedev) complete if and only if P is degree isomorphic (recursively homeomorphic) to the set of complete extensions of $\mathsf{PA}$.

Structural aspects of $\mathcal{P}_w$ and $\mathcal{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 $\mathcal{P}_w$. We have also obtained partial results in this direction for $\mathcal{P}_M$.

The lattices $\mathcal{P}_w$ and $\mathcal{P}_M$ are in some respects similar to the upper semilattice of Turing degrees of recursively enumerable subsets of $\omega$. However, $\mathcal{P}_w$ and $\mathcal{P}_M$ are much better in that they contain specific, known, natural examples of degrees $\ne0,1$. Such examples are especially relevant for f.o.m. In $\mathcal{P}_w$ there is the maximum Muchnik degree of $\Pi^0_1$ subsets of $2^\omega$ of positive measure. This is of interest for the reverse mathematics of measure theory. In $\mathcal{P}_M$ there are the Medvedev degrees of $\{X:X$ is k-valued DNR$\}$, $k\ge3$. This is of interest for the reverse mathematics of graph coloring.

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

About this document ...

This document was generated using the LaTeX2HTML translator Version 98.1p1 release (March 2nd, 1998)

Copyright © 1993, 1994, 1995, 1996, 1997, Nikos Drakos, Computer Based Learning Unit, University of Leeds.

The command line arguments were:
latex2html -split 0 obwfabs.

The translation was initiated by Stephen G Simpson on 2001-04-18