Lesson plan

Word problem for groups

In mathematics, especially in the area of abstract algebra known as combinatorial group theory, the word problem for a finitely generated group G is the algorithmic problem of deciding whether two words in the generators represent the same element of G . The word problems for certain groups provide well-known examples of undecidable problems. If A is a finite set of generators for G , then the word problem is the membership problem for the formal language of all words in A and a formal set of inverses that map to the identity under the natural map from the free monoid with involution on A to the group G . If B is another finite generating set for G , then the word problem over the generating set B is equivalent to the word problem over the generating set A . Thus one can speak unambiguously of the decidability of the word problem for the finitely generated group G . The related but different uniform word problem for a class K of recursively presented groups is the algorithmic problem of deciding, given as input a presentation P for a group G in the class K and two words in the generators of G , whether the words represent the same element of G . Some authors require the class K to be definable by a recursively enumerable set of presentations.

Back to article

Article summary

In mathematics, especially in the area of abstract algebra known as combinatorial group theory, the word problem for a finitely generated group G is the algorithmic problem of deciding whether two words in the generators represent the same element of G . The word problems for certain groups provide well-known examples of undecidable problems. If A is a finite set of generators for G , then the word problem is the membership problem for the formal language of all words in A and a formal set of inverses that map to the identity under the natural map from the free monoid with involution on A to the group G . If B is another finite generating set for G , then the word problem over the generating set B is equivalent to the word problem over the generating set A . Thus one can speak unambiguously of the decidability of the word problem for the finitely generated group G . The related but different uniform word problem for a class K of recursively presented groups is the algorithmic problem of deciding, given as input a presentation P for a group G in the class K and two words in the generators of G , whether the words represent the same element of G . Some authors require the class K to be definable by a recursively enumerable set of presentations.

Key claims

No claims recorded.

Discussion questions

  1. Summarise the article in your own words. Which single claim would you verify first, and why?
  2. Which claim in this article is most likely to be revised as the sources update? How would you check its current status?
  3. If two sources disagreed about one of these facts, what would you need in order to trust one over the other?

Bibliography

No sources recorded.

Key claims and bibliography are generated from the same tracked claims and sources as the article page.