Computable embeddings for classes of structures
A widely used approach to investigating algorithmic complexity involves comparing different classes of structures by using a particular notion of reduction between classes. Examples of such reductions include computable embeddings, based on enumeration operators, and Turing computable embeddings, based on Turing operators. We study computable embeddings for pairs of structures, i.e. for classes containing precisely two non-isomorphic structures. We show that computable embeddings induce a non-trivial degree structure for two-element classes consisting of computable structures, in particular the pair of linear orders {\omega, \omega*}.
This is joint work with Nikolay Bazhenov and Hristo Ganchev.