Some special pairs of \(\Sigma_2\) e-degrees. (English) Zbl 0926.03045

An e-degree \({\mathbf a}\) is called low if every set in \({\mathbf a}\) is \(\Delta_2\). In this paper it is proved that: There exists a non-zero low non-splitting e-degree (Theorem 2.1). For every non-zero low e-degree \({\mathbf a}\) there exists a \(\Sigma_2\) e-degree \({\mathbf b}\) such that \({\mathbf a}\perp {\mathbf b}\) and for every e-degree \({\mathbf z}\), if \({\mathbf z}<{\mathbf a}\) and \({\mathbf z}\nless{\mathbf b}\), then there exists \({\mathbf y}\) such that \({\mathbf y} < {\mathbf b}\) and \({\mathbf y}\cup{\mathbf z}={\mathbf a}\) (Theorem 3.1). From this results follows that there exist \(\Sigma_2\) e-degrees \({\mathbf a},{\mathbf b}\) such that \({\mathbf a}\perp {\mathbf b}\) and every e-degree strictly below \({\mathbf a}\) is also below \({\mathbf b}\).


03D28 Other Turing degree structures
Full Text: DOI


[1] Some results on the structure of the 2 enumeration degrees. Ph. D. dissertation, Simon Fraser University 1989.
[2] Cooper, J. Symbolic Logic 47 pp 854– (1982)
[3] Cooper, J. Symbolic Logic 49 pp 503– (1984)
[4] Enumeration reducibility, nondeterministic computation, and relative computability of partial functions. In: Recursion Theory Week, Oberwolfach 1989 (, and , eds.), Lecture Notes in Mathematics 1432, Springer-Verlag, Berlin-Heidelberg-Now York 1990, pp. 57–110.
[5] Cooper, Zeitschrift Math. Logik Grundlagen Math. 34 pp 491– (1988)
[6] Some results on enumeration reducibility. Ph. D. dissertation, Simon Fraser University 1971.
[7] McKevoy, J. Symbolic Logic 50 pp 839– (1985)
[8] McKevoy, J. Symbolic Logic 50 pp 983– (1985)
[9] Theory of Recursive Functions and Effective Computability. McGraw-Hill, New York 1967. · Zbl 0183.01401
[10] and , Definability in the enumeration degrees. Preprint. · Zbl 0906.03043
[11] Recursively Enumerable Sets and Degrees. Springer-Verlag, Berlin-Heidelberg-New York 1987.
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.