Analytic equivalence relations and bi-embeddability

Journal of Symbolic Logic 76 (1):243-266 (2011)
  Copy   BIBTEX

Abstract

Louveau and Rosendal [5] have shown that the relation of bi-embeddability for countable graphs as well as for many other natural classes of countable structures is complete under Borel reducibility for analytic equivalence relations. This is in strong contrast to the case of the isomorphism relation, which as an equivalence relation on graphs is far from complete.In this article we strengthen the results of [5] by showing that not only does bi-embeddability give rise to analytic equivalence relations which are complete under Borel reducibility, but in fact any analytic equivalence relation is Borel equivalent to such a relation. This result and the techniques introduced answer questions raised in [5] about the comparison between isomorphism and bi-embeddability. Finally, as in [5] our results apply not only to classes of countable structures defined by sentences of ℒω1ω, but also to discrete metric or ultrametric Polish spaces, compact metrizable topological spaces and separable Banach spaces, with various notions of embeddability appropriate for these classes, as well as to actions of Polish monoids.

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 92,323

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

Analytic equivalence relations and bi-embeddability.Sy-David Friedman & Luca Motto Ros - 2011 - Journal of Symbolic Logic 76 (1):243 - 266.
Borel reducibility and finitely Hölder (α) embeddability.Longyun Ding - 2011 - Annals of Pure and Applied Logic 162 (12):970-980.
Isomorphism of Homogeneous Structures.John D. Clemens - 2009 - Notre Dame Journal of Formal Logic 50 (1):1-22.
Actions of non-compact and non-locally compact polish groups.Sławomir Solecki - 2000 - Journal of Symbolic Logic 65 (4):1881-1894.
Infinite Time Decidable Equivalence Relation Theory.Samuel Coskey & Joel David Hamkins - 2011 - Notre Dame Journal of Formal Logic 52 (2):203-228.
Actions of Non-Compact and Non-Locally Compact Polish Groups.Slawomir Solecki - 2000 - Journal of Symbolic Logic 65 (4):1881-1894.
Superrigidity and countable Borel equivalence relations.Simon Thomas - 2003 - Annals of Pure and Applied Logic 120 (1-3):237-262.

Analytics

Added to PP
2017-02-21

Downloads
18 (#837,247)

6 months
9 (#317,373)

Historical graph of downloads
How can I increase my downloads?

Author's Profile

References found in this work

No references found.

Add more references