reduced word (original) (raw)

The word w=w1⁢w2⁢…⁢wn∈(X∐X-1)∗ is called reduced when wj≠wj+1-1 for each j∈{1,2,…,n-1}.

Now, starting from a word w=w1⁢w2⁢…⁢wn∈(X∐X-1)∗, we can iteratively erase factors wj⁢wj+1 from w whenever wj=wj+1-1, and this iterative process, that we call reductionPlanetmathPlanetmath of w, produce a reduced word w′∈(X∐X-1)∗. At each step of the process there may be more than one couple of adiacent letters candidate to be erased, so we may ask if different sequencesPlanetmathPlanetmath of erasing may produce different reduced words. The following theorem answers the question.

Theorem 1

Each couple of reduction of a same word w∈(X∐X-1)∗ produce the same reduced word w′∈(X∐X-1)∗.

The unique reduced word w′ is called the reduced form of w. Thus there exists a well define map red:(X∐X-1)∗→(X∐X-1)∗ that send a word w to his reduced form red⁢(w).

We can use the map red to build the free groupMathworldPlanetmath on X in the following way. Let FG⁢(X)=red⁢((X∐X-1)+) be the set of reduced words on (X∐X-1), i.e.

| FG⁢(X)=red⁢((X∐X-1)+)={red⁢(w)|w∈(X∐X-1)+}={w∈(X∐X-1)+|w=red⁢(u)}. | | -------------------------------------------------------------------------- |

Note that red⁢((X∐X-1)∗)=red⁢((X∐X-1)+), being that red⁢(x⁢x-1)=ε, where ε denotes the empty word. Now, we define a productMathworldPlanetmathPlanetmathPlanetmath ⋅ on FG⁢(X) that makes it a group: given v,w∈FG⁢(X) we define

i.e. v⋅w is the reduced form of the juxtaposition of the words v and w. The we have the following result.

Theorem 2

FG⁢(X) with the product ⋅ is a group. Moreover, it is the free group on X, in the sense that it solves the following universal problem: given a group G and a map Φ:X→G, a group homomorphismMathworldPlanetmath Φ¯:FG⁢(X)→G exists such that the following diagram commutes:

\xymatrix⁢&⁢X⁢\ar⁢[r]ι⁢\ar⁢[d]Φ⁢&⁢FG⁢(X)⁢\ar⁢[d⁢l]Φ¯⁢&⁢G⁢&

where ι:X→FG⁢(X) is the inclusion mapMathworldPlanetmath.

It is well known from universal algebraMathworldPlanetmathPlanetmath that FG⁢(X) is unique up to isomorphismsMathworldPlanetmathPlanetmathPlanetmathPlanetmathPlanetmathPlanetmathPlanetmath. With this construction, the map red:(X∐X-1)+→FG⁢(X) [resp. red:(X∐X-1)∗→FG⁢(X)] is the quotient projectionPlanetmathPlanetmath from the free semigroup with involution on X [resp. the free monoid with involution on X] and the free group on X.

References