|
Brief communications
$CEA$ operators and the Ershov hierarchy
M. M. Arslanov, I. I. Batyrshin, M. M. Yamaleev Kazan Federal University, 18 Kremlyovskaya str., Kazan, 420008 Russia
Abstract:
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.
Received: 18.06.2021 Revised: 18.06.2021 Accepted: 29.06.2021
Citation:
M. M. Arslanov, I. I. Batyrshin, M. M. Yamaleev, “$CEA$ operators and the Ershov hierarchy”, Izv. Vyssh. Uchebn. Zaved. Mat., 2021, no. 8, 72–79; Russian Math. (Iz. VUZ), 65:8 (2021), 63–69
Linking options:
https://www.mathnet.ru/eng/ivm9705 https://www.mathnet.ru/eng/ivm/y2021/i8/p72
|
Statistics & downloads: |
Abstract page: | 211 | Full-text PDF : | 50 | References: | 28 | First page: | 14 |
|