Medvedev and Muchnik Degrees
of Nonempty $\mathbf{\Pi^0_1}$ Subsets of $\mathbf{2^\omega}$

Stephen G. Simpson
Department of Mathematics
Pennsylvania State University
http://www.math.psu.edu/simpson/

Draft: April 18, 2001

This research was partially supported by NSF grant DMS-0070718.
Subject Classification: 03D30, 03D65.

This is a report for my presentation at the upcoming meeting on Berechenbarkeitstheorie (``Computability Theory''), Oberwolfach, January 21-27, 2001.

We use $2^\omega$ to denote the space of infinite sequences of 0's and 1's. For $X,Y\in2^\omega$, $X\le_TY$ means that X is Turing reducible to Y. For $P,Q\subseteq2^\omega$ we say that P is Muchnik reducible to Q, abbreviated $P\le_wQ$, if for all $Y\in Q$ there exists $X\in P$ such that $X\le_TY$. We say that Pis Medvedev reducible to Q, abbreviated $P\le_MQ$, if there exists a recursive functional $\Phi:Q\to P$. Note that $P\le_MQ$implies $P\le_wQ$, but not conversely.

Sorbi [13] gives a useful survey of Medvedev and Muchnik degrees of arbitrary subsets of $2^\omega$. Here we initiate a study of Medvedev and Muchnik degrees of nonempty $\Pi^0_1$ subsets of $2^\omega$. Theorems 1 and 2 below have been proved in collaboration with my Ph. D. student Stephen Binns.

Let $\mathcal{P}$ be the set of nonempty $\Pi^0_1$ subsets of $2^\omega$. Let $\mathcal{P}_M$ (respectively $\mathcal{P}_w$) be the set of Medvedev (respectively Muchnik) degrees of members of $\mathcal{P}$, ordered by Medvedev (respectively Muchnik) reducibility. We say that $P\in\mathcal{P}$ is Medvedev complete (respectively Muchnik complete) if $P\ge_MQ$(respectively $P\ge_wQ$) for all $Q\in\mathcal{P}$. For example, the set of complete extensions of Peano Arithmetic is Medvedev complete. Clearly every Medvedev complete set is Muchnik complete, but not conversely. $\mathcal{P}_M$ and $\mathcal{P}_w$ are countable distributive lattices with a bottom element, , the degree of $2^\omega$, and a top element, 1, the degree of any Medvedev complete set. The lattice operations are given by $P\times Q=\{X\oplus Y:X\in P$ and $Y\in Q\}$ and $P+Q=\{\langle0\rangle^\frown X:X\in P\}\cup\{\langle1\rangle^\frown Y:Y\in Q\}$. Here $P\times Q$(respectively P+Q) is the join (respectively meet) of P and Q.

In both $\mathcal{P}_M$ and $\mathcal{P}_w$, it is easy to see that P,Q> implies P+Q>, but we do not know whether P,Q<1 implies $P\times Q<\mathbf{1}$. In addition, there are many other open problems. For example, we do not know whether the Sacks Density Theorem holds for $\mathcal{P}_M$ or for $\mathcal{P}_w$. This subject appears to be a rich source of problems for recursion theorists.

Theorem 1   In $\mathcal{P}_w$, for every P>, every countable distributive lattice is lattice embeddable below P.

