# Medvedev and Muchnik Degrees of Nonempty Subsets of

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 to denote the space of infinite sequences of 0's and 1's. For , means that X is Turing reducible to Y. For we say that P is Muchnik reducible to Q, abbreviated , if for all there exists such that . We say that Pis Medvedev reducible to Q, abbreviated , if there exists a recursive functional . Note that implies , but not conversely.

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

Let be the set of nonempty subsets of . Let (respectively ) be the set of Medvedev (respectively Muchnik) degrees of members of , ordered by Medvedev (respectively Muchnik) reducibility. We say that is Medvedev complete (respectively Muchnik complete) if (respectively ) for all . For example, the set of complete extensions of Peano Arithmetic is Medvedev complete. Clearly every Medvedev complete set is Muchnik complete, but not conversely. and are countable distributive lattices with a bottom element, , the degree of , and a top element, 1, the degree of any Medvedev complete set. The lattice operations are given by and and . Here (respectively P+Q) is the join (respectively meet) of P and Q.

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

Theorem 1   In , 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 of members of , and are again members of . We define the infinite product in the obvious way, for all , where (X)i(n)=X((n,i)) for all . To define the infinite sum, let be a recursive sequence of recursive subtrees of such that, for each i, Pi is the set of paths through Ti. Let R be a fixed, Medvedev complete member of . Let T be a recursive subtree of such that R is the set of paths through T. Put . Let be a recursive enumeration of without repetition. We define the infinite sum to be the set of paths through . To prove the theorem, construct a recursive sequence of members of such that for all , , . This is a finite injury priority construction, similar to that of Jockusch/Soare [6, Theorem 4.7]. For define . For recursive define . We have and and . Moreover implies . Thus is a lattice embedding of the lattice of recursive subsets of into . Note also that every countable distributive lattice is lattice embeddable into the lattice of recursive subsets of . To push the embedding below P, assume in addition that for all , , . This property can be obtained by a Sacks preservation strategy. Our lattice embedding below P is given by .

It seems likely that Theorem 1 holds with replaced by . In this direction we have the following partial result.

Theorem 2   In , for every P>, the free countable distributive lattice is lattice embeddable below P, as are the lattice of finite subsets of , the lattice of cofinite subsets of , and all finite distributive lattices.

Proof (sketch).With notation as before, we have and , provided are finite. Thus is the desired lattice embedding of the lattice of finite subsets of into below P. Note also that every finite distributive lattice is lattice embeddable into the lattice of finite subsets of . Now assume that has the following stronger properties: (1) for all , , (2) for all , . As before, these properties can be obtained by a finite injury priority argument and a preservation strategy. For define . For recursive define . Note that the definition of is dual to that of . We have and and . For finite we have and . Thus is the desired lattice embedding of the lattice of cofinite subsets of into below P. Finally, with Qi, as above, the Medvedev degrees of Qi+P, freely generate a free distributive sublattice of below P.

RemarkThe study of the distributive lattices and is in some ways parallel to the study of , the upper semilattice of Turing degrees of recursively enumerable subsets of . (For background on this topic, see Soare [12].) However, as is well known, there are no specific examples of recursively enumerable degrees . (See the FOM discussion with Soare [4, July 1999].) In this respect, and 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 subsets of of positive measure, there is a unique largest one. This particular element of is .

Theorem 4   For let DNRk be the set of k-valued DNR functions. In the Medvedev degrees we have . 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 are Medvedev complete, then P and Q are recursively homeomorphic.

Proof (sketch).First we define what it means for 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 are recursively homeomorphic. The details are in Simpson [11, Section 3].

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 -model S of with the following property. For all , X is definable from Y over S if and only if .

## 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.
classes and degrees of theories.
Transactions of the American Mathematical Society, 173:35-56, 1972.

7
Antonín Kucera.
Measure, 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.
sets and models of .
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.

Medvedev and Muchnik Degrees
of Nonempty Subsets of

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

Stephen G Simpson
2001-04-18