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