of Nonempty Subsets of

**Stephen G. Simpson
Department of Mathematics
Pennsylvania State University
**

**Draft: April 18, 2001**

This research was partially supported by NSF grant DMS-0070718.

Subject Classification: 03D30, 03D65.

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 *P**is 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<*

*
*

*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*, *P*_{i} is the set of paths through *T*_{i}. 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.

*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 *Q*_{i},
as above, the Medvedev degrees of
*Q*_{i}+*P*,
freely generate a free distributive sublattice
of
below *P*.

**Remark**The 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.

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

*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].)

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

of Nonempty Subsets of

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

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