Nonisolated degrees and the jump operator (Q1849858): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Set profile property. |
||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank |
Revision as of 04:56, 5 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Nonisolated degrees and the jump operator |
scientific article |
Statements
Nonisolated degrees and the jump operator (English)
0 references
2 December 2002
0 references
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)].
0 references
recursively enumerable sets
0 references
d.r.e.\ degrees
0 references
isolation
0 references
low degrees
0 references
high degrees
0 references
computably enumerable sets
0 references
Turing degree
0 references