Stephen G. Simpson
Department of Mathematics
Pennsylvania State University
Draft: April 18, 2001
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  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.
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.
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 .) 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  and Jockusch  respectively.
Simpson [11, Theorem 3.20] proves the following analog of Myhill's Theorem on creative sets (see Rogers ). This is closely related to a result of Pour-El/Kripke .
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 .)
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