Turing computable embeddings of equivalences other than isomorphism

Wright, Matthew

doi:10.1090/S0002-9939-2014-11878-8

Turing computable embeddings of equivalences other than isomorphism
HTML articles powered by AMS MathViewer

by Matthew Wright

Proc. Amer. Math. Soc. 142 (2014), 1795-1811

DOI: https://doi.org/10.1090/S0002-9939-2014-11878-8

Published electronically: February 4, 2014

PDF

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

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, DOI 10.1023/B:ALLO.0000048827.30718.2c
Riccardo Camerlo, The relation of recursive isomorphism for countable structures, J. Symbolic Logic 67 (2002), no. 2, 879–895. MR 1905171, DOI 10.2178/jsl/1190150114
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, DOI 10.1007/978-3-642-03073-4_{2}1
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, DOI 10.1016/j.apal.2009.10.002
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, DOI 10.2307/2274750
Greg Hjorth, Borel equivalence relations, Handbook of set theory. Vols. 1, 2, 3, Springer, Dordrecht, 2010, pp. 297–332. MR 2768683, DOI 10.1007/978-1-4020-5764-9_{5}
Vladimir Kanovei, Borel equivalence relations, University Lecture Series, vol. 44, American Mathematical Society, Providence, RI, 2008. Structure and classification. MR 2441635, DOI 10.1090/ulect/044
Julia F. Knight, Sara Miller, and M. Vanden Boom, Turing computable embeddings, J. Symbolic Logic 72 (2007), no. 3, 901–918. MR 2354906, DOI 10.2178/jsl/1191333847
Sara B. Quinn, Algorithmic complexity of algebraic structures, ProQuest LLC, Ann Arbor, MI, 2008. Thesis (Ph.D.)–University of Notre Dame. MR 2736772
Robert I. Soare, Recursively enumerable sets and degrees, Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1987. A study of computable functions and computably generated sets. MR 882921, DOI 10.1007/978-3-662-02460-7
Robert I. Soare, Computability theory with applications, the art of classical computability, Springer-Verlag, Heidelberg, 2012, to appear.