Isomorphism of homogeneous structures
type: Item
instance of: scholarly article
title: Isomorphism of homogeneous structures
zbMATH Open document ID: 1188.03031
DOI: 10.1215/00294527-2008-024
author: John D. Clemens
published in: Notre Dame Journal of Formal Logic
publication date: 2009-11-18T00:00:00Z
review text: 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 homogen…
reviewed by: Isaac Goldbring
Mathematics Subject Classification ID: 03E15
Mathematics Subject Classification ID: 03C15
Mathematics Subject Classification ID: 03C50
zbMATH DE Number: 5635372
zbMATH Keywords: countable structures
zbMATH Keywords: homogeneous
zbMATH Keywords: structures
zbMATH Keywords: isomorphism
zbMATH Keywords: Borel completeness
zbMATH Keywords: Borel reducibility
zbMATH Keywords: isometry
zbMATH Keywords: metric spaces
MaRDI profile type: Publication
full work available at URL: https://doi.org/10.1215/00294527-2008-024
OpenAlex ID: W2029077212
description: scientific article; zbMATH DE number 5635372