A Note on Computable Embeddings for Ordinals and Their Reverses

Abstract

We continue the study of computable embeddings for pairs of structures, i.e. for classes containing precisely two non-isomorphic structures. Surprisingly, even for some pairs of simple linear orders, computable embeddings induce a non-trivial degree structure. Our main result shows that although $\{\omega \cdot 2,{\omega }^{\star }\cdot 2\}$ is computably embeddable in $\{{\omega }^2,{({\omega }^2)}^{\star }\}$, the class $\{\omega \cdot k,{\omega }^{\star }\cdot k\}$ is \emph{not} computably embeddable in $\{{\omega }^2,{({\omega }^2)}^{\star }\}$ for any natural number $k\ge 3$.

13 pages, accepted to CiE 2020