Degrees of categoricity and treeable degrees.

In this paper, we give a characterization of the strong degrees of categoricity of computable structures greater or equal to 0 ″ . They are precisely the treeable degrees — the least degrees of paths through computable trees — that compute 0 ″ . As a corollary, we obtain several new examples of degrees of categoricity. Among them we show that every degree d with 0 (α) ≤ d ≤ 0 (α + 1) for α 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 d with 0 ′ ≤ d ≤ 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 d with 0 ′ < d < 0 ″ that is not the degree of categoricity of a rigid structure. [ABSTRACT FROM AUTHOR]