Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)



Turing computable embeddings of equivalences other than isomorphism

Author: Matthew Wright
Journal: Proc. Amer. Math. Soc. 142 (2014), 1795-1811
MSC (2010): Primary 03D45; Secondary 03C57
Published electronically: February 4, 2014
MathSciNet review: 3168485
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: 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.

References [Enhancements On Off] (What's this?)

Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC (2010): 03D45, 03C57

Retrieve articles in all journals with MSC (2010): 03D45, 03C57

Additional Information

Matthew Wright
Affiliation: Department of Mathematics, University of Chicago, 5734 S. University Avenue, Chicago, Illinois 60637

Received by editor(s): February 28, 2011
Received by editor(s) in revised form: November 28, 2011, April 27, 2012, and May 29, 2012
Published electronically: February 4, 2014
Communicated by: Julia Knight
Article copyright: © Copyright 2014 Matthew Wright

American Mathematical Society