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

### Keywords:

enumeration reducibility; Turing degrees; noncuppable
Full Text:

### References:

  DOI: 10.1016/S0168-0072(96)00009-7 · Zbl 0874.03056  DOI: 10.1007/s00153-006-0021-3 · Zbl 1155.03025  Computability theory (2004) · Zbl 1041.03001  Recursion theory week, Oberwolfach 1989 1432 pp 57– (1990)  Complexity, logic and recursion theory pp 303– (1997)  Recursively enumerable sets and degrees (1987)  DOI: 10.1090/S0002-9939-1967-0207558-7  DOI: 10.1090/S0002-9947-1963-0155747-3  Classical recursion theory (1989)  Structural properties and {$$\Sigma$$}2 0 enumeration degrees 65 pp 285– (2000)  DOI: 10.1007/BF01794984 · Zbl 0848.03023  Journal of Logic and Computation  DOI: 10.1090/S0002-9947-1968-0220595-7  DOI: 10.1007/s00153-010-0192-9 · Zbl 1202.03051  DOI: 10.1007/s00153-002-0161-z · Zbl 1026.03031  Properly {$$\Sigma$$}2 0 enumeration degrees and the high/low hierarchy 71 pp 1125– (2006)  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.