Geodesic
Index sets of computable structures
Algebra i logika, Tome 45 (2006) no. 5, pp. 538-574.

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

The index set of a computable structure $\mathcal A$ is the set of indices for computable copies of $\mathcal A$. We determine complexity of the index sets of various mathematically interesting structures including different finite structures, $\mathbb Q$-vector spaces, Archimedean real-closed ordered fields, reduced Abelian $p$-groups of length less than $\omega^2$, and models of the original Ehrenfeucht theory. The index sets for these structures all turn out to be $m$-complete $\Pi_n^0$, $d-\Sigma_n^0$, or $\Sigma_n^0$ , for various $n$. In each case the calculation involves finding an optimal sentence (i.e., one of simplest form) that describes the structure. The form of the sentence (computable $\Pi_n$, $d-\Sigma_n$, or $\Sigma_n$) yields a bound on the complexity of the index set. Whenever we show $m$-completeness of the index set, we know that the sentence is optimal. For some structures, the first sentence that comes to mind is not optimal, and another sentence of simpler form is shown to serve the purpose. For some of the groups, this involves Ramsey's theory.
Keywords: index set, computable structure, vector space, Archimedean real-closed ordered field, reduced Abelian $p$-group, Ehrenfeucht theory. 
@article{AL_2006_45_5_a2,
     author = {W. Calvert and V. S. Harizanova and J. F. Knight and S. Miller},
     title = {Index sets of computable structures},
     journal = {Algebra i logika},
     pages = {538--574},
     publisher = {mathdoc},
     volume = {45},
     number = {5},
     year = {2006},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/AL_2006_45_5_a2/}
}
TY  - JOUR
AU  - W. Calvert
AU  - V. S. Harizanova
AU  - J. F. Knight
AU  - S. Miller
TI  - Index sets of computable structures
JO  - Algebra i logika
PY  - 2006
SP  - 538
EP  - 574
VL  - 45
IS  - 5
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/AL_2006_45_5_a2/
LA  - ru
ID  - AL_2006_45_5_a2
ER  - 
%0 Journal Article
%A W. Calvert
%A V. S. Harizanova
%A J. F. Knight
%A S. Miller
%T Index sets of computable structures
%J Algebra i logika
%D 2006
%P 538-574
%V 45
%N 5
%I mathdoc
%U http://geodesic.mathdoc.fr/item/AL_2006_45_5_a2/
%G ru
%F AL_2006_45_5_a2
W. Calvert; V. S. Harizanova; J. F. Knight; S. Miller. Index sets of computable structures. Algebra i logika, Tome 45 (2006) no. 5, pp. 538-574. http://geodesic.mathdoc.fr/item/AL_2006_45_5_a2/

[1] S. Lempp, T. Slaman, “The complexity of the index sets of \aleph_0-categorical theories and of Ehrenfeucht theories, to appear”, Adv. Logic (Proc. North Texas Logic Conf., October 8–10, 2004), Contemp. Math., Am. Math. Soc. (to appear) | MR

[2] B. F. Csima, A. Montalbán, R. A. Shore, “Boolean algebras, Tarski invariants, and index sets”, Notre Dame J. Formal Logic (to appear) | MR

[3] W. Calvert, “The isomorphism problem for computable Abelian $p$-groups of bounded length”, J. Symb. Log., 70:1 (2005), 331–345 | DOI | MR | Zbl

[4] W. Calvert, “The isomorphism problem for classes of computable fields”, Arch. Math. Log., 75:3 (2004), 327–336 | DOI | MR

[5] U. Kalvert, D. Kammins, Dzh. F. Nait, S. Miller, “Sravnenie klassov konechnykh struktur”, Algebra i logika, 43:6 (2004), 666–701 | MR

[6] S. S. Goncharov, Dzh. Nait, “Vychislimye strukturnye i antistrukturnye teoremy”, Algebra i logika, 41:6 (2002), 639–681 | MR | Zbl

[7] W. White, “On the complexity of categoricity in computable structures”, Math. Logic Quarterly, 49:6 (2003), 603–614 | DOI | MR | Zbl

[8] W. White, Characterizations for computable structures, PhD thesis LCornell Univ., 2000

[9] V. P. Dobritsa, “Slozhnost indeksnogo mnozhestva konstruktivnoi modeli”, Algebra i logika, 22:4 (1983), 269–276 | MR

[10] H. J. Keisler, Model theory for in.nitary logic, North-Holland, Amsterdam, 1971 | MR | Zbl

[11] D. E. Miller, “The invariant $\Pi^0_{\alpha}$ separation principle”, Trans. Am. Math. Soc., 242 (1978), 185–204 | DOI | MR | Zbl

[12] . A. W. Miller, “On the Borel classi.cation of the isomorphism class of a countable model”, Notre Dame J. Formal Logic, 24 (1983), 22–34 | DOI | MR | Zbl

[13] M. Nadel, “Scott sentences and admissible sets”, Ann. Math. Logic, 7 (1974), 267–294 | DOI | MR | Zbl

[14] W. Calvert, D. Cenzer, V. Harizanov, A. Morozov, $\Delta_2^0$ categoricity of Abelian $p$-groups

[15] R. I. Soare, Recursively enumerable sets and degrees, Springer-Verlag, Berlin, 1987 | MR

[16] I. Kaplansky, Infinite Abelian Groups, Univ. Michigan Publ. Math., 2, Univ. Michigan Press, Ann Arbor, 1954 | MR | Zbl

[17] E. Barker, “Back and forth relations for reduced Abelian $p$-groups”, Ann. Pure Appl. Logic, 75:3 (1995), 223–249 | DOI | MR | Zbl

[18] N. G. Khisamiev, “Constructive Abelian p-groups”, Sib. Adv. Math., 2:2 (1992), 68–113 | MR

[19] N. G. Khisamiev, “Constructive abelian groups, in: Handbook of recursive mathematics”, Yu. L.Ershov, S. S.Goncharov, A. Nerode, J.B.Remmel (ed.), v.2, Elsevier, Amsterdam, 1998, 1177–1230 | MR

[20] W. Hodges, A shorter model theory, Cambridge Univ. Press, Cambridge, 1997 | MR

[21] R. L. Vaught, “Denumerable models of complete theories”, Infinitistic Methods, Proc. Symp. Found. Math. (Warsaw 1959), Pergamon Press, 1961, 303–231 | MR