Degrees of categoricity above limit ordinals
Barbara F. Csima, Michael Deveau, Matthew Harrison‐Trainor, Mohammad Assem Mahmoud · Computability · 2019
A computable structure [Formula: see text] has degree of categoricity d if d is exactly the degree of difficulty of computing isomorphisms between isomorphic computable copies of [Formula: see text]. Fokina, Kalimullin, and Miller showed that every degree d.c.e. in and above [Formula: see text], for any [Formula: see text], and also the degree [Formula: see text], are degrees of categoricity. Later, Csima, Franklin, and Shore showed that every degree [Formula: see text] for any computable ordinal α, and every degree d.c.e. in and above [Formula: see text] for any successor ordinal α, is a degree of categoricity. We show that every degree c.e. in and above [Formula: see text], for α a limit ordinal, is a degree of categoricity. We also show that every degree c.e. in and above [Formula: see text] is the degree of categoricity of a prime model, making progress towards a question of Bazhenov and Marchuk.