Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)



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 Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: Given an $ \mathcal{L}_{\omega_1\omega}$-elementary class $ \mathcal{C}$, that is, the collection of the countable models of some $ \mathcal{L}_{\omega_1 \omega}$-sentence, denote by $ \cong_{\mathcal{C}}$ and $ \equiv_{\mathcal{C}}$ the analytic equivalence relations of, respectively, isomorphisms and bi-embeddability on $ \mathcal{C}$. 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 $ (E,F)$ can be realized (up to Borel bireducibility) as pairs of the form $ (\cong_{\mathcal{C}}, \equiv_{\mathcal{C}})$, $ \mathcal{C}$ some $ \mathcal{L}_{\omega_1\omega}$-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 $ E$ and $ F$, it is always possible to find such an $ \mathcal{L}_{\omega_1\omega}$-elementary class $ \mathcal{C}$.

References [Enhancements On Off] (What's this?)

  • [BK96] Howard Becker and Alexander S. Kechris.
    The descriptive set theory of Polish group actions, volume 232 of London Mathematical Society Lecture Note Series.
    Cambridge University Press, Cambridge, 1996. MR 1425877 (98d:54068)
  • [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(3):894-914, 1989. MR 1011177 (91f:03062)
  • [Gao09] Su Gao.
    Invariant Descriptive Set Theory, volume 293 of Monographs and Textbooks in Pure and Applied Mathematics.
    CRC Press, Taylor & Francis Group, 2009. MR 2455198
  • [Gao01] Su Gao.
    Some dichotomy theorems for isomorphism relations of countable models.
    J. Symbolic Logic, 66(2):902-922, 2001. MR 1833486 (2002g:03074)
  • [Hjo00] Greg Hjorth.
    Classification and Orbit Equivalence Relations, volume 75 of Mathematical Surveys and Monographs.
    American Mathematical Society, Providence, RI, 2000. MR 1725642 (2000k:03097)
  • [Hod93] W. A. Hodges.
    Model Theory, volume 42 of Encyclopedia of Mathematics and Its Applications.
    Cambridge University Press, 1993. MR 1221741 (94e:03002)
  • [Kec95] Alexander S. Kechris.
    Classical Descriptive Set Theory, volume 156 of Graduate Texts in Mathematics.
    Springer-Verlag, New York, 1995. MR 1321597 (96e:03057)
  • [LR05] Alain Louveau and Christian Rosendal.
    Complete analytic equivalence relations.
    Trans. Amer. Math. Soc., 357(12):4839-4866 (electronic), 2005. MR 2165390 (2006d:03081)
  • [Mos80] Yiannis N. Moschovakis,
    Descriptive Set Theory.
    North-Holland, Amsterdam-New York-Oxford, 1980. MR 561709 (82e:03002)

Similar Articles

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

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

American Mathematical Society