Word (mathematics)

Get Word Mathematics essential facts below. View Videos or join the Word Mathematics discussion. Add Word Mathematics to your PopFlock.com topic list for future reference or share this resource on social media.
## Definition

## Notation

## Words and presentations

## Reduced words

## Normal forms

## Operations on words

## The word problem

## Notes

## References

This article uses material from the Wikipedia page available here. It is released under the Creative Commons Attribution-Share-Alike License 3.0.

Word Mathematics

In group theory, a **word** is any written product of group elements and their inverses. For example, if *x*, *y* and *z* are elements of a group *G*, then *xy*, *z*^{-1}*xzz* and *y*^{-1}*zxx*^{-1}*yz*^{-1} are words in the set {*x*, *y*, *z*}. Two different words may evaluate to the same value in *G*,^{[1]} or even in every group.^{[2]} Words play an important role in the theory of free groups and presentations, and are central objects of study in combinatorial group theory.

Let *G* be a group, and let *S* be a subset of *G*. A **word in S** is any expression of the form

where *s*_{1},...,*s _{n}* are elements of

Each word in *S* represents an element of *G*, namely the product of the expression. By convention, the **identity** (unique)^{[3]} element can be represented by the **empty word**, which is the unique word of length zero.

When writing words, it is common to use exponential notation as an abbreviation. For example, the word

could be written as

This latter expression is not a word itself—it is simply a shorter notation for the original.

When dealing with long words, it can be helpful to use an overline to denote inverses of elements of *S*. Using overline notation, the above word would be written as follows:

A subset *S* of a group *G* is called a generating set if every element of *G* can be represented by a word in *S*. If *S* is a generating set, a **relation** is a pair of words in *S* that represent the same element of *G*. These are usually written as equations, e.g.
A set of relations **defines G** if every relation in

For example, the Klein four-group can be defined by the presentation

Here 1 denotes the empty word, which represents the identity element.

When *S* is not a generating set for *G*, the set of elements represented by words in *S* is a subgroup of *G*. This is known as the **subgroup of G generated by S**, and is usually denoted . It is the smallest subgroup of

Any word in which a generator appears next to its own inverse (*xx*^{-1} or *x*^{-1}*x*) can be simplified by omitting the redundant pair:

This operation is known as **reduction**, and it does not change the group element represented by the word. (Reductions can be thought of as relations that follow from the group axioms.)

A **reduced word** is a word that contains no redundant pairs. Any word can be simplified to a reduced word by performing a sequence of reductions:

The result does not depend on the order in which the reductions are performed.

If *S* is any set, the free group over *S* is the group with presentation . That is, the free group over *S* is the group generated by the elements of *S*, with no extra relations. Every element of the free group can be written uniquely as a reduced word in *S*.

A word is **cyclically reduced** if and only if every cyclic permutation of the word is reduced.

A **normal form** for a group *G* with generating set *S* is a choice of one reduced word in *S* for each element of *G*. For example:

- The words 1,
*i*,*j*,*ij*are a normal form for the Klein four-group. - The words 1,
*r*,*r*^{2}, ...,*r*,^{n-1}*s*,*sr*, ...,*sr*are a normal form for the dihedral group Dih^{n-1}_{n}. - The set of reduced words in
*S*are a normal form for the free group over*S*. - The set of words of the form
*x*for^{m}y^{n}*m,n*?**Z**are a normal form for the direct product of the cyclic groups ?*x*? and ?*y*?.

The **product** of two words is obtained by concatenation:

Even if the two words are reduced, the product may not be.

The **inverse** of a word is obtained by inverting each generator, and switching the order of the elements:

The product of a word with its inverse can be reduced to the empty word:

You can move a generator from the beginning to the end of a word by conjugation:

Given a presentation for a group *G*, the **word problem** is the algorithmic problem of deciding, given as input two words in *S*, whether they represent the same element of *G*. The word problem is one of three algorithmic problems for groups proposed by Max Dehn in 1911. It was shown by Pyotr Novikov in 1955 that there exists a finitely presented group *G* such that the word problem for *G* is undecidable.(Novikov 1955)

**^**for example, f_{d}r_{1}and r_{1}f_{c}in the group of square symmetries**^**for example,*xy*and*xzz*^{-1}*y***^**Uniqueness of identity element and inverses

- Epstein, David; Cannon, J. W.; Holt, D. F.; Levy, S. V. F.; Paterson, M. S.; Thurston, W. P. (1992).
*Word Processing in Groups*. AK Peters. ISBN 0-86720-244-0.. - Novikov, P. S. (1955). "On the algorithmic unsolvability of the word problem in group theory".
*Trudy Mat. Inst. Steklov*(in Russian).**44**: 1-143.CS1 maint: ref=harv (link) - Robinson, Derek John Scott (1996).
*A course in the theory of groups*. Berlin: Springer-Verlag. ISBN 0-387-94461-3. - Rotman, Joseph J. (1995).
*An introduction to the theory of groups*. Berlin: Springer-Verlag. ISBN 0-387-94285-8. - Schupp, Paul E; Lyndon, Roger C. (2001).
*Combinatorial group theory*. Berlin: Springer. ISBN 3-540-41158-5. - Solitar, Donald; Magnus, Wilhelm; Karrass, Abraham (2004).
*Combinatorial group theory: presentations of groups in terms of generators and relations*. New York: Dover. ISBN 0-486-43830-9. - Stillwell, John (1993).
*Classical topology and combinatorial group theory*. Berlin: Springer-Verlag. ISBN 0-387-97970-0.

This article uses material from the Wikipedia page available here. It is released under the Creative Commons Attribution-Share-Alike License 3.0.

Popular Products

Music Scenes

Popular Artists