Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)

 
 

 

Some undecidable problems in group theory


Author: George S. Sacerdote
Journal: Proc. Amer. Math. Soc. 36 (1972), 231-238
MSC: Primary 20A10; Secondary 02F47, 02G05
DOI: https://doi.org/10.1090/S0002-9939-1972-0320119-6
MathSciNet review: 0320119
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: In this paper we obtain general results for undecidable first order decision problems about groups (that is, problems about elements in a particular group, such as the word and conjugacy problems). We shall describe a class $ \Omega $ of such decision problems and a construction $ \Delta $ such that if P is a problem in $ \Omega $, then $ \Delta (P)$ will be a finitely presented group in which P is recursively undecidable. This work then yields an analog of the Adjan-Rabin theorem for quotient-closed properties.


References [Enhancements On Off] (What's this?)

  • [1] S. I. Adjan, On algorithmic problems in effectively complete classes of groups, Dokl. Akad. Nauk SSSR 123 (1958), 13-16. (Russian) MR 21 #1998. MR 0103217 (21:1998)
  • [2] G. Baumslag, W. W. Boone and B. H. Neumann, Some unsolvable problems about elements and subgroups of groups, Math. Scand. 7 (1959), 191-201. MR 29 #1247. MR 0163948 (29:1247)
  • [3] W. W. Boone, Certain simple, unsolvable problems of group theory. I-VI, Nederl. Akad. Wetensch. Proc. Ser. A 57, 58, 60=Indag. Math. 16 (1954), 231-237, 492-497; ibid. 17 (1955), 252-256, 571-577; ibid. 19 (1957), 22-27, 227-232. MR 16, 564; MR 20 #5230; #5231.
  • [4] -, The word problem, Ann. of Math. (2) 70 (1959), 207-265. MR 31 #3485. MR 0179237 (31:3485)
  • [5] D. J. Collins, On the word, order, and power problems in finitely presented groups, Proc. Irvine Conference on Decision Problems in Group Theory (to appear).
  • [6] M. Dehn, Über unendliche diskontinuierliche Gruppen, Math. Ann. 71 (1911), 116-144. MR 1511645
  • [7] R. C. Lyndon, Properties preserved under homomorphism, Pacific J. Math. 9. (1959), 143-154. MR 21 #7157. MR 0108441 (21:7157)
  • [8] -, On Dehn's algorithm, Math. Ann. 166 (1966), 208-228. MR 35 #5499. MR 0214650 (35:5499)
  • [9] W. Magnus, A. Karrass and D. Solitar, Combinatorial group theory: Presentations of groups in terms of generators and relations, Pure and Appl. Math., vol. 13, Interscience, New York, 1966. MR 34 #7617. MR 0207802 (34:7617)
  • [10] Ju. I. Merzljakov, Positive formulae on free groups, Algebra i Logika. Sem. 5 (1966), no. 4, 25-42. (Russian) MR 36 #5201. MR 0222149 (36:5201)
  • [11] C. F. Miller III, On group-theoretic decision problems and their classification, Ann. of Math. Studies, no. 68, Princeton Univ. Press, Princeton, N.J., 1971. MR 0310044 (46:9147)
  • [12] P. S. Novikov, Unsolvability of the conjugacy problem in the theory of groups, Izv. Akad. Nauk SSSR Ser. Mat. 18 (1954), 485-524. (Russian) MR 17, 706. MR 0075196 (17:706a)
  • [13] -, On the algorithmic insolvability of the word problem in group theory, Trudy Mat. Inst. Steklov. 44 (1955); English transl., Amer. Math. Soc. Transl. (2) 9 (1958), 1-122. MR 17, 706; MR 19, 1158. MR 0092784 (19:1158b)
  • [14] M. O. Rabin, Recursive unsolvability of group theoretic problems, Ann. of Math. (2) 67 (1958), 172-194. MR 22 #1611. MR 0110743 (22:1611)
  • [15] G. S. Sacerdote, Elementary properties of free groups, Trans. Amer. Math. Soc. (to appear). MR 0320146 (47:8686)
  • [16] -, Almost all free products have the same positive theory (to appear).
  • [17] P. E. Schupp, On Dehn's algorithm and the conjugacy problem, Math. Ann. 178 (1968), 119-130. MR 38 #5901. MR 0237620 (38:5901)

Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC: 20A10, 02F47, 02G05

Retrieve articles in all journals with MSC: 20A10, 02F47, 02G05


Additional Information

DOI: https://doi.org/10.1090/S0002-9939-1972-0320119-6
Article copyright: © Copyright 1972 American Mathematical Society

American Mathematical Society