Open Access
2013 Degrees of Categoricity and the Hyperarithmetic Hierarchy
Barbara F. Csima, Johanna N. Y. Franklin, Richard A. Shore
Notre Dame J. Formal Logic 54(2): 215-231 (2013). DOI: 10.1215/00294527-1960479

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 α, 0(α) is the degree of categoricity of some computable structure A. We show additionally that for α a computable successor ordinal, every degree 2-c.e. in and above 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 Π11-complete.

Citation

Download Citation

Barbara F. Csima. Johanna N. Y. Franklin. Richard A. Shore. "Degrees of Categoricity and the Hyperarithmetic Hierarchy." Notre Dame J. Formal Logic 54 (2) 215 - 231, 2013. https://doi.org/10.1215/00294527-1960479

Information

Published: 2013
First available in Project Euclid: 21 February 2013

zbMATH: 1311.03070
MathSciNet: MR3028796
Digital Object Identifier: 10.1215/00294527-1960479

Subjects:
Primary: 03D45

Keywords: computability theory , computable structure theory , isomorphisms , Turing degrees

Rights: Copyright © 2013 University of Notre Dame

Vol.54 • No. 2 • 2013
Back to Top