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