Some undecidable problems in group theory

Sacerdote, George S.

doi:10.1090/S0002-9939-1972-0320119-6

Some undecidable problems in group theory
HTML articles powered by AMS MathViewer

by George S. Sacerdote PDF

Proc. Amer. Math. Soc. 36 (1972), 231-238 Request permission

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

S. I. Adyan, On algorithmic problems in effectively complete classes of groups, Dokl. Akad. Nauk SSSR 123 (1958), 13–16 (Russian). MR 0103217
Gilbert Baumslag, W. W. Boone, and B. H. Neumann, Some unsolvable problems about elements and subgroups of groups, Math. Scand. 7 (1959), 191–201. MR 163948, DOI 10.7146/math.scand.a-10572

Certain simple, unsolvable problems of group theory

57, 58, 60

16

17

19

16

20

William W. Boone, The word problem, Ann. of Math. (2) 70 (1959), 207–265. MR 179237, DOI 10.2307/1970103

On the word, order, and power problems in finitely presented groups

M. Dehn, Über unendliche diskontinuierliche Gruppen, Math. Ann. 71 (1911), no. 1, 116–144 (German). MR 1511645, DOI 10.1007/BF01456932
Roger C. Lyndon, Properties preserved under homomorphism, Pacific J. Math. 9 (1959), 143–154. MR 108441
Roger C. Lyndon, On Dehn’s algorithm, Math. Ann. 166 (1966), 208–228. MR 214650, DOI 10.1007/BF01361168
Wilhelm Magnus, Abraham Karrass, and Donald Solitar, Combinatorial group theory: Presentations of groups in terms of generators and relations, Interscience Publishers [John Wiley & Sons], New York-London-Sydney, 1966. MR 0207802
Ju. I. Merzljakov, Positive formulae on free groups, Algebra i Logika Sem. 5 (1966), no. 4, 25–42 (Russian). MR 0222149
Charles F. Miller III, On group-theoretic decision problems and their classification, Annals of Mathematics Studies, No. 68, Princeton University Press, Princeton, N.J.; University of Tokyo Press, Tokyo, 1971. MR 0310044
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 0075196
P. S. Novikov, On the algorithmic insolvability of the word problem in group theory, American Mathematical Society Translations, Ser. 2, Vol. 9, American Mathematical Society, Providence, R.I., 1958, pp. 1–122. MR 0092784
Michael O. Rabin, Recursive unsolvability of group theoretic problems, Ann. of Math. (2) 67 (1958), 172–194. MR 110743, DOI 10.2307/1969933
George S. Sacerdote, Elementary properties of free groups, Trans. Amer. Math. Soc. 178 (1973), 127–138. MR 320146, DOI 10.1090/S0002-9947-1973-0320146-4

Almost all free products have the same positive theory

Paul E. Schupp, On Dehn’s algorithm and the conjugacy problem, Math. Ann. 178 (1968), 119–130. MR 237620, DOI 10.1007/BF01350654