Isomorphism of Homogeneous Structures
Clemens, John D.
Notre Dame J. Formal Logic, Tome 50 (2009) no. 1, p. 1-22 / Harvested from Project Euclid
Text on Project Euclid
PDF
Alt PDF
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.
Publié le : 2009-01-15
Classification:  countable structures,  homogeneous,  isomorphism,  03E15,  03C15,  03C50 
@article{1232375159,
     author = {Clemens, John D.},
     title = {Isomorphism of Homogeneous Structures},
     journal = {Notre Dame J. Formal Logic},
     volume = {50},
     number = {1},
     year = {2009},
     pages = { 1-22},
     language = {en},
     url = {http://dml.mathdoc.fr/item/1232375159}
}

Clemens, John D. Isomorphism of Homogeneous Structures. Notre Dame J. Formal Logic, Tome 50 (2009) no. 1, pp.  1-22. http://gdmltest.u-ga.fr/item/1232375159/