Computable embeddings for pairs of linear orders

DOI10.1007/S10469-021-09639-7zbMATH Open1515.03159arXiv1901.01933MaRDI QIDQ6312108

Nikolay Bazhenov, Hristo Ganchev, S. Vatev

Publication date: 7 January 2019

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 $omegacdotk,omeg{a}^{s}tarcdotk$ is computably embeddable in $omegacdott,omeg{a}^{s}tarcdott$ iff $k$ divides $t$.

Mathematics Subject Classification ID

Computable structure theory, computable model theory (03C57) Theory of numerations, effectively presented structures (03D45)

This page was built for publication: Computable embeddings for pairs of linear orders