Isomorphism of homogeneous structures
Using the notion of Borel reducibility, it is possible to study how complex the isomorphism relation is amongst countable structures in some first-order language. Languages or theories which have a maximally complicated isomorphism relation amongst their models are called Borel-complete. The typical procedure for proving that a given language or theory is Borel-complete is to code some complicated structure into the models of the given language or theory and this procedure often involves using distinguished points or, more generally, definable sets. The aim of the current paper is to avoid coding such structures by studying the isomorphism relation on countable structures whose automorphism groups are transitive (implying that they have no nontrivial definable sets). The main result in the paper is that the isomorphism relation amongst countable connected vertex-transitive graphs is Borel-complete. Using this main result, the isomorphism relations on other classes of graphs are classified. Also, using the main result, the author classifies the isomorphism relation amongst countable structures with transitive automorphism groups in an arbitrary countable first-order language. Indeed, if \(\mathcal{L}\) is a countable first-order language and \(\mathcal{K}\) is the class of countable \(\mathcal{L}\)-structures with transitive automorphism groups, then the isomorphism relation on \(\mathcal{K}\) is Borel-complete if and only if \(\mathcal{L}\) contains no constant symbols and contains either an \(n\)-ary relation or function symbol for some \(n\geq 2\) or contains at least two unary function symbols. Otherwise, the isomorphism relation on \(\mathcal{K}\) is concretely classifiable, that is, can be Borel-reduced to the equality relation on some Polish space. The results on graphs mentioned above can also be used to study the complexity of the isometry relation on certain metric spaces. In the final sections of the paper, it is shown that the isometry relation on homogeneous discrete metric spaces is Borel-bireducible with graph isomorphism and the isometry relation on ultrahomogeneous locally compact metric spaces is bireducible with the equality relation on countable sets of real numbers.
- Homeomorphism versus isomorphism for varieties
- Can we classify complete metric spaces up to isometry?
- Isomorphic pairs of homogeneous functions and their morphisms
- The isomorphism problem for FST injection structures
- On the classification of vertex-transitive structures
- Structural homeomorphism between structural descriptors and relation between corresponding structures: a mathematical picture
- Non-isomorphism invariant Borel quantifiers
- The relation of recursive isomorphism for countable structures
- Potential isomorphism of elementary substructures of a strictly stable homogeneous model
- Isometry of Polish metric spaces
- scientific article; zbMATH DE number 2015640 (Why is no real title available?)
- The complexity of topological group isomorphism
- The completeness of isomorphism
- On Borel complexity of the isomorphism problems for graph related classes of Lie algebras and finite p-groups
- Structure of iso-scalar sets
- Uncountable structures are not classifiable up to bi-embeddability
- Un isomorphisme de Suslin
This page was built for publication: Isomorphism of homogeneous structures
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1038601)
