Geodesic
Comparing classes of finite sums
Algebra i logika, Tome 54 (2015) no. 6, pp. 748-768
Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

The notion of Turing computable embedding is a computable analog of Borel embedding. It provides a way to compare classes of countable structures, effectively reducing the classification problem for one class to that for the other. Most of the known results on nonexistence of Turing computable embeddings reflect differences in the complexity of the sentences needed to distinguish among nonisomorphic members of the two classes. Here we consider structures obtained as sums. It is shown that the $n$-fold sums of members of certain classes lie strictly below the $(n+1)$-fold sums. The differences reflect model-theoretic considerations related to Morley degree, not differences in the complexity of the sentences that describe the structures. We consider three different kinds of sum structures: cardinal sums, in which the components are named by predicates; equivalence sums, in which the components are equivalence classes under an equivalence relation; and direct sums of certain groups.
Keywords: Turing computable embedding, classes of finite sums, Morley degree, complexity of sentences. 
@article{AL_2015_54_6_a4,
     author = {U. Andrews and D. I. Dushenin and C. Hill and J. F. Knight and A. G. Melnikov},
     title = {Comparing classes of finite sums},
     journal = {Algebra i logika},
     pages = {748--768},
     year = {2015},
     volume = {54},
     number = {6},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/AL_2015_54_6_a4/}
}
TY  - JOUR
AU  - U. Andrews
AU  - D. I. Dushenin
AU  - C. Hill
AU  - J. F. Knight
AU  - A. G. Melnikov
TI  - Comparing classes of finite sums
JO  - Algebra i logika
PY  - 2015
SP  - 748
EP  - 768
VL  - 54
IS  - 6
UR  - http://geodesic.mathdoc.fr/item/AL_2015_54_6_a4/
LA  - ru
ID  - AL_2015_54_6_a4
ER  - 
%0 Journal Article
%A U. Andrews
%A D. I. Dushenin
%A C. Hill
%A J. F. Knight
%A A. G. Melnikov
%T Comparing classes of finite sums
%J Algebra i logika
%D 2015
%P 748-768
%V 54
%N 6
%U http://geodesic.mathdoc.fr/item/AL_2015_54_6_a4/
%G ru
%F AL_2015_54_6_a4
U. Andrews; D. I. Dushenin; C. Hill; J. F. Knight; A. G. Melnikov. Comparing classes of finite sums. Algebra i logika, Tome 54 (2015) no. 6, pp. 748-768. http://geodesic.mathdoc.fr/item/AL_2015_54_6_a4/

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

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

[3] E. B. Fokina, J. F. Knight, A. Melnikov, S. M. Quinn, C. M. Safranski, “Classes of Ulm type and coding rank-homogeneous trees in other structures”, J. Symb. Log., 76:3 (2011), 846–869 | DOI | MR | Zbl

[4] J. F. Knight, S. Miller, M. Vanden Boom, “Turing computable embeddings”, J. Symb. Log., 72:3 (2007), 901–918 | DOI | Zbl

[5] C. Maher, On embeddings of computable structures, classes of structures, and computable isomorphism, PhD Thesis, Univ. Notre Dame, 2009

[6] E. B. Fokina, S.-D. Friedman, “On $\Sigma^1_1$ equivalence relations over the natural numbers”, Math. Log. Q., 58:1/2 (2012), 113–124 | DOI | MR | Zbl

[7] E. B. Fokina, S.-D. Friedman, V. Harizanov, J. F. Knight, C. McCoy, A. Montalbán, “Isomorphism relations on computable structures”, J. Symb. Log., 77:1 (2012), 122–132 | DOI | MR | Zbl

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

[9] V. Kalvert, V. S. Kharizanova, D. F. Nait, S. Miller, “Indeksnye mnozhestva vychislimykh modelei”, Algebra i logika, 45:5 (2006), 538–574 | MR | Zbl

[10] H. Becker, “Isomorphism of computable structures and Vaught's Conjecture”, J. Symb. Log., 78:4 (2013), 1328–1344 | DOI | MR | Zbl

[11] A. Montalbán, A computability theoretic equivalent to Vaught's Conjecture, Preprint

[12] I. Kaplansky, Infinite abelian groups, Univ. Michigan Publ. Math., 2, Univ. Michigan Press, Ann Arbor, 1954 | MR | Zbl