On the complexity of the relations of isomorphism and bi-embeddability

Author:
Luca Motto Ros

Journal:
Proc. Amer. Math. Soc. **140** (2012), 309-323

MSC (2010):
Primary 03E15

Published electronically:
May 16, 2011

MathSciNet review:
2833542

Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: Given an -elementary class , that is, the collection of the countable models of some -sentence, denote by and the analytic equivalence relations of, respectively, isomorphisms and bi-embeddability on . Generalizing some questions of A. Louveau and C. Rosendal, in a paper by S. Friedman and L. Motto Ros they proposed the problem of determining which pairs of analytic equivalence relations can be realized (up to Borel bireducibility) as pairs of the form , some -elementary class (together with a partial answer for some specific cases). Here we will provide an almost complete solution to such a problem: under very mild conditions on and , it is always possible to find such an -elementary class .

**[BK96]**Howard Becker and Alexander S. Kechris,*The descriptive set theory of Polish group actions*, London Mathematical Society Lecture Note Series, vol. 232, Cambridge University Press, Cambridge, 1996. MR**1425877****[CMMR10]**Riccardo Camerlo, Alberto Marcone and Luca Motto Ros.

Invariantly universal analytic quasi-orders.

Submitted, 2010.**[FMR09]**Sy-David Friedman and Luca Motto Ros.

Analytic equivalence relations and bi-embeddability.

J. Symbolic Logic, 76(1):243-266, 2011.**[FS89]**Harvey Friedman and Lee Stanley,*A Borel reducibility theory for classes of countable structures*, J. Symbolic Logic**54**(1989), no. 3, 894–914. MR**1011177**, 10.2307/2274750**[Gao09]**Su Gao,*Invariant descriptive set theory*, Pure and Applied Mathematics (Boca Raton), vol. 293, CRC Press, Boca Raton, FL, 2009. MR**2455198****[Gao01]**Su Gao,*Some dichotomy theorems for isomorphism relations of countable models*, J. Symbolic Logic**66**(2001), no. 2, 902–922. MR**1833486**, 10.2307/2695052**[Hjo00]**Greg Hjorth,*Classification and orbit equivalence relations*, Mathematical Surveys and Monographs, vol. 75, American Mathematical Society, Providence, RI, 2000. MR**1725642****[Hod93]**Wilfrid Hodges,*Model theory*, Encyclopedia of Mathematics and its Applications, vol. 42, Cambridge University Press, Cambridge, 1993. MR**1221741****[Kec95]**Alexander S. Kechris,*Classical descriptive set theory*, Graduate Texts in Mathematics, vol. 156, Springer-Verlag, New York, 1995. MR**1321597****[LR05]**Alain Louveau and Christian Rosendal,*Complete analytic equivalence relations*, Trans. Amer. Math. Soc.**357**(2005), no. 12, 4839–4866 (electronic). MR**2165390**, 10.1090/S0002-9947-05-04005-5**[Mos80]**Yiannis N. Moschovakis,*Descriptive set theory*, Studies in Logic and the Foundations of Mathematics, vol. 100, North-Holland Publishing Co., Amsterdam-New York, 1980. MR**561709**

Retrieve articles in *Proceedings of the American Mathematical Society*
with MSC (2010):
03E15

Retrieve articles in all journals with MSC (2010): 03E15

Additional Information

**Luca Motto Ros**

Affiliation:
Mathematisches Institut–Abteilung für Mathematische Logik, Albert-Ludwigs-Universität Freiburg, Eckerstraße, 1, D-79104 Freiburg im Breisgau, Germany

Email:
luca.motto.ros@math.uni-freiburg.de

DOI:
http://dx.doi.org/10.1090/S0002-9939-2011-10896-7

Keywords:
Analytic equivalence relation,
isomorphism,
(bi-)embeddability,
Borel reducibility.

Received by editor(s):
April 15, 2010

Received by editor(s) in revised form:
November 10, 2010

Published electronically:
May 16, 2011

Additional Notes:
The author would like to thank the FWF (Austrian Research Fund) for generously supporting this research through project number P 19898-N18.

Communicated by:
Julia Knight

Article copyright:
© Copyright 2011
American Mathematical Society