Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)

 
 

 

Computable completely decomposable groups


Authors: Rodney Downey and Alexander G. Melnikov
Journal: Trans. Amer. Math. Soc. 366 (2014), 4243-4266
MSC (2010): Primary 03D45, 03C57
DOI: https://doi.org/10.1090/S0002-9947-2014-06115-1
Published electronically: April 14, 2014
MathSciNet review: 3206458
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: A completely decomposable group is an abelian group of the form $ \bigoplus _i H_i$, where $ H_i \leq (Q,+)$. We show that every computable completely decomposable group is $ \Delta ^0_5$-categorical. We construct a computable completely decomposable group which is not $ \Delta ^0_4$-categorical, and give an example of a computable completely decomposable group $ G$ which is $ \Delta ^0_4$-categorical but not $ \Delta ^0_3$-categorical. We also prove that the index set of computable completely decomposable groups is arithmetical.


References [Enhancements On Off] (What's this?)

  • [1] David M. Arnold, Finite rank torsion free abelian groups and rings, Lecture Notes in Mathematics, vol. 931, Springer-Verlag, Berlin, 1982. MR 665251 (84d:20002)
  • [2] C. J. Ash and J. Knight, Computable structures and the hyperarithmetical hierarchy, Studies in Logic and the Foundations of Mathematics, vol. 144, North-Holland Publishing Co., Amsterdam, 2000. MR 1767842 (2001k:03090)
  • [3] C. J. Ash, Recursive labelling systems and stability of recursive structures in hyperarithmetical degrees, Trans. Amer. Math. Soc. 298 (1986), no. 2, 497-514. MR 860377 (87j:03060), https://doi.org/10.2307/2000633
  • [4] Reinhold Baer, Abelian groups without elements of finite order, Duke Math. J. 3 (1937), no. 1, 68-122. MR 1545974, https://doi.org/10.1215/S0012-7094-37-00308-9
  • [5] Ewan J. Barker, Back and forth relations for reduced abelian $ p$-groups, Ann. Pure Appl. Logic 75 (1995), no. 3, 223-249. MR 1355134 (96j:03066), https://doi.org/10.1016/0168-0072(94)00045-5
  • [6] M. C. R. Butler, A class of torsion-free abelian groups of finite rank, Proc. London Math. Soc. (3) 15 (1965), 680-698. MR 0218446 (36 #1532)
  • [7] R. Downey, A. Kach, and D. Turetsky, Limitwise monotonic functions and applications, Proceedings of STACS 2012, 2011, pp. 56-85.
  • [8] Rodney Downey and Alexander G. Melnikov, Effectively categorical abelian groups, J. Algebra 373 (2013), 223-248. MR 2995024, https://doi.org/10.1016/j.jalgebra.2012.09.020
  • [9] R. G. Downey, Computability theory and linear orderings, Handbook of recursive mathematics, Vol. 2, Stud. Logic Found. Math., vol. 139, North-Holland, Amsterdam, 1998, pp. 823-976. MR 1673590 (2000j:03059), https://doi.org/10.1016/S0049-237X(98)80047-5
  • [10] Rod Downey and Antonio Montalbán, The isomorphism problem for torsion-free abelian groups is analytic complete, J. Algebra 320 (2008), no. 6, 2291-2300. MR 2437501 (2009e:20122), https://doi.org/10.1016/j.jalgebra.2008.06.007
  • [11] Rod Downey and J. B. Remmel, Questions in computable algebra and combinatorics, Computability theory and its applications (Boulder, CO, 1999) Contemp. Math., vol. 257, Amer. Math. Soc., Providence, RI, 2000, pp. 95-125. MR 1770737 (2001i:03094), https://doi.org/10.1090/conm/257/04030
  • [12] Rodney G. Downey, On presentations of algebraic structures, Complexity, logic, and recursion theory, Lecture Notes in Pure and Appl. Math., vol. 187, Dekker, New York, 1997, pp. 157-205. MR 1455136 (98k:03099)
  • [13] Rodney G. Downey, Sergei S. Goncharov, Asher M. Kach, Julia F. Knight, Oleg V. Kudinov, Alexander G. Melnikov, and Daniel Turetsky, Decidability and computability of certain torsion-free abelian groups, Notre Dame J. Form. Log. 51 (2010), no. 1, 85-96. MR 2666571 (2011f:03060), https://doi.org/10.1215/00294527-2010-006
  • [14] Yuri L. Ershov and Sergei S. Goncharov, Constructive models, Siberian School of Algebra and Logic, Consultants Bureau, New York, 2000. MR 1749622 (2002a:03069)
  • [15] A. Fröhlich and J. C. Shepherdson, Effective procedures in field theory, Philos. Trans. Roy. Soc. London. Ser. A. 248 (1956), 407-432. MR 0074349 (17,570d)
  • [16] László Fuchs, Infinite abelian groups. Vol. I, Pure and Applied Mathematics, Vol. 36, Academic Press, New York, 1970. MR 0255673 (41 #333)
  • [17] László Fuchs, Infinite abelian groups. Vol. II, Academic Press, New York, 1973. Pure and Applied Mathematics. Vol. 36-II. MR 0349869 (50 #2362)
  • [18] Abelian group theory and related topics, Contemporary Mathematics, vol. 171, American Mathematical Society, Providence, RI, 1994. Edited by Rüdiger Göbel, Paul Hill and Wolfgang Liebert. MR 1293127 (95c:20002)
  • [19] S. S. Gončarov, Autostability of models and abelian groups, Algebra i Logika 19 (1980), no. 1, 23-44, 132 (Russian). MR 604656 (82g:03081)
  • [20] Sergei S. Goncharov, Countable Boolean algebras and decidability, Siberian School of Algebra and Logic, Consultants Bureau, New York, 1997. MR 1444819 (98h:03044b)
  • [21] K Harris, Categoricity in boolean algebras, to appear.
  • [22] Handbook of algebra. Vol. 2, North-Holland, Amsterdam, 2000. Edited by M. Hazewinkel. MR 1759594 (2001b:00003)
  • [23] Grete Hermann, Die Frage der endlich vielen Schritte in der Theorie der Polynomideale, Math. Ann. 95 (1926), no. 1, 736-788 (German). MR 1512302, https://doi.org/10.1007/BF01206635
  • [24] A. Kach, K. Lange, and D. Solomon, Orders on computable torsion-free abelian groups, to appear.
  • [25] I. Kalimullin, B. Khoussainov, and A. Melnikov, Limitwise monotonic sequences and degree spectra of structures, to appear.
  • [26] N. G. Khisamiev, Constructive abelian groups, Handbook of recursive mathematics, Vol. 2, Stud. Logic Found. Math., vol. 139, North-Holland, Amsterdam, 1998, pp. 1177-1231. MR 1673602 (2000d:03093), https://doi.org/10.1016/S0049-237X(98)80050-5
  • [27] N. G. Khisamiev, On a class of strongly decomposable abelian groups, Algebra Logika 41 (2002), no. 4, 493-509, 511-512 (Russian, with Russian summary); English transl., Algebra Logic 41 (2002), no. 4, 274-283. MR 1950578 (2003m:20072), https://doi.org/10.1023/A:1020112806274
  • [28] N. G. Khisamiev and A. A. Krykpaeva, Effectively completely decomposable abelian groups, Sibirsk. Mat. Zh. 38 (1997), no. 6, 1410-1412, iv (Russian, with Russian summary); English transl., Siberian Math. J. 38 (1997), no. 6, 1227-1229. MR 1618414 (99c:20075), https://doi.org/10.1007/BF02675949
  • [29] Friedrich Levi, Abelsche gruppen mit abzhlbaren elementen, Habilitationsschrift, Leipzig, Teubner, 1917.
  • [30] Adolf Mader, Almost completely decomposable groups, Algebra, Logic and Applications, vol. 13, Gordon and Breach Science Publishers, Amsterdam, 2000. MR 1751515 (2001c:20114)
  • [31] A. I. Malcev, Constructive algebras. I, Uspehi Mat. Nauk 16 (1961), no. 3 (99), 3-60 (Russian). MR 0151377 (27 #1362)
  • [32] A. I. Malcev, On recursive Abelian groups, Dokl. Akad. Nauk SSSR 146 (1962), 1009-1012 (Russian). MR 0151378 (27 #1363)
  • [33] A. I. Maltsev, Torsion-free abelian groups of finite rank, Mat. Sb. 4 (1938), no. 2, 45-68.
  • [34] Charles F. D. McCoy, $ \Delta ^0_2$-categoricity in Boolean algebras and linear orderings, Ann. Pure Appl. Logic 119 (2003), no. 1-3, 85-120. MR 1937847 (2004h:03094), https://doi.org/10.1016/S0168-0072(02)00035-0
  • [35] Alexander G. Melnikov, Enumerations and completely decomposable torsion-free abelian groups, Theory Comput. Syst. 45 (2009), no. 4, 897-916. MR 2529752 (2010m:03069), https://doi.org/10.1007/s00224-009-9175-9
  • [36] Alexander G. Melnikov, Computable ordered abelian groups and fields, Programs, proofs, processes, Lecture Notes in Comput. Sci., vol. 6158, Springer, Berlin, 2010, pp. 321-330. MR 2678144 (2012c:03121), https://doi.org/10.1007/978-3-642-13962-8_36
  • [37] G. Metakides and A. Nerode, Effective content of field theory, Ann. Math. Logic 17 (1979), no. 3, 289-320. MR 556895 (82b:03082), https://doi.org/10.1016/0003-4843(79)90011-1
  • [38] George Metakides and Anil Nerode, The introduction of nonrecursive methods into mathematics, The L. E. J. Brouwer Centenary Symposium (Noordwijkerhout, 1981) Stud. Logic Found. Math., vol. 110, North-Holland, Amsterdam, 1982, pp. 319-335. MR 717251 (85d:03121), https://doi.org/10.1016/S0049-237X(09)70135-1
  • [39] A.T. Nurtazin, Computable classes and algebraic criteria of autostability, Summary of Scientific Schools, Math. Inst., SB USSRAS, Novosibirsk, 1974.
  • [40] Michael O. Rabin, Computable algebra, general theory and theory of computable fields, Trans. Amer. Math. Soc. 95 (1960), 341-360. MR 0113807 (22 #4639)
  • [41] Hartley Rogers Jr., Theory of recursive functions and effective computability, 2nd ed., MIT Press, Cambridge, MA, 1987. MR 886890 (88b:03059)
  • [42] Rick L. Smith, 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 Math., vol. 859, Springer, Berlin, 1981, pp. 302-311. MR 619876 (83h:03064)
  • [43] 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 (88m:03003)
  • [44] B. L. van der Waerden, Moderne Algebra. Parts I and II, G. E. Stechert and Co., New York, 1943. MR 0009016 (5,88a)
  • [45] Bartel L. van der Waerden, Eine Bemerkung über die Unzerlegbarkeit von Polynomen, Math. Ann. 102 (1930), no. 1, 738-739 (German). MR 1512605, https://doi.org/10.1007/BF01782374

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC (2010): 03D45, 03C57

Retrieve articles in all journals with MSC (2010): 03D45, 03C57


Additional Information

Rodney Downey
Affiliation: School of Mathematics, Statistics and Operations Research, Victoria University of Wellington, P. O. Box 600, Wellington, New Zealand

Alexander G. Melnikov
Affiliation: Department of Mathematics, Nanyang Technological University, Singapore 639798 Singapore

DOI: https://doi.org/10.1090/S0002-9947-2014-06115-1
Received by editor(s): August 28, 2012
Published electronically: April 14, 2014
Additional Notes: We are thankful to Isaac Newton Institute for Mathematical Sciences and, more specifically, Semantics and Syntax: A Legacy of Alan Turing program, for partial support of our project. The first author thanks the Marsden Fund of New Zealand for its support. The second author’s research was also partially supported by SPMS, Nanyang Technological University, Singapore, and the University of Auckland, New Zealand. Many thanks to André Nies, Asher Kach and Kyle Riggs for pointing out numerous typos and minor mathematical problems in the early draft of the paper.
Article copyright: © Copyright 2014 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.

American Mathematical Society