This article is cited in 2 papers

$CEA$-operators and the Ershov hierarchy. I

M. M. Arslanov, I. I. Batyrshin, M. M. Yamaleev

Kazan (Volga Region) Federal University

Abstract: 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.

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

UDC: 510.535

Received: 03.12.2024
Revised: 11.04.2025

DOI: 10.33048/alglog.2024.63.302

 English version: Algebra and Logic, 2024, 63:3, 164–178