Finitely presented expansions of groups, semigroups, and algebras
Authors:
Bakhadyr Khoussainov and Alexei Miasnikov
Journal:
Trans. Amer. Math. Soc. 366 (2014), 14551474
MSC (2010):
Primary 03D45, 03D50, 03D80; Secondary 03D40, 20F05
Published electronically:
October 23, 2013
Fulltext PDF
Abstract 
References 
Similar Articles 
Additional Information
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 BergstraTucker 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 GolodShafaverevich).
 1.
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
(84d:68020), http://dx.doi.org/10.1137/0212024
 2.
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
(89f:68048), http://dx.doi.org/10.1016/03043975(87)90123X
 3.
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
(2009h:03084), http://dx.doi.org/10.1002/malq.200710066
 4.
E.
S. Golod, On nilalgebras and finitely approximable
𝑝groups, Izv. Akad. Nauk SSSR Ser. Mat. 28
(1964), 273–276 (Russian). MR 0161878
(28 #5082)
 5.
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 (28 #5056)
 6.
George
Grätzer, Universal algebra, D. Van Nostrand Co., Inc.,
Princeton, N.J.Toronto, Ont.London, 1968. MR 0248066
(40 #1320)
 7.
Logic Notebook (Open questions in Logic), Novosibirsk University Press, editors Yu. Ershov and S. Goncharov, 1989.
 8.
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,
NorthHolland, Amsterdam, 1998. Recursive model theory. MR 1673617
(99k:03003)
 9.
Edward
R. Griffor (ed.), Handbook of computability theory, Studies in
Logic and the Foundations of Mathematics, vol. 140, NorthHolland
Publishing Co., Amsterdam, 1999. MR 1721236
(2000e:03001)
 10.
N. K. Kassymov, On Finitely Approximable and R.E. Representable Algebras, Algebra and Logic, 26, No 6, 1986.
 11.
Bakhadyr
Khoussainov, Randomness, computability, and algebraic
specifications, Ann. Pure Appl. Logic 91 (1998),
no. 1, 1–15. MR 1601610
(98k:03098), http://dx.doi.org/10.1016/S01680072(97)000407
 12.
B. Khoussainov, D. Hirschfeldt. On finitely presented expansions of semigroups. Algebra and Logic. Submitted.
 13.
A.
I. Mal′cev, Constructive algebras. I, Uspehi Mat. Nauk
16 (1961), no. 3 (99), 3–60 (Russian). MR 0151377
(27 #1362)
 14.
A.
I. Mal′cev, On the general theory of algebraic systems,
Mat. Sb. N.S. 35(77) (1954), 3–20 (Russian). MR 0065533
(16,440e)
 15.
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
(97g:08004)
 16.
Ilya
Kapovich, Alexei
Miasnikov, Paul
Schupp, and Vladimir
Shpilrain, Genericcase complexity, decision problems in group
theory, and random walks, J. Algebra 264 (2003),
no. 2, 665–694. MR 1981427
(2005m:20080), http://dx.doi.org/10.1016/S00218693(03)001674
 17.
Alexei
Miasnikov and Denis
Osin, Algorithmically finite groups, J. Pure Appl. Algebra
215 (2011), no. 11, 2789–2796. MR 2802165
(2012e:20093), http://dx.doi.org/10.1016/j.jpaa.2011.03.019
 18.
Joseph
S. Miller, Two notes on subshifts, Proc. Amer. Math. Soc. 140 (2012), no. 5, 1617–1622. MR
2869146, http://dx.doi.org/10.1090/S000299392011110001
 19.
Michael
O. Rabin, Computable algebra, general theory and
theory of computable fields., Trans. Amer.
Math. Soc. 95
(1960), 341–360. MR 0113807
(22 #4639), http://dx.doi.org/10.1090/S00029947196001138074
 20.
Robert
I. Soare, Recursively enumerable sets and degrees,
Perspectives in Mathematical Logic, SpringerVerlag, Berlin, 1987. A study
of computable functions and computably generated sets. MR 882921
(88m:03003)
 21.
V.
StoltenbergHansen 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
(96m:68117)
 1.
 J. A. Bergstra, J. V. Tucker, Initial and Final Algebra Semantics for Data Type Specifications: Two characterization Theorems, SIAM J. Comput. 12, 1983. MR 697167 (84d:68020)
 2.
 J. A. Bergstra, J. V. Tucker, Algebraic Specifications of Computable and Semicomputable DataTypes, Theoretical Comp. science, 50, 1987. MR 907280 (89f:68048)
 3.
 D. Cenzer, S. A. Dashti, and J. L. F. King, Computable symbolic dynamics, Math. Log. Q. 54 (2008) 460469. MR 2451907 (2009h:03084)
 4.
 E. S. Golod, On nilalgebras and finitely approximable pgroups, Izv. Akad. Nauk SSSR Ser. Mat. 28 (1964), 273276. (Russian) MR 0161878 (28:5082)
 5.
 E. S. Golod, I. R. Shafarevich. On the class field tower, Izv. Akad. Nauk SSSSR 28: 261272 (in Russian), 1964. MR 0161852 (28:5056)
 6.
 G. Gratzer, Universal Algebra, Van Nostrand, Princeton, NJ, 1968. MR 0248066 (40:1320)
 7.
 Logic Notebook (Open questions in Logic), Novosibirsk University Press, editors Yu. Ershov and S. Goncharov, 1989.
 8.
 Handbook of Recursive Mathematics, Volume 1: Recursive Model Theory, Studies in Logic and the Foundations of Mathematics, 138, North Holland, 1998. MR 1673617 (99k:03003)
 9.
 Handbook of Computability Theory, E. Griffor (ed.), Elsevier, 1999. MR 1721236 (2000e:03001)
 10.
 N. K. Kassymov, On Finitely Approximable and R.E. Representable Algebras, Algebra and Logic, 26, No 6, 1986.
 11.
 B. Khoussainov. Randomness, computability, and algebraic specifications. Annals of Pure and Applied Logic, V 91, Issue 1, p.115, 1998. MR 1601610 (98k:03098)
 12.
 B. Khoussainov, D. Hirschfeldt. On finitely presented expansions of semigroups. Algebra and Logic. Submitted.
 13.
 A.I. Malcev, Constructive Algebras, Uspekhi Matem. Nauk, 16, No 3, 1961. MR 0151377 (27:1362)
 14.
 A. I. Malcev, On the general theory of algebraic systems (Russian). Mat. Sb. (N.S.) 35, 320, 1954. MR 0065533 (16:440e)
 15.
 K. Meinke and J. V. Tucker, Universal algebra. In S. Abramsky, D. Gabbay and T Maibaum (eds.), Handbook of Logic in Computer Science, 1992. MR 1426365 (97g:08004)
 16.
 I. Kapovich, A. Myasnikov, P. Schupp and V. Shpilrain, Generic case complexity, decision problems in group theory and random walks. J. Algebra, vol. 264, 665694, 2003. MR 1981427 (2005m:20080)
 17.
 Alexei Miasnikov, Denis Osin. Algorithmically finite groups. Journal of Pure and Applied Algebra, Volume 215, Issue 11, November 2011, pp. 27892796. MR 2802165 (2012e:20093)
 18.
 J. S. Miller, Two notes on subshifts, Proc. Amer. Math. Soc. 140 (2012), no. 5, 16171622. MR 2869146
 19.
 M. O. Rabin. Computable Algebra, General Theory and Theory of Computable Fields. Trans. AMS, 95, 341360, 1960. MR 0113807 (22:4639)
 20.
 R. I. Soare. Recursively Enumerable Sets and Degrees, SpringerVerlag, Berlin, 1987. MR 882921 (88m:03003)
 21.
 V. StoltenbergHansen and J. V. Tucker. Effective algebras. In S. Abramsky, D. Gabbay and T. Maibaum (eds.), Handbook of Logic in Computer Science. Volume IV: Semantic Modelling, Oxford University Press, 1995, pp. 357526. MR 1365757 (96m:68117)
Similar Articles
Retrieve articles in Transactions of the American Mathematical Society
with MSC (2010):
03D45,
03D50,
03D80,
03D40,
20F05
Retrieve articles in all journals
with MSC (2010):
03D45,
03D50,
03D80,
03D40,
20F05
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
Email:
amiasnik@stevens.edu
DOI:
http://dx.doi.org/10.1090/S000299472013058989
PII:
S 00029947(2013)058989
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.
Article copyright:
© Copyright 2013
American Mathematical Society
