Csima, B. F., & Rossegger, D. (2023). Degrees of categoricity and treeable degrees. Journal of Mathematical Logic. https://doi.org/10.1142/S0219061324500028
Computable structure theory; degrees of categoricity; isomorphisms
en
Turing 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.
en
Project title:
Algorithmische Komplexität von Strukturen und deren Äquivalenzrelationen: 101026834 (European Commission)
