Bounding computably enumerable degrees in the Ershov hierarchy (Q2498901): Difference between revisions
From MaRDI portal
Set profile property. |
Set OpenAlex properties. |
||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/j.apal.2005.10.004 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2067769900 / rank | |||
Normal rank |
Revision as of 02:50, 20 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Bounding computably enumerable degrees in the Ershov hierarchy |
scientific article |
Statements
Bounding computably enumerable degrees in the Ershov hierarchy (English)
0 references
16 August 2006
0 references
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.
0 references
Ershov hierarchy
0 references
recursively enumerable sets
0 references
differences of r.e. sets
0 references
Turing degrees
0 references
high Turing degrees
0 references
degrees of d.r.e. sets
0 references