Some results on the structure of the [sigma]2 enumeration degrees
Seema Ahmad · Summit (Simon Fraser University) · 1989
A s+l for every s, and jWe l e a denotes a fixed acceptable numbering of the r.e.sets and { ' Z } e .s~ denotes a fixed standard enumeration of the r.e.sets.The symbol K is reserved for {e: e E We} which has Turing degree O m .Intuitively.A is enumeration reducible to B if there is an effective procedure for producing an enumeration of A from any enumeration of B. There is a natural one-one correspondence between all such procedures and the r.e.sets (see Rogers [I9671 (pp.145-147)).Hence the i-th enumeration operator (e-operator) is defined by z (DJ and U. Vu [h(€I.X,y.s) ( u ( s + Dx c X I], otherwise 1 if F ! € w:(xS), H(0.X.F.s) = { p < s 3 [F w e and vu [ I 6 u 5 s 3 D ExU]~.otherwise.h(8.X.y.s) and H(8.X.y. s) are called history functions.Remrk.If U(B.X.~.S)~ G xS+' (u(B.x.F,s)~ G xS+l) then h(8.~.y,s+l)l = h(8.X.y.s) and u ( ~. ~. ~. s + l ) ~ = u(8,X.y.s) (H(~.x.F.s+~)~ = H(8.X.F.s) and u(B.x,F.s+~)~= U(8,X.F.s)).Hence if Y E 8(X) (F S 8(X)).then h(8.X.y.s) and u(8.X.y.s) (H(8.X.F.s) and U(8.X.F.s)) reach limits denoted by h(8,X.y)and u(9.X.y) (H(8 ,X.F) and U(8.X.F) ) respectively.Note that the definition of h(8.X.y.s) and u(8,X.y.s)only t On { ' t and {X Itis.Hence given recursive sequences t {et}te Oe.Let Q = 9 -{po.pl, . . ., pn}.We partition Q * into sets Pi, where i 5 n and Qi = {q E Q: i = pj [q 2 p ] } .Let A. E ai for i I n.For every q E Q we construct a Z2 set B L 9 such that for every i n, q E Qi, and the following maximal independence properties hold: and (2.2.3)For every s E 9, set Then * x Now it is clear that s 2 t implies f ( s ) Ie f ( t ) .Suppose t i s .Assume t = Pi ( i <_ n ) .Then f ( t ) = at and By 2.2.2 f ( t ) = ai ie f ( s ) .Assume t = q, where q E Q. ( i < n ) .Then deg, B < f ( t ) and 7. Q -e By 2.2.3 deg, B $ f ( s ) .therefore f ( t ) ie f ( s ) .Hence f is the ' -4 e