The degrees of categoricity above $\mathbf{0}"$

Barbara F. Csima, Dino Rossegger

Published 2022-09-09Version 1

We give a characterization of the degrees of categoricity of computable structures greater or equal to $\mathbf 0"$. They are precisely the treeable degrees - the least degrees of paths through computable trees - that compute $\mathbf 0"$. As a corollary, we obtain several new examples of degrees of categoricity. Among them we show that every degree $\mathbf d$ with $\mathbf 0^{(\alpha)}\leq \mathbf d\leq \mathbf 0^{(\alpha+1)}$ or $\alpha$ a computable ordinal greater than $2$ is the strong degree of categoricity of a rigid structure. Another corollary of our characterization partially answers a question of Fokina, Kalimullin, and Miller: Every degree of categoricity above $\mathbf 0"$ is strong. Using quite different techniques we show that every degree $\mathbf d$ with $\mathbf 0'\leq \mathbf d\leq \mathbf 0"$ is the strong degree of categoricity of a structure. Together with the above example this answers a question of Csima and Ng. To complete the picture we show that there is a degree $\mathbf d$ with $\mathbf 0'\leq \mathbf d\leq \mathbf 0"$ that is not the degree of categoricity of a rigid structure.