Nonisolated degrees and the jump operator (Q1849858): Difference between revisions

A Turing degree is called r.e.\ if it contains a recursively enumerable set and d.r.e.\ if it contains a set which is the set-theoretic difference of two r.e.\ sets. A d.r.e.\ degree \(\mathbf d\) is nonisolated if for any r.e.\ degree \({\mathbf a} < {\mathbf d}\) there is another r.e.\ degree \(\mathbf b\) properly between these two degrees: \({\mathbf a} < {\mathbf b} < {\mathbf d}\). It is shown that there are a low d.r.e.\ degree and a high nonisolated d.r.e.\ degree above it such that both bound the same r.e.\ degrees. More precisely, there is a low d.r.e.\ degree \(\mathbf c\) and a high nonisolated d.r.e.\ degree \(\mathbf d\) such that \({\mathbf c} < {\mathbf d}\) and \((\forall\) r.e.\ \({\mathbf a} < {\mathbf d})\,(\exists\) r.e.\ \({\mathbf b})\,({\mathbf a} < {\mathbf b} < {\mathbf c})\). Note that the degree \(\mathbf d\) can be taken to be properly d.r.e., that is, \(\mathbf d\) does not contain a recursively enumerable set. The degree \(\mathbf c\) is automatically properly d.r.e.\ and automatically nonisolated by the condition that it bounds all r.e.\ degrees below the nonisolated degree \(\mathbf d\). Ishmukhametov and the author proved the parallel result for isolated degrees: There is a high d.r.e.\ degree \(\mathbf d\) and a low r.e.\ degree \(\mathbf c\) such that every r.e.\ degree \({\mathbf a} \leq {\mathbf d}\) satisfies \({\mathbf a} \leq {\mathbf c}\) [\textit{Sh. Ishmukhametov} and \textit{G. Wu}, Arch. Math. Logic 41, 259--266 (2002; Zbl 1028.03035)].