Annals of Pure and Applied Logic 141 (1):61-78 (2006)
Authors |
|
Abstract |
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 |
Options |
![]() ![]() ![]() ![]() |
Download options
References found in this work BETA
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.
Recursive Isomorphism Types of Recursive Boolean Algebras.J. B. Remmel - 1981 - Journal of Symbolic Logic 46 (3):572-594.
Enumerations in Computable Structure Theory.Sergey Goncharov, Valentina Harizanov, Julia Knight, Charles McCoy, Russell Miller & Reed Solomon - 2005 - Annals of Pure and Applied Logic 136 (3):219-246.
View all 22 references / Add more references
Citations of this work BETA
Isomorphism Relations on Computable Structures.Ekaterina B. Fokina, Sy-David Friedman, Valentina Harizanov, Julia F. Knight, Charles Mccoy & Antonio Montalbán - 2012 - Journal of Symbolic Logic 77 (1):122-132.
Degrees of Bi-Embeddable Categoricity of Equivalence Structures.Nikolay Bazhenov, Ekaterina Fokina, Dino Rossegger & Luca San Mauro - 2019 - Archive for Mathematical Logic 58 (5-6):543-563.
On Σ1 1 Equivalence Relations Over the Natural Numbers.Ekaterina B. Fokina & Sy-David Friedman - 2012 - Mathematical Logic Quarterly 58 (1-2):113-124.
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.
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.
View all 19 citations / Add more citations
Similar books and articles
Equivalence Structures and Isomorphisms in the Difference Hierarchy.Douglas Cenzer, Geoffrey LaForte & Jeffrey Remmel - 2009 - Journal of Symbolic Logic 74 (2):535-556.
Effective Categoricity of Abelian P -Groups.Wesley Calvert, Douglas Cenzer, Valentina S. Harizanov & Andrei Morozov - 2009 - Annals of Pure and Applied Logic 159 (1-2):187-197.
A Real Number Structure That is Effectively Categorical.Peter Hertling - 1999 - Mathematical Logic Quarterly 45 (2):147-182.
Degrees of Categoricity of Computable Structures.Ekaterina B. Fokina, Iskander Kalimullin & Russell Miller - 2010 - Archive for Mathematical Logic 49 (1):51-67.
Computable and Continuous Partial Homomorphisms on Metric Partial Algebras.Viggo Stoltenberg-Hansen & John V. Tucker - 2003 - Bulletin of Symbolic Logic 9 (3):299-334.
Degrees of Categoricity and the Hyperarithmetic Hierarchy.Barbara F. Csima, Johanna N. Y. Franklin & Richard A. Shore - 2013 - Notre Dame Journal of Formal Logic 54 (2):215-231.
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.
Isomorphism Relations on Computable Structures.Ekaterina B. Fokina, Sy-David Friedman, Valentina Harizanov, Julia F. Knight, Charles Mccoy & Antonio Montalbán - 2012 - Journal of Symbolic Logic 77 (1):122-132.
An Algebraic Result About Soft Model Theoretical Equivalence Relations with an Application to H. Friedman's Fourth Problem.Daniele Mundici - 1981 - Journal of Symbolic Logic 46 (3):523-530.
Analytics
Added to PP index
2013-12-31
Total views
24 ( #475,795 of 2,517,928 )
Recent downloads (6 months)
1 ( #409,045 of 2,517,928 )
2013-12-31
Total views
24 ( #475,795 of 2,517,928 )
Recent downloads (6 months)
1 ( #409,045 of 2,517,928 )
How can I increase my downloads?
Downloads