Degrees which do not bound minimal degrees (Q1073789)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Degrees which do not bound minimal degrees |
scientific article |
Statements
Degrees which do not bound minimal degrees (English)
0 references
1986
0 references
The generalized high/low hierarchy measures how close a degree is to realizing its least or greatest possible jump. The high/low hierarchy measures the same phenomenon for degrees below 0'. In particular, \(GH_ 1\) is the class of generalized high degrees, i.e., the class of degrees a satisfying \(a'=(a\cup 0')'\), and \(H_ 1\) is the class of high degrees, i.e., the class of degrees a satisfying \(a'=0''.\) Various order-theoretic properties have been studied in terms of their relationship to the high/low hierarchy. Thus we say that a hierarchy class is invariant for a property if every degree in the class has the property. This paper considers the property P(a) specifying that a bounds a minimal degree. \textit{C. G. Jockusch jun.} [Canad. J. Math. 29, 1072- 1080 (1977; Zbl 0342.02030)] showed that \(GH_ 1\) is invariant for P(a). He also showed [Recursion theory: its generalizations and applications, Proc. Logic Colloq., Leeds/Engl. 1979, Lond. Math. Soc. Lect. Note Ser. 45, 110-139 (1980; Zbl 0457.03042)] that certain small classes of the generalized high/low hierarchy are not invariant for P(a), and conjectured that \(GH_ 1\) is the only class of the generalized high/low hierarchy which is invariant for P(a). Jockusch's conjecture is proved in this paper. It is also shown, with a much more difficult proof, that \(H_ 1\) is the only class of the high/low hierarchy which is invariant for P(a).
0 references
generalized high/low hierarchy
0 references
high degrees
0 references