FOM: lack of examples of r.e. Turing degrees

[Stephen G Simpson]

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.