Complementing below recursively enumerable degrees

DOI10.1016/0168-0072(87)90039-XMaRDI QIDQ1093627zbMATH OpenFDO

Authors S. Barry Cooper, Richard L. Epstein

Publication date 1987

Published in Annals of Pure and Applied Logic (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0168-0072(87)90039-X

zbMATH Keywords

complementation theoremminimal degreer.e. degrees

Mathematics Subject Classification ID

Recursively (computably) enumerable sets and degrees (03D25) Other degrees and reducibilities in computability and recursion theory (03D30)

Review text

This paper contains two main results about r.e. degrees. First, it is shown that for any nonzero low r.e. degree \(\underset \tilde{} c\) and any r.e. degree \(\underset \tilde{} a\) not below \(\underset \tilde{} c\), there exists a minimal degree below \(\underset \tilde{} a\) and incomparable with \(\underset \tilde{} c\). Second, the authors construct a specific r.e. degree \(\underset \tilde{} a\) such that a complementation theorem like that of Posner for the degrees below \(\underset \tilde{} 0'\) does not hold for the degrees below \(\underset \tilde{} a\). In fact, they build a particular r.e. degree \(\underset \tilde{} b\) between \(\underset \tilde{} 0\) and \(\underset \tilde{} a\) such that no \(\underset \tilde{} c\) can both cap \(\underset \tilde{} b\) to \(\underset \tilde{} 0\) and cup \(\underset \tilde{} b\) to \(\underset \tilde{} a\).

Recommendations

• Complementation in the Turing degrees
• Cupping the Recursively Enumerable Degrees by D.R.E. Degrees
• scientific article; zbMATH DE number 468962
• Complementing cappable degrees in the difference hierarchy.
• Some results about the R.E. degrees

Cites work

• A minimal degree less than 0’
• A theorem on minimal degrees
• Degrees joining to 0′
• Degrees of unsolvability complementary between recursively enumerable degrees, Part 1
• Degrees of unsolvability: structure and theory
• Initial segments of degrees below 0′
• Initial segments of the degrees of unsolvability Part II: minimal degrees
• Lower Bounds for Pairs of Recursively Enumerable Degrees
• Minimal degrees of unsolvability and the full approximation construction
• The upper semilattice of degrees ≤ 0′ is complemented

Cited in

(8)

• A splitting theorem for n-REA degrees
• Computably enumerable Turing degrees and the meet property
• Complementation in the Turing degrees
• The jump is definable in the structure of the degrees of unsolvability
• Bounding minimal degrees by computably enumerable degrees
• On a problem of Cooper and Epstein
• The strong anticupping property for recursively enumerable degrees
• Extending the Cooper minimal pair theorem

This page was built for publication: Complementing below recursively enumerable degrees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1093627)