Categorical Linearly Ordered Structures

Abstract

We prove that for every computable limit ordinal $\alpha$ there exists a computable linear ordering $\mathcal{A}$ which is $\Delta^0_\alpha$-categorical and $\alpha$ is smallest such, but nonetheless for every isomorphic computable copy $\mathcal{B}$ of $\mathcal{A}$ there exists a $\beta< \alpha$ such that $\mathcal{A} \cong_{\Delta^0_\beta} \mathcal{B}$. This answers a question left open in the earlier work of Downey, Igusa, and Melnikov. We also show that such examples can be found among ordered abelian groups and real-closed fields.