Abstract

Journal of Mathematical Logic, Volume 24, Issue 03, December 2024. In this paper, we give a characterization of the strong degrees of categoricity of computable structures greater or equal to [math]. They are precisely the treeable degrees — the least degrees of paths through computable trees — that compute [math]. As a corollary, we obtain several new examples of degrees of categoricity. Among them we show that every degree [math] with [math] for [math] 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 [math] with [math] 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 [math] with [math] that is not the degree of categoricity of a rigid structure.