Computable Embeddings for Pairs of Linear Orders
Nikolay A. Bazhenov, Hristo Ganchev, Stefan Vatev · Algebra and Logic · 2021
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 nontrivial degree structure.Our main result shows that {ω•k, ω ⋆ •k} is computably embeddable in {ω • t, ω ⋆ • t} iff k divides t.