Hostname: page-component-cd9895bd7-fscjk Total loading time: 0 Render date: 2024-12-23T23:42:06.867Z Has data issue: false hasContentIssue false
  • English
  • Français

An algebraic characterization of groups with soluble word problem1

Published online by Cambridge University Press:  09 April 2009

William W. Boone  and
Graham Higman
William W. Boone
Affiliation:
University of Illinois, Urbana-Champaign, Illinois, U.S.A.
Graham Higman
Affiliation:
Mathematical Institute, University of Oxford, 24-29 St Giles, Oxford OXI, 3LB, England.
Rights & Permissions [Opens in a new window]

Extract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

The following theorem is the focal point of the present paper. It stipulates an algebraic condition equivalent, in any finitely generated group, to the solubility of the word problem.

THEOREM I. A necessary and sufficient condition that a finitely generated group G have a soluble word problem is that there exist a simple group H, and a finitely presented group K, such that G is a subgroup of H, and H is a subgroup of K.

Type
Research Article
Information
Journal of the Australian Mathematical Society , Volume 18 , Issue 1 , August 1974 , pp. 41 - 53
Copyright
Copyright © Australian Mathematical Society 1974

References

[1]Aanderaa, S., ‘A proof of Higman's embedding theorem, using Britton extensions of groups’, 1–17 of Word problems: decision problems and the Burnside problem in group theory, W. W. Boone, F. B. Cannonito, R. C. Lyndon, editors, Studies in Logic and Foundations of Mathematics Series, North-Holland Publishing Company, Amsterdam-London, 1973.CrossRefGoogle Scholar
[2]Boone, W. W., ‘Word problems and recursively enumerable degrees of unsolvability. A first paper on Thue systems’, Annals of Mathematics 83 (1966), 520–571.CrossRefGoogle Scholar
[3]Boone, W. W., ‘Word problems and recursively enumerable degrees of unsolvability. A sequel on finitely presented groups’, Annals of Mathematics 84 (1966), 49–84.CrossRefGoogle Scholar
[4]Boone, W. W., and Rogers, H. Jr, ‘On a problem of J. H. C. Whitehead and a problem of Alonzo Church’, Math. Scand. 19 (1966), 185–192.CrossRefGoogle Scholar
[5]Britton, J. L., ‘The word problem’, Annals of Mathematics 77 (1963), 16–32.CrossRefGoogle Scholar
[6]Clapham, C. R. J., ‘Finitely presented groups with word problems of arbitrary degrees of insolubility’, Proc. London Math. Soc. Series 3, 14 (1964), 633–676.CrossRefGoogle Scholar
[7]Clapham, C. R. J., ‘An embedding theorem for finitely generated groups’, Proc. London Math. Soc. (Ser. 3), 17 (1967), 419–430.CrossRefGoogle Scholar
[8]Fridman, A. A., Degrees of unsolubility of the problem of identity in finitely presented groups (in Russian), Izdalel'sto ‘Nauka’, Moscow 1967, 193.Google Scholar
[9]Hall, M. Jr, ‘The word problem for semi-groups with two generators’, J. Symbolic Logic, 14 (1949), 115–118.CrossRefGoogle Scholar
[10]Higman, G., ‘Subgroups of finitely presented groups’, Proceedings of the Royal Society A, 262 (1961), 455–475.Google Scholar
[11]Higman, G., Neumann, B. H., and Neumann, H., ‘Embedding theorems for groups’, J. London Math. Soc. 24 (1949), 247–254.CrossRefGoogle Scholar
[12]McKenzie, R. and Thompson, R. J., ‘Unsolvable word problems’, 457–478 of Word problems: decision problems and the Burnside problem in group theory. Publication data are above in reference [1].Google Scholar
[13]Markov, A. A., ‘Impossibility of algorithms for recognizing some properties of associative systems’ (in Russian), Doklady Akademii Nauk SSSR, 77 (1951), 953–956. (This paper can be understood completely from a review in The Journal of Symbolic Logic, 17 (1952), page 151, by A. Mostowski.)Google Scholar
[14]Markov, A. A., Theory of algorithms (published for the U.S. National Science Foundation by the Israd Program for Scientific Translations, 1961. Available from the Office of Technical Services, U.S. Department of Commerce).Google Scholar
[15]Miller, C. F., III, On group-theoretic decision problems and their classification, Annals of Mathematics Studies, No. 68 (Princeton University Press and University of Tokyo Press, 1971).Google Scholar
[16]Murskii, V. L., ‘Isomorphic embedding of a semi-group with an enumerable set of defining relations in a finitely presented semi-group’ D (in Russian), Mathem. Sametki, 1, (1967), 217–224.Google Scholar
[17]Rotman, J. J., The theory of groups: an introduction, second edition (Allyn and Bacon, Boston, 1973.)Google Scholar