Isomorphism of homogeneous structures

Research output: Contribution to journalArticlepeer-review

4 Scopus citations

Abstract

We consider the complexity of the isomorphism relation on countable first-order structures with transitive automorphism groups. We use the theory of Borel reducibility of equivalence relations to show that the isomorphism problem for vertex-transitive graphs is as complicated as the isomorphism problem for arbitrary graphs and determine for which first-order languages the isomorphism problem for transitive countable structures is as complicated as it is for arbitrary countable structures. We then use these results to characterize the complexity of the isometry relation for certain classes of homogeneous and ultrahomogeneous metric spaces.

Original languageEnglish
Pages (from-to)1-22
Number of pages22
JournalNotre Dame Journal of Formal Logic
Volume50
Issue number1
DOIs
StatePublished - 2009

Keywords

  • Countable structures
  • Homogeneous
  • Isomorphism

Fingerprint

Dive into the research topics of 'Isomorphism of homogeneous structures'. Together they form a unique fingerprint.

Cite this