Affiliations: [a] Pure Mathematics, University of Waterloo, Waterloo, ON, Canada. [email protected] | [b] Pure Mathematics, University or Waterloo, Waterloo, ON, Canada. [email protected] | [c] Department first, Victoria University of Wellington, Wellington, New Zealand. [email protected] | [d] Pure Mathematics, University of Waterloo, Waterloo, ON, Canada. [email protected]
Abstract: A computable structure A has degree of categoricity d if d is exactly the degree of difficulty of computing isomorphisms between isomorphic computable copies of A. Fokina, Kalimullin, and Miller showed that every degree d.c.e. in and above 0(n), for any n<ω, and also the degree 0(ω), are degrees of categoricity. Later, Csima, Franklin, and Shore showed that every degree 0(α) for any computable ordinal α, and every degree d.c.e. in and above 0(α) for any successor ordinal α, is a degree of categoricity. We show that every degree c.e. in and above 0(α), for α a limit ordinal, is a degree of categoricity. We also show that every degree c.e. in and above 0(ω) is the degree of categoricity of a prime model, making progress towards a question of Bazhenov and Marchuk.
Keywords: Degrees of categoricity, limit ordinals
DOI: 10.3233/COM-190254
Journal: Computability, vol. 9, no. 2, pp. 127-137, 2020
