Geodesic
Computable families of sets in Ershov hierarchy without principal numberings
Sibirskij žurnal čistoj i prikladnoj matematiki, Tome 15 (2015) no. 1, pp. 54-62 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

There was constructed example of computable family of sets without $\Sigma^{-1}_{a}$-principal numberings, for any $a\in\mathcal{O}$.
Keywords: computable numbering, Ershov hierarchy. 
@article{VNGU_2015_15_1_a4,
     author = {S. S. Ospichev},
     title = {Computable families of sets in {Ershov} hierarchy without principal numberings},
     journal = {Sibirskij \v{z}urnal \v{c}istoj i prikladnoj matematiki},
     pages = {54--62},
     year = {2015},
     volume = {15},
     number = {1},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/VNGU_2015_15_1_a4/}
}
TY  - JOUR
AU  - S. S. Ospichev
TI  - Computable families of sets in Ershov hierarchy without principal numberings
JO  - Sibirskij žurnal čistoj i prikladnoj matematiki
PY  - 2015
SP  - 54
EP  - 62
VL  - 15
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/VNGU_2015_15_1_a4/
LA  - ru
ID  - VNGU_2015_15_1_a4
ER  - 
%0 Journal Article
%A S. S. Ospichev
%T Computable families of sets in Ershov hierarchy without principal numberings
%J Sibirskij žurnal čistoj i prikladnoj matematiki
%D 2015
%P 54-62
%V 15
%N 1
%U http://geodesic.mathdoc.fr/item/VNGU_2015_15_1_a4/
%G ru
%F VNGU_2015_15_1_a4
S. S. Ospichev. Computable families of sets in Ershov hierarchy without principal numberings. Sibirskij žurnal čistoj i prikladnoj matematiki, Tome 15 (2015) no. 1, pp. 54-62. http://geodesic.mathdoc.fr/item/VNGU_2015_15_1_a4/

[1] S. S. Goncharov, A. Sorbi, “Generalized computable numerations and nontrivial Rogers semilattices”, Algebra and Logic, 36:6 (1997), 359–369 | DOI | MR | Zbl

[2] S. S. Goncharov, S. Lempp, D. R. Solomon, “Friedberg numberings of families of $n$-computably enumerable sets”, Algebra and Logic, 41:2 (2002), 81–86 | DOI | MR | Zbl

[3] Badaev S. A., Lempp S., “A Decomposition of the Rogers Semilattice of a Family of D.C.E. Sets”, J. Symb. Logic, 74:2 (2009), 618–640 | DOI | MR | Zbl

[4] S. S. Ospichev, “Infinite family of $\Sigma_a^{-1}$-sets with a unique computable numbering”, J. Math. Sci., 188:4 (2013), 449–451 | DOI | MR | Zbl

[5] S. S. Ospichev, “Properties of numberings in various levels of the Ershov hierarchy”, J. Math. Sci., 188:4 (2013), 441–448 | DOI | MR | MR | Zbl

[6] M. Manat, A. Sorbi, “Positive undecidable numberings in the Ershov hierarchy”, Algebra and Logic, 50:6 (2012), 512–525 | DOI | MR | Zbl

[7] K. Sh. Abeshev, S. A. Badaev, M. Manat, “Families without minimal numberings”, Algebra and Logic, 53:4 (2014), 271–286 | DOI | MR | Zbl

[8] Abeshev K., “On the Existence of Universal Numberings for Finite Families of D.C.E. Sets”, Math. Logic Quat., 60:3 (2014), 161–167 | DOI | MR | Zbl

[9] S. A. Badaev, S. S. Goncharov, “Rogers semilattices of families of arithmetic sets”, Algebra and Logic, 40:5 (2001), 283–291 | DOI | MR | Zbl

[10] S. A. Badaev, S. S. Goncharov, A. Sorbi, “Elementary theories for Rogers semilattices”, Algebra and Logic, 44:3 (2005), 143–147 | DOI | MR | MR | Zbl | Zbl

[11] S. A. Badaev, S. S. Goncharov, A. Sorbi, “Isomorphism types of Rogers semilattices for families from different levels of the arithmetical hierarchy”, Algebra and Logic, 45:6 (2006), 361–370 | DOI | MR | MR | Zbl | Zbl

[12] S. A. Badaev, S. Yu. Podzorov, “Minimal coverings in the Rogers semilattices of $\Sigma^0_n$-computable numberings”, Sib. Mat. J., 43:4 (2002), 616–622 | DOI | MR | Zbl

[13] S. Yu. Podzorov, “Local structure of Rogers semilattices of $\Sigma^0_n$-computable numberings”, Algebra and Logic, 44:2 (2005), 82–94 | DOI | MR | Zbl

[14] Badaev S. A., Goncharov S. S., “Computability and Numberings”, New Computational Paradigms, eds. S. B. Cooper, B. Lowe, A. Sorbi, Springer, 2008, 19–34 | DOI | MR | Zbl

[15] N. A. Baklanova, “Undecidability of elementary theories of Rogers semilattices on the limit levels of the arithmetical hierarchy”, Vestn. Novosib. Gos. Univ., Ser. Mat. Mekh. Inform., 11:4 (2011), 3–7 (in Russian)

[16] N. A. Baklanova, “Minimal elements and minimal coverings in the Rogers semilattice of computable numberings in the hyperarithmetical hierarchy”, Vestn. Novosib. Gos. Univ., Ser. Mat. Mekh. Inform., 11:3 (2011), 77–84 (in Russian) | Zbl

[17] Yu. L. Ershov, “On a hierarchy of sets, III”, Algebra and Logic, 9:1 (1970), 20–31 | DOI | MR

[18] Yu. L. Ershov, Theory of Numberings, Nauka, M., 1977 (in Russian) | MR

[19] V. L. Selivanov, “Hierarchy of limiting computations”, Sib. Mat. J., 25:5 (1984), 798–806 | DOI | MR | Zbl

[20] Ospichev S., “Computable Family of $\Sigma^{-1}_a$-Sets without Friedberg Numberings”, Proc. of $6^\text{th}$ Conference on Computability in Europe, CiE 2010 (Ponta Delgada, 2010), 311–315