next up previous

Medvedev Degrees, Muchnik Degrees,
Subsystems of
$\mathsf{Z}_2$, and Reverse Mathematics

Stephen G. Simpson
Pennsylvania State University

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

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

next up previous
Stephen G Simpson