This article is cited in 2 papers

Brief communications

Computable linear orders and the Ershov hierarchy

Y. A. Michailovskaya^a, A. N. Frolov<sup>b

a</sup> Kazan Federal University, 18 Kremlyovskaya str., Kazan, 420008 Russia
^b Innopolis University, 1 Universitetskaya str., Innopolis, 420500 Russia

Abstract: This work corrects the inaccuracy of the authors' previous work. Namely, we correctly prove that there exists a computable linear order and a series of natural relations on it, the spectrum of which consist of exactly all $n$-c.e. degrees (for any natural number $n$).

Keywords: computable linear orders, the degree spectrum of relations, $n$-computable enumerable ($n$-c.e.) degrees.

UDC: 510.53

Received: 17.12.2021
Revised: 17.12.2021
Accepted: 23.12.2021

DOI: 10.26907/0021-3446-2022-1-85-89

 English version: Russian Mathematics (Izvestiya VUZ. Matematika), 2022, 66:1, 71–74