Equivalence structures and isomorphisms in the difference hierarchy

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

Abstract

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

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 94,385

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

Categoricity Spectra for Rigid Structures.Ekaterina Fokina, Andrey Frolov & Iskander Kalimullin - 2016 - Notre Dame Journal of Formal Logic 57 (1):45-57.
On the complexity of categoricity in computable structures.Walker M. White - 2003 - Mathematical Logic Quarterly 49 (6):603.

Analytics

Added to PP
2010-09-12

Downloads
32 (#495,642)

6 months
16 (#218,914)

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