[FOM] natural r.e. degrees

[Stephen G Simpson]

NATURAL R.E. DEGREES

Stephen G. Simpson

February 27, 2005


INTRODUCTION

Several of the FOM editors have urged me to post on the topic of
natural r.e. degrees. (Note that "r.e." is a standard abbreviation for
recursively enumerable, and "degrees" is short for degrees of
unsolvability.)

At the request of the FOM editors, I shall stay as far as possible
away from the history of this topic, and concentrate solely on the
scientific issues.

The current situation as regards natural r.e. degrees may be
summarized as follows:

   NNE (No Natural Examples):

   Despite more than 50 years of intensive investigation of the
   r.e. degrees of unsolvability, nobody has yet discovered a
   specific, natural example of an r.e. degree other than the two
   examples originally noted by Turing: 0 = the degree of solvable
   decision problems, and 0' = the degree of the Halting Problem.
   This is in contrast to most other branches of mathematics, which
   are motivated and nurtured by a rich stock of specific, natural
   examples.

This suggests the following problem in mathematical logic:

   NEP (Natural Examples Problem):

   To discover and exhibit at least one specific, natural example of
   an r.e. degree other than 0 and 0'.

To set the stage for our discussion of NNE and NEP, it must be noted
that many researchers, including many experts on r.e. degrees, regard
NNE as an indisputably true description of the current situation.
However, for reasons which I shall not discuss here, at least one
r.e. degree expert, whom I shall not name here, has chosen to dispute
NNE, even though NNE is indisputable.  (The curious reader may search
for "canard" in the FOM archive.)  Furthermore, over a number of
years, this dispute over NNE has caused a great deal of
misunderstanding and confusion in the mathematical logic community.

In a recent attempt to dispell this scientific confusion, I have
written two research papers: "Mass Problems and Randomness" (27 pages,
to appear in the Bulletin of Symbolic Logic), and "An Extension of the
Recursively Enumerable Turing Degrees" (15 pages, submitted for
publication).  These papers are available on my web page at
http://www.math.psu.edu/simpson/papers/.

In my two papers referenced above, I place the dispute over NNE into a
slightly wider mathematical context, aimed at highlighting and
bringing into clearer focus the (already indisputable) truth of NNE,
as well as the nature and urgency of the NEP problem.

My purpose here on FOM is to present a condensed summary of the
principal findings in my two papers referenced above.


PRINCIPAL FINDINGS

First, let R_T be the set of r.e. Turing degrees, i.e., the degrees of
unsolvability of r.e. sets of natural numbers.  Recall that R_T is a
partial ordering and an upper semilattice with bottom element 0 and
top element 0'.

The upshot of more than 50 years of intensive investigation of R_T is
that R_T, viewed as a semilattice, is infinite and structurally rich.

[ For example, the Sacks Splitting Theorem says that every non-zero
degree in R_T is the least upper bound of two other degrees in R_T.
The Sacks Density Theorem says that for every a < b in R_T there
exists c in R_T such that a < c < b. ]

On the other hand, as asserted in NNE, no specific, natural degrees
other than 0 and 0' in R_T are presently known.  NEP is the problem of
finding such a degree.

In order to bring NNE and NEP into sharper focus, I embed R_T into a
slightly larger degree structure, called P_w.  Briefly, P_w is the
lattice of weak degrees of mass problems associated with nonempty,
effectively closed sets in the Cantor space.  For a more leisurely
definition of P_w, see the Appendix below.

My findings concerning the relationship between R_T and P_w are as
follows.

 1. There is a natural embedding I: R_T --> P_w of the semilattice R_T
    into the lattice P_w.  (For the definition of I, see the Appendix
    below.)

 2. The embedding I: R_T --> P_w is one-to-one and respects and
    preserves key algebraic properties of R_T, namely, the bottom and
    top elements, the partial ordering, and the semilattice operation.

 3. The embedding I: R_T --> P_w respects and preserves key structural
    and methodological properties of R_T.

    [ For example, Stephen Binns (Ph.D. thesis, Penn State, 2003) has
    shown that every non-zero degree in P_w is the least upper bound
    of two other degrees in P_w.  Thus the Binns Splitting Theorem for
    P_w is obviously analogous to the Sacks Splitting Theorem for R_T.
    Moreover, the proof of the Binns Splitting Theorem -- by means of
    a priority argument -- is similar to the proof of the Sacks
    Splitting theorem.  In addition, I conjecture that the P_w analog
    of the Sacks Density Theorem holds, and by a similar proof. ]

