Extending Cooper’s theorem to Δ30 Turing degrees

Issue title: In Memory of S. Barry Cooper (1943–2015)

Guest editors: Benedikt Löwe

Article type: Research Article

Authors: Selivanov, Victor L.^{a; b} | Yamaleev, Mars M.^c

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. [email protected] | [c] N.I. Lobachevsky Institute of Mathematics and Mechanics, Kazan (Volga region) Federal University, 18 Kremlyovskaya str., Kazan, 420008, Russia. [email protected]

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, Σ₂⁰-sets

DOI: 10.3233/COM-180085

Journal: Computability, vol. 7, no. 2-3, pp. 289-300, 2018