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?)

  • [1] U. Kalvert, D. Kammins, Dz. F. Naĭt, and S. Miller, Comparison of classes of finite structures, Algebra Logika 43 (2004), no. 6, 666-701, 759 (Russian, with Russian summary); English transl., Algebra Logic 43 (2004), no. 6, 374-392. MR 2135387 (2006e:03049),
  • [2] Riccardo Camerlo, The relation of recursive isomorphism for countable structures, J. Symbolic Logic 67 (2002), no. 2, 879-895. MR 1905171 (2003b:03064),
  • [3] Ekaterina B. Fokina and Sy-David Friedman, Equivalence relations on classes of computable structures, Mathematical theory and computational practice, Lecture Notes in Comput. Sci., vol. 5635, Springer, Berlin, 2009, pp. 198-207. MR 2545894 (2011h:03086),
  • [4] Ekaterina B. Fokina, Sy-David Friedman, and Asger Törnquist, The effective theory of Borel equivalence relations, Ann. Pure Appl. Logic 161 (2010), no. 7, 837-850. MR 2601014 (2011m:03089),
  • [5] Harvey Friedman and Lee Stanley, A Borel reducibility theory for classes of countable structures, J. Symbolic Logic 54 (1989), no. 3, 894-914. MR 1011177 (91f:03062),
  • [6] Greg Hjorth, Borel equivalence relations, Handbook of set theory. Vols. 1, 2, 3, Springer, Dordrecht, 2010, pp. 297-332 (Vol. 1). MR 2768683,
  • [7] Vladimir Kanovei, Borel equivalence relations. Structure and classification, University Lecture Series, vol. 44, American Mathematical Society, Providence, RI, 2008. MR 2441635 (2009f:03060)
  • [8] Julia F. Knight, Sara Miller, and M. Vanden Boom, Turing computable embeddings, J. Symbolic Logic 72 (2007), no. 3, 901-918. MR 2354906 (2008h:03031),
  • [9] Sara B. Quinn, Algorithmic complexity of algebraic structures, Thesis (Ph.D.)-University of Notre Dame, 2008, ProQuest LLC, Ann Arbor, MI. MR 2736772
  • [10] Robert I. Soare, Recursively enumerable sets and degrees. A study of computable functions and computably generated sets, Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1987. MR 882921 (88m:03003)
  • [11] Robert I. Soare, Computability theory with applications, the art of classical computability, Springer-Verlag, Heidelberg, 2012, to appear.

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