Equivalence structures and isomorphisms in the difference hierarchy

Journal of Symbolic Logic 74 (2):535-556 (2009)
  Copy   BIBTEX


We examine the effective categoricity of equivalence structures via Ershov's difference hierarchy. We explore various kinds of categoricity available by distinguishing three different notions of isomorphism available in this hierarchy. We prove several results relating our notions of categoricity to computable equivalence relations: for example, we show that, for such relations, computable categoricity is equivalent to our notion of weak ω-c.e. categoricity, and that $\Delta _2^0 $ -categoricity is equivalent to our notion of graph-ω-c.e. categoricity



    Upload a copy of this work     Papers currently archived: 84,108

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

Maximal R.e. Equivalence relations.Jeffrey S. Carroll - 1990 - Journal of Symbolic Logic 55 (3):1048-1058.
Partial isomorphisms and intuitionistic logic.Bernd I. Dahn - 1981 - Studia Logica 40 (4):405 - 413.
A theory of hierarchical consequence and conditionals.Dov M. Gabbay & Karl Schlechta - 2010 - Journal of Logic, Language and Information 19 (1):3-32.
Interpolation, preservation, and pebble games.Jon Barwise & Johan van Benthem - 1999 - Journal of Symbolic Logic 64 (2):881-903.


Added to PP

14 (#770,000)

6 months
1 (#511,561)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

Σ 1 0 and Π 1 0 equivalence structures.Douglas Cenzer, Valentina Harizanov & Jeffrey B. Remmel - 2011 - Annals of Pure and Applied Logic 162 (7):490-503.

Add more citations

References found in this work

Add more references