FOM: natural r.e. degrees; Pi01 classes

[Stephen G Simpson]

This is a contribution to the recent FOM discussion of the lack of
natural examples in the theory of r.e. sets and degrees.  

The discussion was initiated by Harvey Friedman in 28 Jul 1999
16:34:09

 > Usually, when mathematicians undertake an intensive investigation
 > of some specific structure or class of structures, the need for
 > such an investigation has already been motivated by a set of
 > specific, natural examples showing the richness and interest of the
 > subject.  For instance, group theory was motivated by a wealth of
 > examples such as matrix groups, permutation groups, symmetries of
 > geometrical figures, etc.  Contrast this with the r.e. sets and
 > degrees that are so much beloved by recursion theorists.  The only
 > natural examples known to date are the original ones, i.e. the
 > halting problem and the complete r.e. degree.  Thus there is really
 > only one example, and that example is highly atypical of the way
 > the subject has developed.  It is reasonable to wonder whether this
 > lack of examples may indicate some sort of defect or imbalance in
 > the subject.

and continued by Cooper, Odifreddi, Soare, Davis, Shipman, and
Friedman.  Before today I have not been directly involved in this
discussion.  Now I am getting involved, partly at Friedman's urging,
in order to do penance for my earlier ``trivial'' postings
(cf. Friedman, FOM 5 Aug 1999 16:40:22, ``no more trivia'').

The group theory example is not unique.  Virtually all branches of
mathematics follow this pattern: first a rich set of important natural
examples, then the general theory.  Think of algebraic number theory,
real analysis, complex analysis, differential geometry, etc etc.  The
study of r.e. sets and degrees appears to be an exception to this
pattern.  Is it the only exception?  What are the consequences of a
lack of natural examples for a branch of mathematics?

Odifreddi 4 Aug 1999 10:06:24 pointed out that the set of
non-Kolmogorov-random natural numbers

       { n : {m}(0) = n for some m < n }

is a ``sort-of natural'' example of an r.e. set which is simple in the
sense of Post, hence not many-one complete.  Friedman 4 Aug 1999
12:07:26 said

 > it is most interesting to try to see if Odifreddi's example can be
 > improved, since it relies on an artificial encoding, any one of
 > which seems to be unnatural. So it probably does not meet the
 > normal criteria most mathematicians apply - at least without
 > modification.

Here presumably Friedman is referring to the encoding of Turing
machines by natural numbers, and to the use of Turing machines
themselves.

Furthermore, as Odifreddi also mentioned, the set of
non-Kolmogorov-random numbers is not *Turing* incomplete.  One way to
see this is to apply the Arslanov completeness criterion, as expounded
for instance in Soare's 1987 monograph on r.e. sets and degrees.  The
Arslanov criterion points up a serious difficulty or obstacle to
finding natural examples of nonrecursive r.e. sets which are Turing
incomplete.

If the problem of finding natural examples of incomplete nonrecursive
r.e. degrees seems difficult, I would like to suggest a perhaps easier
problem: to find natural examples of nonempty Pi01 subclasses of
2^omega which have no recursive members yet are ``incomplete'' in some
appropriate sense.

If P and Q are nonempty Pi01 subclasses of 2^omega with no recursive
members, let us say that P is less than or equal to Q if for every Y
in Q there exists X in P such that X is Turing reducible to Y.  (Has
this ordering been studied by the experts on Pi01 classes?)  There are
well-known natural examples of Pi01 classes that are complete with
respect to this ordering.  What about ones that are incomplete?  I
have not thought about this very long or hard.  Maybe other FOM
participants can quickly come up with natural examples.

The class of 1-random reals provides an example which some people
might consider natural.  The 1-random reals have the following
properties: (1) there exists a Pi01 class P of 1-random reals which is
of positive measure; (2) if Q is any Pi01 class of positive measure,
then any 1-random real differs finitely from some element of Q.  Now
any P as in (1) is necessarily incomplete with respect to the
above-mentioned ordering, and (2) suggests a sense in which P is
natural, being ``essentially'' just the class of all 1-random reals.

[ Background: 

A real (i.e., an element of 2^omega) is said to be 1-random if it does
not belong to any effective null G_delta set of reals.  An effective
null G_delta is a set of reals of the form

   U_0 intersect U_1 intersect ... intersect U_n intersect ...

where U_0, U_1, ..., U_n, ... is a decreasing, recursively indexed
sequence of Sigma^0_1 sets of reals such that for all n, the measure
of U_n is less than 1/2^n.  

Being 1-random is equivalent to being random in the sense of
Chaitin/Solovay (I thank Stuart Kurtz for pointing this out to me in
off-line discussion) and in the sense of Martin-Lof 1966 (see remark
X.1.8 in my book ``Subsystems of Second Order Arithmetic''
<http://www.math.psu.edu/simpson/sosoa/>).

]

-- Steve