$CEA$-операторы и иерархия Ершова. I

Рассматривается связь между $CEA$-иерархией и иерархией Ершова в $\Delta_2^0$-тьюринговых степенях. Степень $\mathbf c$ называется $CEA(\mathbf a)$, если $\mathbf c$ является вычислимо перечислимой относительно $\mathbf a$, и $\mathbf a\leq\mathbf c$. Соар и Стоб [Logic colloquium '81, Proc. Herbrand Symp. (Marseille, 1981), (Stud. Logic Found. Math., 107), North-Hollad, 1982, 299—324] доказали, что для невычислимой низкой в. п. степени ${\mathbf a}$ существует $CEA(\mathbf a)$, не являющаяся в. п. Позднее, Арсланов, Лемпп и Шор [Ann. Pure Appl. Logic, 78, Nos. 1–3 (1996), 29—56] сформулировали проблему описания таких пар степеней ${\mathbf a}<{\mathbf e}$, что существует $CEA({\mathbf a})$ $2$-в. п. степень ${\mathbf d}\leq{\mathbf e}$, не являющаяся в. п. С тех пор более 20 лет оставался открытым вопрос: можно ли $CEA({\mathbf a})$ степень из работы Соара и Стоба сделать $2$-в. п.? Здесь даётся отрицательный ответ на этот вопрос, который решается в более сильной формулировке: существует такая невычислимая низкая в. п. степень ${\mathbf a}$, что любая $CEA(\mathbf a)$ $\omega$-в. п. степень является в. п. Также обсуждаются возможные обобщения полученного результата и различные вопросы, связанные с упомянутой проблемой.