Turing computable embeddings of equivalences other than isomorphism
Matthew Wright · Proceedings of the American Mathematical Society · 2014
The concept of a Turing computable embedding was introduced by Calvert, Cummins, Miller, and Knight as an effective analog of Borel embeddings. However, while the theory of Borel embeddings is often applied to general equivalence relations, research so far in Turing computable embeddings has focused mostly on the isomorphism relation. This paper investigates Turing computable embeddings of general equivalence relations. We first examine a relation on trees which is coarser than isomorphism and can be handled in much the same way as isomorphism. We then examine the computable isomorphism relation on computable structures, a finer relation which requires new techniques. The main result of this paper is that every class of computable structures under computable isomorphism embeds into the class of computable copies of ω \omega as a linear ordering under the computable isomorphism, indicating that Turing computable embeddings are unlikely to produce meaningful distinctions when restricted to computable isomorphism relations.