On the jump classes of noncuppable enumeration degrees. (English) Zbl 1215.03056

Harris, Charles M.

J. Symb. Log. 76, No. 1, 177-197 (2011).

The upper semilattice of enumeration degrees (e-degrees) is generated by the relation ‘\(A\) is enumeration reducible to \(B\)’ \((A \leq _{\text{e}} B)\), which holds iff there is an effective procedure that takes any enumeration of \(B\) to an enumeration of \(A\). The jump of the e-degree of \(A\) is defined as the e-degree of the characteristic function of the set \(\{e\mid e \in\Phi^A_e\}\). The Turing degrees are embedded in the e-degrees by a map that takes any set’s Turing degree to the e-degree of its characteristic function. This preserves jump. Thus ‘high\(_m\)’, ‘low\(_n\)’, and ‘cuppable’ may be ascribed in the natural way to e-degrees.
A main theorem shows that for every \(\Sigma^0_2\) e-degree b there is a noncuppable \(\Sigma^0_2\) e-degree \({\mathbf a}>{\mathbf{0}}_{\text{e}}\) with \({\mathbf b}'\leq_{\text{e}}{\mathbf a}'\) and \({\mathbf a}''\leq_{\text{e}}{\mathbf b}''\). It follows that for every \(m \geq 0\) and \(n \geq 1\) there are noncuppable e-degrees \({\mathbf x},{\mathbf y}< {\mathbf{0}}'_{\text{e}}\) such that \({\mathbf x}\) is high\(_{m+1}\) but not high\(_m\) and \({\mathbf y}\) is low\(_{n+1}\) but not low\(_n\). Moreover, there is a noncuppable \({\mathbf z}<{\mathbf{0}}'_{\text{e}}\) with the property that \({\mathbf{0}}^n _{\text{e}}< {\mathbf z}^n< {\mathbf{0}}^{n+1}_{\text{e}}\) for all \(n\).

Reviewer: Joseph S. Ullian (Santa Barbara)

MSC:

03D25	Recursively (computably) enumerable sets and degrees
03D30	Other degrees and reducibilities in computability and recursion theory

Keywords:

enumeration reducibility; Turing degrees; noncuppable

References:

[1]	DOI: 10.1016/S0168-0072(96)00009-7 · Zbl 0874.03056
[2]	DOI: 10.1007/s00153-006-0021-3 · Zbl 1155.03025
[3]	Computability theory (2004) · Zbl 1041.03001
[4]	Recursion theory week, Oberwolfach 1989 1432 pp 57– (1990)
[5]	Complexity, logic and recursion theory pp 303– (1997)
[6]	Recursively enumerable sets and degrees (1987)
[7]	DOI: 10.1090/S0002-9939-1967-0207558-7
[8]	DOI: 10.1090/S0002-9947-1963-0155747-3
[9]	Classical recursion theory (1989)
[10]	Structural properties and {\(\Sigma\)}2 0 enumeration degrees 65 pp 285– (2000)
[11]	DOI: 10.1007/BF01794984 · Zbl 0848.03023
[12]	Journal of Logic and Computation
[13]	DOI: 10.1090/S0002-9947-1968-0220595-7
[14]	DOI: 10.1007/s00153-010-0192-9 · Zbl 1202.03051
[15]	DOI: 10.1007/s00153-002-0161-z · Zbl 1026.03031
[16]	Properly {\(\Sigma\)}2 0 enumeration degrees and the high/low hierarchy 71 pp 1125– (2006)
[17]	On minimal pairs of enumeration degrees 50 pp 983– (1985) · Zbl 0615.03031