357502984

19

1.4. GRUPY WOLNE I KODY GENETYCZNE GRUP

Z drugiej strony, jeśli h : M(X) —* M jest jakimkolwiek homomorfizmem monoidów spełniającym warunek h o p = /, to dla każdego x G X mamy h(x) = h o p(x) = f(x) i dla każdego słowa xiX2 ... x_n e M(X) mamy

h(xix₂ - - - x_n) = h(xi * x₂ * • • • * x_n) = h(xi) ■ h(x₂) ■ ■ ■ h(x_n) = f(xi) • f(x₂) ■ • • /(*„).

A więc homomorfizm h jest jednoznacznie wyznaczony przez warunek h o fi = f.    □

1.4.2 Grupy wolne

Monoid wolny M(X) nie jest grupą, żadne bowiem niepuste słowo nie jest odwracalne. Tym niemniej istnieje sposób rozszerzenia monoidu wolnego M(X) do grupy, którą nazywa się grupą wolną o alfabecie X. Opiszemy teraz tę konstrukcję.

Przede wszystkim rozszerzymy nasz wyjściowy alfabet X dołączając do niego dla każdego elementu x € X nowy element, który oznaczać będziemy x~^l. Zbiór wszystkich dołączonych elementów oznaczamy X^-1 i tworzymy nowy alfabet X' zdefiniowany jako

X^, = XUX~¹.

Zatem zbiór X' wraz z każdym elementem x € X zawiera także związany z nim element a:^-1 € X~¹. Rozpatrujemy teraz monoid wolny M(X') o alfabecie X'. Oczywiście M(X') nie jest grupą, gdyż dopisanie do słowa niepustego innego słowa daje słowo niepuste i wobec tego niepuste słowa w M(X') nie są odwracalne. Pokażemy, że można w monoidzie M(X') określić relację równoważnościową zgodną z działaniem w M(X¹) i taką, że klasy abstrakcji tej relacji z działaniem indukowanym z M{X') tworzą grupę. Punktem wyjścia tej konstrukcji jest następująca definicja.

Definicja 1.4.2. 1. Słowo w € M(X') nazywamy redukowalnym jeśli w ciągu w występują dwa kolejne elementy xx~^x lub x^_1x dla pewnego x € X.

2.    Słowo, które nie jest redukowalne nazywa się słowem zredukowanym.

3.    Słowo w¹ powstaje przez redukcję słowa w jeśli w' jest ostatnim słowem w ciągu skończonym słów

W\ = W, W₂,W3,.. .,

w którym słowo Wi+\ powstaje ze słowa w?j przez usunięcie ze słowa Wi przynajmniej jednej pary kolejnych elementów postaci xx~^l lub x~^lx, gdzie iel

4.    Słowo w' nazywa się zredukowaną postacią słowa w jeśli w' jest słowem zredukowanym i powstaje przez redukcję słowa w.

Konieczność użycia opisanego w punkcie 3 definicji ciągu słów ilustruje następujący przykład. Niech w = xyy~^lx~^lz. W słowie w tylko jedna para kolejnych elementów podlega redukcji, po której otrzymujemy słowo w\ = xx~^lz. Po redukcji w słowie w\ otrzymujemy w₂ = z. A więc z jest postacią zredukowaną słowa w.

Wprawdzie jest jasne, że każde słowo ma postać zredukowaną, jednakże nie jest rzeczą całkiem oczywistą, że każde słowo ma tylko jedną postać zredukowaną. Wątpliwości powstają przede wszystkim dlatego, że proces redukcji słowa można na ogół przeprowadzić na wiele sposobów i w związku z tym można byłoby oczekiwać różnych rezultatów redukcji słowa. Na przykład, słowo x~^lxyy~^lx~^ly można redukować na dwa różne sposoby następująco

x~¹xyy~¹x~¹y i-* yy~¹x~¹y ■-> x~^ly

x~¹xyy~¹x~¹y    x~¹xx~^ly •—* x~^ly

otrzymując zresztą to samo słowo zredukowane. Okazuje się, że postać zredukowana słowa nie zależy od wyboru kolejności operacji w procesie redukcji słowa.

Lemat 1.4.3. Każde słowo ma tylko jedną postać zredukowaną.

Dowód. Pominiemy techniczny dowód tego faktu. Zainteresowanego Czytelnika odsyłamy do książki Kargapołowa i Mierzliakowa [KM], str. 129-130.    □