Degrees of categoricity that are never strongly realized

Must a Turing degree that is the degree of categoricity of some computable structure also be the strong degree of categoricity of some computable structure, that is, realized by a single pair of computable copies all of whose isomorphisms compute it? Both notions were introduced by Fokina, Kalimullin and Miller in 2010, and whether they coincide at the level of degrees has been open since; the analogous question for one fixed structure was settled negatively by Bazhenov-Kalimullin-Yamaleev in 2018. Every degree of categoricity currently known is strong: the degrees d-c.e. in and above a finite jump $0^{(n)}$ (Fokina-Kalimullin-Miller), $0^{(\alpha)}$ for computable limit ordinals $\alpha$ together with the degrees d-c.e. in and above $0^{(\alpha)}$ for computable successor ordinals $\alpha$ (Csima-Franklin-Shore), the degrees c.e. in and above $0^{(\lambda)}$ for computable limit ordinals $\lambda$ (Csima-Deveau-Harrison-Trainor-Mahmoud), every degree at or below $0'$ (Csima-Ng), and every degree between $0'$ and $0''$ together with every treeable degree above $0''$ (Csima-Rossegger). The Bazhenov-Kalimullin-Yamaleev structure-level separation uses a computably enumerable degree, which is strong by Csima-Ng, so it does not lift to degrees. Lakerdas-Gayle (2026) records the question as open and proves that any structure witnessing a never-strong degree must have infinite spectral dimension, an infinite automorphism group, and a pair of computable copies whose isomorphism spectrum is not finitely generated. The question remains open in the 2025-2026 literature.

Background

Computable structure theory measures the algorithmic content of classical mathematics by asking how hard it is to compute isomorphisms between computable presentations of the same structure. A countable structure in a computable language is computable if, after coding its elements by natural numbers, the set of true atomic facts about it (its atomic diagram) is decidable. A computable copy of a structure $M$ is a computable structure isomorphic to $M$. Two computable copies of the same structure need not be computably isomorphic. A structure $M$ is computably categorical if every two computable copies of $M$ admit a computable isomorphism, and, for a Turing degree $d$ (an equivalence class of sets under mutual Turing computability; $0'$ denotes the degree of the halting problem, the Turing jump of the least degree $0$), $M$ is $d$-computably categorical if every two computable copies admit an isomorphism computable from $d$.

Fokina, Kalimullin and Miller (2010) defined the categoricity spectrum of $M$ to be the set $CatSpec(M)$ of all degrees $d$ such that $M$ is $d$-computably categorical; it is upward closed under Turing reducibility. If $CatSpec(M)$ has a least element $d$, then $d$ is the degree of categoricity of $M$, and $CatSpec(M)$ is then the cone $D_{\geq}(d)$ of all degrees computing $d$. For a pair of computable copies $A\cong B$, the isomorphism spectrum $IsoSpec(A,B)$ is the set of degrees computing some isomorphism from $A$ onto $B$, and $CatSpec(M)$ is the intersection of $IsoSpec(M,B)$ over all computable copies $B$ of $M$. The standard example is the linear order $(\omega,<)$. It is rigid, so between any two copies there is a unique isomorphism; this isomorphism is $0'$-computable whenever both copies are computable, and for the copy $(\omega,<_{\emptyset'})$ built from a computable enumeration of the halting problem it computes $\emptyset'$, so $CatSpec((\omega,<))=IsoSpec((\omega,<),(\omega,<_{\emptyset'}))=D_{\geq}(0')$: the whole categoricity spectrum is a single isomorphism spectrum.

A degree of categoricity is strong when the spectrum is achieved by one pair of copies: $d$ is a strong degree of categoricity if some computable structure $A$ has degree of categoricity $d$ and has computable copies $A_0,A_1$ such that every isomorphism $f:A_0\to A_1$ computes $d$. Bazhenov, Kalimullin and Yamaleev (2018) defined the spectral dimension of $M$ to be the least $k$ such that $CatSpec(M)$ is the intersection of $k$ isomorphism spectra of pairs of computable copies of $M$; a computable structure with a degree of categoricity has strong degree of categoricity exactly when its spectral dimension is 1. Every strong degree of categoricity is a degree of categoricity; whether the converse holds at the level of degrees is the problem of this task.

Known constraints and positive classes. Not every Turing degree is a degree of categoricity: Anderson and Csima produced a $\Sigma^0_2$ degree (a degree at the second level of the arithmetical hierarchy) that is not one, and showed that the degree of any set 2-generic relative to a perfect tree (a Baire-category genericity condition) and every noncomputable hyperimmune-free degree (every function computable from it is dominated by a computable function) fail to be degrees of categoricity. Csima, Franklin and Shore proved that every degree of categoricity is hyperarithmetic (computable from some transfinite jump $0^{(\alpha)}$ for a computable ordinal $\alpha$). On the positive side, the following are all strong degrees of categoricity: every degree d-c.e. in and above a finite jump $0^{(n)}$ (Fokina-Kalimullin-Miller), meaning the degree of a set that is the difference of two sets computably enumerable in $0^{(n)}$ and that computes $0^{(n)}$; $0^{(\alpha)}$ for computable limit ordinals $\alpha$ and every degree d-c.e. in and above $0^{(\alpha)}$ for computable successor ordinals $\alpha$ (Csima-Franklin-Shore); every degree c.e. in and above $0^{(\lambda)}$ for computable limit ordinals $\lambda$ (Csima-Deveau-Harrison-Trainor-Mahmoud); every $\Delta^0_2$ degree, that is, every degree at or below $0'$ (Csima-Ng); and every degree in the interval $[0',0'']$ together with every treeable degree above $0''$ (Csima-Rossegger). A degree is treeable if some computable tree (equivalently, some $\Pi^0_1$ class, i.e. effectively closed set) has a path $p$ of that degree such that $p$ is computable from every path through the tree; Csima and Rossegger also proved that every strong degree of categoricity is treeable, and that above $0''$ treeability is equivalent to being a strong degree of categoricity.

