Geodesic
Undecidability of elementary theory of Rogers semilattices in analytical hierarchy
Sibirskie èlektronnye matematičeskie izvestiâ, Tome 13 (2016), pp. 148-153 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

We prove that the elementary theory of any nontrivial Rogers semilattice for analytical sets of bounded complexity is hereditarily undecidable. We also prove some results on the existence of minimal numberings in such lattices.
Keywords: analitycal hierarchy, computable numberings, minimal numberings, Rogers semilattices. 
@article{SEMR_2016_13_a5,
     author = {M. V. Dorzhieva},
     title = {Undecidability of elementary theory of {Rogers} semilattices in analytical hierarchy},
     journal = {Sibirskie \`elektronnye matemati\v{c}eskie izvesti\^a},
     pages = {148--153},
     year = {2016},
     volume = {13},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/SEMR_2016_13_a5/}
}
TY  - JOUR
AU  - M. V. Dorzhieva
TI  - Undecidability of elementary theory of Rogers semilattices in analytical hierarchy
JO  - Sibirskie èlektronnye matematičeskie izvestiâ
PY  - 2016
SP  - 148
EP  - 153
VL  - 13
UR  - http://geodesic.mathdoc.fr/item/SEMR_2016_13_a5/
LA  - ru
ID  - SEMR_2016_13_a5
ER  - 
%0 Journal Article
%A M. V. Dorzhieva
%T Undecidability of elementary theory of Rogers semilattices in analytical hierarchy
%J Sibirskie èlektronnye matematičeskie izvestiâ
%D 2016
%P 148-153
%V 13
%U http://geodesic.mathdoc.fr/item/SEMR_2016_13_a5/
%G ru
%F SEMR_2016_13_a5
M. V. Dorzhieva. Undecidability of elementary theory of Rogers semilattices in analytical hierarchy. Sibirskie èlektronnye matematičeskie izvestiâ, Tome 13 (2016), pp. 148-153. http://geodesic.mathdoc.fr/item/SEMR_2016_13_a5/

[1] S. Yu. Podzorov, “Initial segments in Rogers semilattices of $\Sigma_{n}^{0}$-computable numberings”, Algebra and Logic, 42:2 (2003), 211–226 | DOI | MR | Zbl

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

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

[4] S. Badaev, S. Goncharov, S. Podzorov, A. Sorbi, “Algebraic properties of Rogers semilattices of arithmetical numberings”, Computability and Models, eds. S. B. Cooper, S. S. Goncharov, Kluwer/Plenum Publishers, New York, 2003, 45–77 | DOI | MR

[5] S. Badaev, S. Goncharov, A. Sorbi, “Completeness and universality of arithmetical numberings”, Computability and Models, eds. S. B. Cooper, S. S. Goncharov, Kluwer/Plenum Publishers, New York, 2003, 11–44 | DOI | MR

[6] M. V. Dorzhieva, “Eliminatsiya metarekursii iz teoremy Owinsa”, Vestnik NGU. Seriya: Matematika, mekhanika, informatika, 14:1 (2014), 35–43

[7] M. V. Dorzhieva, “Odnoznachnaya numeratsiya semeystva vsex $\Sigma_{2}^{1}$-mnozhestv”, Vestnik NGU (to appear)

[8] N. A. Baklanova, “Nerazreshimost' elementarnykh teoriy polureshetok Rodzhersa na predel'nykh urovnyakh arifmeticheskoy ierarkhii”, Vestnik NSU. Seriya: Matematika, mekhanika, informatika, 11:4 (2011), 3–7 | Zbl