FOM: Natural examples

[Stephen G Simpson]

Shipman, FOM, Thu Oct 14 12:01:19 1999:

 > (I'm a little confused about the precise statement of Cooper's
 > other result that the jump operator itself is definable;

Cooper's old result (around 1989) is that the jump operator is first
order definable in the semilattice of all Turing degrees.  Recently
Shore and Slaman announced a new proof of this, and they say that
Cooper's old proof is incorrect.

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

Yes, that's right, these classes are first order definable in the
semilattice of all Turing degrees.

 > but I also read that Cooper says L(1) is not definable.  Can
 > someone please clarify this by giving precise statements?)

Cooper is saying that L_1 (the class of r.e. degrees x with x'=0') is
not first order definable in the semilattice of r.e. degrees, because
of his automorphism results.  This does not contradict his old result
about definability of the jump operator.

By the way, George Odifreddi pointed out that H_1 *is* first order
definable in the semilattice of r.e. degrees, also by
Nies/Shore/Slaman.  Thanks, George!

On another issue, I pointed out that there are finite sets of
intermediate r.e. degrees whose sup is not intermediate, and Shipman
asked for a reference.  This was first proved by Sacks in the 1960s I
think.  Sacks proved that any nonzero r.e. degree is the sup of two
strictly smaller r.e. degrees.

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

I guess so, but you would really have to ask Cooper, because his
proof may give additional information.

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

I don't know whether the recursion theorists have studied this kind of
issue.  I agree it would be very nice to have some insight about this.

The recursion theorists seem more interested in structural questions
about the semilattice of r.e. degrees, etc, all of which relativize
and therefore are apparently unaffected by the choice of a model of
computation.  There could be some very interesting issues lurking
here.

-- Steve