Extending the Cooper minimal pair theorem

DOI10.1007/BF02948855MaRDI QIDQ5934293zbMATH OpenOpenAlexFDO

Authors Zaiyue Zhang

Publication date 23 September 2001

Published in Journal of Computer Science and Technology (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf02948855

zbMATH Keywords

minimal pairrecursively enumerable degree

Mathematics Subject Classification ID

Recursively (computably) enumerable sets and degrees (03D25)

Review text

The author proves that for any high recursively enumerable (r.e.) degree \(h\) and r.e. degree \(b\) such that \(h\nleq b\), there exist r.e. degrees \(a_0\) and \(a_1\) such that \(a_0,a_1 \nleq b\) and \(a_0,a_1\) form a minimal pair below \(h\).

Recommendations

• Working below a high recursively enumerable degree
• On the existence of a strong minimal pair
• Highness and bounding minimal pairs
• Complementing below recursively enumerable degrees
• Constructing minimal pairs of degrees

Cites work

• A minimal pair of recursively enumerable degrees
• Bounding cappable degrees
• scientific article; zbMATH DE number 833149 (Why is no real title available?)
• Lower Bounds for Pairs of Recursively Enumerable Degrees
• Minimal pairs and high recursively enumerable degrees
• On a conjecture of Lempp
• The recursively enumerable degrees are dense
• Working below a high recursively enumerable degree

Cited in

(5)

• Bounding computably enumerable degrees in the Ershov hierarchy
• Working below a high recursively enumerable degree
• Highness and bounding minimal pairs
• Extending Cooper's theorem to \(\Delta_3^0\) Turing degrees
• On very high degrees

This page was built for publication: Extending the Cooper minimal pair theorem

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