Affiliations: [a] Laboratory of Theoretical Programming, A.P. Ershov Institute of Informatics Systems SB RAS, 6 Academician Lavrentiev ave., Novosibirsk, 630090, Russia | [b] N.I. Lobachevsky Institute of Mathematics and Mechanics, Kazan (Volga region) Federal University, 18 Kremlyovskaya str., Kazan, 420008, Russia. vseliv@iis.nsk.su | [c] N.I. Lobachevsky Institute of Mathematics and Mechanics, Kazan (Volga region) Federal University, 18 Kremlyovskaya str., Kazan, 420008, Russia. Mars.Yamaleev@kpfu.ru
Abstract: In 1971 B. Cooper proved that there exists a 2-c.e. Turing degree which doesn’t contain a c.e. set. Thus, he showed that the second level of the Ershov hierarchy is proper. In this paper we investigate proper levels of some extensions of the Ershov hierarchy to higher levels of the arithmetical hierarchy. Thus we contribute to the theory of Δ30-degrees by extending Cooper’s theorem to some levels of the fine hierarchy within Δ30-sets.
Keywords: Ershov’s hierarchy, fine hierarchy, arithmetical hierarchy, Turing degrees, Σ20-sets
DOI: 10.3233/COM-180085
Journal: Computability, vol. 7, no. 2-3, pp. 289-300, 2018