Minimal Upper Bounds for Sequences of Recursively Enumerable Degrees
S. Barry Cooper · Journal of the London Mathematical Society · 1972
G. E. Sacks [3; p. 171, q. 4] asked whether there is a uniformly recursively enumerable (r.e.) ascending sequence of r.e. degrees which has as one of its minimal upper bounds another r.e. degree. We show (see the Corollary below) that the answer is " yes ". a is said to be a string if it is the restriction A[n] of a characteristic function A to the first n +1 non-negative integers for some number n. a is said to be a beginning of A of length n +1. We use (j> to denote the empty string. Let { s} of finite approximations to {Oc} such that for each e, s, and such that for each s, Oe s is empty for all but a finite number of e's. Define, for each e, Then {Fe} is a standard list of the partial recursive functions with suitably well-behaved set of approximations {Fes, then the following objectives are satisfied: