RUS  ENG
Full version
JOURNALS // Izvestiya Vysshikh Uchebnykh Zavedenii. Matematika // Archive

Izv. Vyssh. Uchebn. Zaved. Mat., 2021 Number 8, Pages 72–79 (Mi ivm9705)

This article is cited in 1 paper

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.

UDC: 510.535

Received: 18.06.2021
Revised: 18.06.2021
Accepted: 29.06.2021

DOI: 10.26907/0021-3446-2021-8-72-79


 English version:
Russian Mathematics (Izvestiya VUZ. Matematika), 2021, 65:8, 63–69


© Steklov Math. Inst. of RAS, 2025