Lakerdas-Gayle (2026; published as ZML: Zeitschrift für Mathematische Logik und Grundlagen der Mathematik 72, 197-210) studies isomorphism spectra directly. The paper introduces computably composite structures $\mathcal{S}[\mathcal{A}_x:x\in S]$, built by effectively attaching a uniformly computable copy $\mathcal{A}_x$ to each element $x$ of a computable base structure $S$, so that the isomorphisms between computable copies of the composite are exactly the unions of isomorphisms between the attached components, and proves that the class of isomorphism spectra is closed under computable unions (Theorem 29); applying this to a 1971 result of Thomason on sublattices of the computably enumerable degrees yields an explicit isomorphism spectrum that is not finitely generated (a set of degrees is finitely generated if it is a finite union of cones $D_{\geq}(c)$). Adapting results of Bazhenov-Kalimullin-Yamaleev, the paper proves (Theorem 17) that if $d$ is the degree of categoricity of a computable structure $M$ but is not the strong degree of categoricity of any computable structure, then $M$ has infinite spectral dimension, an infinite automorphism group, and a pair of computable copies whose isomorphism spectrum is not finitely generated. The paper also studies uniform categoricity (a partial $d$-computable function mapping an index of any computable copy to an isomorphism; a total $d$-computable list of such maps for a uniformly computable collection of copies) and asks (Question 48) whether the global version is strictly stronger than the familywise version.

Problem Statement

Does there exist a Turing degree $d$ such that: (1) $d$ is the degree of categoricity of some computable structure $M$, i.e. $CatSpec(M)=D_{\geq}(d)$; and (2) $d$ is not the strong degree of categoricity of any computable structure, i.e. there is no computable structure $A$ with degree of categoricity $d$ admitting computable copies $A_0,A_1$ such that every isomorphism $A_0\cong A_1$ computes $d$ (equivalently, no computable structure with degree of categoricity $d$ has spectral dimension 1)? The complementary form: is every degree of categoricity a strong degree of categoricity?

The question is strictly about degrees, not about one fixed structure. Bazhenov, Kalimullin and Yamaleev already constructed a computable structure whose own degree of categoricity is not strong for that structure; that degree is computably enumerable, hence $\Delta^0_2$, hence by Csima-Ng the strong degree of categoricity of some other computable structure. A positive answer must therefore produce a degree for which every realizing structure fails condition (2); by Lakerdas-Gayle's Theorem 17, any witnessing structure must have infinite spectral dimension, an infinite automorphism group, and a pair of computable copies with a non-finitely-generated isomorphism spectrum. A negative answer is a theorem that the two notions of degree of categoricity coincide.

References

