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

DOI10.1090/S0002-9939-2011-10896-7MaRDI QIDQ5388809zbMATH OpenOpenAlexFDO

Authors Luca Motto Ros

Publication date 20 April 2012

Published in Proceedings of the American Mathematical Society (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1112.0349

zbMATH Keywords

isomorphismBorel reducibilitybi-embeddabilityanalytic equivalence relation

Mathematics Subject Classification ID

Descriptive set theory (03E15) Other infinitary logic (03C75)

Abstract: Given an L_{omega_1 omega}-elementary class C, that is the collection of the countable models of some L_{omega_1 omega}-sentence, denote by cong_C and equiv_C the analytic equivalence relations of, respectively, isomorphism and bi-embeddability on C. Generalizing some questions of Louveau and Rosendal [LR05], in [FMR09] it was 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_C,equiv_C), C some 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 problem: under very mild conditions on E and F, it is always possible to find such an L_{omega_1 omega}-elementary class C.

Recommendations

• Analytic equivalence relations and bi-embeddability
• Complete analytic equivalence relations
• The completeness of isomorphism
• scientific article; zbMATH DE number 2204765
• Borel equivalence relations and classifications of countable models

Cites work

• scientific article; zbMATH DE number 53151 (Why is no real title available?)
• scientific article; zbMATH DE number 722611 (Why is no real title available?)
• scientific article; zbMATH DE number 976831 (Why is no real title available?)
• scientific article; zbMATH DE number 1388189 (Why is no real title available?)
• A Borel reductibility theory for classes of countable structures
• Analytic equivalence relations and bi-embeddability
• Complete analytic equivalence relations
• Descriptive set theory
• Invariant descriptive set theory
• Invariantly universal analytic quasi-orders
• Some dichotomy theorems for isomorphism relations of countable models

Cited in

(12)

• Condensational equivalence, equimorphism, elementary equivalence and similar similarities
• Analytic equivalence relations and bi-embeddability
• Souslin quasi-orders and bi-embeddability of uncountable structures
• (Looking for) the heart of abelian Polish groups
• The definable content of homological invariants. II: Čech cohomology and homotopy classification
• The definable content of homological invariants. I: \( \mathrm{Ext}\) and \(\lim^1\)
• On realizable biorders and the biorder dimension of a relation
• On isometry and isometric embeddability between ultrametric Polish spaces
• Weihrauch Complexity in Computable Analysis
• Coarse groups, and the isomorphism problem for oligomorphic groups
• Uncountable structures are not classifiable up to bi-embeddability
• Invariantly universal analytic quasi-orders

This page was built for publication: On the complexity of the relations of isomorphism and bi-embeddability

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5388809)