Geodesic
Index sets for $n$-decidable structures categorical relative to $m$-decidable presentations
Algebra i logika, Tome 54 (2015) no. 4, pp. 520-528.

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

We say that a structure is categorical relative to $n$-decidable presentations (or autostable relative to $n$-constructivizations) if any two $n$-decidable copies of the structure are computably isomorphic. For $n=0$, we have the classical definition of a computably categorical (autostable) structure. Downey, Kach, Lempp, Lewis, Montalbán, and Turetsky proved that there is no simple syntactic characterization of computable categoricity. More formally, they showed that the index set of computably categorical structures is $\Pi^1_1$-complete. We study index sets of $n$-decidable structures that are categorical relative to $m$-decidable presentations, for various $m,n\in\omega$. If $m\ge n\ge0$, then the index set is again $\Pi^1_1$-complete, i.e., there is no nice description of the class of $n$-decidable structures that are categorical relative to $m$-decidable presentations. In the case $m=n-1\ge0$, the index set is $\Pi^0_4$-complete, while if $0\le m\le n-2$, the index set is $\Sigma^0_3$-complete.
Keywords: index set, structure categorical relative to $n$-decidable presentations, $n$-decidable structure categorical relative to $m$-decidable presentations. 
@article{AL_2015_54_4_a6,
     author = {E. B. Fokina and S. S. Goncharov and V. Harizanov and O. V. Kudinov and D. Turetsky},
     title = {Index sets for $n$-decidable structures categorical relative to $m$-decidable presentations},
     journal = {Algebra i logika},
     pages = {520--528},
     publisher = {mathdoc},
     volume = {54},
     number = {4},
     year = {2015},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/AL_2015_54_4_a6/}
}
TY  - JOUR
AU  - E. B. Fokina
AU  - S. S. Goncharov
AU  - V. Harizanov
AU  - O. V. Kudinov
AU  - D. Turetsky
TI  - Index sets for $n$-decidable structures categorical relative to $m$-decidable presentations
JO  - Algebra i logika
PY  - 2015
SP  - 520
EP  - 528
VL  - 54
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/AL_2015_54_4_a6/
LA  - ru
ID  - AL_2015_54_4_a6
ER  - 
%0 Journal Article
%A E. B. Fokina
%A S. S. Goncharov
%A V. Harizanov
%A O. V. Kudinov
%A D. Turetsky
%T Index sets for $n$-decidable structures categorical relative to $m$-decidable presentations
%J Algebra i logika
%D 2015
%P 520-528
%V 54
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/AL_2015_54_4_a6/
%G ru
%F AL_2015_54_4_a6
E. B. Fokina; S. S. Goncharov; V. Harizanov; O. V. Kudinov; D. Turetsky. Index sets for $n$-decidable structures categorical relative to $m$-decidable presentations. Algebra i logika, Tome 54 (2015) no. 4, pp. 520-528. http://geodesic.mathdoc.fr/item/AL_2015_54_4_a6/

[1] A. Fröhlich, J. Shepherdson, “Effective procedures in field theory”, Philos. Trans. Roy. Soc. London Ser. A, 248:950 (1956), 407–432 | DOI | MR | Zbl

[2] A. I. Maltsev, “Konstruktivnye algebry. 1”, UMN, 16:3 (1961), 3–60 | MR | Zbl

[3] A. I. Maltsev, “O rekursivnykh abelevykh gruppakh”, Dokl. AN SSSR, 146:5 (1962), 1009–1012 | Zbl

[4] S. S. Goncharov, “Autostable models and algorithmic dimensions”, Handbook of recursive mathematics, v. 1, Stud. Logic Found. Math., 138, Recursive model theory, eds. Yu. L. Ershov et al., Elsevier, Amsterdam, 1998, 261–287 | DOI | MR | Zbl

[5] E. B. Fokina, V. Harizanov, A. Melnikov, “Computable model theory”, Turing's Legacy: Developments from Turing's ideas in logic, Lect. Notes Log., 42, ed. R. Downey, Cambridge Univ. Press, Assoc. Symbol. Logic, Cambridge, 2014, 124–194

