Medvedev Degrees, Muchnik Degrees,

Subsystems of , and Reverse Mathematics

Stephen G. Simpson

Pennsylvania State University

`simpson@math.psu.edu`

April 18, 2001

Subsystems of , 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 , consisting of plus Weak König's Lemma.

Let
be the set of nonempty
subsets of
.
Forcing with
is known as Jockusch/Soare
forcing. I have used iterated Jockusch/Soare forcing to obtain an
-model *M* of
with the following property:
for all ,
*X* is definable over *M* from *Y* if and only if
.
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
one says that *P* is Muchnik reducible to *Q*if for all
there exists
such that .
One
says that *P* is Medvedev reducible to *Q* if there exists a recursive
functional
.
I introduce the countable distributive
lattices
(
)
consisting of the Muchnik
(Medvedev) degrees of members of
.
I have shown that
is Muchnik (Medvedev) complete if and only if *P* is
degree isomorphic (recursively homeomorphic) to the set of complete
extensions of
.

Structural aspects of and 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 . We have also obtained partial results in this direction for .

The lattices
and
are in some respects
similar to the upper semilattice of Turing degrees of recursively
enumerable subsets of .
However,
and
are much better in that they contain specific, known,
natural examples of degrees .
Such examples are especially
relevant for f.o.m. In
there is the maximum Muchnik
degree of
subsets of
of positive measure. This
is of interest for the reverse mathematics of measure theory. In
there are the Medvedev degrees of
is
*k*-valued DNR,
.
This is of interest for the reverse
mathematics of graph coloring.

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

This document was generated using the
**LaTeX**2`HTML` 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