The word problem for a group is just the generalized word problem for the trivial subgroup in since u = v holds in if and only if holds in , i.e. . Thus the existence of a group with undecidable word problem yields undecidability for the generalized word problem for this group as well. On the other hand, decidable word problem for a group does not imply decidable generalized word problem (for an overview on various decision problems for groups see e.g. [Mi91]).
Now due to the existence of inverses, the word problem for congruences on free groups can also be formulated as a special type of subgroup problem. Let T be a set of relations on a free group . Then we can associate a set to T by setting . Let be the normal closure6 of T1 in . Then in fact the word problem for the group can be reduced to the subgroup problem for since a relation u=v holds in if and only if holds in , i.e. . Notice that in general is not a finitely generated subgroup.
Subgroups of groups can be characterized by one-sided congruences on the
In the following we restrict ourselves to the case of right congruences (left congruences can be
introduced in a similar fashion).
be a subgroup of a group .
we can define
The fact that holds if and only if , is used in the proof of the next theorem, which states that the subgroup problem for a group is equivalent to a special instance of the right respectively left ideal membership problem in the corresponding group ring.