Degrees of Categoricity and the Hyperarithmetic Hierarchy

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

Abstract

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

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 90,616

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

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 - 2005 - 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.

Analytics

Added to PP
2013-03-01

Downloads
323 (#57,070)

6 months
3 (#445,838)

Historical graph of downloads
How can I increase my downloads?