Word (group theory)

Word (group theory)

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"}. Words play an important role in the theory of free groups and presentations, and are central objects of study in combinatorial group theory.

Definition

Let "G" be a group, and let "S" be a subset of "G". A word in "S" is any expression of the form:s_1^{epsilon_1} s_2^{epsilon_2} cdots s_n^{epsilon_n}where "s"1,...,"sn" are elements of "S" and each "εi" is ±1. The number "n" is known as the length of the word.

Each word in "S" represents an element of "G", namely the product of the expression. By convention, the identity element can be represented by the empty word, which is the unique word of length zero.

Notation

When writing words, it is common to use exponential notation as an abbreviation. For example, the word:x x y^{-1} z y z z z x^{-1} x^{-1} ,could be written as:x^2 y^{-1} z y z^3 x^{-2}. ,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::x^2overline{y}zyz^3overline{x}^2. ,

Words and presentations

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::x^{-1} y x = y^2.,A set mathcal{R} of relations defines "G" if every relation in "G" follows logically from those in mathcal{R}, using the axioms for a group. A presentation for "G" is a pair langle S mid mathcal{R} angle, where "S" is a generating set for "G" and mathcal{R} is a defining set of relations.

For example, the Klein four-group can be defined by the presentation:langle i,j mid i^2 = 1,,j^2 = 1,,ij=ji angle.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 langle S angle. It is the smallest subgroup of "G" that contains the elements of "S".

Reduced words

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::y^{-1}zxx^{-1}y;;longrightarrow;;y^{-1}zy.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::xzy^{-1}xx^{-1}yz^{-1}zz^{-1}yz;;longrightarrow;;xyz.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 langle Smid; angle. 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.

Normal forms

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, ..., "rn-1", "s", "sr", "srn-1" are a normal form for the dihedral group Dih"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 "xmyn" for "m,n" ∈ Z are a normal form for the direct product of the cyclic groups 〈"x"〉 and 〈"y"〉.

Operations on words

The product of two words is obtained by concatenation::left(xzyz^{-1} ight)left(zy^{-1}x^{-1}y ight) = xzyz^{-1}zy^{-1}x^{-1}y.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::left(zy^{-1}x^{-1}y ight)^{-1}=y^{-1}xyz^{-1}.The product of a word with its inverse can be reduced to the empty word::zy^{-1}x^{-1}y ; y^{-1}xyz^{-1} ; longrightarrow;;1.

You can move a generator from the beginning to the end of a word by conjugation::x^{-1}left(xy^{-1}z^{-1}yz ight)x = y^{-1}z^{-1}yzx.

The word problem

Given a presentation langle Smid mathcal{R} angle 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 Sergeyevich Novikov in 1955 that there exists a finitely presented group "G" such that the word problem for "G" is undecidable harv|Novikov|1955.

References

*Citation
last = Epstein | first = David | author-link = David Epstein
last2 = Cannon | first2 = J. W. | last3 = Holt | first3 = D. F.
last4 = Levy | first4 = S. V. F.
last5 = Paterson | first5 = M. S.
last6 = Thurston | first6 = W. P. | author6-link=William Thurston
title = Word Processing in Groups | publisher = AK Peters | year = 1992 | isbn = 0-867-20244-0
.
*citation|last1=Novikov|first1=P. S.|author1-link=Pyotr Sergeyevich Novikov|title=On the algorithmic unsolvability of the word problem in group theory|journal=Trudy Mat. Inst. Steklov|volume=44|year=1955|pages=1–143|language=Russian
*cite book |author=Robinson, Derek John Scott |title=A course in the theory of groups |publisher=Springer-Verlag |location=Berlin |year=1996|isbn=0-387-94461-3
*cite book |author=Rotman, Joseph J. |title=An introduction to the theory of groups |publisher=Springer-Verlag |location=Berlin |year=1995|isbn=0-387-94285-8
*cite book |author=Schupp, Paul E.; Lyndon, Roger C. |title=Combinatorial group theory |publisher=Springer |location=Berlin |year=2001 |pages= |isbn=3-540-41158-5
*citation|last1=Solitar|first1=Donald|last2=Magnus|first2=Wilhelm|author2-link=Wilhelm Magnus|last3=Karrass|first3=Abraham |title=Combinatorial group theory: presentations of groups in terms of generators and relations |publisher=Dover|location=New York |year=2004 |isbn=0-486-43830-9
*cite book |author=Stillwell, John |title=Classical topology and combinatorial group theory |publisher=Springer-Verlag |location=Berlin |year=1993|isbn=0-387-97970-0


Wikimedia Foundation. 2010.

Игры ⚽ Нужно сделать НИР?

Look at other dictionaries:

  • Group theory — is a mathematical discipline, the part of abstract algebra that studies the algebraic structures known as groups. The development of group theory sprang from three main sources: number theory, theory of algebraic equations, and geometry. The… …   Wikipedia

  • Geometric group theory — is an area in mathematics devoted to the study of finitely generated groups via exploring the connections between algebraic properties of such groups and topological and geometric properties of spaces on which these groups act (that is, when the… …   Wikipedia

  • Combinatorial group theory — In mathematics, combinatorial group theory is the theory of free groups, and the concept of a presentation of a group by generators and relations. It is much used in geometric topology, the fundamental group of a simplicial complex having in a… …   Wikipedia

  • Growth rate (group theory) — In group theory, the growth rate of a group with respect to a symmetric generating set describes the size of balls in the group. Every element in the group can be written as a product of generators, and the growth rate counts the number of… …   Wikipedia

  • List of group theory topics — Contents 1 Structures and operations 2 Basic properties of groups 2.1 Group homomorphisms 3 Basic types of groups …   Wikipedia

  • Matsumoto's theorem (group theory) — In algebra, Matsumoto s theorem, proved by Hideya Matsumoto (1964), gives conditions for two reduced words of a Coxeter group to represent the same element. Statement If two reduced words represent the same element of a Coxeter group, then… …   Wikipedia

  • Word (disambiguation) — A word is a unit of language. Word(s) may also refer to:In computing: *Word (computing), a group of bits or digits/characters processed as a unit *words (Unix), a standard file in UNIX *Microsoft Word, a word processing application *William… …   Wikipedia

  • Word problem for groups — In mathematics, especially in the area of abstract algebra known as combinatorial group theory, the word problem for a recursively presented group G is the algorithmic problem of deciding whether two words represent the same element. Although it… …   Wikipedia

  • Word metric — In group theory, a word metric on a group G is a way to measure distance between any two elements of G . As the name suggests, the word metric is a metric on G , assigning to any two elements g , h of G a distance d(g,h) that measures how… …   Wikipedia

  • Group (mathematics) — This article covers basic notions. For advanced topics, see Group theory. The possible manipulations of this Rubik s Cube form a group. In mathematics, a group is an algebraic structure consisting of a set together with an operation that combines …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”