Monoid – półgrupa, której działanie ma element neutralny. Formalnie, monoid to algebra ( S , e , ∗ ) , {\displaystyle (S,e,*),} sygnatury ( 0 , 2 ) , {\displaystyle (0,2),} gdzie S {\displaystyle S} jest niepustym zbiorem, natomiast

∗ : S × S → S {\displaystyle *\colon S\times S\to S}

jest działaniem dwuargumentowym, spełniającym warunki:

1. ∀ a ∈ S e ∗ a = a ∗ e = a {\displaystyle \forall _{a\in S}\;e*a=a*e=a}       ( e {\displaystyle e} jest elementem neutralnym),
2. ∀ a , b , c ∈ S ( a ∗ b ) ∗ c = a ∗ ( b ∗ c ) {\displaystyle \forall _{a,b,c\in S}\;\left(a*b\right)*c=a*\left(b*c\right)}       (działanie jest łączne).

Szczególny przypadek monoidu stanowi grupa. Wynika stąd następujące zawieranie:

⊇ {\displaystyle \supseteq }

⊇ {\displaystyle \supseteq }

Każdy monoid M {\displaystyle M} jest izomorficzny z półgrupą wszystkich endomorfizmów pewnej algebry M . {\displaystyle M.} Jest to uogólnienie twierdzenia Cayleya.

Przykłady[ | edytuj kod]

Każdej półgrupie ( S , ∗ ) {\displaystyle (S,*)} można przyporządkować jej monoid M ( S ) {\displaystyle M(S)} w następujący sposób:

S {\displaystyle S}

e , {\displaystyle e,}

M ( S ) = ( S , e , ∗ ) , {\displaystyle M(S)=(S,e,*),}

S {\displaystyle S}

M ( S ) = ( S ∪ { 1 } , 1 , ∘ ) , {\displaystyle M(S)=(S\cup \{1\},1,\circ ),}

1 ∉ S , {\displaystyle 1\notin S,}

x , y ∈ S {\displaystyle x,y\in S}

x ∘ y = x ∗ y , {\displaystyle x\circ y=x*y,}

x ∈ S {\displaystyle x\in S}

x ∘ 1 = 1 ∘ x = x , {\displaystyle x\circ 1=1\circ x=x,}

1 ∘ 1 = 1. {\displaystyle 1\circ 1=1.}

Monoid wolny. ( X ∗ , ε , ∼ ) {\displaystyle \left(X^{*},\varepsilon ,\sim \right)} – zbiór słów nad alfabetem X , {\displaystyle X,} z ε {\displaystyle \varepsilon } jako słowem pustym i ∼ {\displaystyle \sim } jako operacją konkatenacji. Jeśli X = { 0 , 1 } , {\displaystyle X=\{0,1\},} to słowami są na przykład: 110111 , 011000 , 000 , 1111 , {\displaystyle 110111,\,011000,\,000,\,1111,} a przykładami konkatenacji są:

110111 ∼ 000 = 110111000 , {\displaystyle 110111\sim 000=110111000,}

ε ∼ 000 = 000. {\displaystyle \varepsilon \sim 000=000.}

Własność uniwersalności monoidu wolnego. Po utożsamieniu elementów zbioru X {\displaystyle X} ze słowami jednoelementowymi można uznać X {\displaystyle X} za podzbiór monoidu wolnego X ∗ {\displaystyle X^{*}}

Uniwersalność monoidu wolnego

i : a ↦ a , {\displaystyle i:a\mapsto a,}

X ∗ {\displaystyle X^{*}}

i : X → X ∗ {\displaystyle i:X\to X^{*}}

X {\displaystyle X}

M {\displaystyle M}

α : X → M {\displaystyle \alpha :X\to M}

α ∗ : X ∗ → M {\displaystyle \alpha ^{*}:X^{*}\to {M}}

Zbiór wszystkich odwzorowań dowolnego zbioru M {\displaystyle M} w zbiór M {\displaystyle M} wraz z działaniem składania odwzorowań tworzy monoid. Jedynką jest w nim odwzorowanie identycznościowe na M . {\displaystyle M.} Półgrupę tę nazywa się często pełną półgrupą przekształceń lub półgrupą symetryczną.

Jeśli M {\displaystyle M} jest monoidem, A {\displaystyle A} jest półgrupą, a h : M → A {\displaystyle h:M\to A} jest homomorfizmem na A , {\displaystyle A,} to A {\displaystyle A} jest monoidem.

Przypisy[ | edytuj kod]

Bibliografia[ | edytuj kod]