Properly \(\Sigma_2^0\) enumeration degrees and the high/low hierarchy. (English) Zbl 1114.03034

In the paper under review the authors prove that every high enumeration degree bounds a noncuppable enumeration degree. Since every noncuppable enumeration degree is downwards properly \(\Sigma_2^0\), it follows that there are downwards properly \(\Sigma_2^0\) degrees that are not high. By definition, an enumeration degree \({\mathbf a}\leq_{\text{e}}{\mathbf 0}_{\text{e}}^{\prime}\) is downwards properly \(\Sigma_2^0\) if \({\mathbf a}\neq{\mathbf 0}_{\text{e}}\) and any nontrivial enumeration degree below a is a properly \(\Sigma_2^0\) enumeration degree.


03D30 Other degrees and reducibilities in computability and recursion theory
03D55 Hierarchies of computability and definability
Full Text: DOI


[1] Annals of Pure and Applied Logic 82 pp 317– (1997)
[2] DOI: 10.1002/malq.19880340603 · Zbl 0667.03034
[3] Recursion Theory Week, Oberwolfach 1989 1432 pp 57– (1990)
[4] The distribution of properly enumeration degrees 65 pp 19– (2000)
[5] Complexity, logic and recursion theory pp 303– (1997)
[6] Recursively enumerable sets and degrees (1987)
[7] DOI: 10.1090/S0002-9939-1954-0063995-6
[8] DOI: 10.1090/S0002-9947-1963-0155747-3
[9] Structural properties and enumeration degrees 65 pp 285– (2000)
[10] On minimal pairs of enumeration degrees 50 pp 983– (1985) · Zbl 0615.03031
[11] Archive for Mathematical Logic 42 (2003)
[12] Archive for Mathematical Logic
[13] Recursion theory and complexity pp 157– (1999)
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.