Monoid

Monoid^[1] (z gr. μονοειδές od μόνος monos „jedyny” i εἶδος eîdos „wygląd, postać, kształt”) – półgrupa, której działanie ma element neutralny^[2]. Formalnie monoid to algebra ${\displaystyle (S,e,*),}$ sygnatury ${\displaystyle (0,2),}$ gdzie ${\displaystyle S}$ jest niepustym zbiorem, natomiast

${\displaystyle *\colon S\times S\to S}$

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

1. ${\displaystyle \forall _{a\in S}\;e*a=a*e=a}$       (${\displaystyle e}$ jest elementem neutralnym),
2. ${\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:

klasa półgrup ${\displaystyle \supseteq }$ klasa monoidów ${\displaystyle \supseteq }$ klasa grup.

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

Przykłady

• Liczby naturalne (koniecznie z zerem) z działaniem dodawania: elementem neutralnym jest w tym przypadku zero.

• Liczby naturalne (z zerem bądź bez) z działaniem mnożenia: elementem neutralnym tego monoidu jest 1 (w obu przykładach).

• Przedziały dowolnego zbioru częściowo uporządkowanego (posetu) tworzą monoid z działaniem przekroju zbiorów. Elementem neutralnym jest tutaj cały rozważany poset^{[potrzebny przypis]}.

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

Jeśli ${\displaystyle S}$ ma element neutralny ${\displaystyle e,}$ to monoidem tym jest ${\displaystyle M(S)=(S,e,*),}$

Jeśli ${\displaystyle S}$ nie ma elementu neutralnego, to monoidem tym jest ${\displaystyle M(S)=(S\cup \{1\},1,\circ ),}$ dla pewnego ${\displaystyle 1\notin S,}$ przy czym:

dla wszystkich ${\displaystyle x,y\in S}$ zachodzi ${\displaystyle x\circ y=x*y,}$

dla każdego ${\displaystyle x\in S}$ spełniona jest równość ${\displaystyle x\circ 1=1\circ x=x,}$

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

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

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

${\displaystyle \varepsilon \sim 000=000.}$

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

Uniwersalność monoidu wolnego

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

przy czym podzbiór ten generuje ${\displaystyle X^{*}}$ i odwzorowanie

${\displaystyle i:X\to X^{*}}$

ma następującą własność uniwersalności: dla dowolnego odwzorowania zbioru ${\displaystyle X}$ w monoid ${\displaystyle M}$

${\displaystyle \alpha :X\to M}$

istnieje jedyny taki homomorfizm

${\displaystyle \alpha ^{*}:X^{*}\to {M}}$

dla którego następujący diagram jest przemienny.

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

• Jeśli ${\displaystyle M}$ jest monoidem, ${\displaystyle A}$ jest półgrupą, a ${\displaystyle h:M\to A}$ jest homomorfizmem na ${\displaystyle A,}$ to ${\displaystyle A}$ jest monoidem^[6].