Computable categoricity and the Ershov hierarchy

, &
Annals of Pure and Applied Logic 156 (1):86-95 (2008)
  Copy   BIBTEX

Abstract

In this paper, the notions of Fα-categorical and Gα-categorical structures are introduced by choosing the isomorphism such that the function itself or its graph sits on the α-th level of the Ershov hierarchy, respectively. Separations obtained by natural graphs which are the disjoint unions of countably many finite graphs. Furthermore, for size-bounded graphs, an easy criterion is given to say when it is computable-categorical and when it is only G2-categorical; in the latter case it is not Fα-categorical for any recursive ordinal α

Categories

Keywords

Reprint years

DOI

10.1016/j.apal.2008.06.010

Other Versions

No versions found

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 100,497

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

My notes

Similar books and articles

Effective categoricity of equivalence structures.Wesley Calvert, Douglas Cenzer, Valentina Harizanov & Andrei Morozov - 2006 - Annals of Pure and Applied Logic 141 (1):61-78.
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.
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.
Computable isomorphisms, degree spectra of relations, and Scott families.Bakhadyr Khoussainov & Richard A. Shore - 1998 - Annals of Pure and Applied Logic 93 (1-3):153-193.
Degrees of categoricity of trees and the isomorphism problem.Mohammad Assem Mahmoud - 2019 - Mathematical Logic Quarterly 65 (3):293-304.
Computable categoricity of trees of finite height.Steffen Lempp, Charles McCoy, Russell Miller & Reed Solomon - 2005 - Journal of Symbolic Logic 70 (1):151-215.
On the complexity of categoricity in computable structures.Walker M. White - 2003 - Mathematical Logic Quarterly 49 (6):603.
Feasible graphs with standard universe.Douglas Cenzer & Jeffrey B. Remmel - 1998 - Annals of Pure and Applied Logic 94 (1-3):21-35.
Torsion-free abelian groups with optimal Scott families.Alexander G. Melnikov - 2018 - Journal of Mathematical Logic 18 (1):1850002.
Relative categoricity in abelian groups II.Wilfrid Hodges & Anatoly Yakovlev - 2009 - Annals of Pure and Applied Logic 158 (3):203-231.

Analytics

Added to PP
2013-12-26

Downloads
33 (#674,122)

6 months
7 (#669,170)

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

Limiting recursion.E. Mark Gold - 1965 - Journal of Symbolic Logic 30 (1):28-48.
Δ20-categoricity in Boolean algebras and linear orderings.Charles F. D. McCoy - 2003 - Annals of Pure and Applied Logic 119 (1-3):85-120.
A proof of Beigel's cardinality conjecture.Martin Kummer - 1992 - Journal of Symbolic Logic 57 (2):677-681.

Add more references