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