请输入您要查询的字词:

 

单词 ReducedWord
释义

reduced word


Let X be a set, and (XX-1) the free monoid with involution on X. An element w(XX-1) can be uniquely written by juxtaposition of elements of (XX-1), i.e.

w=w1w2wn,wj(XX-1),

then we may improperly say that w is a word on (XX-1), considering (XX-1) simply as the free monoid on (XX-1).

The word w=w1w2wn(XX-1) is called reduced when wjwj+1-1 for each j{1,2,,n-1}.

Now, starting from a word w=w1w2wn(XX-1), we can iteratively erase factors wjwj+1 from w whenever wj=wj+1-1, and this iterative process, that we call reductionPlanetmathPlanetmath of w, produce a reduced word w(XX-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(XX-1) produce the same reduced word w(XX-1).

The unique reduced word w is called the reduced form of w. Thus there exists a well define map red:(XX-1)(XX-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((XX-1)+) be the set of reduced words on (XX-1), i.e.

FG(X)=red((XX-1)+)={red(w)|w(XX-1)+}={w(XX-1)+|w=red(u)}.

Note that red((XX-1))=red((XX-1)+), being that red(xx-1)=ε, where ε denotes the empty word. Now, we define a productMathworldPlanetmathPlanetmathPlanetmath on FG(X) that makes it a group: given v,wFG(X) we define

vw=red(vw),

i.e. vw 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 Φ:XG, a group homomorphismMathworldPlanetmath Φ¯:FG(X)G exists such that the following diagram commutes:

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

where ι:XFG(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:(XX-1)+FG(X) [resp. red:(XX-1)FG(X)] is the quotient projectionPlanetmathPlanetmath fromthe free semigroup with involution on X [resp. the free monoid with involution on X] and the free group on X.

References

  • 1 J.M. Howie, Fundamentals of SemigroupPlanetmathPlanetmath Theory, Oxford University Press, Oxford, 1991.
  • 2 R. Lyndon and P. Schupp, Combinatorial Group Theory, Springer-Verlag, 1977.
  • 3 N. Petrich, Inverse Semigroups, Wiley, New York, 1984.
随便看

 

数学辞典收录了18232条数学词条,基本涵盖了常用数学知识及数学英语单词词组的翻译及用法,是数学学习的有利工具。

 

Copyright © 2000-2023 Newdu.com.com All Rights Reserved
更新时间:2025/5/4 11:50:08