Geodesic
$CEA$ operators and the Ershov hierarchy
Izvestiâ vysših učebnyh zavedenij. Matematika, no. 8 (2021), pp. 72-79.

Voir la notice de l'article provenant de la source Math-Net.Ru

We examine the relationship between the $CEA$ hierarchy and the Ershov hierarchy within $\Delta_2^0$ Turing degrees. We study the long-standing problem raised in [1] about the existence of a low computably enumerable (c.e.) degree $\mathbf{a}$ for which the class of all non-c.e. $CEA(\mathbf{a})$ degrees does not contain $2$-c.e. degrees. We solve the problem by proving a stronger result: there exists a noncomputable low c.e. degree $\mathbf{a}$ such that any $CEA(\mathbf{a})$ $\omega$-c.e. degree is c.e. Also we discuss related questions and possible generalizations of this result.
Keywords: relative enumerability, computably enumerable set, Ershov's hierarchy, low degree. 
@article{IVM_2021_8_a7,
     author = {M. M. Arslanov and I. I. Batyrshin and M. M. Yamaleev},
     title = {$CEA$ operators and the {Ershov} hierarchy},
     journal = {Izvesti\^a vys\v{s}ih u\v{c}ebnyh zavedenij. Matematika},
     pages = {72--79},
     publisher = {mathdoc},
     number = {8},
     year = {2021},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/IVM_2021_8_a7/}
}
TY  - JOUR
AU  - M. M. Arslanov
AU  - I. I. Batyrshin
AU  - M. M. Yamaleev
TI  - $CEA$ operators and the Ershov hierarchy
JO  - Izvestiâ vysših učebnyh zavedenij. Matematika
PY  - 2021
SP  - 72
EP  - 79
IS  - 8
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/IVM_2021_8_a7/
LA  - ru
ID  - IVM_2021_8_a7
ER  - 
%0 Journal Article
%A M. M. Arslanov
%A I. I. Batyrshin
%A M. M. Yamaleev
%T $CEA$ operators and the Ershov hierarchy
%J Izvestiâ vysših učebnyh zavedenij. Matematika
%D 2021
%P 72-79
%N 8
%I mathdoc
%U http://geodesic.mathdoc.fr/item/IVM_2021_8_a7/
%G ru
%F IVM_2021_8_a7
M. M. Arslanov; I. I. Batyrshin; M. M. Yamaleev. $CEA$ operators and the Ershov hierarchy. Izvestiâ vysših učebnyh zavedenij. Matematika, no. 8 (2021), pp. 72-79. http://geodesic.mathdoc.fr/item/IVM_2021_8_a7/

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

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

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

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

[5] Soare R. I., Stob M., “Relative computable enumerability”, Proceedings of the Herbrand symposium, Logic Colloquium'81, ed. J. Stern, North-Hollad, Amsterdam, 1982, 299–324 | DOI | MR

[6] Arslanov M. M., “The Ershov hierarchy”, Computability in Context: Computation and Logic In the Real World, eds. S. B. Cooper, A. Sorbi, Imperial College Press, London, 2011, 49–101 | DOI | MR

[7] Soar R. I., Vychislimo perechislimye mnozhestva i stepeni, Kazansk. matem. o-vo, Kazan, 2000

[8] Downey R. G., Hirschfeldt D. R., “Algorithmic Randomness and Complexity”, Theory and Appl. of Computability, Springer, New York, 2010 | DOI | MR | Zbl

[9] Jockusch Jr. C.G., Shore R. A., “Pseudojump operators II: transfinite iterations, hierarchies, and minimal covers”, J. Symb. Logic, 49 (1984), 1205–1236 | DOI | MR | Zbl

[10] Selivanov V. L., “Ob ierarkhii Ershova”, Sib. matem. zhurn., 26:1 (1985), 134–149 | MR | Zbl

[11] Ospichev S. S., “Fridbergovy numeratsii v ierarkhii Ershova”, Algebra i logika, 54:4 (2015), 283–295 | MR | Zbl

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

[13] Bickford M., Mills C., Lowness properties of r.e. sets, Preprint, University of Wisconsin, Madison, 1982

[14] Carstens H. G., “$\Delta_2^0$-mengen”, Arch. Math. Log. Grundlag, 18 (1978), 55–65 | DOI | MR

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

[16] Faizrakhmanov M. Kh., “Tyuringovye skachki v ierarkhii Ershova”, Algebra i logika, 50:3 (2011), 399–414 | MR | Zbl

[17] Cooper S. B., Yi X., Isolated $d$-r.e. degrees, Preprint, The University of Leeds, Leeds, 1996

[18] LaForte G. L., “The isolated d-r.e. degrees are dense in the r.e. degrees”, Math. Log. Quart., 42 (1995), 83–103 | DOI | MR

[19] Arslanov M. M., Lempp S., Shore R. A., “On isolating r.e. and isolated $d$-r.e. degrees”, London Math. Soc. Lect. Note Ser., 224 (1996), 61–80 | MR | Zbl