Complementing cappable degrees in the difference hierarchy.
The authors study r.e.\ and d.r.e.\ degrees (which are called c.e.\ and d.c.e.\ in the paper). A degree is called r.e.\ if it contains an r.e.\ set and d.r.e.\ if it contains a set which is the difference of two r.e.\ sets. The authors show that the following statements are equivalent for any nonzero r.e.\ degree \(a\): (1) \(a\) is cappable. That is, there is a nonzero r.e.\ degree \(b\) such that \(0\) is the only Turing degree below \(a\) and \(b\). (2) \(a\) has an d.r.e.\ complement \(c\). That is, \(0\) is the only degree below \(a\) and \(c\), \(0'\) is the least Turing degree above \(a\) and \(c\). (3) \(a\) cups with an d.r.e.\ degree \(c\) such that \(c\) is isolated by \(b\) and \(a\), \(b\) form a minimal pair. That is, \(0\) is the only Turing degree below \(a\) and \(b\), \(0'\) is the least Turing degree above \(a\) and \(c\), \(b\) is the greatest r.e.\ Turing degree below \(c\). Note that (3) is not a direct corollary from (2) since there are d.r.e.\ degrees which are not isolated by an r.e.\ Turing degree below. Statement (1) is an obvious corollary of (3). \textit{Guohua Wu} [J. Symb. Log. 67, No. 3, 1055--1064 (2002; Zbl 1023.03037)] proved that (3) implies (2). So the main result of the paper is that (1) implies (3).
- scientific article; zbMATH DE number 2063233
- Isolation and lattice embeddings
- Isolated d-r.e. degree below r.e. degree
- The Isolated D. R. E. Degrees are Dense in the R. E. Degrees
- On relative enumerability of Turing degrees
- Bounding cappable degrees
- Nonisolated degrees and the jump operator
- scientific article; zbMATH DE number 4087652
- Isolated from above d-r. e. degrees. I
- Cappable recursively enumerable degrees and Post's program
- A minimal degree less than 0’
- A minimal pair of recursively enumerable degrees
- A Splitting Theorem for the N-R.E. Degrees
- An Algebraic Decomposition of the Recursively Enumerable Degrees and the Coincidence of Several Degree Classes with the Promptly Simple Degrees
- Bounding minimal pairs
- Cupping the Recursively Enumerable Degrees by D.R.E. Degrees
- D.R.E. Degrees and the Nondiamond Theorem
- scientific article; zbMATH DE number 194103 (Why is no real title available?)
- scientific article; zbMATH DE number 2063233 (Why is no real title available?)
- scientific article; zbMATH DE number 841082 (Why is no real title available?)
- scientific article; zbMATH DE number 3342831 (Why is no real title available?)
- Isolated d.r.e. degrees are dense in r.e. degree structure
- Isolation and lattice embeddings
- Isolation and the high/low hierarchy
- Lattice embedding into d-r. e. degrees preserving 0 and 1
- Lower Bounds for Pairs of Recursively Enumerable Degrees
- Minimal complements for degrees below 0′
- Minimal degrees and the jump operator
- Minimal pairs and high recursively enumerable degrees
- On the degrees less than 0'
- The d.r.e. degrees are not dense
- The Isolated D. R. E. Degrees are Dense in the R. E. Degrees
- The recursively enumerable degrees are dense
- The upper semilattice of degrees ≤ 0′ is complemented
- Turing Definability in the Ershov Hierarchy
- Weak density and cupping in the d-r.e. degrees
- Complementing below recursively enumerable degrees
- On a conjecture of Lempp
- Bounding cappable degrees
- Nonisolated degrees and the jump operator
- Bounding computably enumerable degrees in the Ershov hierarchy
- scientific article; zbMATH DE number 4016885 (Why is no real title available?)
- Cupping and diamond embeddings: a unifying approach
- scientific article; zbMATH DE number 468962 (Why is no real title available?)
- Quasi-complements of the cappable degrees
- scientific article; zbMATH DE number 2063233 (Why is no real title available?)
- Generalized high degrees have the complementation property
This page was built for publication: Complementing cappable degrees in the difference hierarchy.
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1428038)
