Degrees of Categoricity Above Limit Ordinals

Abstract

A computable structure $\mathcal{A}$ has degree of categoricity $\mathbf{d}$ if $\mathbf{d}$ is exactly the degree of difficulty of computing isomorphisms between isomorphic computable copies of $\mathcal{A}$. Fokina, Kalimullin, and Miller showed that every degree d.c.e. in and above $0^{(n)}$, for any $n<\omega$, and also the degree $0^{(\omega )}$, are degrees of categoricity. Later, Csima, Franklin, and Shore showed that every degree $0^{(\alpha )}$ for any computable ordinal $\alpha$, and every degree d.c.e. in and above $0^{(\alpha )}$ for any successor ordinal $\alpha$, is a degree of categoricity. We show that every degree c.e. in and above $0^{(\alpha )}$, for $\alpha$ a limit ordinal, is a degree of categoricity. We also show that every degree c.e. in and above $0^{(\omega )}$ is the degree of categoricity of a prime model, making progress towards a question of Bazhenov and Marchuk.

14 pages