Bounding cappable degrees (Q1576591)

From MaRDI portal





scientific article; zbMATH DE number 1491681
Language Label Description Also known as
default for all languages
No label defined
    English
    Bounding cappable degrees
    scientific article; zbMATH DE number 1491681

      Statements

      Bounding cappable degrees (English)
      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
      recursively enumerable degrees
      0 references
      cappable degrees
      0 references
      minimal pairs
      0 references
      Turing reducibility
      0 references
      Turing degrees
      0 references
      0 references

      Identifiers