Degrees of categoricity and treeable degrees

Abstract

We give a characterization of the strong degrees of categoricity of computable structures greater or equal to $0^{\prime \prime }$. They are precisely the \emph{treeable} degrees -- the least degrees of paths through computable trees -- that compute $0^{\prime \prime }$. As a corollary, we obtain several new examples of degrees of categoricity. Among them we show that every degree $\mathbf{d}$ with $0^{(\alpha )}\le \mathbf{d}\le 0^{(\alpha +1)}$ for $\alpha$ a computable ordinal greater than $2$ is the strong degree of categoricity of a rigid structure. Using quite different techniques we show that every degree $\mathbf{d}$ with $0^{\prime }\le \mathbf{d}\le 0^{\prime \prime }$ 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 $0^{\prime }<\mathbf{d}<0^{\prime \prime }$ that is not the degree of categoricity of a rigid structure.

arXiv commentReplaces arXiv:2209.04524 where it was incorrectly claimed that "Every degree of categoricity above 0'' is strong". We do not have a proof of this fact. Changes were made to reflect this