Hostname: page-component-cd9895bd7-jn8rn Total loading time: 0 Render date: 2024-12-22T14:19:59.589Z Has data issue: false hasContentIssue false
  • English
  • Français

COMPUTABLE ABELIAN GROUPS

Published online by Cambridge University Press:  24 October 2014

ALEXANDER G. MELNIKOV
ALEXANDER G. MELNIKOV*
Affiliation:
DEPARTMENT OF MATHEMATICS, UNIVERSITY OF CALIFORNIA, BERKELEY, CA, USA.
Get access Rights & Permissions [Opens in a new window]

Abstract

We provide an introduction to methods and recent results on infinitely generated abelian groups with decidable word problem.

Keywords

Abelian groupslogiccomputability theory
Type
Articles
Information
Bulletin of Symbolic Logic , Volume 20 , Issue 3 , September 2014 , pp. 315 - 356
Copyright
Copyright © The Association for Symbolic Logic 2014 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

Andersen, B., Kach, A., Melnikov, A., and Solomon, R., Jump degrees of torsion-free abelian groups. Journal of Symbolic Logic, vol. 77 (2012), no. 4, pp. 1067–1100.CrossRefGoogle Scholar
Ash, C., Recursive labeling systems and stability of recursive structures in hyperarithmetical degrees. Transactions of the American Mathematical Society, vol. 298 (1986), pp. 497–514.Google Scholar
Ash, C., Jockusch, C., and Knight, J., Jumps of orderings. Transactions of the American Mathematical Society, vol. 319 (1990), no. 2, pp. 573–599.Google Scholar
Ash, C. and Knight, J., Computable structures and the hyperarithmetical hierarchy, Studies in Logic and the Foundations of Mathematics, vol. 144, North-Holland, Amsterdam, 2000.Google Scholar
Ash, C., Knight, J., and Oates, S., Recursive abelian p-groups of small length, Unpublished. An annotated manuscript: https://dl.dropbox.com/u/4752353/Homepage/AKO.pdf.Google Scholar
Baer, R., Abelian groups without elements of finite order. Duke Mathematical Journal, vol. 3 (1937), no. 1, pp. 68–122.CrossRefGoogle Scholar
Barker, E., Back and forth relations for reduced abelian p-groups. Annals of Pure and Applied Logic, vol. 75 (1995), no. 3, pp. 223–249.Google Scholar
Baumslag, G., Dyer, E., and Miller, C. IIIOn the integral homology of finitely presented groups. Topology, vol. 22 (1983), no. 1, pp. 27–46.Google Scholar
Boone, W., The word problem. Annals of Mathematics, vol. 70 (1959), pp. 207–265.Google Scholar
Braun, G. and Strüngmann, L., Breaking up finite automata presentable torsion-free abelian groups. International Journal of Algebra and Computation, vol. 21x(2011), no. 8, pp. 1463–1472.Google Scholar
Lin, C., The effective content of Ulm’s theorem, Aspects of effective algebra (Clayton, 1979), Upside Down A Book, Yarra Glen, 1981, pp. 147–160.Google Scholar
Lin, C., Recursively presented abelian groups: Effective p-group theory. I. Journal of Symbolic Logic, vol. 46 (1981), no. 3, pp. 617–624.CrossRefGoogle Scholar
Calvert, W., Algebraic structure and computable structure, ProQuest LLC, Ann Arbor, MI, 2005, Thesis (Ph.D.)–University of Notre Dame.Google Scholar
Calvert, W., The isomorphism problem for computable abelian p-groups of bounded length. Journal of Symbolic Logic, vol. 70 (2005), no. 1, pp. 331–345.Google Scholar
Calvert, W., Cenzer, D., Harizanov, V., and Morozov, A., Effective categoricity of abelian p-groups. Annals of Pure and Applied Logic, vol. 159 (2009), no. 1–2, pp. 187–197.Google Scholar
Calvert, W., Harizanov, V., and Shlapentokh, A., Turing degrees of isomorphism types of algebraic objects. Journal of London Mathematical Society (2), vol. 75 (2007), no. 2, pp. 273–286.Google Scholar
Calvert, W., Knight, J., and Millar, J., Computable trees of Scott rank $\omega _1^{CK} {\rm{,}}$and computable approximation. Journal of Symbolic Logic, vol. 71 (2006), no. 1, pp. 283–298.Google Scholar
Cenzer, D. and Remmel, J., Feasibly categorical abelian groups, Feasible mathematics, II (Ithaca, NY, 1992), Progress in Computer Science and Applied Logic, vol. 13, Birkhäuser Boston, Boston, MA, 1995, pp. 91–153.Google Scholar
Coles, R., Downey, R., and Slaman, T., Every set has a least jump enumeration. Journal of London Mathematical Society (2), vol. 62 (2000), no. 3, pp. 641–649.Google Scholar
Crossley, J. (EDITOR)Aspects of Effective Algebra, Upside Down A Book, Yarra Glen, 1981.Google Scholar
Csima, B. and Solomon, R., The complexity of central series in nilpotent computable groups. Annals of Pure and Applied Logic, vol. 162 (2011), no. 8, pp. 667–678.Google Scholar
Dekker, J., Countable vector spaces with recursive operations. I. Journal of Symbolic Logic, vol. 34 (1969), pp. 363–387.Google Scholar
Dekker, J., Countable vector spaces with recursive operations. II. Journal of Symbolic Logic, vol. 36 (1971), pp. 477–493.Google Scholar
Dobrica, V., Constructivizable abelian groups. Sibirskii Matematicheskii Zhurnal, vol. 22 (1981), no. 3, pp. 208–213, 239.Google Scholar
Dobritsa, V., Some constructivizations of abelian groups. Siberian Journal of Mathematics, vol. 24 (1983), 167–173 (in Russian).Google Scholar
Downey, R., On presentations of algebraic structures, Complexity, logic, and recursion theory, Lecture Notes in Pure and Applied Mathematics, vol. 187, Dekker, New York, 1997, pp. 157–205.Google Scholar
Downey, R., Computability, definability and algebraic structures, Proceedings of the 7th and 8th Asian Logic Conferences, Singapore University Press, Singapore, 2003, pp. 63–102.CrossRefGoogle Scholar
Downey, R., Goncharov, S., Kach, A., Knight, J., Kudinov, O., Melnikov, A., and Turetsky, D., Decidability and computability of certain torsion-free abelian groups. Notre Dame Journal of Formal Logic, vol. 51 (2010), no. 1, pp. 85–96.Google Scholar
Downey, R. and Hirschfeldt, D., Algorithmic Randomness and Complexity, Theory and Applications of Computability, Springer, New York, 2010.Google Scholar
Downey, R., Hirschfeldt, D., Kach, A., Lempp, S., Mileti, J., and Montalbán, A.Subspaces of computable vector spaces. Journal of Algebra, vol. 314 (2007), no. 2, pp. 888–894.CrossRefGoogle Scholar
Downey, R. and Kurtz, S., Recursion theory and ordered groups. Annals of Pure and Applied Logic, vol. 32 (1986), no. 2, pp. 137–151.Google Scholar
Downey, R. and Melnikov, A., Computable completely decomposable groups. Transactions of the American Mathematical Society, vol. 366 (2014), no. 8, pp. 4243–4266.CrossRefGoogle Scholar
Downey, R. and Melnikov, A., Effectively categorical abelian groups. Journal of Algebra, vol. 373 (2013), pp. 223–248.Google Scholar
Downey, R., Melnikov, A., and Ng, K., Abelian p-groups and the halting problem, submitted.Google Scholar
Downey, R., Melnikov, A., and Ng, K., Iterated effective embeddings of abelian p-groups. International Journal of Algebra and Computation, to appear.Google Scholar
Downey, R. and Montalbán, A., The isomorphism problem for torsion-free abelian groups is analytic complete. Journal of Algebra, vol. 320 (2008), no. 6, pp. 2291–2300.Google Scholar
Ershov, Y. and Goncharov, S., Constructive models, Siberian School of Algebra and Logic, Consultants Bureau, New York, 2000.Google Scholar
Ershov, Yu., Problems of Solubility and Constructive Models [in Russian], Nauka, Moscow, 1980.Google Scholar
Fokina, E., Friedman, S., Harizanov, V., Knight, J., McCoy, C., and Montalban, A., Isomorphism and bi-embeddability relations on computable structures. Journal of Symbolic Logic, vol. 77 (2012), pp. 122–132.Google Scholar
Fokina, E., Knight, J., Melnikov, A., Quinn, S., and Safranski, C., Classes of Ulm type and coding rank-homogeneous trees in other structures. Journal of Symbolic Logic, vol. 76 (2011), no. 3, pp. 846–869.Google Scholar
Fröhlich, A. and Shepherdson, J., Effective procedures in field theory. Philosophical Transactions of the Royal Society of London, Series A, vol. 248 (1956), pp. 407–432.Google Scholar
Frolov, A., Kalimullin, I., Harizanov, V., Kudinov, O., and Miller, R., Spectra of high nand non-low ndegrees. Journal of Logic and Computation, vol. 22 (2012), no. 4, pp. 755–777.Google Scholar
Fuchs, L., Partially Ordered Algebraic Systems, Pergamon Press, Oxford, 1963.Google Scholar
Fuchs, L., Infinite Abelian Groups. Vol. I, Pure and Applied Mathematics, Vol. 36, Academic Press, New York, 1970.Google Scholar
Fuchs, L., Infinite Abelian Groups. Vol. II, Pure and Applied Mathematics, Vol. 36–II, Academic Press, New York, 1973.Google Scholar
Goncharov, S., Autostability of models and abelian groups. Algebra i Logika, vol. 19 (1980), no. 1, pp. 23–44, 132.Google Scholar
Goncharov, S., The problem of the number of nonautoequivalent constructivizations. Algebra i Logika, vol. 19 (1980), no. 6, pp. 621–639, 745.Google Scholar
Goncharov, S., Groups with a finite number of constructivizations. Doklady Akademii Nauk SSSR, vol. 256 (1981), no. 2, pp. 269–272.Google Scholar
Goncharov, S., Countable Boolean Algebras and Decidability, Siberian School of Algebra and Logic, Consultants Bureau, New York, 1997.Google Scholar
Goncharov, S. and Knight, J., Computable structure and antistructure theorems. Algebra Logika, vol. 41 (2002), no. 6, pp. 639–681, 757.Google Scholar
Goncharov, S., Lempp, S., and Solomon, R.. The computable dimension of ordered abelian groups, Advances in Mathematics, vol. 175 (2003), no. 1, pp. 102–143.CrossRefGoogle Scholar
Harris, K., η-representation of sets and degrees. Journal of Symbolic Logic, vol. 73 (2008), no. 4, pp. 1097–1121.Google Scholar
Harrison, J., Recursive pseudo-well-orderings. Transactions of the American Mathematical Society, vol. 131 (1968), pp. 526–543.Google Scholar
Hatzikiriakou, K. and Simpson, S., WKL 0 and orderings of countable abelian groups, Logic and computation (Pittsburgh, PA, 1987), Contemporary Mathematics, vol. 106, American Mathematical Society, Providence, RI, 1990, pp. 177–180.Google Scholar
Higman, G., Subgroups of finitely presented groups. Proceedings of the Royal Society, Series A, vol. 262 (1961), pp. 455–475.Google Scholar
Hirschfeldt, D., Khoussainov, B., Shore, R., and Slinko, A., Degree spectra and computable dimensions in algebraic structures. Annals of Pure and Applied Logic, vol. 115 (2002), no. 1–3, pp. 71–113.Google Scholar
Hisamiev, N., Criterion for constructivizability of a direct sum of cyclic p-groups. Izv. Akad. Nauk Kazakh. SSR Ser. Fiz.-Mat., (1981), no. 1, pp. 51–55, 86.Google Scholar
Hjorth, G., The isomorphism relation on countable torsion free abelian groups. Fundamenta Mathematicae, vol. 175 (2002), no. 3, pp. 241–257.Google Scholar
Kach, A., Lange, K., and Solomon, R., Degrees of orders on torsion-free Abelian groups. Annals of Pure and Applied Logic, vol. 164 (2013), no. 7–8, pp. 822–836.Google Scholar
Kalimullin, I., Khoussainov, B., and Melnikov, A., Limitwise monotonic sequences and degree spectra of structures. Proceedings of the American Mathematical Society, vol. 141 (2013), no. 9, pp. 3275–3289.Google Scholar
Kaplansky, A., Infinite abelian groups, Revised edition, The University of Michigan Press, Ann Arbor, MI, 1969.Google Scholar
Khisamiev, A., On the Ershov upper semilattice L E. Sibirskii Matematicheskii Zhurnal, vol. 45 (2004), no. 1, pp. 211–228.Google Scholar
Khisamiev, N., Strongly constructive abelian p-groups. Algebra i Logika, vol. 22 (1983), no. 2, pp. 198–217.Google Scholar
Khisamiev, N., Hierarchies of torsion-free abelian groups. Algebra i Logika, vol. 25 (1986), no. 2, pp. 205–226, 244.Google Scholar
Khisamiev, N., Constructive abelian p-groups. Siberian Advances in Mathematics, vol. 2 (1992), no. 2, pp. 68–113.Google Scholar
Khisamiev, N., Constructive Abelian Groups, Vol. 2, Handbook of recursive mathematics, Studies in Logic and the Foundations of Mathematics, vol. 139, North-Holland, Amsterdam, 1998, pp. 1177–1231.Google Scholar
Khisamiev, N., On a class of strongly decomposable abelian groups. Algebra Logika, vol. 41 (2002), no. 4, pp. 493–509, 511–512.Google Scholar
Khisamiev, N., On constructive nilpotent groups. Sibirskii Matematicheskii Zhurnal, vol. 48 (2007), no. 1, pp. 214–223.Google Scholar
Khisamiev, N. and Khisamiev, Z., Nonconstructivizability of the reduced part of a strongly constructive torsion-free abelian group. Algebra i Logika, vol. 24 (1985), pp. 69–76.Google Scholar
Khisamiev, N. and Krykpaeva, A., Effectively completely decomposable abelian groups. Sibirskii Matematicheskii Zhurnal, vol. 38 (1997), no. 6, pp. 1410–1412, iv.Google Scholar
Khoussainov, B., Nies, A., and Shore, R., Computable models of theories with few models. Notre Dame Journal of Formal Logic, vol. 38 (1997), no. 2, pp. 165–178.Google Scholar
Kokorin, A. and Kopytov, V., Fully ordered groups, Halsted Press [John Wiley & Sons], New York-Toronto, 1974, Translated from the Russian by D. Louvish.Google Scholar
Kurosh, A., The Theory of Groups, Chelsea, New York, 1960, Translated from the Russian and edited by K. A. Hirsch. 2nd English ed. 2 volumes.Google Scholar
Lempp, S., The computational complexity of torsion-freeness of finitely presented groups. Bulletin of the Australian Mathematical Society, vol. 56 (1997), no. 2, pp. 273–277.Google Scholar
Levi, F., Abelsche gruppen mit abzhlbaren elementen, Habilitationsschrift, Leipzig, Teubner, 1917.Google Scholar
Loth, Peter, Classifications of abelian groups and Pontrjagin duality, Algebra, Logic and Applications, vol. 10, Gordon and Breach Science Publishers, Amsterdam, 1998.Google Scholar
Mader, A., Almost completely decomposable groups, Algebra, Logic and Applications, vol. 13, Gordon and Breach Science Publishers, Amsterdam, 2000.Google Scholar
Malʹ cev, A., Torsion-free abelian groups of finite rank. Matematicheskii Sbornik, vol. 4 (1938), no. 2, pp. 45–68.Google Scholar
Malʹ cev, A., Constructive algebras. I. Uspekhi Matematicheskikh Nauk, vol. 16 (1961), no. 3(99), pp. 3–60.Google Scholar
Malʹ cev, A., On recursive Abelian groups. Doklady Akademii Nauk SSSR, vol. 146 (1962), pp. 1009–1012.Google Scholar
Melnikov, A., Effective properties of completely decomposable abelian groups, CSc dissertation (2012).Google Scholar
Melnikov, A., Enumerations and completely decomposable torsion-free abelian groups. Theory of Computing Systems, vol. 45 (2009), no. 4, pp. 897–916.Google Scholar
Melnikov, A., Transforming trees into abelian groups. New Zealand Journal of Mathematics, vol. 41 (2011), pp. 75–81.Google Scholar
Melnikov, A., Computability and Structure, The University of Auckland, 2012.Google Scholar
Metakides, G. and Nerode, A., Recursively enumerable vector spaces, Annals of Mathematical Logic, vol. 11 (1977), no. 2, pp. 147–171.Google Scholar
Metakides, G., Effective content of field theory. Annals of Mathematical Logic, vol. 17 (1979), no. 3, pp. 289–320.Google Scholar
Miller, C. IIIDecision problems for groups—survey and reflections, Algorithms and classification in combinatorial group theory (Berkeley, CA, 1989), Mathematical Sciences Research Institute Publications, vol. 23, Springer, New York, 1992, pp. 1–59.Google Scholar
Miller, R., The${\rm{\Delta }}_2^0$-spectrum of a linear order. Journal of Symbolic Logic, vol. 66 (2001), no. 2, pp. 470–486.Google Scholar
Novikov, P., On the algorithmic unsolvability of the word problem in group theory. Trudy Matematicheskogo Instituta imeni VA Steklova, vol. 44 (1955), pp. 1–143.Google Scholar
Nurtazin, A., Computable classes and algebraic criteria of autostability, Summary of Scientific Schools, Mathematics Institute, SB USSRAS, Novosibirsk, 1974.Google Scholar
Oates, S., Jump Degrees of Groups, ProQuest LLC, Ann Arbor, MI, 1989, Thesis (Ph.D.)–University of Notre Dame.Google Scholar
Odifreddi, P., Classical Recursion Theory. Vol. II, Studies in Logic and the Foundations of Mathematics, vol. 143, North-Holland, Amsterdam, 1999.Google Scholar
Rabin, M., Computable algebra, general theory and theory of computable fields.Transactions of the American Mathematical Society, vol. 95 (1960), pp. 341–360.Google Scholar
Richter, L., Degrees of structures. Journal of Symbolic Logic, vol. 46 (1981), no. 4, pp. 723–731.Google Scholar
Riggs, K., The decomposability problem for torsion-free abelian groups is analytic complete. Proceedings of the American Mathematical Society, to appear.Google Scholar
Rogers, H., Theory of Recursive Functions and Effective Computability, second edition, MIT Press, Cambridge, MA, 1987.Google Scholar
Rogers, L., 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.Google Scholar
Shore, R., Controlling the dependence degree of a recursively enumerable vector space. Journal of Symbolic Logic, vol. 43 (1978), no. 1, pp. 13–22.Google Scholar
Simpson, S., Subsystems of Second Order Arithmetic, second edition, Perspectives in Logic, Cambridge University Press, Cambridge, 2009.Google Scholar
Slaman, T., Relative to any nonrecursive set. Proceedings of the American Mathematical Society, vol. 126 (1998), no. 7, pp. 2117–2122.Google Scholar
Smith, R., Two theorems on autostability in p-groups, Logic Year 1979–80 (Proc. Seminars and Conf. Math. Logic, Univ. Connecticut, Storrs, Conn., 1979/80), Lecture Notes in Mathematics, vol. 859, Springer, Berlin, 1981, pp. 302–311.Google Scholar
Soare, R., Recursively Enumerable Sets and Degrees, A study of computable functions and computably generated sets, Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1987.Google Scholar
Solomon, R., ${\rm{\Pi }}_1^0$classes and orderable groups. Annals of Pure and Applied Logic, vol. 115 (2002), no. 1–3, pp. 279–302.Google Scholar
Soskov, , A jump inversion theorem for the enumeration jump. Archive for Mathematical Logic, vol. 39 (2000), no. 6, pp. 417–437.Google Scholar
Szmielew, W., Elementary properties of Abelian groups. Fundamenta Mathematicae, vol. 41 (1955), pp. 203–271.Google Scholar
Thomas, S., The classification problem for torsion-free abelian groups of finite rank. Journal of American Mathematical Society, vol. 16 (2003), no. 1, pp. 233–258.Google Scholar
Tsankov, T., The additive group of the rationals does not have an automatic presentation. Journal of Symbolic Logic, vol. 76 (2011), no. 4, pp. 1341–1351.Google Scholar
van der Waerden, B., Eine Bemerkung über die Unzerlebarkeit von Polynomen. Mathematische Annalen, vol. 102 (1930), no. 1, pp. 738–739.Google Scholar
Wehner, S., Enumerations, countable structures and Turing degrees. Proceedings of the American Mathematical Society, vol. 126 (1998), no. 7, pp. 2131–2139.Google Scholar