×

Isomorphism relations on computable structures. (English) Zbl 1255.03040

Let \(E\) and \(E'\) be \(\Sigma_1^1\)-equivalence relations on hyperarithmetical subsets \(X,Y\subseteq\omega\), respectively. The relation \(E\) is said to be \({F\!F}\)-reducible to \(E'\) iff there exists a partial computable function \(f\) such that \(X\subseteq\text{dom}\,(f)\) and \(Y\subseteq f(X)\) such that for all \(x,y\in X\) there holds \(xEy\Leftrightarrow f(x)E'f(y)\). A relation \(E\) on a hyperarithmetical subset of \(\omega\) is said to be an \(F\!F\)-complete \(\Sigma_1^1\)-equivalence relation if \(E\) is \(\Sigma_1^1\) and every \(\Sigma_1^1\)-equivalence relation on a hyperarithmetical subset of \(\omega\) is \(F\!F\)-reducible to \(E\).
Assuming that computable structures are identified with their indices, the authors prove that the isomorphism relations on classes of computable trees, graphs, torsion-free abelian groups, abelian \(p\)-groups, torsion abelian groups, undirected graphs, fields of characteristic \(0\), \(2\)-step niplotent groups, and linear orderings are \(F\!F\)-complete \(\Sigma_1^1\)-equivalence relations. They also formulate and discuss some open problems.

MSC:

03C57 Computable structure theory, computable model theory
03D45 Theory of numerations, effectively presented structures
PDFBibTeX XMLCite
Full Text: DOI Euclid Link

References:

[1] C. J. Ash and J. F. Knight Computable structures and the hyperarithmetical hierarchy , Elsevier,2000. · Zbl 0960.03001
[2] W. Calvert Algebraic structure and computable structure , PhD Dissertation, University of Notre Dame,2005.
[3] W. Calvert, D. Cenzer, V. Harizanov, and A. Morozov Effective categoricity of equivalence structures , Annals of Pure and Applied Logic , vol. 141(2006), pp. 61-78. · Zbl 1103.03037
[4] W. Calvert, D. Cummins, J. F. Knight, and S. Miller Comparing classes of finite structures , Algebra and Logic , vol. 43(2004), pp. 374-392. · Zbl 1097.03026
[5] W. Calvert, J. Knight, and J. Millar Computable trees of Scott rank \(\omega_1^{CK}\) and computable approximations, Journal of Symbolic Logic, vol. 71(2006), pp. 283-298. · Zbl 1112.03039
[6] J. Carson, E. Fokina, V. S. Harizanov, J. F. Knight, S. Quinn, C. Safranski, and J. Wallbaum Computable embedding problem , submitted. · Zbl 1334.03037
[7] D. Cenzer, V. Harizanov, and J. Remmel \(\Sigma^0_1\) and \(\Pi^0_1\) equivalence structures , Computability in Europe, 2009 , Lecture Notes in Computer Science, vol. 5635,2009, pp. 99-108. · Zbl 1239.03023
[8] R. Downey and A. Montalbán The isomorphism problem for torsion-free Abelian groups is analytic complete , Journal of Algebra , vol. 320(2008), pp. 2291-2300. · Zbl 1156.03042
[9] E. Fokina and S. Friedman Equivalence relations on classes of computable structures , Computability in Europe, 2009 , Lecture Notes in Computer Science, vol. 5635,2009, pp. 198-207. · Zbl 1268.03039
[10] —- \(\Sigma^1_1\) equivalence relations on \(\omega\) , submitted.
[11] E. Fokina, S. Friedman, and A. Törnquist The effective theory of Borel equivalence relations , Annals of Pure and Applied Logic , vol. 161(2010), pp. 837-850. · Zbl 1223.03031
[12] E. Fokina, J. Knight, A. Melnikov, S. Quinn, and C. Safranski Ulm type, and coding rank-homogeneous trees in other structures , Journal of Symbolic Logic, vol. 76(2011), pp. 846-869. · Zbl 1241.03042
[13] H. Friedman 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
[14] S. D. Friedman and L. Motto Ros Analytic equivalence relations and bi-embeddability , Journal of Symbolic Logic, vol. 76(2011), pp. 243-266. · Zbl 1256.03050
[15] S. Gao Invariant descriptive set theory , Pure and Applied Mathematics, CRC Press/Chapman & Hall,2009. · Zbl 1154.03025
[16] S. S. Goncharov and J. F. Knight Computable structure and non-structure theorems , Algebra and Logic , vol. 41(2002), pp. 351-373, English translation. · Zbl 1034.03044
[17] J. Harrison Recursive pseudo well-orderings , Transactions of the American Mathematical Society , vol. 131(1968), pp. 526-543. · Zbl 0186.01101
[18] G. Hjorth The isomorphism relation on countable torsion-free Abelian groups , Fundamenta Mathematica , vol. 175(2002), pp. 241-257. · Zbl 1021.03042
[19] V. Kanovei Borel equivalence relations. Structure and classification , University Lecture Series 44, American Mathematical Society,2008.
[20] I. Kaplansky Infinite Abelian groups , University of Michigan Press, Ann Arbor,1954. · Zbl 0057.01901
[21] A. Kechris New directions in descriptive set theory , Bulletin of Symbolic Logic, vol. 5(1999), no. 2, pp. 161-174. · Zbl 0933.03057
[22] A. Kechris and A. Louveau The classification of hypersmooth Borel equivalence relations , Journal of the American Mathematical Society , vol. 10(1997), no. 1, pp. 215-242. · Zbl 0865.03039
[23] B. Khoussainov, F. Stephan, and Y. Yang Computable categoricity and the Ershov hierarchy , Annals of Pure and Applied Logic , vol. 156(2008), pp. 86-95. · Zbl 1165.03012
[24] J. F. Knight, S. Miller Quinn, and M. Vanden Boom Turing computable embeddings , Journal of Symbolic Logic, vol. 73(2007), pp. 901-918. · Zbl 1123.03026
[25] A. Louveau and C. Rosendal Complete analytic equivalence relations , Transactions of the American Mathematical Society , vol. 357(2005), no. 12, pp. 4839-4866. · Zbl 1118.03043
[26] A. Montalbán On the equimorphism types of linear orderings , Bulletin of Symbolic Logic, vol. 13(2007), pp. 71-99. · Zbl 1129.03024
[27] H. Rogers Theory of recursive functions and effective computability , McGraw-Hill,1967. · Zbl 0183.01401
[28] L. Rogers Ulm’s theorem for partially ordered structures related to simply presented Abelian \(p\)-groups , Transactions of the American Mathematical Society , vol. 227(1977), pp. 333-343. · Zbl 0357.20032
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.