1. Joey Lakerdas-Gayle. Isomorphism spectra and computably composite structures. ZML: Zeitschrift für Mathematische Logik und Grundlagen der Mathematik, 72:197-210, 2026. DOI 10.60866/CAM.260 (DataCite); arXiv:2501.16586. https://doi.org/10.60866/CAM.260; https://arxiv.org/abs/2501.16586.
2. Ekaterina B. Fokina, Iskander Kalimullin, and Russell Miller. Degrees of categoricity of computable structures. Archive for Mathematical Logic, 49(1):51-67, 2010. DOI 10.1007/s00153-009-0160-4. https://doi.org/10.1007/s00153-009-0160-4.
3. Bernard A. Anderson and Barbara F. Csima. Degrees that are not degrees of categoricity. Notre Dame Journal of Formal Logic, 57(3):389-398, 2016. DOI 10.1215/00294527-3496154; arXiv:1210.4220. https://doi.org/10.1215/00294527-3496154; https://arxiv.org/abs/1210.4220.
4. Barbara F. Csima, Johanna N. Y. Franklin, and Richard A. Shore. Degrees of categoricity and the hyperarithmetic hierarchy. Notre Dame Journal of Formal Logic, 54(2):215-231, 2013. DOI 10.1215/00294527-1960479. https://doi.org/10.1215/00294527-1960479.
5. N. A. Bazhenov, I. Sh. Kalimullin, and M. M. Yamaleev. Degrees of categoricity vs. strong degrees of categoricity. Algebra and Logic, 55(2):173-177, 2016. DOI 10.1007/s10469-016-9385-6. https://doi.org/10.1007/s10469-016-9385-6.
6. Nikolay A. Bazhenov, Iskander Sh. Kalimullin, and Mars M. Yamaleev. Degrees of categoricity and spectral dimension. The Journal of Symbolic Logic, 83(1):103-116, 2018. DOI 10.1017/jsl.2017.70. https://doi.org/10.1017/jsl.2017.70.
7. N. A. Bazhenov, I. Sh. Kalimullin, and M. M. Yamaleev. Strong degrees of categoricity and weak density. Lobachevskii Journal of Mathematics, 41(9):1630-1639, 2020. DOI 10.1134/S1995080220090048. https://doi.org/10.1134/S1995080220090048.
8. Barbara F. Csima and Jonathan Stephenson. Finite computable dimension and degrees of categoricity. Annals of Pure and Applied Logic, 170(1):58-94, 2019. DOI 10.1016/j.apal.2018.08.012. https://doi.org/10.1016/j.apal.2018.08.012.
9. Dan Turetsky. Coding in the automorphism group of a computably categorical structure. Journal of Mathematical Logic, 20(3):2050016, 2020. DOI 10.1142/S0219061320500166; arXiv:1905.07850. https://doi.org/10.1142/S0219061320500166; https://arxiv.org/abs/1905.07850.
10. Barbara F. Csima, Michael Deveau, Matthew Harrison-Trainor, and Mohammad Assem Mahmoud. Degrees of categoricity above limit ordinals. Computability, 9(2):127-137, 2020. DOI 10.3233/COM-190254. https://doi.org/10.3233/COM-190254.
11. Barbara F. Csima and Keng Meng Ng. Every $\Delta^0_2$ degree is a strong degree of categoricity. Journal of Mathematical Logic, 22(3):2250022, 2022. DOI 10.1142/S0219061322500222. https://doi.org/10.1142/S0219061322500222.
12. Barbara F. Csima and Dino Rossegger. Degrees of categoricity and treeable degrees. Journal of Mathematical Logic, 24(3):2450002, 2024 (published online 2023). DOI 10.1142/S0219061324500028; arXiv:2209.04524. https://doi.org/10.1142/S0219061324500028; https://arxiv.org/abs/2209.04524.
13. Nikolay Bazhenov, Heer Tern Koh, and Keng Meng Ng. Primitive recursive categoricity spectra of functional structures. The Journal of Symbolic Logic, published online 2026, pp. 1-32. DOI 10.1017/jsl.2026.10230; arXiv:2603.08010. https://doi.org/10.1017/jsl.2026.10230; https://arxiv.org/abs/2603.08010.
14. Mohammad Mahmoud and Mostafa Mirabi. Scott complexity of trees of finite rank via degrees of categoricity. arXiv:2606.27151, 2026. https://arxiv.org/abs/2606.27151.
15. Johanna N. Y. Franklin, Dino Rossegger, and Dan Turetsky. Structural vs. computational complexity. arXiv:2606.15196, 2026. https://arxiv.org/abs/2606.15196.
16. Jun Le Goh and Chieu-Minh Tran. Categoricity without Power. arXiv:2605.00697, 2026. https://arxiv.org/abs/2605.00697.
17. Java Darleen Villano. Extensions of categoricity relative to a degree. arXiv:2505.15706, 2025. https://arxiv.org/abs/2505.15706.