FOM: Natural examples

[Stephen G Simpson]

Shipman (FOM, Mon Oct 11 14:26:03 1999) asks some questions about
natural definitions of individual r.e. degrees and classes of
r.e. degrees.

A few remarks:

1.  FIRST ORDER DEFINABILITY IN THE SEMILATTICE

Some of Shipman's questions equate ``naturalness'' to first order
definability over the semilattice of r.e. degrees.  It is known that
many classes of r.e. degrees are ``natural'' in this technical sense.
Indeed, for a class C of r.e. degrees to be first order definable over
the semilattice, it suffices that (1) C is arithmetical and (2) for
all r.e. degrees x and y, if x'' = y'' then x is in C iff y is in C.
This general result is due to Nies/Shore/Slaman, Proc London Math Soc,
1998.  In particular, this applies to each of the classes L_n and H_n,
at least for n > 1.  Here L_n (H_n) is the class of so-called low-n
(high-n) r.e. degrees, i.e., those whose nth jump is equal to the nth
jump of 0 (0').

2.  NATURAL FIRST ORDER DEFINITIONS IN THE SEMILATTICE

In a more restricted sense of ``naturalness'', the first order
definitions produced by Nies/Shore/Slaman are arguably not very
natural, because (a) they are very long and complicated when written
out in full, (b) they arise in an artificial way, by interpreting the
standard model of first order arithmetic into the semilattice.  And it
is unclear whether there exist alternative first order semilattice
definitions which are natural in this more restricted sense.  Shore
himself makes this criticism, as well as a similar criticism of the
results in my old paper on first order definability in the semilattice
of all Turing degrees with the jump operator, Annals of Math, 1977.

A good reference for all this is Shore's writeup of his talk at the
CTA meeting (see http://www.math.psu.edu/simpson/cta/), entitled
``Natural Definability in Degree Structures''.  As Shore points out,
there are at least some non-trivial classes of r.e. degrees with first
order semilattice definitions that are natural even in the more
restricted sense, i.e., easily understandable in terms of the
semilattice itself.  For instance, there is the class M of nonzero
r.e. degrees x such that inf(x,y)=0 for some nonzero r.e. degree y.

3.  COOPER'S AUTOMORPHISM RESULTS

Cooper's results say that there is no individual r.e. degree other
than 0 and 0' that is first order definable in the semilattice, or
even fixed by all automorphisms of the semilattice.  However, the
experts other than Cooper are not yet ready to accept Cooper's
automorphism results, despite the fact that Cooper's detailed writeup
has been available for several years.  One such expert is Shore.  In
the current draft of Shore's writeup mentioned above, Shore states
this as an open question (Question 2.16).

To an outsider such as myself, this situation seems quite remarkable.
Cooper, a highly respected expert on r.e. degrees, proves a theorem
that is of key importance in this field, yet the other experts are
unable to adjudicate the correctness of the theorem.  What is going on
here?  Is this field getting too technical even for the experts?

4.  LACK OF NATURAL EXAMPLES OF R.E. DEGREES

There is currently no individual r.e. degree other than 0 and 0' that
is even a candidate for being simply or naturally describable *by any
means whatsoever* (not only by first order definability over the
semilattice).  This is, in my opinion, a very significant fact.  This
fact, unlike the other results cited above, goes to the very heart of
the issue of the lack of examples of r.e. degrees.  It is directly
relevant to Friedman's far-reaching critique of the whole subject of
r.e. degrees.  See for instance my FOM postings of Wed Jul 28 16:40:30
1999 and Fri Aug 13 13:46:04 1999, and Friedman's series of FOM
postings on ``Central Issues in Foundations'' beginning Sep 1 1999.

5. SOME SPECIFIC POINTS RAISED BY SHIPMAN

 > Precise version 1.3: Is there a naturally defined SET of intermediate
 > degrees?
 > 
 > Answer: Yes, for example the "High" degrees satisfying d'=0'', or the
 > "Low" degrees satisfying d'=0'.

These classes of r.e. degrees are ``natural'' in an obvious sense, but
I am not so sure they are first order definable in the semilattice.
However, the set M (see above) surely qualifies as a non-trivial,
naturally defined class of r.e. degrees, in this and even more
restricted senses of naturalness.

 > Whatever the definition of "natural", there cannot be a naturally
 > defined FINITE set of intermediate degrees unless there is a
 > naturally defined SINGLETON intermediate degree, because one could
 > join the finite collection together in an natural way to obtain a
 > single intermediate degree.

I don't understand.  There are finite sets of r.e. degrees strictly
between 0 and 0' whose lattice-theoretic join (i.e. least upper bound)
is 0'.  Did you intend ``join'' in some other sense?

6. R.E. DEGREES IN CORE MATHEMATICS ???

 > Precise version 2.3: Has any collection of c.e. sets that was defined in
 > "ordinary mathematics" (this can be made precise using the standard
 > Mathematics subject Classifications, but I won't bother) included SOME
 > but NOT ALL sets of intermediate degree?
 > 
 > Answer: I think not,

I agree.  That is correct.  There is no known set of r.e. sets arising
from core mathematics that includes r.e. sets of some but not all
r.e. degrees other than 0 and 0'.

 > but if an ordinary mathematical structure reflects the c.e. degrees
 > with sufficient faithfulness, then the analogues of the "high" and
 > "low" degrees may become "natural".  For example, if the jump
 > operator had some reasonable interpretation that stayed within the
 > "ordinary mathematics", this would be the case; this is not true
 > for finitely presented groups or diophantine equations, but I don't
 > know whether this is true for other examples (like the work of
 > Nabutovsky and Weinberger that Soare has recommended).

Despite Soare's claims, it is also not true of Nabutovsky/Weinberger.
This statement is based on my reading of Nabutovsky/Weinberger.

-- Steve