$CEA$-operators and the Ershov hierarchy. I

M. M. Arslanov ; I. I. Batyrshin ; M. M. Yamaleev

Algebra i logika, Tome 63 (2024) no. 3, pp. 248-270

Résumé

We consider the relationship between the $CEA$-hierarchy and the Ershov hierarchy in $\Delta_2^0$ Turing degrees. A degree $\mathbf c$ is called a $CEA(\mathbf a)$ if ${\mathbf c}$ is computably enumerable in ${\mathbf a}$, and $\mathbf a\leq\mathbf c$. Soare and Stob [Logic colloquium '81, Proc. Herbrand Symp. (Marseille, 1981) (Stud. Logic Found. Math., 107), North-Hollad, 1982, 299—324] proved that for a noncomputable low c.e. degree ${\mathbf a}$ there exists a $CEA(\mathbf a)$ that is not c.e. Later, Arslanov, Lempp, and Shore [Ann. Pure Appl. Logic, 78, Nos. 1-3 (1996), 29—56] formulated the problem of describing pairs of degrees ${\mathbf a}<{\mathbf e}$ such that there exists a $CEA(\mathbf a)$ $2$-c.e. degree ${\mathbf d}\leq{\mathbf e}$ which is not c.e. Since then the question has remained open as to whether a $CEA(\mathbf a)$ degree in the sense of Soare and Stob can be made $2$-c.e. Here we answer this question in the negative, solving it in a stronger formulation: there exists a noncomputable low c.e. degree ${\mathbf a}$ such that any $CEA(\mathbf a)$ $\omega$-c.e. degree is c.e. Also possible generalizations of the result obtained are discussed, as well as various issues associated with the problem mentioned.

Détail

Keywords: $cEA$-hierarchy, ershov hierarchy, turing degree.

Bibliographie

[1] Yu. L. Ershov, “Ob odnoi ierarkhii mnozhestv I”, Algebra i logika, 7:1 (1968), 47–74

[2] Yu. L. Ershov, “Ob odnoi ierarkhii mnozhestv. II”, Algebra i logika, 7:4 (1968), 15–47

[3] Yu. L. Ershov, “Ob odnoi ierarkhii mnozhestv. III”, Algebra i logika, 9:1 (1970), 34–51

[4] S. B. Cooper, Degrees of unsolvability, Ph. D. thesis, Leicester Univ., England, 1971

[5] C. G. Jockusch, jun., R. A. Shore, “Pseudo-jump operators. II: Transfinite iterations, hierarchies and minimal covers”, J. Symb. Log., 49:4 (1984), 1205–1236

[6] V. L. Selivanov, “Ob ierarkhii Ershova”, Sib. matem. zh., 26:1 (1985), 134–149

[7] M. M. Arslanov, G. L. LaForte, T. A. Slaman, “Relative enumerability in the difference hierarchy”, J. Symb. Logic, 63:2 (1998), 411–420

[8] I. I. Batyrshin, “Otnositelnaya perechislimost v ierarkhii Ershova”, Matem. zametki, 84:4 (2008), 506–515

[9] R .I. Soare, M. Stob, “Relative recursive enumerability”, Logic colloquium '81, Proc. Herbrand Symp. (Marseille, 1981), Stud. Logic Found. Math., 107, North-Hollad, 1982, 299–324

[10] M. M. Arslanov, S. Lempp, R. A. Shore, “Interpolating $d$-r.e. and REA degrees between r. e. degrees”, Ann. Pure Appl. Logic, 78:1-3 (1996), 29–56

[11] M. M. Arslanov, “The Ershov hierarchy”, Computability in context. Computation and logic in the real world, eds. S. B. Cooper et al., Imperial College Press, London, 2011, 49–100

[12] M. M. Arslanov, I. I. Batyrshin, M. M. Yamaleev, “$CEA$-operatory i ierarkhiya Ershova. II”, Algebra i logika, 63:4 (2024)

[13] M. Bickford, C. Mills, Lowness properties of r.e. sets, unpublished manuscript, UW Madison, 1982

[14] H. G. Carstens, “$\Delta^0_2$-Mengen”, Arch. Math. Logik Grundlagenforsch., 18 (1976), 55–65

[15] R. I. Soare, Recursively enumerable sets and degrees. A study of computable functions and computably generated sets, Perspect. Math. Log., Omega Series, Springer-Verlag, Berlin etc., 1987

[16] R. G. Downey, D. R. Hirschfeldt, Algorithmic Randomness and Complexity, Theory and Applications of Computability, Springer, New York, 2010