×

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

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\).

MSC:

03D25 Recursively (computably) enumerable sets and degrees
03D30 Other degrees and reducibilities in computability and recursion theory
PDF BibTeX XML Cite
Full Text: DOI

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
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.