Geodesic
Ash’s theorem on $\Delta^0_\alpha$-categorical structures and a condition for infinite $\Delta^0_\alpha$-dimension
Algebra i logika, Tome 54 (2015) no. 5, pp. 551-574 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

An old classical result in computable structure theory is Ash's theorem stating that for every computable ordinal $\alpha\ge2$, under some additional conditions, a computable structure is $\Delta^0_\alpha$-categorical iff it has a computable $\Sigma_\alpha$ Scott family. We construct a counterexample revealing that the proof of this theorem has a serious error. Moreover, we show how the error can be corrected by revising the proof. In addition, we formulate a sufficient condition under which the $\Delta^0_\alpha$-dimension of a computable structure is infinite.
Keywords: computable structure, Ash's theorem, $\Delta^0_\alpha$-categorical structure, $\Sigma_\alpha$ Scott family, $\Delta^0_\alpha$-dimension of a computable structure. 
@article{AL_2015_54_5_a0,
     author = {P. E. Alaev},
     title = {Ash{\textquoteright}s theorem on $\Delta^0_\alpha$-categorical structures and a~condition for infinite $\Delta^0_\alpha$-dimension},
     journal = {Algebra i logika},
     pages = {551--574},
     year = {2015},
     volume = {54},
     number = {5},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/AL_2015_54_5_a0/}
}
TY  - JOUR
AU  - P. E. Alaev
TI  - Ash’s theorem on $\Delta^0_\alpha$-categorical structures and a condition for infinite $\Delta^0_\alpha$-dimension
JO  - Algebra i logika
PY  - 2015
SP  - 551
EP  - 574
VL  - 54
IS  - 5
UR  - http://geodesic.mathdoc.fr/item/AL_2015_54_5_a0/
LA  - ru
ID  - AL_2015_54_5_a0
ER  - 
%0 Journal Article
%A P. E. Alaev
%T Ash’s theorem on $\Delta^0_\alpha$-categorical structures and a condition for infinite $\Delta^0_\alpha$-dimension
%J Algebra i logika
%D 2015
%P 551-574
%V 54
%N 5
%U http://geodesic.mathdoc.fr/item/AL_2015_54_5_a0/
%G ru
%F AL_2015_54_5_a0
P. E. Alaev. Ash’s theorem on $\Delta^0_\alpha$-categorical structures and a condition for infinite $\Delta^0_\alpha$-dimension. Algebra i logika, Tome 54 (2015) no. 5, pp. 551-574. http://geodesic.mathdoc.fr/item/AL_2015_54_5_a0/

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

[2] C. J. Ash, J. F. Knight, M. Manasse, T. Slaman, “Generic copies of countable structures”, Ann. Pure Appl. Logic, 42:3 (1989), 195–205 | DOI | MR | Zbl

[3] J. Chisholm, “Effective model theory vs. recursive model theory”, J. Symb. Log., 55:3 (1990), 1168–1191 | DOI | MR | Zbl

[4] S. S. Goncharov, “Avtoustoichivost i vychislimye semeistva konstruktivizatsii”, Algebra i logika, 14:6 (1975), 647–680 | MR | Zbl

[5] S. S. Goncharov, “O chisle neavtoekvivalentnykh konstruktivizatsii”, Algebra i logika, 16:3 (1977), 257–282 | MR | Zbl

[6] O. V. Kudinov, “Avtoustoichivaya 1-razreshimaya model bez vychislimogo semeistva Skotta $\exists$-formul”, Algebra i logika, 35:4 (1996), 458–467 | MR | Zbl

[7] C. J. Ash, “Categoricity in hyperarithmetical degrees”, Ann. Pure Appl. Logic, 34:1 (1987), 1–14 | DOI | MR | Zbl

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

[9] S. Goncharov, V. Harizanov, J. Knight, C. McCoy, R. Miller, R. Solomon, “Enumerations in computable structure theory”, Ann. Pure Appl. Logic, 136:3 (2005), 219–246 | DOI | MR | Zbl

[10] J. Chisholm, E. B. Fokina, S. S. Goncharov, V. S. Harizanov, J. F. Knight, S. Quinn, “Intrinsic bounds on complexity and definability at limit levels”, J. Symb. Log., 74:3 (2009), 1047–1060 | DOI | MR | Zbl

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

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

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