Isomorphism of Homogeneous Structures

Notre Dame Journal of Formal Logic 50 (1):1-22 (2009)
  Copy   BIBTEX

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

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 90,616

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

Homogeneous and universal dedekind algebras.George Weaver - 2000 - Studia Logica 64 (2):173-192.
A theorem on the isomorphism property.Renling Jin - 1992 - Journal of Symbolic Logic 57 (3):1011-1017.
Interpreting groups in ω-categorical structures.Dugald Macpherson - 1991 - Journal of Symbolic Logic 56 (4):1317-1324.
ℵ0-categorical tree-decomposable structures.A. H. Lachlan - 1992 - Journal of Symbolic Logic 57 (2):501 - 514.
The pragmatics of empirical adequacy.Bryson Brown - 2004 - Australasian Journal of Philosophy 82 (2):242 – 264.
Isomorphism of structures in s-toposes.J. L. Bell - 1981 - Journal of Symbolic Logic 46 (3):449-459.
Automorphisms of Homogeneous Structures.A. Ivanov - 2005 - Notre Dame Journal of Formal Logic 46 (4):419-424.
Countable structures of given age.H. D. Macpherson, M. Pouzet & R. E. Woodrow - 1992 - Journal of Symbolic Logic 57 (3):992-1010.
Reconstruction of Homogeneous Relational Structures.Silvia Barbina & Dugald Macpherson - 2007 - Journal of Symbolic Logic 72 (3):792 - 802.

Analytics

Added to PP
2010-09-13

Downloads
35 (#396,067)

6 months
4 (#320,252)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

Isometry of Polish metric spaces.John D. Clemens - 2012 - Annals of Pure and Applied Logic 163 (9):1196-1209.

Add more citations

References found in this work

Stability of nilpotent groups of class 2 and prime exponent.Alan H. Mekler - 1981 - Journal of Symbolic Logic 46 (4):781-788.

Add more references