Geodesic
Families without minimal numberings
Algebra i logika, Tome 53 (2014) no. 4, pp. 427-450.

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

It is proved that for any nonzero computable ordinal and its arbitrary notation $a$, there exists $\Sigma_a^{-1}$-computable family without minimal computable numberings.
Keywords: computable numbering, Ershov hierarchy, minimal numbering. 
@article{AL_2014_53_4_a0,
     author = {K. Sh. Abeshev and S. A. Badaev and M. Mustafa},
     title = {Families without minimal numberings},
     journal = {Algebra i logika},
     pages = {427--450},
     publisher = {mathdoc},
     volume = {53},
     number = {4},
     year = {2014},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/AL_2014_53_4_a0/}
}
TY  - JOUR
AU  - K. Sh. Abeshev
AU  - S. A. Badaev
AU  - M. Mustafa
TI  - Families without minimal numberings
JO  - Algebra i logika
PY  - 2014
SP  - 427
EP  - 450
VL  - 53
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/AL_2014_53_4_a0/
LA  - ru
ID  - AL_2014_53_4_a0
ER  - 
%0 Journal Article
%A K. Sh. Abeshev
%A S. A. Badaev
%A M. Mustafa
%T Families without minimal numberings
%J Algebra i logika
%D 2014
%P 427-450
%V 53
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/AL_2014_53_4_a0/
%G ru
%F AL_2014_53_4_a0
K. Sh. Abeshev; S. A. Badaev; M. Mustafa. Families without minimal numberings. Algebra i logika, Tome 53 (2014) no. 4, pp. 427-450. http://geodesic.mathdoc.fr/item/AL_2014_53_4_a0/

[1] V. V. Vyugin, “O nekotorykh primerakh verkhnikh polureshëtok vychislimykh numeratsii”, Algebra i logika, 12:5 (1973), 512–529

[2] S. A. Badaev, “Minimalnye numeratsii”, Matematicheskaya logika i teoriya algoritmov, Trudy in-ta matem. SO RAN, 25, 1993, 3–34 | MR | Zbl

[3] S. A. Badaev, Zh. T. Talasbaeva, “Computable numberings in the hierarchy of Ershov”, Mathematical logic in Asia, Proceedings of the 9th Asian logic conference (Novosibirsk, Russia, August 16–19, 2005), eds. Goncharov S. S. et al., World Scientific, NJ, 2006, 17–30 | DOI | MR | Zbl

[4] S. A. Badaev, S. Lempp, “A decomposition of the Rogers semilattice of a family of d.c.e. sets J.”, Symb. Log., 74:2 (2009), 618–640 | DOI | MR | Zbl

[5] A. V. Khutoretskii, “O moschnosti verkhnei polureshetki vychislimykh numeratsii”, Algebra i logika, 10:5 (1971), 561–569

[6] K. Sh. Abeshev, “On the existence of universal numberings for finite families of d.c.e. sets”, Math. Log. Q., 60:3 (2014), 161–167 | DOI | MR | Zbl

[7] S. A. Badaev, S. S. Goncharov, “Theory of numberings: open problems”, Computability theory and its applications, Contemp. Math., 257, eds. P. Cholak et al., Am. Math. Soc., Providence, RI, 2000, 23–38 | DOI | MR | Zbl

[8] 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 | MR

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

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

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

[12] 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

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

[14] Yu. L. Ershov, Teoriya numeratsii, Nauka, M., 1977 | MR