Categorical Linearly Ordered Structures

View/ Open
Date
2018-04-26MFO Scientific Program
Research in Pairs 2018Series
Oberwolfach Preprints;2018,08Author
Downey, Rod
Melnikov, Alexander
Ng, Keng Meng
Metadata
Show full item recordOWP-2018-08
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.