Geodesic
The branching theorem and computable categoricity in the Ershov hierarchy
Algebra i logika, Tome 54 (2015) no. 2, pp. 137-157.

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

Computable categoricity in the Ershov hierarchy is studied. We consider $F_a$- and $G_a$-categorical structures. These were introduced by B. Khoussainov, F. Stephan, and Y. Yang for $a$, which is a notation for a constructive ordinal. A generalization of the branching theorem is proved for $F_a$-categorical structures. As a consequence we obtain a description of $F_a$-categorical structures for classes of Boolean algebras and Abelian $p$-groups. Furthermore, it is shown that the branching theorem cannot be generalized to $G_a$-categorical structures.
Keywords: computable categoricity, Ershov hierarchy, $F_a$-categoricity, $G_a$-categoricity, branching structure. 
@article{AL_2015_54_2_a0,
     author = {N. A. Bazhenov},
     title = {The branching theorem and computable categoricity in the {Ershov} hierarchy},
     journal = {Algebra i logika},
     pages = {137--157},
     publisher = {mathdoc},
     volume = {54},
     number = {2},
     year = {2015},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/AL_2015_54_2_a0/}
}
TY  - JOUR
AU  - N. A. Bazhenov
TI  - The branching theorem and computable categoricity in the Ershov hierarchy
JO  - Algebra i logika
PY  - 2015
SP  - 137
EP  - 157
VL  - 54
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/AL_2015_54_2_a0/
LA  - ru
ID  - AL_2015_54_2_a0
ER  - 
%0 Journal Article
%A N. A. Bazhenov
%T The branching theorem and computable categoricity in the Ershov hierarchy
%J Algebra i logika
%D 2015
%P 137-157
%V 54
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/AL_2015_54_2_a0/
%G ru
%F AL_2015_54_2_a0
N. A. Bazhenov. The branching theorem and computable categoricity in the Ershov hierarchy. Algebra i logika, Tome 54 (2015) no. 2, pp. 137-157. http://geodesic.mathdoc.fr/item/AL_2015_54_2_a0/

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

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

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

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

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

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

[7] S. Ospichev, “Computable family of $\Sigma_a^{-1}$-sets without Friedberg numberings”, CiE 2010, 6th Conf. Comput. Europe, Univ. Azores, Ponta Delgada, 2010, 311–315

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

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

[10] S. A. Badaev, M. Manat, A. Sorbi, “Rogers semilattices of families of two embedded sets in the Ershov hierarchy”, Math. Log. Q., 58:4/5 (2012), 366–376 | DOI | MR | Zbl

[11] B. Khoussainov, F. Stephan, Y. Yang, “Computable categoricity and the Ershov hierarchy”, Ann. Pure Appl. Logic, 156:1 (2008), 86–95 | DOI | MR | Zbl

[12] D. Cenzer, G. LaForte, J. B. Remmel, “Equivalence structures and isomorphisms in the difference hierarchy”, J. Symb. Log., 74:2 (2009), 535–556 | DOI | MR | Zbl

[13] S. S. Goncharov, V. D. Dzgoev, “Avtoustoichivost modelei”, Algebra i logika, 19:1 (1980), 45–58 | MR | Zbl

[14] S. S. Goncharov, “Avtoustoichivost modelei i abelevykh grupp”, Algebra i logika, 19:1 (1980), 23–44 | MR | Zbl

[15] P. E. Alaev, “Avtoustoichivye $I$-algebry”, Algebra i logika, 43:5 (2004), 511–550 | MR | Zbl

[16] D. I. Dushenin, “Otnositelnaya avtoustoichivost pryamykh summ abelevykh $p$-grupp”, Vestn. NGU. Ser. matem., mekh., inform., 10:1 (2010), 29–39 | Zbl

[17] N. T. Kogabaev, “Avtoustoichivost bulevykh algebr s vydelennym idealom”, Sib. matem. zh., 39:5 (1998), 1074–1084 | MR | Zbl

[18] P. E. Alaev, “Computably categorical Boolean algebras enriched by ideals and atoms”, Ann. Pure Appl. Logic, 163:5 (2012), 485–499 | DOI | MR | Zbl

[19] N. T. Kogabaev, “Klass proektivnykh ploskostei nevychislim”, Algebra i logika, 47:4 (2008), 428–455 | MR | Zbl

[20] N. T. Kogabaev, “Nevychislimost klassov pappovykh i dezargovykh proektivnykh ploskostei”, Sib. matem. zh., 54:2 (2013), 325–335 | MR | Zbl

[21] R. R. Tukhbatullina, “Avtoustoichivost bulevoi algebry $\mathfrak B_\omega$, obogaschennoi avtomorfizmom”, Vestn. NGU. Ser. matem., mekh., inform., 10:3 (2010), 110–118 | Zbl

[22] S. S. Goncharov, Yu. L. Ershov, Konstruktivnye modeli, Sibirskaya shkola algebry i logiki, Nauchnaya kniga, Novosibirsk, 1999

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

[24] Kh. Rodzhers, Teoriya rekursivnykh funktsii i effektivnaya vychislimost, Mir, M., 1972 | MR

[25] J. B. Remmel, “Recursively categorical linear orderings”, Proc. Am. Math. Soc., 83:2 (1981), 387–391 | DOI | MR | Zbl

[26] J. B. Remmel, “Recursive isomorphism types of recursive Boolean algebras”, J. Symb. Log., 46:3 (1981), 572–594 | DOI | MR | Zbl

[27] L. Fuks, Beskonechnye abelevy gruppy, v. 1, Mir, M., 1974

[28] R. L. Smith, Logic Year 1979–80, Two theorems on autostability in $p$-groups, Lect. Notes Math., 859, Springer-Verlag, Berlin etc., 1981, 302–311 | DOI | MR