Phenomena in the n-r.e. and n-REA degrees.

Abstract

We study the degrees below 0$\sp\prime$ by examining some phenomena relating two well-known hierarchies in the Turing degrees--the difference hierarchy, produced by allowing error correction in computations, and the REA hierarchy, produced by iterating relative recursive enumerability. By a result of Soare and Stob, if W is nonrecursive, then some W-REA set fails to be of r.e. degree. We show that this phenomenon fails in the d.r.e degrees: There is a nonrecursive r.e. set W such that every W-REA set has d.r.e. degree. We conjecture that this result can be extended to construct, for example, a d.r.e. set W such that every W-REA set has 3-r.e. degree and some W-REA set is not of d.r.e. degree. We show that in this case W cannot be recursively enumerable. Indeed, we show (using joint work with T.A. Slaman) that any $\omega$-r.e. set which has 2-REA degree must have d.r.e. degree. Turning to isolation phenomena in the $\Delta\sbsp{2}{0}$ degrees, we show that there are, for every $n > 0,\ (n + 1)$-r.e. sets isolated in the n-r.e. degrees by n-r.e. sets below them, that is, no n-r.e. sets lie in the interval between the two. We indicate the wide distribution of the degrees of these sets when n = 2 in the structure of the $\Delta\sbsp{2}{0}$ degrees by showing that d.r.e. sets isolated in the r.e. degrees by an r.e. set below them occur in any nontrivial interval in the r.e. degrees. We show that for $n >$ 2 such phenomena arise below any recursively enumerable degree, and conjecture that this result holds densely in the r.e. degrees as well.