Proof (sketch).We begin by defining infinitary ``almost lattice'' operations in such a way that, given a recursive sequence $\langle P_i:i\in\omega\rangle$ of members of $\mathcal{P}$, $\prod_{i\in\omega}P_i$ and $\sum_{i\in\omega}P_i$ are again members of $\mathcal{P}$. We define the infinite product in the obvious way, $\prod_{i\in\omega}P_i=\{X\in2^\omega:(X)_i\in P_i$ for all $i\in\omega\}$, where (X)_i(n)=X((n,i)) for all $n\in\omega$. To define the infinite sum, let $\langle T_i:i\in\omega\rangle$ be a recursive sequence of recursive subtrees of $2^{<\omega}$ such that, for each i, P_i is the set of paths through T_i. Let R be a fixed, Medvedev complete member of $\mathcal{P}$. Let T be a recursive subtree of $2^{<\omega}$ such that R is the set of paths through T. Put $\widetilde{T}=\{\tau^\frown\langle k\rangle:\tau\in T,k\in\{0,1\},\tau^\frown\langle k\rangle\notin T\}$. Let $\langle\sigma_i:i\in\omega\rangle$ be a recursive enumeration of $\widetilde{T}$ without repetition. We define the infinite sum $\sum_{i\in\omega}P_i$ to be the set of paths through $T^*=T\cup\{\sigma_i^\frown\tau:i\in\omega,\tau\in T_i\}$. To prove the theorem, construct a recursive sequence $\langle Q_i:i\in\omega\rangle$ of members of $\mathcal{P}$ such that $X\not\le_TY$ for all $X\in Q_i$, $Y\in Q_j$, $i\ne j$. This is a finite injury priority construction, similar to that of Jockusch/Soare [6, Theorem 4.7]. For $i\in\omega$ define $\hat{Q}_i=\sum_{j\ne i}Q_j$. For recursive $A\subseteq\omega$ define $\hat{Q}(A)=\prod_{i\in A}\hat{Q}_i$. We have $\hat{Q}(A)\in\mathcal{P}$ and $\hat{Q}(A\cup B)\equiv_w\hat{Q}(A)\times\hat{Q}(B)$ and $\hat{Q}(A\cap B)\equiv_w\hat{Q}(A)+\hat{Q}(B)$. Moreover $A\ne B$ implies $\hat{Q}(A)\not\equiv_w\hat{Q}(B)$. Thus $A\mapsto\hat{Q}(A)$ is a lattice embedding of the lattice of recursive subsets of $\omega$ into $\mathcal{P}_w$. Note also that every countable distributive lattice is lattice embeddable into the lattice of recursive subsets of $\omega$. To push the embedding below P, assume in addition that $X\not\le_TY$ for all $X\in P$, $Y\in Q_i$, $i\in\omega$. This property can be obtained by a Sacks preservation strategy. Our lattice embedding below P is given by $A\mapsto\hat{Q}(A)+P$. $\Box$

It seems likely that Theorem 1 holds with $\mathcal{P}_w$ replaced by $\mathcal{P}_M$. In this direction we have the following partial result.

Theorem 2   In $\mathcal{P}_M$, for every P>, the free countable distributive lattice is lattice embeddable below P, as are the lattice of finite subsets of $\omega$, the lattice of cofinite subsets of $\omega$, and all finite distributive lattices.

Proof (sketch).With notation as before, we have $\hat{Q}(A\cup B)\equiv_M\hat{Q}(A)\times\hat{Q}(B)$ and $\hat{Q}(A\cap B)\equiv_M\hat{Q}(A)+\hat{Q}(B)$, provided $A,B\subseteq\omega$ are finite. Thus $A\mapsto\hat{Q}(A)+P$ is the desired lattice embedding of the lattice of finite subsets of $\omega$ into $\mathcal{P}_M$ below P. Note also that every finite distributive lattice is lattice embeddable into the lattice of finite subsets of $\omega$. Now assume that $\langle Q_i:i\in\omega\rangle$ has the following stronger properties: (1) $X_i\not\le_TY$ for all $X_i\in Q_i$, $Y\in\prod_{j\ne i}Q_j$, (2) $X\not\le_TY$ for all $X\in P$, $Y\in\prod_{i\in\omega}Q_i$. As before, these properties can be obtained by a finite injury priority argument and a preservation strategy. For $i\in\omega$ define $\check{Q}_i=\prod_{j\ne i}Q_i$. For recursive $A\subseteq\omega$ define $\check{Q}(A)=\sum_{i\in A}\check{Q}_i$. Note that the definition of $\check{Q}(A)$ is dual to that of $\hat{Q}(A)$. We have $\check{Q}(A)\in\mathcal{P}$ and $\check{Q}(A\cap B)\equiv_w\check{Q}(A)\times\check{Q}(B)$ and $\check{Q}(A\cup B)\equiv_w\check{Q}(A)+\check{Q}(B)$. For finite $A,B\subseteq\omega$ we have $\check{Q}(A\cap B)\equiv_M\check{Q}(A)\times\check{Q}(B)$ and $\check{Q}(A\cup B)\equiv_M\check{Q}(A)+\check{Q}(B)$. Thus $\omega\setminus A\mapsto\check{Q}(A)+P$ is the desired lattice embedding of the lattice of cofinite subsets of $\omega$ into $\mathcal{P}_M$ below P. Finally, with Q_i, $i\in\omega$ as above, the Medvedev degrees of Q_i+P, $i\in\omega$ freely generate a free distributive sublattice of $\mathcal{P}_M$ below P. $\Box$

