2022/09/09 by Csima, Barbara F., Rossegger, Dino
#03C75 #03D45 #03E15 #FOS: Mathematics #Logic (math.LO)
paper · doi:10.48550/arxiv.2209.04524
We give a characterization of the strong 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(α)≤ \mathbf d≤ \mathbf 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 \mathbf d with \mathbf 0'≤ \mathbf d≤ \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'< \mathbf d< \mathbf 0'' that is not the degree of categoricity of a rigid structure.