Degrees of Categoricity and the Hyperarithmetic Hierarchy

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.