×

zbMATH — the first resource for mathematics

The isomorphism problem for torsion-free abelian groups is analytic complete. (English) Zbl 1156.03042
The paper proves that the isomorphism problem for torsion-free abelian groups is \(\Sigma_1^1\) complete.

MSC:
03D40 Word problems, etc. in computability and recursion theory
03D15 Complexity of computation (including implicit computational complexity)
20K15 Torsion-free groups, finite rank
20K20 Torsion-free groups, infinite rank
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Baumslag, G.; Dyer, E.; Miller, C.F., On the integral homology of finitely presented groups, Topology, 22, 1, 27-46, (1983) · Zbl 0503.20018
[2] Wesley Calvert, Algebraic Structure and Computable Structure, PhD thesis, University of Notre Dame, 2005 · Zbl 1099.03031
[3] Peter Cholak, Rod Downey, Leo A. Harrington, On the orbits of computable enumerable sets, J. Amer. Math. Soc., in press · Zbl 1214.03028
[4] Calvert, Wesley; Knight, Julia F., Classification from a computable viewpoint, Bull. symbolic logic, 12, 191-218, (2006) · Zbl 1123.03024
[5] Friedman, Harvey; Stanley, Lee, A Borel reducibility theory for classes of countable structures, J. symbolic logic, 54, 3, 894-914, (1989) · Zbl 0692.03022
[6] Goncharov, Sergei S.; Knight, J., Computable structure and non-structure theorems, Algebra logic, 41, 351-373, (2002)
[7] Greunberg, K., Cohomological topics in group theory, Springer lecture notes, vol. 143, (1970)
[8] Harrison, J., Recursive pseudo-well-orderings, Trans. amer. math. soc., 131, 526-543, (1968) · Zbl 0186.01101
[9] Hjorth, Greg, The isomorphism relation on torsion-free abelian groups, Fund. math., 175, 241-257, (2002) · Zbl 1021.03042
[10] Khisamiev, N.G., Hierarchies of torsion-free abelian groups, Algebra logika, 25, 2, 205-226, (1986), 244 · Zbl 0625.03026
[11] Lempp, Steffen, The computational complexity of torsion-freeness of finitely presented groups, Bull. austral. math. soc., 56, 2, 273-277, (1997) · Zbl 0889.03033
[12] Miller, Charles F., Decision problems for groups—survey and reflections, (), 1-59 · Zbl 0752.20014
[13] Sacks, Gerald E., Higher recursion theory, () · Zbl 1365.03011
[14] Soare, Robert I., Recursively enumerable sets and degrees: A study of computable functions and computably generated sets, () · Zbl 0667.03030
[15] Stallings, J.R., A finitely presented group whose 3 dimensional integral homology is not finitely generated, Amer. J. math., 85, 541-543, (1963) · Zbl 0122.27301
[16] Slaman, Theodore A.; Woodin, W. Hugh, Extending partial orders to dense linear orders, Conference on computability theory, Oberwolfach, 1996, Ann. pure appl. logic, 94, 1-3, 253-261, (1998) · Zbl 0924.03094
[17] Thomas, Simon, The classification problem for torsion-free abelian groups of finite rank, J. amer. math. soc., 16, 233-258, (2003) · Zbl 1021.03043
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.