6442373931

12

.. STRUKTURY ALGEBRAICZNE

T jest łączną (i nieprzemienną) operacją 2-argumentową, zwaną szczepieniem, która polega na przyłączeniu korzenia drugiego argumentu do wyróżnionego wierzchołka pierwszego argumentu, który leży na końcu ścieżki prowadzącej od korzenia i skręcającej w prawo w każdym wierzchołku łączącym ze sobą trzy krawędzie.

DEFINICJA 5. Monoid to trójka (5,02,0o), w której para (5,02) jest półgrupą, natomiast 0o jest operacją O-argumentową zadającą stałą 0o(*) = e e 5, która jest elementem neutralnym względem operacji 02, przy czym tę ostatnią własność wyrażają diagramy przemienne

▲

PRZYKŁAD(Y) 4.

(1)    Trójka (IN,+.0) złożona ze zbioru IN liczb naturalnych, dodawania + oraz operacji O-argumentowej 0, której obrazem jest stała 0 e IN.

(2)    Trójka (^x,c,0) złożona ze słownika &ćx będącego zbiorem skończonych ciągów elementów zbioru skończonego X = {x\,X2, • • • ,£_n}, n € IN, zwanego alfabetem, z operacji 2-argumentowej c zwanej konkatenacją i polegaj aąej na dostawianiu wyrazów drugiego argumentu do wyrazów pierwszego argumentu na jego końcu, tj., np.

c ((li,, *ia, ■ - ■ , Xi_M ),    , X_h ,. . ., Xj„ )) = (l_fl, Xi₂ ,.. . , Xi_M ,x_h , x_h ,. . . , X_jN ) ,

oraz z operacji O-argumentowej 0, której obrazem jest ciąg pusty. Elementy słownika (tj. wyrazy) są zwykle zapisywane z opuszczeniem nawiasów i przecinków, np.

(xj, , Xi₂ , . . . , Xi_M ) — Xi_r Xi₂ • • ‘Xi_M .

Opisany monoid nosi miano monoidu swobodnego nad X.

DEFINICJA 6. Grupa to czwórka (5,02,0i,0o), w której trójka (5,02,0o) jest monoidem, natomiast 0i : 5 O jest operacją 1-argumentową o własności wyrażonej przez diagramy przemienne

(id_s,0i)°pri

(</>i,id_s)°pri