FOM: Natural examples: reply to Simpson

[Joe Shipman]

Simpson:

>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.

I understood this; definability in the semilattice was just one possible
way of being "natural".  Definable in the semilattice with the jump
operator is another way, which obviously suffices here.  (I'm a little
confused about the precise statement of Cooper's other result that the
jump operator itself is definable; the most obvious interpretation of
this would imply that the iterated High and Low degrees
L(1),H(1),L(2),H(2),L(3)... are all definable as sets of degrees [e.g.
by equations d'=0' and the like], but I also read that Cooper says L(1)
is not definable.  Can someone please clarify this by giving precise
statements?)

> > 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?

Hmm.  Maybe I am wrong here.  I had in mind the following construction:
given intermediate degrees d1 and d2 corresponding to computable partial
functions F1 and F2, construct the partial function G

G(2n)=F1(n)
G(2n+1)=F2(n).

But I see now that this need not be of intermediate degree as I had
supposed.  Who originally proved the result you state (which must
obviously be true for a pair of degrees if it is true for a finite
set)?  I guess that it is still open, then, whether there is a definable
finite set of intermediate degrees (since Cooper's nonrigidity result
applies only to individual degrees and there could be an intermediate
degree whose orbit under the automorphism group was finite).

>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?

I second this.  Given the obvious importance of the result, if after a
couple of years the experts are willing neither to assent to the proof
NOR to assert that it has a gap, then either something is wrong with the
experts, or something is wrong with the field, or something is wrong
with the common understanding of the sociology mathematical proof (and
this is obviously of foundational significance and deserves further
discussion here).

Proofs can be extraordinarily difficult to verify.  Harvey Friedman's
recent paper "Finite Functions and the Necessary Use of Large
Cardinals"  in "Annals of Mathematics" is an example of a very difficult
and technical proof that required a great effort to verify; I know that
Dougherty of OSU has verified it and presume the referees did also.   A
fair question is "how much time should be necessary before the proof is
declared incomplete"?  Obviously a few weeks is not enough, but it seems
that two years ought to be.

I am still interested in the issue of sensitivity of degrees in a
construction to one's basis (choice of enumeration of the c.e.
functions) for computation.  Constructions like the one from the Soare
book that Fenner detailed for us obviously don't depend on any specific
basis to establish that the constructed set has the required property;
but it's a much harder question whether the degree of the constructed
set depends on the basis, or whether, if it does depend on the basis,
the different degrees attained are equivalent modulo automorphisms of
the degrees.

-- Joe Shipman