Finitely presented expansions of groups, semigroups, and algebras
HTML articles powered by AMS MathViewer
- by Bakhadyr Khoussainov and Alexei Miasnikov PDF
- Trans. Amer. Math. Soc. 366 (2014), 1455-1474 Request permission
Abstract:
Finitely presented algebraic systems, such as groups and semigroups, are of foundational interest in algebra and computation. Finitely presented algebraic systems necessarily have a computably enumerable (c.e. for short) word equality problem and these systems are finitely generated. Call finitely generated algebraic systems with a c.e. word equality problem computably enumerable. Computably enumerable finitely generated algebraic systems are not necessarily finitely presented. This paper is concerned with finding finitely presented expansions of finitely generated c.e. algebraic systems. The method of expansions of algebraic systems, such as turning groups into rings or distinguishing elements in the underlying algebraic systems, is an important method used in algebra, model theory, and in various areas of theoretical computer science. Bergstra and Tucker proved that all c.e. algebraic systems with decidable word problem possess finitely presented expansions. Then they, and, independently, Goncharov asked if every finitely generated c.e. algebraic system has a finitely presented expansion. In this paper we build examples of finitely generated c.e. semigroups, groups, and algebras that fail to possess finitely presented expansions, thus answering the question of Bergstra-Tucker and Goncharov for the classes of semigroups, groups and algebras. We also construct an example of a residually finite, infinite, and algorithmically finite group, thus answering the question of Miasnikov and Osin. Our constructions are based on the interplay between key concepts and known results from computability theory (such as simple and immune sets) and algebra (such as residual finiteness and the theorem of Golod-Shafaverevich).References
- J. A. Bergstra and J. V. Tucker, Initial and final algebra semantics for data type specifications: two characterization theorems, SIAM J. Comput. 12 (1983), no. 2, 366–387. MR 697167, DOI 10.1137/0212024
- J. A. Bergstra and J. V. Tucker, Algebraic specifications of computable and semicomputable data types, Theoret. Comput. Sci. 50 (1987), no. 2, 137–181. MR 907280, DOI 10.1016/0304-3975(87)90123-X
- Douglas Cenzer, S. Ali Dashti, and Jonathan L. F. King, Computable symbolic dynamics, MLQ Math. Log. Q. 54 (2008), no. 5, 460–469. MR 2451907, DOI 10.1002/malq.200710066
- E. S. Golod, On nil-algebras and finitely approximable $p$-groups, Izv. Akad. Nauk SSSR Ser. Mat. 28 (1964), 273–276 (Russian). MR 0161878
- E. S. Golod and I. R. Šafarevič, On the class field tower, Izv. Akad. Nauk SSSR Ser. Mat. 28 (1964), 261–272 (Russian). MR 0161852
- George Grätzer, Universal algebra, D. Van Nostrand Co., Inc., Princeton, N.J.-Toronto, Ont.-London, 1968. MR 0248066
- Logic Notebook (Open questions in Logic), Novosibirsk University Press, editors Yu. Ershov and S. Goncharov, 1989.
- Yu. L. Ershov, S. S. Goncharov, A. Nerode, J. B. Remmel, and V. W. Marek (eds.), Handbook of recursive mathematics. Vol. 1, Studies in Logic and the Foundations of Mathematics, vol. 138, North-Holland, Amsterdam, 1998. Recursive model theory. MR 1673617
- Edward R. Griffor (ed.), Handbook of computability theory, Studies in Logic and the Foundations of Mathematics, vol. 140, North-Holland Publishing Co., Amsterdam, 1999. MR 1721236
- N. K. Kassymov, On Finitely Approximable and R.E. Representable Algebras, Algebra and Logic, 26, No 6, 1986.
- Bakhadyr Khoussainov, Randomness, computability, and algebraic specifications, Ann. Pure Appl. Logic 91 (1998), no. 1, 1–15. MR 1601610, DOI 10.1016/S0168-0072(97)00040-7
- B. Khoussainov, D. Hirschfeldt. On finitely presented expansions of semigroups. Algebra and Logic. Submitted.
- 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 the general theory of algebraic systems, Mat. Sb. N.S. 35(77) (1954), 3–20 (Russian). MR 0065533
- K. Meinke and J. V. Tucker, Universal algebra, Handbook of logic in computer science, Vol. 1, Handb. Log. Comput. Sci., vol. 1, Oxford Univ. Press, New York, 1992, pp. 189–411. MR 1426365
- Ilya Kapovich, Alexei Myasnikov, Paul Schupp, and Vladimir Shpilrain, Generic-case complexity, decision problems in group theory, and random walks, J. Algebra 264 (2003), no. 2, 665–694. MR 1981427, DOI 10.1016/S0021-8693(03)00167-4
- Alexei Miasnikov and Denis Osin, Algorithmically finite groups, J. Pure Appl. Algebra 215 (2011), no. 11, 2789–2796. MR 2802165, DOI 10.1016/j.jpaa.2011.03.019
- Joseph S. Miller, Two notes on subshifts, Proc. Amer. Math. Soc. 140 (2012), no. 5, 1617–1622. MR 2869146, DOI 10.1090/S0002-9939-2011-11000-1
- 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
- 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
- V. Stoltenberg-Hansen and J. V. Tucker, Effective algebras, Handbook of logic in computer science, Vol. 4, Handb. Log. Comput. Sci., vol. 4, Oxford Univ. Press, New York, 1995, pp. 357–526. MR 1365757
Additional Information
- Bakhadyr Khoussainov
- Affiliation: Department of Computer Science, The University of Auckland, Auckland, New Zealand
- Email: bmk@cs.auckland.ac.nz
- Alexei Miasnikov
- Affiliation: Department of Mathematics, Stevens Institute of Technology, Hoboken, New Jersey 07030
- MR Author ID: 670299
- Email: amiasnik@stevens.edu
- Received by editor(s): February 8, 2012
- Published electronically: October 23, 2013
- Additional Notes: The authors were partially supported by Marsden Fund, Royal New Zealand Society.
- © Copyright 2013 American Mathematical Society
- Journal: Trans. Amer. Math. Soc. 366 (2014), 1455-1474
- MSC (2010): Primary 03D45, 03D50, 03D80; Secondary 03D40, 20F05
- DOI: https://doi.org/10.1090/S0002-9947-2013-05898-9
- MathSciNet review: 3145738