Some undecidable problems in group theory

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 Q of such decision problems and a construction A such that if P is a problem in Q, then A(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. In the past 20 years there has been a rash of undecidability results for finitely presented groups. Some of these are the conjugacy problem [12], the word problem ([4,] [13]), the isomorphism problem ([1], [14]), the center problem [2], and many others (see [2] for a collection of other examples). With the single exception of the Adjan-Rabin theorem, which shows the undecidability of the isomorphism problem, each of these results is obtained by providing a construction for the particular problem in question, and then concluding the desired unsolvability from peculiarities of the construction. The Adjan-Rabin theorem, on the other hand, gives a general construction which can be applied to any Markov property P of finitely presented groups, and from which one can conclude the impossibility of deciding which presentations present groups enjoying P. In this paper we obtain general results for undecidable first order decision problems (that is, problems about elements in a particular group, such as the word and conjugacy problems). We shall describe a class Q of such decision problems and a construction A such that if P is a problem in Q, then A(P) will be a finitely presented group in which P is recursively undecidable. The following list tabulates some problems in Q (the (?x)( ) notation Received by the editors November 4, 1971. AMS 1970 suibject classifications. Primary 02F47, 02H15, 20A10, 20E30, 20F10. 1 This research conducted at the University of Illinois, while the author held an NSF Traineeship. ( American Mathematical Society 1972