Degrees of categoricity and treeable degrees

Abstract

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.