The recursively enumerable degrees have infinitely many one-types

DOI10.1016/0168-0072(89)90042-0MaRDI QIDQ1823931zbMATH OpenOpenAlexWikidataFDO

Authors Robert I. Soare, Klaus Ambos-Spies

Publication date 1989

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(89)90042-0

zbMATH Keywords

many-one typesminimal pairr.e. degrees

Mathematics Subject Classification ID

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

Review text

The authors prove the following theorem: There exist r.e. degrees \(\{c_ m\}_{m\in \omega}\) such that for all m: (i) \(c_ m>0\); (ii) \(c_ m\) does not bound a minimal pair; (iii) for every \(n\neq m\), \(c_ m\) and \(c_ n\) form a minimal pair. Applications and an informal motivation are also included. This is a deep mathematical paper which should be of great value for many ``practically oriented computer scientists.

Recommendations

• On Pairs of Recursively Enumerable Degrees
• Undecidability and 1-types in the recursively enumerable degrees
• On the r. e. predecessors of d. r. e. degrees
• scientific article; zbMATH DE number 3845569
• The elementary theory of the recursively enumerable degrees is not \(\aleph _ 0\)-categorical

Cites work

• A minimal pair of recursively enumerable degrees
• Bounding minimal pairs
• scientific article; zbMATH DE number 194103 (Why is no real title available?)
• scientific article; zbMATH DE number 3895050 (Why is no real title available?)
• scientific article; zbMATH DE number 3404227 (Why is no real title available?)
• Lower Bounds for Pairs of Recursively Enumerable Degrees
• Wtt-degrees and T-degrees of r.e. sets

Cited in

(16)

• Structural interactions of the recursively enumerable T- and W-degrees
• Intervals and sublattices of the r.e. weak truth table degrees. I: Density
• Classification of degree classes associated with r.e. subspaces
• Undecidability and 1-types in intervals of the computably enumerable degrees
• Interpreting \(\mathbb{N}\) in the computably enumerable weak truth table degrees
• On the strongly bounded Turing degrees of the computably enumerable sets
• On the definable ideal generated by nonbounding c.e. degrees
• Degree Structures: Local and Global Investigations
• scientific article; zbMATH DE number 3977006 (Why is no real title available?)
• Correction to “Simple r. e. degree structures”
• The theory of the recursively enumerable weak truth-table degrees is undecidable
• Generalized nonsplitting in the recursively enumerable degrees
• Contiguity and distributivity in the enumerable Turing degrees
• Model theory of the computably enumerable many-one degrees
• THE THEORY OF THE METARECURSIVELY ENUMERABLE DEGREES
• Undecidability and 1-types in the recursively enumerable degrees

This page was built for publication: The recursively enumerable degrees have infinitely many one-types

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