Bounding computably enumerable degrees in the Ershov hierarchy (Q2498901): Difference between revisions

The authors first survey the prior work about the relations between recursively enumerable (r.e.) and d.r.e.\ degrees (which the authors call ``c.e.'' and ``d.c.e.'') and then state their main result. Recall that a d.r.e.\ set is the difference of two r.e.\ sets. Main Theorem. For every nonrecursive r.e.\ set \(A\) there is a nonrecursive r.e.\ set \(B \leq_T A\) and a high d.r.e.\ set \(D \geq_T B\) such that every r.e.\ set \(C \leq_T D\) is already below \(B\): \(C \leq_T B\). This result has several corollaries. The first is a result of \textit{S. Ishmukhametov} and \textit{G. Wu} [``Isolation and the high/low hierarchy'', Arch.\ Math.\ Logic 41, 259--266 (2002; Zbl 1028.03035)] that there is a low but nonrecursive r.e.\ set \(B\) and a high d.r.e.\ set \(D >_T B\) such that the r.e.\ sets below \(D\) are exactly those below \(B\). The second corollary is a result by \textit{C. T. Chong, A. Li} and \textit{Y. Yang} [``The existence of high nonbounding degrees in the difference hierarchy'', Ann.\ Pure Appl.\ Logic 138, 31--51 (2006; Zbl 1093.03028)] that there is a high d.r.e.\ set \(D\) not bounding any minimal pair of r.e.\ sets. That is, there are no r.e.\ sets \(A,B\) with \(\emptyset <_T A <_T D\), \(\emptyset <_T B <_T D\) and \(\forall C (C \leq_T A \wedge C \leq_T B \Rightarrow C \leq_T \emptyset)\). The authors write that similar results as the above Main Theorem also hold in higher levels of the Ershov hierarchy.