Notre Dame Journal of Formal Logic 54 (2):215-231 (2013)

We study arithmetic and hyperarithmetic degrees of categoricity. We extend a result of E. Fokina, I. Kalimullin, and R. Miller to show that for every computable ordinal $\alpha$, $\mathbf{0}^{}$ is the degree of categoricity of some computable structure $\mathcal{A}$. We show additionally that for $\alpha$ a computable successor ordinal, every degree $2$-c.e. in and above $\mathbf{0}^{}$ is a degree of categoricity. We further prove that every degree of categoricity is hyperarithmetic and show that the index set of structures with degrees of categoricity is $\Pi_{1}^{1}$-complete
Keywords computability theory   computable structure theory   Turing degrees   isomorphisms
Categories (categorize this paper)
DOI 10.1215/00294527-1960479
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

PhilArchive copy

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

References found in this work BETA

Non Σn Axiomatizable Almost Strongly Minimal Theories.David Marker - 1989 - Journal of Symbolic Logic 54 (3):921 - 927.

Add more references

Citations of this work BETA

Categoricity Spectra for Rigid Structures.Ekaterina Fokina, Andrey Frolov & Iskander Kalimullin - 2016 - Notre Dame Journal of Formal Logic 57 (1):45-57.

View all 13 citations / Add more citations

Similar books and articles

Degrees of Unsolvability of Continuous Functions.Joseph S. Miller - 2004 - Journal of Symbolic Logic 69 (2):555 - 584.
On the Complexity of Categoricity in Computable Structures.Walker M. White - 2003 - Mathematical Logic Quarterly 49 (6):603.
Effective Algebraicity.Rebecca M. Steiner - 2013 - Archive for Mathematical Logic 52 (1-2):91-112.
The Jump Operation for Structure Degrees.V. Baleva - 2006 - Archive for Mathematical Logic 45 (3):249-265.
On Turing Degrees of Points in Computable Topology.Iraj Kalantari & Larry Welch - 2008 - Mathematical Logic Quarterly 54 (5):470-482.
Maximal Contiguous Degrees.Peter Cholak, Rod Downey & Stephen Walk - 2002 - Journal of Symbolic Logic 67 (1):409-437.
On the Symmetric Enumeration Degrees.Charles M. Harris - 2007 - Notre Dame Journal of Formal Logic 48 (2):175-204.


Added to PP index

Total views
315 ( #30,602 of 2,462,140 )

Recent downloads (6 months)
1 ( #449,335 of 2,462,140 )

How can I increase my downloads?


My notes