Effective categoricity of equivalence structures

Annals of Pure and Applied Logic 141 (1):61-78 (2006)
  Copy   BIBTEX


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



    Upload a copy of this work     Papers currently archived: 86,336

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

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.


Added to PP

26 (#501,136)

6 months
2 (#520,889)

Historical graph of downloads
How can I increase my downloads?

Author's Profile

Valentina Harizanov
George Washington University

References found in this work

Computable structures and the hyperarithmetical hierarchy.C. J. Ash - 2000 - New York: Elsevier. Edited by J. Knight.
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.
Effective model theory vs. recursive model theory.John Chisholm - 1990 - Journal of Symbolic Logic 55 (3):1168-1191.
Recursive isomorphism types of recursive Boolean algebras.J. B. Remmel - 1981 - Journal of Symbolic Logic 46 (3):572-594.

View all 22 references / Add more references