Effective categoricity of equivalence structures

Annals of Pure and Applied Logic 141 (1):61-78 (2006)
Valentina Harizanov
George Washington University
We investigate effective categoricity of computable equivalence structures . We show that is computably categorical if and only if has only finitely many finite equivalence classes, or has only finitely many infinite classes, bounded character, and at most one finite k such that there are infinitely many classes of size k. We also prove that all computably categorical structures are relatively computably categorical, that is, have computably enumerable Scott families of existential formulas. Since all computable equivalence structures are relatively categorical, we further investigate when they are categorical. We also obtain results on the index sets of computable equivalence structures
Keywords No keywords specified (fix it)
Categories (categorize this paper)
DOI 10.1016/j.apal.2005.10.002
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

Our Archive

Upload a copy of this paper     Check publisher's policy     Papers currently archived: 38,035
Through your library

References found in this work BETA

Effective Content of Field Theory.G. Metakides & A. Nerode - 1979 - Annals of Mathematical Logic 17 (3):289-320.
Generic Copies of Countable Structures.Chris Ash, Julia Knight, Mark Manasse & Theodore Slaman - 1989 - Annals of Pure and Applied Logic 42 (3):195-205.
Computable Models of Theories with Few Models.Bakhadyr Khoussainov, Andre Nies & Richard A. Shore - 1997 - Notre Dame Journal of Formal Logic 38 (2):165-178.

View all 17 references / Add more references

Citations of this work BETA

On Δ 2 0 -Categoricity of Equivalence Relations.Rod Downey, Alexander G. Melnikov & Keng Meng Ng - 2015 - Annals of Pure and Applied Logic 166 (9):851-880.
Abelian P -Groups and the Halting Problem.Rodney Downey, Alexander G. Melnikov & Keng Meng Ng - 2016 - Annals of Pure and Applied Logic 167 (11):1123-1138.

View all 13 citations / Add more citations

Similar books and articles

And Equivalence Structures.Douglas Cenzer, Valentina Harizanov & Jeffrey B. Remmel - 2011 - Annals of Pure and Applied Logic 162 (7):490-503.
A Real Number Structure That is Effectively Categorical.Peter Hertling - 1999 - Mathematical Logic Quarterly 45 (2):147-182.
Effective Algebraicity.Rebecca M. Steiner - 2013 - Archive for Mathematical Logic 52 (1-2):91-112.
Thin Equivalence Relations and Effective Decompositions.Greg Hjorth - 1993 - Journal of Symbolic Logic 58 (4):1153-1164.
On the Complexity of Categoricity in Computable Structures.Walker M. White - 2003 - Mathematical Logic Quarterly 49 (6):603.
Space Complexity of Abelian Groups.Douglas Cenzer, Rodney G. Downey, Jeffrey B. Remmel & Zia Uddin - 2009 - Archive for Mathematical Logic 48 (1):115-140.
Largest E-Thin, E-Invariant Sets Below Δ1 3.Xuhua Li - 2004 - Archive for Mathematical Logic 43 (5):681-690.


Added to PP index

Total views
10 ( #560,163 of 2,312,747 )

Recent downloads (6 months)
6 ( #118,589 of 2,312,747 )

How can I increase my downloads?

Monthly downloads

My notes

Sign in to use this feature