[6] R. G. Downey, A. M. Kach, S. Lempp, A. E. M. Lewis-Pye, A. Montalbán, D. D. Turetsky, “The complexity of computable categoricity”, Adv. Math., 268 (2015), 423–466 | DOI | MR | Zbl

[7] S. S. Goncharov, “Problema chisla neavtoekvivalentnykh konstruktivizatsii”, Algebra i logika, 19:6 (1980), 621–639 | MR

[8] S. S. Goncharov, N. A. Bazhenov, M. I. Marchuk, “Indeksnoe mnozhestvo avtoustoichivykh otnositelno silnykh konstruktivizatsii bulevykh algebr”, Sib. matem. zh., 56:3 (2015), 498–512 | MR | Zbl

[9] S. S. Goncharov, “Stepeni avtoustoichivosti otnositelno silnykh konstruktivizatsii”, Algoritmicheskie voprosy algebry i logiki, K 80-letiyu so dnya rozhdeniya akad. S. I. Adyana, Tr. MIAN, 274, MAIK, M., 2011, 119–129 | MR

[10] S. S. Goncharov, “Ob avtoustoichivosti otnositelno silnykh konstruktivizatsii pochti prostykh modelei”, UMN, 65:5(395) (2010), 107–142 | DOI | MR | Zbl

[11] S. S. Goncharov, “Avtoustoichivost prostykh modelei otnositelno silnykh konstruktivizatsii”, Algebra i logika, 48:6 (2009), 729–740 | MR | Zbl

[12] S. S. Goncharov, M. I. Marchuk, “Indeksnye mnozhestva avtoustoichivykh otnositelno silnykh konstruktivizatsii konstruktivnykh modelei”, Vestn. NGU. Ser. matem., mekh., inform., 13:4 (2013), 43–67

[13] S. S. Goncharov, “Indeksnye mnozhestva pochti prostykh konstruktivnykh modelei”, Vestn. NGU. Ser. matem., mekh., inform., 13:3 (2013), 38–52 | Zbl

[14] S. S. Goncharov, M. I. Marchuk, “Indeksnye mnozhestva avtoustoichivykh otnositelno silnykh konstruktivizatsii konstruktivnykh modelei ogranichennoi signatury”, Algebra i logika, 54:2 (2015), 163–192 | Zbl

[15] S. S. Goncharov, M. I. Marchuk, “Indeksnye mnozhestva avtoustoichivykh otnositelno silnykh konstruktivizatsii konstruktivnykh modelei netrivialnykh signatur”, Dokl. AN, 461:2 (2015), 140–142 | DOI | MR | Zbl

[16] D. Marker, “Non $\Sigma_n$ axiomatizable almost strongly minimal theories”, J. Symb. Log., 54:3 (1989), 921–927 | DOI | MR | Zbl

[17] U. Andrews, J. S. Miller, “Spectra of theories and structures”, Proc. Am. Math. Soc., 143:3 (2015), 1283–1298 | DOI | MR | Zbl

[18] S. S. Goncharov, B. Khusainov, “Slozhnost teorii vychislimykh kategorichnykh modelei”, Algebra i logika, 43:6 (2004), 650–665 | MR | Zbl

[19] E. B. Fokina, I. Kalimullin, R. Miller, “Degrees of categoricity of computable structures”, Arch. Math. Logic, 49:1 (2010), 51–67 | DOI | MR | Zbl

[20] R. G. Downey, A. M. Kach, S. Lempp, D. D. Turetsky, “Computable categoricity versus relative computable categoricity”, Fundam. Math., 221:2 (2013), 129–159 | DOI | MR | Zbl

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

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

[23] M. Kummer, S. Vekhner, K. Ii, “Diskretnye semeistva rekursivnykh funktsii i indeksnye mnozhestva”, Algebra i logika, 33:2 (1994), 149–165 | MR

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