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)



Finitely presented expansions of groups, semigroups, and algebras

Authors: Bakhadyr Khoussainov and Alexei Miasnikov
Journal: Trans. Amer. Math. Soc. 366 (2014), 1455-1474
MSC (2010): Primary 03D45, 03D50, 03D80; Secondary 03D40, 20F05
Published electronically: October 23, 2013
MathSciNet review: 3145738
Full-text 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 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 [Enhancements On Off] (What's this?)

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

Alexei Miasnikov
Affiliation: Department of Mathematics, Stevens Institute of Technology, Hoboken, New Jersey 07030

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

American Mathematical Society