On the Degrees of Index Sets. II
C. E. M. Yates · Transactions of the American Mathematical Society · 1969
In [8] we proved that the index-set corresponding to any recursively enumerable degree a is of the highest isomorphism-type possible for sets belonging to S3(a).From the proof of this result we derived Sacks' theorem [4] that the recursively enumerable degrees are dense.In the present paper we classify three other indexsets associated with any given recursively enumerable degree a, namely the indexsets corresponding to the recursively enumerable sets which are respectively of degree á«, ä a and incomparable with a.We then use the indirect method of [8] to extend three theorems of Sacks ([3], [5]); these extensions were announced in [8].Finally, amongst other results we infer from our classifications that certain enumerations are not recursively enumerable; for example, the recursively enumerable degrees (as distinct from sets) can not be recursively enumerated without repetitions.We shall use most of the definitions employed in [8], but our notation will be slightly different and so we restate the more important definitions.One superficial but convenient change is that we shall do recursion-theory mainly on the positive integers rather than the nonnegative integers, since this leaves 0 free for various special purposes.Therefore, the terms "number" and "set" should be reinterpreted accordingly.We now assemble some of the definitions that we shall use.If A is a set then we let A(x) =1 if xe A and A(x) = 2if x<£ A. For any number e and set A we define the partial function 0^ by putting 0^(x)= ¡7(minyFi(e,x,v)); we follow the convention of setting U(0) = 0.For each e and s we define x e Rse <-* (3y)ySsTx(e, x, y); if Re = USR% then Rx, R2,..., is an enumeration of all recursively enumerable sets.If S is any recursively enumerable set then each number e such that Re = S is called an index of S. We recall that an «-ary sequence {Ah ,J of recursively enumerable sets is called recursively enumerable if there is a recursive function a(ix,..., in) such that Ati_An = Ra(h.wfor all ix, ...,/".A class of recursively enumerable sets is called recursively enumerable if it can be ordered into a recursively enumerable sequence.The index-set G(si) of a class si of sets is defined by e e G(sf) Re is of degree a.