Bounding cappable degrees (Q1576591)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Bounding cappable degrees
scientific article

    Statements

    Bounding cappable degrees (English)
    0 references
    0 references
    7 October 2001
    0 references
    The paper deals with the Turing degrees of the recursively (= computably) enumerable degrees. Let \(\mathbf 0\) be the degree of the recursive sets and let \(\mathbf a\), \(\mathbf b\) and \(\mathbf c\) range over the Turing degrees of recursively enumerable sets. A degree \(\mathbf a\) is called cappable if there is a degree \(\mathbf b\) such that \({\mathbf 0} < {\mathbf a}\), \({\mathbf 0} < {\mathbf b}\) and \(\mathbf 0\) is the only degree \(\mathbf c\) satisfying both, \({\mathbf c} < {\mathbf a}\) and \({\mathbf c} < {\mathbf b}\). The main result of the paper is that there are degrees \(\mathbf a\) and \(\mathbf b\) such that \(\mathbf b\) is strictly below \(\mathbf a\) and bounds all cappable degrees below \(\mathbf a\). More precisely, this means that (a) \({\mathbf 0} < {\mathbf b} < {\mathbf a}\); (b) some degree \({\mathbf c} < {\mathbf a}\) is cappable; (c) every cappable degree \({\mathbf c} < {\mathbf a}\) satisfies \({\mathbf c} < {\mathbf b}\); (d) \(\mathbf a\) and \(\mathbf b\) are not cappable. Condition (b) is omitted in the paper since it holds whenever the degree \(\mathbf a\) is not recursive [\textit{R. I. Soare}, Recursively enumerable sets and degrees, Springer-Verlag, Berlin (1987; Zbl 0667.03030 and Zbl 0623.03042), Exercise XIII.2.6].
    0 references
    0 references
    0 references
    recursively enumerable degrees
    0 references
    cappable degrees
    0 references
    minimal pairs
    0 references
    Turing reducibility
    0 references
    Turing degrees
    0 references
    0 references
    0 references