I summarize findings 1, 2, and 3 by saying that the lattice P_w is an
extension of the semilattice R_T which is in many respects close to
and similar to R_T.

 4. I have exhibited a host of specific, natural degrees in P_w.

    These specific, natural degrees in P_w have names such as 0, 1,
    r_1, r^*_2, d, d_REC, d_POLY, d_EXP, d_ER, d_PR, ..., d^2, d^3,
    ....

    These specific, natural degrees in P_w are ordered as follows:

      1 > r^*_2 > r_1 > d > 0 ,

      r_1 > d_POLY > d_EXP > d_ER > d_PR > ... > d_REC > d > 0 ,

      r_1 > ... > d^3 > d^2 > d > 0 .

    I conjecture that each of the specific, natural degrees d^2, d^3,
    ... is incomparable with each of the specific, natural degrees
    d_POLY, ..., d_REC.
      
    For the definitions of these specific, natural degrees in P_w, see
    the Appendix below.
    
 5. I have shown that these specific, natural degrees in P_w are
    closely related to interesting topics in the foundations of
    mathematics.  The topics are:

       a. algorithmic randomness.

       b. reverse mathematics.

       c. subrecursive hierarchies.

       d. computational complexity.

  6. My discovery of a host of specific, natural, interesting degrees
     in P_w is in striking contrast to the situation in R_T, where no
     specific, natural degrees other than 0 and 0' are known.

     In particular, all of the specific, natural degrees in P_w
     mentioned above are incomparable with all of the degrees in the
     image of R_T under the natural embedding I: R_T --> P_w.  The
     only exceptions to this are 0 = I(0), and 1 = I(0').

In my opinion, findings 1 - 6 above provide an elegant, compelling
demonstration of the sense in which the lack of specific, natural
examples of r.e. degrees (NNE) and the problem of finding such
examples (NEP) are or should be pressing issues for the mathematical
logic community.  Namely, I have done this by showing people what
specific, natural degrees look like in a degree structure, P_w, which
is slightly larger than and closely related to the r.e. degrees, R_T.


ANSWERS TO SOME OBJECTIONS

Naturally, my findings and their significance will be disputed.

A. One logician dismisses my findings 1 - 6 as irrelevant to the NEP
   problem, because the specific, natural degrees which I have
   discovered do not belong to R_T.

   I regard this objection as itself irrelevant.  Of course I admit
   that my findings do not provide a definitive *answer* to NEP, nor
   do they suggest how to find an answer.  However, I maintain that
   that my findings are nevertheless *relevant* to NNE and NEP, in the
   way described above, and in at least one other way which I shall
   not discuss here.

   Speaking generally, it is possible for some new knowledge to be
   *relevant* to a problem, even if it does not provide or suggest the
   *answer* to the problem.  That is the case here.

B. Another logician objects to NNE itself, on the grounds that such a
   statement requires a rigorous mathematical definition of the word
   "natural" as it applies to r.e. degrees.  So long as no such
   definition exists, it is proposed to dismiss statements such as NNE
   as meaningless, unimportant, unenlightening, unproductive,
   contentious, etc.

   I find this stance unreasonable, because it is well known that
   non-rigorous considerations of naturalness have always played a key
   role in almost all high-quality mathematical research, even in the
   absence of rigorous definitions of "naturalness".  Without
   considerations of naturalness, it would be difficult or impossible
   to pursue the ideal of "exquisite taste" in mathematical research,
   as famously enunciated by von Neumann.

C. A more interesting objection to my findings has been raised in a
   series of private conversations, by an expert on r.e. degrees (not
   the same expert who was mentioned in the Introduction above).

   In non-technical terms, the thrust of this expert's objection is
   that NNE is true but does not matter, because specific, natural
   examples are not needed in order to have a rich theory.  I of
   course disagree.  It seems clear to me that, without examples,
   mathematical research topics tend to lose their vitality and fade
   into obscurity.  There are signs that this is already happening to
   the r.e. degrees.

   Actually, I find it remarkable that the r.e. degrees have survived
   for so many years and engaged such an able group of researchers,
   despite the lack of examples.  This certainly sets r.e. degrees
   apart from virtually all other highly developed branches of
   mathematics.

   Unfortunately, the expert just mentioned above is unlikely to post
   on FOM or to address these issues in print.  Thus, the full
   statement of his viewpoint may never see the light of day.  That
   would be unfortunate, because a thorough discussion of his
   viewpoint would get us into a number of interesting technical
   issues.  These issues concern relativization, a conjecture of
   Donald A. Martin, classes of r.e. degrees, and the nature of mass
   problems.

In any case, I would be glad for the chance to discuss these issues
further, with experts or non-experts, on FOM or privately.


APPENDIX: MASS PROBLEMS AND P_w

In this appendix I define the degree structure P_w, state some of its
properties, define the embedding I: R_T --> P_w, and define some
specific, natural degrees in P_w.


1. MASS PROBLEMS AND THEIR WEAK DEGREES

Let N^N be the BAIRE SPACE, i.e., the set of all 1-place total
functions f: N --> N from the natural numbers to the natural numbers.

Informally, we identify a subset P of N^N with the "problem" of
finding an element of P.  A "solution" of this problem is an element
of P.  Problems of this kind are called "MASS PROBLEMS".  Thus a mass
problem is a "generalized decision problem", which may have more than
one solution.  Conversely, a decision problem is a special kind of
mass problem, which has exactly one solution, i.e., P is a singleton
set.  In general, a mass problem may have no solutions, one solution,
or more than one solution.  A mass problem is said to be "SOLVABLE" if
it has at least one solution which is computable.  A mass problem
which is not solvable is said to be "UNSOLVABLE".

Example:

  Let PA = { f in N^N | f is the characteristic function of the set of
  G"odel numbers of theorems of some complete, consistent theory in
  the language of Peano Arithmetic which includes all the axioms of
  Peano Arithmetic }.  Then PA may be viewed as a mass problem,
  namely, the problem of finding a complete, consistent theory
  extending Peano Arithmetic.  According to a familiar theorem of
  Tarski/Mostowski/Robinson, Peano Arithmetic is "essentially
  undecidable", i.e., PA has no computable element.  In other words,
  viewed as a mass problem, PA is unsolvable.

Formally, let P and Q be subsets of N^N.  We say that P is WEAKLY
REDUCIBLE to Q if, given any g in Q, we can use g as a Turing oracle
to compute some f in P.  (Informally this means that, given any
"solution" of the mass problem Q, we can use it to compute a
"solution" of the mass problem P.)

The WEAK DEGREES are the equivalence classes of subsets of N^N under
the equivalence relation of mutual weak reducibility.  The set of all
weak degrees is partially ordered according to weak reducibility.
Thus, the weak degree of P is less than or equal to the weak degree of
Q if and only if P is weakly reducible to Q.

The weak degree of solvable mass problems is denoted 0.  Thus, P is of
weak degree 0 if and only if there exists f in P such that f is Turing
computable, i.e., f is recursive.

The partial ordering of all weak degrees is denoted D_w.  It is
straightforward to show that D_w is a complete distributive lattice,
and that 0 is the least element of D_w.

Let D_T be the upper semilattice of all Turing degrees, i.e., degrees
of unsolvability.  It is straightforward to show that D_T is naturally
embeddable in D_w.  Namely, the Turing degree of f in N^N is
identified with the weak degree of {f}, the singleton set whose only
element is f.


2. THE LATTICE P_w

It is common to regard the set R_T of r.e. Turing degrees as the
smallest or simplest natural, nontrivial substructure of D_T.  We wish
to introduce an analogous set of weak degrees, P_w.  Our guiding
analogy is:

                 P_w / D_w   =   R_T / D_T .

We shall now define P_w.

Let P be a subset of N^N.  P is said to be PI^0_1 if, for some
recursive predicate R,

             P = { f in N^N | (for all n) R(f,n) } .

Here n ranges over N, the set of natural numbers.  Note that a PI^0_1
subset of N^N is sometimes called an EFFECTIVELY CLOSED set, because
it is just the complement within the Baire space N^N of of an
EFFECTIVELY OPEN set, i.e., the union of a recursive sequence of basic
open sets in N^N.

A subset P of N^N is said to be RECURSIVELY BOUNDED if there exists a
recursive function g in N^N such that f(n) < g(n) for all f in P and
all n in N.  Recursively bounded PI^0_1 subsets of N^N are sometimes
called EFFECTIVELY COMPACT.

We define P_w to be the set of weak degrees of nonempty, recursively
bounded, PI^0_1 subsets of N^N.

Remark: 

  It can be shown that every recursively bounded PI^0_1 subset of N^N
  is recursively homeomorphic to, hence weakly equivalent to, a
  recursively bounded PI^0_1 set of a special kind, namely a PI^0_1
  subset of the CANTOR SPACE, {0,1}^N.  (Here the recursive bounding
  function g is the constant function 2, i.e., g(n) = 2 for all n in
  N.)

  Thus P_w may be alternatively defined as the set of weak degrees of
  nonempty PI^0_1 subsets of {0,1}^N.

It is straightforward to show that P_w is a countable distributive
sublattice of D_w, and that P_w has the same bottom element as D_w,
namely 0, the weak degree of solvable mass problems.  This is
analogous to the fact that R_T is a countable subsemilattice of D_T
with the same bottom element as D_T.

It can be shown that P_w has a top element, denoted 1.  It turns out
that 1 is the weak degree of PA, the set of completions of Peano
Arithmetic, as in the Example above.  See also the discussion of 1
below, in the section on specific, natural degrees in P_w.

3. THE EMBEDDING I: R_T --> P_w

The embedding I: R_T --> P_w is defined as follows.  Given d in R_T,
i(d) is defined to be the weak degree of the union of d and PA.  Here
PA is the set of completions of Peano Arithmetic, as above.

[ It is not obvious that i(d) as just defined belongs to P_w.
However, this can be shown as a consequence of a key lemma in my paper
"An Extension of the Recursively Enumerable Turing Degrees". ]

[ It is not obvious that the embedding I: R_T --> P_w is one-to-one.
However, this can be shown as a consequence of a theorem known as the
Arslanov Completeness Criterion. ]

It is straightforward to verify the following facts:

   I(0) = 0 .

   I(0') = 1 .

   I preserves the partial ordering and the semilattice or least upper
   bound operation from R_T.  Namely,

       I(a v b) = I(a) v I(b) ,

   and

       a < b implies I(a) < I(b) .


4. SOME SPECIFIC, NATURAL DEGREES IN P_w

Some specific, natural degrees in P_w are:

    0 = the weak degree of {0,1}^N

      = the weak degree of solvable mass problems.

    1 = the weak degree of PA, the set of completions of Peano
        Arithmetic

      = the weak degree of the set of separating functions for an
        effectively inseparable pair of r.e. sets.

    [ It can be shown that 1 is the top degree in P_w.  We could
    replace Peano Arithmetic by any recursively axiomatizable theory
    which exhibits the G"odel/Rosser effective incompleteness
    property. ]

    r_1 = the weak degree of the set of infinite sequences of 0's and
          1's which are random in the sense of Martin-L"of.

    r^*_2 = inf (r_2, 1), where r_2 is the weak degree of the set of
            infinite sequences of 0's and 1's which are random (in the
            sense of Martin-L"of) relative to the Halting Problem.
    
    d = the weak degree of the set of diagonally non-recursive functions

      = the weak degree of the set of effectively immune sets.

    d_REC = the weak degree of the set of recursively bounded,
            diagonally non-recursive functions.

    d_POLY = the weak degree of the set of polynomially bounded,
             diagonally non-recursive functions.

    d_EXP = the weak degree of the set of exponentially bounded,
            diagonally non-recursive functions.

    d_ER = the weak degree of the set of elementarily recursively
           bounded, diagonally non-recursive functions.

    d_PR = the weak degree of the set of primitively recursively
           bounded, diagonally non-recursive functions.
    ...

    d^2 = the weak degree of the set of pairs (f,g) such that f is
          diagonally non-recursive, and g is diagonally non-recursive
          relative to f.

    d^3 = the weak degree of the set of triples (f,g,h) such that f is
          diagonally non-recursive, g is diagonally non-recursive
          relative to f, and h is diagonally non-recursive relative to
          (f,g).
    ...

[ It is not obvious that all of these weak degrees belong to P_w.
However, this can be shown as a consequence of a key lemma in my paper
"An Extension of the Recursively Enumerable Turing Degrees". ]

THE END