×

zbMATH — the first resource for mathematics

On the degree structure of equivalence relations under computable reducibility. (English) Zbl 07167766
Summary: We study the degree structure of the \(\omega \)-c.e., \(n\)-c.e., and \(\Pi_1^0\) equivalence relations under the computable many-one reducibility. In particular, we investigate for each of these classes of degrees the most basic questions about the structure of the partial order. We prove the existence of the greatest element for the \(\omega \)-c.e. and \(n\)-computably enumerable equivalence relations. We provide computable enumerations of the degrees of \(\omega \)-c.e., \(n\)-c.e., and \(\Pi^0_1\) equivalence relations. We prove that for all the degree classes considered, upward density holds and downward density fails.

MSC:
03D28 Other Turing degree structures
03D45 Theory of numerations, effectively presented structures
PDF BibTeX XML Cite
Full Text: DOI Euclid
References:
[1] Andrews, U., S. Lempp, J. S. Miller, K. M. Ng, L. San Marco, and A. Sorbi, “Universal computably enumerable equivalence relations,” Journal of Symbolic Logic, vol. 79 (2014), pp. 60-88. · Zbl 1338.03076
[2] Bernardi, C., and A. Sorbi, “Classifying positive equivalence relations,” Journal of Symbolic Logic, vol. 48 (1983), pp. 529-38. · Zbl 0528.03030
[3] Calvert, W., D. Cummins, J. F. Knight, and S. Miller, “Comparing classes of finite structures” (in Russian), Algebra i Logika, vol. 43 (2004), pp. 666-701; English translation in Algebra and Logic, vol. 43 (2004), pp. 374-92. · Zbl 1097.03026
[4] Calvert, W., and J. F. Knight, “Classification from a computable viewpoint,” Bulletin of Symbolic Logic, vol. 12 (2006), pp. 191-218. · Zbl 1123.03024
[5] Coskey, S., J. D. Hamkins, and R. Miller, “The hierarchy of equivalence relations on the natural numbers under computable reducibility,” Computability, vol. 1 (2012), pp. 15-38. · Zbl 1325.03049
[6] Ershov, Y. I., “Theory of numberings,” pp. 473-503 in Handbook of Computability Theory, edited by E. R. Griffor, vol. 140 of Studies in Logic and the Foundations of Mathematics, North-Holland, Amsterdam, 1999. · Zbl 0948.03040
[7] Fokina, E. B., and S.-D. Friedman, “Equivalence relations on classes of computable structures,” pp. 198-207 in Mathematical Theory and Computational Practice, edited by K. Ambos-Spies, B. Löwe, and W. Merkle, vol. 5635 of Lecture Notes in Computer Science, Springer, Berlin, 2009. · Zbl 1268.03039
[8] Friedman, H., and L. Stanley, “A Borel reducibility theory for classes of countable structures,” Journal of Symbolic Logic, vol. 54 (1989), pp. 894-914. · Zbl 0692.03022
[9] Gao, S., and P. Gerdes, “Computably enumerable equivalence relations,” Studia Logica, vol. 67 (2001), pp. 27-59. · Zbl 0981.03046
[10] Ianovski, E., R. Miller, K. M. Ng, and A. Nies, “Complexity of equivalence relations and preorders from computability theory,” Journal of Symbolic Logic, vol. 79 (2014), pp. 859-81. · Zbl 1353.03043
[11] Lachlan, A. H., “Initial segments of one-one degrees,” Pacific Journal of Mathematics, vol. 29 (1969), pp. 351-66. · Zbl 0182.01603
[12] Miller, R., and K. M. Ng, “Finitary reducibility on equivalence relations,” Journal of Symbolic Logic, vol. 81 (2016), pp. 1225-54. · Zbl 1403.03070
[13] Soare, R. I., Recursively Enumerable Sets and Degrees: A Study of Computable Functions and Computably Generated Sets, Perspectives in Mathematical Logic, Springer, Berlin, 1987. · Zbl 0623.03042
[14] Young, P. R., “Notes on the structure of recursively enumerable sets,” Ph.D. dissertation, Massachusetts Institute of Technology, Cambridge, Mass., 1963.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.