RemarkThe study of the distributive lattices $\mathcal{P}_M$ and $\mathcal{P}_w$ is in some ways parallel to the study of $\mathcal{R}_T$, the upper semilattice of Turing degrees of recursively enumerable subsets of $\omega$. (For background on this topic, see Soare [12].) However, as is well known, there are no specific examples of recursively enumerable degrees $\ne\mathbf{0},\mathbf{0'}$. (See the FOM discussion with Soare [4, July 1999].) In this respect, $\mathcal{P}_M$ and $\mathcal{P}_w$ are much better, as shown by the following two theorems, due to Kucera [7] and Jockusch [5] respectively.

Theorem 3   Among all Muchnik degrees of $\Pi^0_1$ subsets of $2^\omega$ of positive measure, there is a unique largest one. This particular element of $\mathcal{P}_w$ is $\ne\mathbf{0},\mathbf{1}$.

Theorem 4   For $k\ge2$ let DNR_k be the $\Pi^0_1$ set of k-valued DNR functions. In the Medvedev degrees $\mathcal{P}_M$ we have $\mathbf{1}\equiv_M\mathrm{DNR}_2>_M\mathrm{DNR}_3>_M\cdots >_M\mathrm{DNR}_k>_M\cdots>_M\mathbf{0}$. All of these Medvedev degrees are Muchnik complete.

Simpson [11, Theorem 3.20] proves the following analog of Myhill's Theorem on creative sets (see Rogers [9]). This is closely related to a result of Pour-El/Kripke [8].

Theorem 5   If $P,Q\in\mathcal{P}$ are Medvedev complete, then P and Q are recursively homeomorphic.

Proof (sketch).First we define what it means for $P\in\mathcal{P}$ to be productive. Then we use the Recursion Theorem to prove the following two results: (1) P is productive if and only if P is Medvedev complete. (2) Any two productive sets $P,Q\in\mathcal{P}$ are recursively homeomorphic. The details are in Simpson [11, Section 3]. $\Box$

Simpson [11, Theorem 6.9] applies Theorem 5 plus Jockusch/Soare forcing [6, Theorem 2.4] to prove the following result concerning subsystems of second order arithmetic. (For background on this topic, see Simpson [10].)

Theorem 6   There is a countable $\omega$-model S of $\mathsf{WKL}_0$ with the following property. For all $X,Y\in S$, X is definable from Y over S if and only if $X\le_TY$.

Bibliography

1

S. B. Cooper, T. A. Slaman, and S. S. Wainer, editors.
Computability, Enumerability, Unsolvability: Directions in Recursion Theory.
Number 224 in London Mathematical Society Lecture Notes. Cambridge University Press, 1996.
VII + 347 pages.

2

H.-D. Ebbinghaus, G.H. Müller, and G.E. Sacks, editors.
Recursion Theory Week.
Number 1141 in Lecture Notes in Mathematics. Springer-Verlag, 1985.
IX + 418 pages.

3

J.-E. Fenstad, I. T. Frolov, and R. Hilpinen, editors.
Logic, Methodology and Philosophy of Science VIII.
Studies in Logic and the Foundations of Mathematics. Elsevier, 1989.
XVII + 702 pages.

4

FOM e-mail list.
http://www.math.psu.edu/simpson/fom/, September 1997 to the present.

5

Carl G. Jockusch, Jr.
Degrees of functions with no fixed points.
In [3], pages 191-201, 1989.

6

Carl G. Jockusch, Jr. and Robert I. Soare.
$\Pi^0_1$ classes and degrees of theories.
Transactions of the American Mathematical Society, 173:35-56, 1972.

7

Antonín Kucera.
Measure, $\Pi^0_1$ classes and complete extensions of PA.
In [2], pages 245-259, 1985.

8

Marian B. Pour-El and Saul Kripke.
Deduction-preserving ``recursive isomorphisms'' between theories.
Fundamenta Mathematicae, 61:141-163, 1967.

9

Hartley Rogers, Jr.
Theory of Recursive Functions and Effective Computability.
McGraw-Hill, 1967.
XIX + 482 pages.

10

Stephen G. Simpson.
Subsystems of Second Order Arithmetic.
Perspectives in Mathematical Logic. Springer-Verlag, 1999.
XIV + 445 pages.

11

Stephen G. Simpson.
$\Pi^0_1$ sets and models of $\mathsf{WKL}_0$.
April 2000.
Preprint, 28 pages, to appear.

12

Robert I. Soare.
Recursively Enumerable Sets and Degrees.
Perspectives in Mathematical Logic. Springer-Verlag, 1987.
XVIII + 437 pages.

13

Andrea Sorbi.
The Medvedev lattice of degrees of difficulty.
In [1], pages 289-312, 1996.

About this document ...

Medvedev and Muchnik Degrees
of Nonempty $\mathbf{\Pi^0_1}$ Subsets of $\mathbf{2^\omega}$

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 oberwf.

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