Degrees of categoricity and the hyperarithmetic hierarchy (Q1949167): Difference between revisions

Let \(\mathbf d\) be a Turing degree. A computable structure is \(\mathbf d\)-\textit{computably categorical} if any of its computable isomorphic copies is isomorphic to it via a \(\mathbf d\)-computable isomorphism. If there is a least degree with this property, then this degree is called the \textit{degree of categoricity} of this structure. A degree is called a degree of categoricity if it is the degree of categoricity for some computable structure. If \(\mathbf d\) is a degree of categoricity with the property that there are isomorphic computable structures \({\mathcal A}_0\) and \({\mathcal A}_1\) for which \(\mathbf d\) is the degree of categoricity and every isomorphism from \({\mathcal A}_0\) onto \({\mathcal A}_1\) computes \(\mathbf d\), then \(\mathbf d\) is called \textit{strong degree of categoricity}. The authors prove the following results: 1) for any computable ordinal \(\alpha\), \({\mathbf 0}^{(\alpha)}\) is the strong degree of categoricity for some computable structure; 2) if in addition \(\alpha\) is a successor ordinal, then any degree \(2\)-c.e. in and above \({\mathbf 0}^{(\alpha)}\) is a strong degree of categoricity; 3) every degree of categoricity is hyperarithmetic; 4) the set of codes of all structures having a degree of categoricity is \(\Pi_1^1\)-complete.