Geodesic
Comparing Classes of Finite Structures
Algebra i logika, Tome 43 (2004) no. 6, pp. 666-701.

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

We compare classes of structures using the notion of a computable embedding, which is a partial order on the classes of structures. Our attention is mainly, but not exclusively, focused on classes of finite structures. Also, a number of problems are formulated.
Keywords: computable embedding, finite prime field, finite linear order, finite-dimensional vector space over rationals, linear order. 
@article{AL_2004_43_6_a2,
     author = {W. Calvert and D. Cummins and J. F. Knight and S. Miller},
     title = {Comparing {Classes} of {Finite} {Structures}},
     journal = {Algebra i logika},
     pages = {666--701},
     publisher = {mathdoc},
     volume = {43},
     number = {6},
     year = {2004},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/AL_2004_43_6_a2/}
}
TY  - JOUR
AU  - W. Calvert
AU  - D. Cummins
AU  - J. F. Knight
AU  - S. Miller
TI  - Comparing Classes of Finite Structures
JO  - Algebra i logika
PY  - 2004
SP  - 666
EP  - 701
VL  - 43
IS  - 6
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/AL_2004_43_6_a2/
LA  - ru
ID  - AL_2004_43_6_a2
ER  - 
%0 Journal Article
%A W. Calvert
%A D. Cummins
%A J. F. Knight
%A S. Miller
%T Comparing Classes of Finite Structures
%J Algebra i logika
%D 2004
%P 666-701
%V 43
%N 6
%I mathdoc
%U http://geodesic.mathdoc.fr/item/AL_2004_43_6_a2/
%G ru
%F AL_2004_43_6_a2
W. Calvert; D. Cummins; J. F. Knight; S. Miller. Comparing Classes of Finite Structures. Algebra i logika, Tome 43 (2004) no. 6, pp. 666-701. http://geodesic.mathdoc.fr/item/AL_2004_43_6_a2/

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

[2] H. Becker, A. S. Kechris, The descriptive set theory of Polish group actions, Lond. Math. Soc. Lect. Note Ser., 232, Cambridge Univ. Press, Cambridge, 1996 | MR | Zbl

[3] G. Hjorth, Classification and orbit equivalence relations, Math. Surv. Monogr., 75, Am. Math. Soc., Providence, RI, 2000 | MR | Zbl

[4] G. Hjorth, A. S. Kechris, “Recent developments in the theory of Borel reducibility”, Fundam. Math., 170:1–2 (2001), 21–52 | DOI | MR | Zbl

[5] G. Hjorth, A. S. Kechris, “Analytic equivalence relations and Ulm-type classifications”, J. Symb. Log., 60:4 (1995), 1273–1300 | DOI | MR | Zbl

[6] H. Rogers, Theory of recursive functions and effective computability, MIT Press, 1987 | MR

[7] M. O. Rabin, D. Scott, The undecidability of some simple theories

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

[9] D. Hirschfeldt, B. Khoussainov, R. 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

[10] W. Calvert, “The isomorphism problem for classes of computable fields”, Arch. Math. Logic. (to appear) | MR

[11] W. Calvert, The isomorphism problem for computable Abelian $p$-groups of bounded length

[12] Yu. T. Medvedev, “Stepeni trudnosti massovykh problem”, Dokl. AN SSSR, 104:4 (1955), 501–504 | Zbl

[13] A. Sorbi, “Some remarks on the algebraic structure of the Medvedev lattice”, J. Symb. Log., 55:2 (1990), 831–853 | DOI | MR | Zbl

[14] S. Simpson, S. Binns, Embeddings into the Medvedev and Muchnik lattices of $\Pi_1^0$ classes

[15] E. Z. Dyment, “O nekotorykh svoistvakh reshetki Medvedeva”, Matem. sb., 101(143):3(11) (1976), 360–379 | MR | Zbl

[16] J. F. Knight, Algebraic structure of classes under computable embedding

[17] C. J. Ash, A. Nerode, “Intrinsically recursive relations”, Aspects of effective algebra, Proc. conf. (1979, Monash Univ., Clayton), ed. J. N. Crossley, Upside Down A Book Co., Steel's Creek, Aust., 1981, 26–41 | MR

[18] V. S. Harizanov, “Some effects of Ash-Nerode and other decidability conditions on degree spectra”, Ann. Pure Appl. Logic, 55:1 (1991), 51–65 | DOI | MR | Zbl

[19] C. J. Ash, J. F. Knight, Computable structures and the hyperarithmetical hierarchy, Stud. Logic Found. Math., 144, Elsevier Science, Amsterdam, 2000 | MR | Zbl

[20] R. I. Soare, Recursively enumerable sets and degrees, Perspect. Math. Log., Omega Series, Springer-Verlag, Berlin a. o., 1987 | MR

[21] D. Cummins, Senior thesis, University of Notre Dame, in preparation