Sage Journals: Discover world-class research

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 $Δ_{3}^{0}$ -degrees by extending Cooper’s theorem to some levels of the fine hierarchy within $Δ_{3}^{0}$ -sets.

Keywords

Ershov’s hierarchy fine hierarchy arithmetical hierarchy Turing degrees

Get full access to this article

View all access options for this article.

References

S.B.

Cooper, Degrees of unsolvability, PhD thesis, Leicester University, Leicester, England, 1971.

Y.L.

Ershov, On a hierarchy of sets, Algebra i Logika7(1) (1968), 47–74(Russian); English translation: Algebra and Logic7 (1968), 23–41.

Y.L.

Ershov, On a hierarchy of sets II, Algebra i Logika7(4) (1968), 15–47(Russian); English translation: Algebra and Logic7 (1968), 212–232.

Y.L.

Ershov, On a hierarchy of sets III, Algebra i Logika9(1) (1970), 34–51(Russian); English translation: Algebra and Logic9 (1970), 20–31. doi:10.1007/BF02219847.

C.G.

Josckush and

Shore, Pseudo jump operators II: Transfinite iterations, hierarchies and minimal covers, Journal of Symbolic Logic49(4) (1984), 1205–1236. doi:10.2307/2274273.

Kihara and

Montalban, The uniform Martin’s conjecture for many-one degrees, arXiv:1608.05065v1 (17 Aug 2016).

V.L.

Selivanov, Hierarchies of hyperarithmetical sets and functions, Algebra i Logika22(6) (1983), 666–692, (Russian); English translation: Algebra and Logic22 (1983), 473–491.

V.L.

Selivanov, On the Ershov hierarchy, Sibirskii Matematicheskii Zhurnal26 (1985), 134–149(Russian); English translation: Siberian Mathematical Journal26 (1985), 105–116.

V.L.

Selivanov, Fine hierarchies of arithmetical sets and definable index sets, Trudy Instituta Matematiki SO AN SSSR12 (1989), 165–185(Russian); since 2007 journal has English translation Siberian Advances in Mathematics.

10.

V.L.

Selivanov, Fine hierarchies and Boolean terms, Journal of Symbolic Logic60 (1995), 289–317. doi:10.2307/2275522.

11.

V.L.

Selivanov and

M.M.

Yamaleev, On Turing degrees in refinements of the arithmetical hierarchy, Algebra and Logic, accepted.

12.

Soare, Recursively Enumerable Sets and Degrees, Springer, Berlin, 1987.