Bounding non-\(\mathrm{GL}_2\) and r.e.a. (English) Zbl 1201.03025

The main result is to show that any non-GL\(_2\) degree is computably enumerable in and above some 1-generic degree. The proof splits into two parts. First the authors deal with the case that a is non-low\(_2\) and \(\Delta_2^0\). This filters through a result on linear orderings by, respectively, Harizanov, and (a re-interpretation of a result of) Hirschfeldt and Shore. Then the authors show that if a is non-GL\(_2\) then there is a degree \({\mathbf c}<{\mathbf a}\) such that a is c.e. and non-low\(_2\) over a.


03D28 Other Turing degree structures
Full Text: DOI


[1] Recursion theory: Its generalizations and applications. Proceedings of Logic Colloquium ’79, Leeds, August 1979 pp 110– (1980)
[2] Combinatorial principles weaker than Ramsey’s theorem for pairs 72 pp 171– (2007) · Zbl 1118.03055
[3] DOI: 10.1016/S0168-0072(97)00056-0 · Zbl 0946.03051
[4] DOI: 10.1007/s00153-005-0306-y · Zbl 1148.03033
[5] Recursively enumerable sets and degrees (1987)
[6] Double jumps of minimal degrees 43 pp 715– (1978)
[7] A minimal degree not realizing least possible jump 39 pp 571– (1974)
[8] DOI: 10.1002/malq.19660120125 · Zbl 0181.30504
[9] Degrees of unsolvability pp 307– (1983)
[10] A 1-generic degree with a strong minimal cover 65 pp 1395– (2000) · Zbl 0967.03039
[11] Relative recursive enumerability of generic degrees 56 pp 1075– (1991) · Zbl 0753.03017
[12] DOI: 10.2307/1970889 · Zbl 0259.02034
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.