Geodesic
Turing degrees in refinements of the arithmetical hierarchy
Algebra i logika, Tome 57 (2018) no. 3, pp. 338-361 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

We investigate the problem of characterizing proper levels of the fine hierarchy (up to Turing equivalence). It is known that the fine hierarchy exhausts arithmetical sets and contains as a small fragment finite levels of Ershov hierarchies (relativized to $\varnothing^n$, $n<\omega$), which are known to be proper. Our main result is finding a least new (i.e., distinct from the levels of the relativized Ershov hierarchies) proper level. We also show that not all new levels are proper.
Keywords: Ershov hierarchy, fine hierarchy, arithmetical hierarchy, Turing degrees. 
@article{AL_2018_57_3_a5,
     author = {V. L. Selivanov and M. M. Yamaleev},
     title = {Turing degrees in refinements of the arithmetical hierarchy},
     journal = {Algebra i logika},
     pages = {338--361},
     year = {2018},
     volume = {57},
     number = {3},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/AL_2018_57_3_a5/}
}
TY  - JOUR
AU  - V. L. Selivanov
AU  - M. M. Yamaleev
TI  - Turing degrees in refinements of the arithmetical hierarchy
JO  - Algebra i logika
PY  - 2018
SP  - 338
EP  - 361
VL  - 57
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/AL_2018_57_3_a5/
LA  - ru
ID  - AL_2018_57_3_a5
ER  - 
%0 Journal Article
%A V. L. Selivanov
%A M. M. Yamaleev
%T Turing degrees in refinements of the arithmetical hierarchy
%J Algebra i logika
%D 2018
%P 338-361
%V 57
%N 3
%U http://geodesic.mathdoc.fr/item/AL_2018_57_3_a5/
%G ru
%F AL_2018_57_3_a5
V. L. Selivanov; M. M. Yamaleev. Turing degrees in refinements of the arithmetical hierarchy. Algebra i logika, Tome 57 (2018) no. 3, pp. 338-361. http://geodesic.mathdoc.fr/item/AL_2018_57_3_a5/

[1] S. B. Cooper, Degrees of unsolvability, Ph. D. thesis, Leicester Univ., England, 1971

[2] Yu. L. Ershov, “Ob odnoi ierarkhii mnozhestv. I”, Algebra i logika, 7:1 (1968), 47–74 | MR | Zbl

[3] C. G. Jockusch (jun.), R. A. Shore, “Pseudo-jump operators. II: Transfinite iterations, hierarchies and minimal covers”, J. Symb. Log., 49:4 (1984), 1205–1236 | DOI | MR | Zbl

[4] V. L. Selivanov, “Ob ierarkhii Ershova”, Sib. matem. zh., 26:1 (1985), 134–149 | MR | Zbl

[5] Yu. L. Ershov, “Ob odnoi ierarkhii mnozhestv. II”, Algebra i logika, 7:4 (1968), 15–47 | MR | Zbl

[6] Yu. L. Ershov, “Ob odnoi ierarkhii mnozhestv. III”, Algebra i logika, 9:1 (1970), 34–51 | MR

[7] V. L. Selivanov, “Ierarkhii giperarifmeticheskikh mnozhestv i funktsii”, Algebra i logika, 22:6 (1983), 666–692 | MR | Zbl

[8] V. L. Selivanov, “Fine hierarchies and Boolean terms”, J. Symb. Log., 60:1 (1995), 289–317 | DOI | MR | Zbl

[9] R. Rogers, Theory of recursive functions and effective computability, McGraw-Hill, New York, 1967 ; Kh. Rodzhers, Teoriya rekursivnykh funktsii i effektivnaya vychislimost, Mir, M., 1972 | MR | Zbl

[10] V. L. Selivanov, “Tonkaya ierarkhiya arifmeticheskikh mnozhestv i opredelimye indeksnye mnozhestva”, Matematicheskaya logika i algoritmicheskie problemy, Tr. In-ta matem. SO AN SSSR, 12, 1989, 165–185 | Zbl

[11] W. Wadge, Reducibility and determinateness in the Baire space, Ph. D. thesis, Univ. California, Berkeley, 1984

[12] K. Kuratovskii, A. Mostovskii, Teoriya mnozhestv, Mir, M., 1970 | MR

[13] R. I. Soare, Recursively enumerable sets and degrees, Perspect. Math. Log. Omega Series, Springer-Verlag, Heidelberg a.o., 1987 ; R. I. Soar, Vychislimo perechislimye mnozhestva i stepeni, Kazanskoe matem. ob-vo, Kazan, 2000 | DOI | MR | Zbl