Recursive enumerability and the jump operator
Gerald E. Sacks · Transactions of the American Mathematical Society · 1963
By degree we mean degree of recursive unsolvability as defined by Kleene and Post in [4].Following Shoenfield [7], we say a degree c is recursively enumerable in a degree b if there is a set of degree c which is the range of a function of degree less than or equal to b, and we call a degree recursively enumerable if it is recursively enumerable in 0 (i.e., if it is the degree of a recursively enumerable set).The jump operator, which takes the degree d to the degree d' (the completion of d), was defined in [4] and has the following properties: if h is recursively enumerable in d, then h^ d'; d' > d; and d' is recursively enumerable in d.In [4] a degree c is said to be complete if there exists a degree d such that d' = c.Friedberg [1] showed that a degree c is complete if and only if c ^ 0'.For any degree b, if b ^ d ^ b', then b' ^ d' ^ b and d' is recursively enumerable in b'.Shoenfield [7] proved that if b' i% c z% b" and c is recursively enumerable in b', then there is a degree d such that b z% d g b' and d' = c.Thus the degrees which lie between b' and b" and are recursively enumerable in b' can be viewed as the completions of the degrees which lie between b and b'.He also showed there is a degree greater than b and less than b' which is not recursively enumerable in b.Our main result below is that the degrees which lie between b' and b" and are recursively enumerable in b' can be viewed as the completions of the degrees which lie between b and b' and are recursively enumerable in b.Our notation is that of [3].Theorem 1.Let a, b and c be degrees such that a^b, a i% b' ¿j c and c is recursively enumerable in b'.Then there exists a degree d such that a ^d, b ^ d, d' = c and d is recursively enumerable in b.Proof.We first prove the theorem when b = 0, and then indicate the changes needed when b > 0. Thus we have degrees a and c such that a > 0, a ^ 0' ^ c and c is recursively enumerable in 0', and we wish find a recursively enumerable degree d such that a^ d and d' = c.Let/ be a function of degree less than or equal to 0' whose range is a set C of Presented to the Society, April 19, 1962;