Computable embeddings for pairs of linear orders

Abstract

We study 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 $\{\omega \cdot k,{\omega }^{\star }\cdot k\}$ is computably embeddable in $\{\omega \cdot t,{\omega }^{\star }\cdot t\}$ iff $k$ divides $t$.

20 pages

References in corpus (2)

• Learning families of algebraic structures from informant
• Isomorphism and classification for countable structures

Cited by in corpus (1)

• A Lopez-Escobar Theorem for Continuous Domains