Computable completely decomposable groups

Downey, Rodney; Melnikov, Alexander

doi:10.1090/S0002-9947-2014-06115-1

Computable completely decomposable groups
HTML articles powered by AMS MathViewer

by Rodney Downey and Alexander G. Melnikov PDF

Trans. Amer. Math. Soc. 366 (2014), 4243-4266 Request permission

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

David M. Arnold, Finite rank torsion free abelian groups and rings, Lecture Notes in Mathematics, vol. 931, Springer-Verlag, Berlin-New York, 1982. MR 665251
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
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, DOI 10.1090/S0002-9947-1986-0860377-7
Reinhold Baer, Abelian groups without elements of finite order, Duke Math. J. 3 (1937), no. 1, 68–122. MR 1545974, DOI 10.1215/S0012-7094-37-00308-9
Ewan J. Barker, Back and forth relations for reduced abelian $p$-groups, Ann. Pure Appl. Logic 75 (1995), no. 3, 223–249. MR 1355134, DOI 10.1016/0168-0072(94)00045-5
M. C. R. Butler, A class of torsion-free abelian groups of finite rank, Proc. London Math. Soc. (3) 15 (1965), 680–698. MR 218446, DOI 10.1112/plms/s3-15.1.680
R. Downey, A. Kach, and D. Turetsky, Limitwise monotonic functions and applications, Proceedings of STACS 2012, 2011, pp. 56–85.
Rodney Downey and Alexander G. Melnikov, Effectively categorical abelian groups, J. Algebra 373 (2013), 223–248. MR 2995024, DOI 10.1016/j.jalgebra.2012.09.020
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, DOI 10.1016/S0049-237X(98)80047-5
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, DOI 10.1016/j.jalgebra.2008.06.007
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, DOI 10.1090/conm/257/04030
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
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, DOI 10.1215/00294527-2010-006
Yuri L. Ershov and Sergei S. Goncharov, Constructive models, Siberian School of Algebra and Logic, Consultants Bureau, New York, 2000. MR 1749622, DOI 10.1007/978-1-4615-4305-3
A. Fröhlich and J. C. Shepherdson, Effective procedures in field theory, Philos. Trans. Roy. Soc. London Ser. A 248 (1956), 407–432. MR 74349, DOI 10.1098/rsta.1956.0003
László Fuchs, Infinite abelian groups. Vol. I, Pure and Applied Mathematics, Vol. 36, Academic Press, New York-London, 1970. MR 0255673
László Fuchs, Infinite abelian groups. Vol. II, Pure and Applied Mathematics. Vol. 36-II, Academic Press, New York-London, 1973. MR 0349869
Rüdiger Göbel, Paul Hill, and Wolfgang Liebert (eds.), Abelian group theory and related topics, Contemporary Mathematics, vol. 171, American Mathematical Society, Providence, RI, 1994. MR 1293127, DOI 10.1090/conm/171
S. S. Gončarov, Autostability of models and abelian groups, Algebra i Logika 19 (1980), no. 1, 23–44, 132 (Russian). MR 604656
Sergei S. Goncharov, Countable Boolean algebras and decidability, Siberian School of Algebra and Logic, Consultants Bureau, New York, 1997. MR 1444819
K Harris, Categoricity in boolean algebras, to appear.
M. Hazewinkel (ed.), Handbook of algebra. Vol. 2, Handbook of Algebra, vol. 2, Elsevier/North-Holland, Amsterdam, 2000. MR 1759594
Grete Hermann, Die Frage der endlich vielen Schritte in der Theorie der Polynomideale, Math. Ann. 95 (1926), no. 1, 736–788 (German). MR 1512302, DOI 10.1007/BF01206635
A. Kach, K. Lange, and D. Solomon, Orders on computable torsion-free abelian groups, to appear.
I. Kalimullin, B. Khoussainov, and A. Melnikov, Limitwise monotonic sequences and degree spectra of structures, to appear.
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, DOI 10.1016/S0049-237X(98)80050-5
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, DOI 10.1023/A:1020112806274
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, DOI 10.1007/BF02675949
Friedrich Levi, Abelsche gruppen mit abzhlbaren elementen, Habilitationsschrift, Leipzig, Teubner, 1917.
Adolf Mader, Almost completely decomposable groups, Algebra, Logic and Applications, vol. 13, Gordon and Breach Science Publishers, Amsterdam, 2000. MR 1751515
A. I. Mal′cev, Constructive algebras. I, Uspehi Mat. Nauk 16 (1961), no. 3 (99), 3–60 (Russian). MR 0151377
A. I. Mal′cev, On recursive Abelian groups, Dokl. Akad. Nauk SSSR 146 (1962), 1009–1012 (Russian). MR 0151378
A. I. Maltsev, Torsion-free abelian groups of finite rank, Mat. Sb. 4 (1938), no. 2, 45–68.
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, DOI 10.1016/S0168-0072(02)00035-0
Alexander G. Melnikov, Enumerations and completely decomposable torsion-free abelian groups, Theory Comput. Syst. 45 (2009), no. 4, 897–916. MR 2529752, DOI 10.1007/s00224-009-9175-9
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, DOI 10.1007/978-3-642-13962-8_{3}6
G. Metakides and A. Nerode, Effective content of field theory, Ann. Math. Logic 17 (1979), no. 3, 289–320. MR 556895, DOI 10.1016/0003-4843(79)90011-1
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, DOI 10.1016/S0049-237X(09)70135-1
A.T. Nurtazin, Computable classes and algebraic criteria of autostability, Summary of Scientific Schools, Math. Inst., SB USSRAS, Novosibirsk, 1974.
Michael O. Rabin, Computable algebra, general theory and theory of computable fields, Trans. Amer. Math. Soc. 95 (1960), 341–360. MR 113807, DOI 10.1090/S0002-9947-1960-0113807-4
Hartley Rogers Jr., Theory of recursive functions and effective computability, 2nd ed., MIT Press, Cambridge, MA, 1987. MR 886890
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-New York, 1981, pp. 302–311. MR 619876
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, DOI 10.1007/978-3-662-02460-7
B. L. van der Waerden, Moderne Algebra. Parts I and II, G. E. Stechert & Co., New York, 1943. MR 0009016
Bartel L. van der Waerden, Eine Bemerkung über die Unzerlegbarkeit von Polynomen, Math. Ann. 102 (1930), no. 1, 738–739 (German). MR 1512605, DOI 10.1007/BF01782374