Interpolation and Embedding in the Recursively Enumerable Degrees
Robert W. Robinson · Annals of Mathematics · 1971
By a degree is meant a degree of recursive unsolvability. A degree is recursively enumerable (r.e.) just if it contains a recursively enumerable subset of N, the set of non-negative integers. Two infinite injury priority arguments are presented, in ? 2 and ? 3, which are generalizations of parts of Sacks' proof that the r.e. degrees are dense [9]. These results are in a form sufficiently flexible to admit a variety of applications. It is found, for example, that a degree which is a minimal r.e.-uniform upper bound for a sequence of degrees must be the join of a finite subsequence. By way of contrast, any non-recursive r.e. degree is a minimal upper bound for some strictly ascending sequence of r.e. degrees. It is also found that if a, b are r.e. and a < b, then any countable partial ordering is embeddable in the r.e. degrees between a and b with joins preserved whenever they exist. In ? 4 it is shown that if a' = 0' then there is always such an embedding which also preserves greatest and least elements when they exist. The proof of the latter result is a finite injury priority argument which is more closely related to two splitting theorems of Sacks [8, Th. 2 of ? 5 and Th. 2 of ? 61 than to the preceding results. Our basic notation follows Kleene [4], Kleene and Post [5], and Sacks [8]. A convenient property of Kleene's T-predicates is that if Tn(e, x1, * * * x ,nq y) or Tn(p e xi, ...,xny) holds then U(y) <y and xi<y for 1<? i n. As does Sacks we denote this fact by GND. It is convenient to have U(O) = 2, an inessential departure from Kleene. Another slight variation from Kleene's notation is that we put