Geodesic
Friedberg numberings in the Ershov hierarchy
Algebra i logika, Tome 54 (2015) no. 4, pp. 444-462.

Voir la notice de l'article provenant de la source Math-Net.Ru

A Friedberg numbering of the family of all sets for any given level of the Ershov hierarchy is constructed, and we also consider different consequences of this result.
Keywords: computable numbering, Friedberg numbering, Ershov hierarchy. 
@article{AL_2015_54_4_a2,
     author = {S. S. Ospichev},
     title = {Friedberg numberings in the {Ershov} hierarchy},
     journal = {Algebra i logika},
     pages = {444--462},
     publisher = {mathdoc},
     volume = {54},
     number = {4},
     year = {2015},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/AL_2015_54_4_a2/}
}
TY  - JOUR
AU  - S. S. Ospichev
TI  - Friedberg numberings in the Ershov hierarchy
JO  - Algebra i logika
PY  - 2015
SP  - 444
EP  - 462
VL  - 54
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/AL_2015_54_4_a2/
LA  - ru
ID  - AL_2015_54_4_a2
ER  - 
%0 Journal Article
%A S. S. Ospichev
%T Friedberg numberings in the Ershov hierarchy
%J Algebra i logika
%D 2015
%P 444-462
%V 54
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/AL_2015_54_4_a2/
%G ru
%F AL_2015_54_4_a2
S. S. Ospichev. Friedberg numberings in the Ershov hierarchy. Algebra i logika, Tome 54 (2015) no. 4, pp. 444-462. http://geodesic.mathdoc.fr/item/AL_2015_54_4_a2/

[1] R. M. Friedberg, “Three theorems on recursive enumeration. I. Decomposition. II. Maximal set. III. Enumeration without duplication”, J. Symb. Log., 23:3 (1958), 309–316 | DOI | MR

[2] S. S. Goncharov, S. Lempp, D. R. Solomon, “Fridbergovskie numeratsii semeistv $n$-vychislimo perechislimykh mnozhestv”, Algebra i logika, 41:2 (2002), 143–154 | MR | Zbl

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

[4] C. J. Ash, J. F. Knight, Computable structures and the hyperarithmetical hierarchy, Stud. Logic Found. Math., 144, Elsevier Sci. B.V., Amsterdam etc., 2000 | MR | Zbl

[5] S. S. Goncharov, A. Sorbi, “Obobschenno vychislimye numeratsii i netrivialnye polureshetki Rodzhersa”, Algebra i logika, 36:6 (1997), 621–641 | MR | Zbl

[6] S. S. Ospichev, “Beskonechnoe semeistvo $\Sigma_a^{-1}$-mnozhestv s edinstvennoi vychislimoi numeratsiei”, Vestn. NGU. Ser. matem., mekh., inform., 11:2 (2011), 89–92 | Zbl

[7] S. S. Ospichev, “Nekotorye svoistva numeratsii razlichnykh klassov ierarkhii Ershova”, Vestn. NGU. Ser. matem., mekh., inform., 10:4 (2010), 125–132 | Zbl

[8] V. L. Selivanov, “Ob ierarkhii predelnykh vychislenii”, Sib. matem. zh., 25:5 (1984), 146–156 | MR

[9] Zh. T. Talasbaeva, “O pozitivnykh numeratsiyakh semeistv mnozhestv ierarkhii Ershova”, Algebra i logika, 42:6 (2003), 737–746 | MR | Zbl

[10] S. A. Badaev, “O pozitivnykh numeratsiyakh”, Sib. matem. zh., 18:3 (1977), 483–496 | MR | Zbl

[11] M. Manat, A. Sorbi, “Pozitivnye nerazreshimye numeratsii v ierarkhii Ershova”, Algebra i logika, 50:6 (2011), 759–780 | MR

[12] M. Kummer, “Numberings of $\mathcal{R_1\cup F}$”, CSL' 88, Proc. 2nd Workshop (Duisburg/FRG 1988), Lect. Notes Comput. Sci., 385, eds. E. Börger et al., Springer-Verlag, Berlin, 1989, 166–186 | DOI | MR

[13] M. B. Pour-El, W. A. Howard, “A structural criterion for recursive numeration without repetition”, Z. Math. Logik Grundlagen Math., 10:2 (1964), 105–114 | DOI | MR | Zbl