FOM: lack of examples of r.e. Turing degrees
Stephen G Simpson
simpson at math.psu.edu
Wed Apr 5 21:38:07 EDT 2000
My paper ``Pi01 Sets and Models of WKL0'' (on-line at
http://www.math.psu.edu/simpson/papers/, discussed in my posting of
April 3, 2000) contains the following remark. This is relevant to and
refers to the extensive FOM discussion of the lack of natural examples
of r.e. Turing degrees, in July-August 1999.
By the way, I regard this as a good example of how to cite FOM
postings in published papers.
-- Steve
----------
Remark 2.21. Let L_M be the lattice of Medvedev degrees of nonempty
Pi^0_1 subsets of 2^omega, as in Theorem 2.2. There are many obvious
structural questions to ask about L_M. One may ask about
embeddability, initial segments, final segments, definability,
automorphisms, etc. There is reason to believe that a study of
structural aspects of the distributive lattice L_M could be more
rewarding than the ongoing study of the structural aspects of R_T, the
upper semilattice of Turing degrees of recursively enumerable subsets
of omega, as pursued for instance in (word omitted) [26]. For one
thing, there is a (words omitted) lack of natural examples of elements
of R_T, but there are some interesting natural examples of elements of
L_M. In particular, putting
DNR_k = {X in k^omega : forall n (X(n) not equal to {n}(n))} ,
Jockusch [12] has shown that DNR_2 >_M DNR_3 >_M ... >_M DNR_k >_M
..., k < omega, and of course DNR_2 is Medvedev complete (see the
proof of Lemma 2.14). See also Simpson [23], [24] and other FOM
postings in the same thread.
[8] FOM e-mail list. http://www.math.psu.edu/simpson/fom/, September
1997 to the present.
[23] Stephen G. Simpson. FOM: natural r.e. degrees; Pi01 classes.
FOM e-mail list [8], August 13, 1999.
[24] Stephen G. Simpson. FOM: priority arguments;
Kleene-r.e. degrees; Pi01 classes. FOM e-mail list [8], August
16, 1999.
More information about the FOM
mailing list