Geodesic
Preserving categoricity and complexity of relations
Algebra i logika, Tome 54 (2015) no. 2, pp. 212-235.

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

In [Algebra i Logika, 16, No. 3 (1977), 257–282; Ann. Pure Appl. Logic, 136, No. 3 (2005), 219–246; J. Symb. Log., 74, No. 3 (2009), 1047–1060], it was proved that for each computable ordinal $\alpha$, there is a structure that is $\Delta^0_\alpha$ categorical but not relatively $\Delta^0_\alpha$ categorical. The original examples were not familiar algebraic kinds of structures. In [Ann. Pure Appl. Logic, 115, Nos. 1–3 (2002), 71–113], it was shown that for $\alpha=1$, there are further examples in several familiar classes of structures, including rings and $2$-step nilpotent groups. Similar examples for all computable successor ordinals were constructed in [Algebra i Logika, 46, No. 4 (2007), 514–524]. In the present paper, this result is extended to computable limit ordinals. We know of an example of an algebraic field that is computably categorical but not relatively computably categorical. Here we show that for each computable limit ordinal $\alpha>\omega$, there is a field which is $\Delta^0_\alpha$ categorical but not relatively $\Delta^0_\alpha$ categorical. Examples on dimension and complexity of relations are given.
Keywords: $\Delta^0_\alpha$ categorical structure, structure that is not relatively $\Delta^0_\alpha$categorical, field. 
@article{AL_2015_54_2_a4,
     author = {J. Johnson and J. F. Knight and V. Ocasio and J. Tussupov and S. VanDenDriessche},
     title = {Preserving categoricity and complexity of relations},
     journal = {Algebra i logika},
     pages = {212--235},
     publisher = {mathdoc},
     volume = {54},
     number = {2},
     year = {2015},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/AL_2015_54_2_a4/}
}
TY  - JOUR
AU  - J. Johnson
AU  - J. F. Knight
AU  - V. Ocasio
AU  - J. Tussupov
AU  - S. VanDenDriessche
TI  - Preserving categoricity and complexity of relations
JO  - Algebra i logika
PY  - 2015
SP  - 212
EP  - 235
VL  - 54
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/AL_2015_54_2_a4/
LA  - ru
ID  - AL_2015_54_2_a4
ER  - 
%0 Journal Article
%A J. Johnson
%A J. F. Knight
%A V. Ocasio
%A J. Tussupov
%A S. VanDenDriessche
%T Preserving categoricity and complexity of relations
%J Algebra i logika
%D 2015
%P 212-235
%V 54
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/AL_2015_54_2_a4/
%G ru
%F AL_2015_54_2_a4
J. Johnson; J. F. Knight; V. Ocasio; J. Tussupov; S. VanDenDriessche. Preserving categoricity and complexity of relations. Algebra i logika, Tome 54 (2015) no. 2, pp. 212-235. http://geodesic.mathdoc.fr/item/AL_2015_54_2_a4/

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

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

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

[4] S. A. Badaev, “O vychislimykh numeratsiyakh semeistv obscherekursivnykh funktsii”, Algebra i logika, 16:2 (1977), 129–148 | MR | Zbl

[5] V. L. Selivanov, “O numeratsiyakh semeistv obscherekursivnykh funktsii”, Algebra i logika, 15:2 (1976), 205–226 | MR | Zbl

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

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

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

[9] S. S. Goncharov, Schetnye bulevy algebry i razreshimost, Sibirskaya shkola algebry i logiki, Nauchnaya kniga (NII MIOO NGU), Novosibirsk, 1996 | MR

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

[11] D. R. Hirschfeldt, B. Khoussainov, R. A. Shore, A. M. Slinko, “Degree spectra and computable dimensions in algebraic structures”, Ann. Pure Appl. Logic, 115:1–3 (2002), 71–113 | DOI | MR | Zbl

[12] D. A. Tusupov, “Izomorfizmy, opredelimye otnosheniya i semeistva Skotta dvustupenno nilpotentnykh grupp”, Algebra i logika, 46:4 (2007), 514–524 | MR | Zbl

[13] D. Marker, Model theory: an introduction, Grad. Texts Math., 217, Springer-Verlag, New York etc., 2002 | MR | Zbl

[14] A. Nies, “Undecidable fragments of elementary theories”, Algebra Univers., 35:1 (1996), 8–33 | DOI | MR | Zbl

[15] D. Hirschfeldt, K. Kramer, R. Miller, A. Shlapentokh, “Categoricity properties for computable algebraic fields”, Trans. Am. Math. Soc., 367:6 (2015), 3981–4017 | DOI | MR | Zbl

[16] H. Friedman, L. Stanley, “A Borel reducibility theory for classes of countable structures”, J. Symb. Log., 54:3 (1989), 894–914 | DOI | MR | Zbl

[17] R. Miller, J. Park, B. Poonen, H. Schoutens, A. Shlapentokh, A computable functor from graphs to fields, in preparation

[18] I. N. Soskov, “Intrinsically hyperarithmetical sets”, Math. Log. Q., 42:4 (1996), 469–480 | DOI | MR | Zbl

[19] I. N. Soskov, “Intrinsically $\Pi^1_1$ relations”, Math. Log. Q., 42:1 (1996), 109–126 | DOI | MR | Zbl

[20] S. S. Goncharov, V. Harizanov, J. F. Knight, R. A. Shore, “$\Pi^1_1$ relations and paths through $\mathcal O$”, J. Symb. Log., 69:2 (2004), 585–611 | DOI | MR | Zbl