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

Ambos-Spies, Klaus; Ding, Decheng; Wang, Wei; Yu, Liang

J. Symb. Log. 74, No. 3, 989-1000 (2009).

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.

Reviewer: Rodney Downey (Wellington)

MSC:

03D28

Other Turing degree structures

Keywords:

generalized high/low hierarchies; recursively enumerable in and above; generic degree

References:

[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