Isomorphism of homogeneous structures (Q1038601)

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.