Zoran Skoda monoid

Polugrupa (engl. semigroup) je skup s jednom asocijativnom binarnom operacijom koja je svuda definirana. Drugim riječima, polugrupa je asocijativna binarna algebarska struktura (asocijativna magma).

Dakle, polugrupa $(M,\cdot)$ je skup $M$ zajedno s funkcijom $\cdot : M\times M\to M$ koju zovemo operacija polugrupe i koja je asocijativna, tj.

$$a\cdot (b\cdot c) = (a\cdot b)\cdot c,\,\,\,\,\,\,\,\forall a,b,c\in M.$$

Jednostavni primjer polugrupe je polugrupa riječi $(W(A), \cdot)$ gdje je $A$ neki skup simbola, koji zovemo alfabet, a $W(A)$ je skup svih nepraznih riječi tj. slogova (= konačnih nizova) simbola koje se mogu sastaviti iz alfabeta. Operacija je spajanje (konkatenacija) riječi. Npr. za alfabet možemo uzeti skup slova abecede pa će npr. KNJI $\cdot$ GA = KNJIGA. Lako se vidi da je ta operacija asocijativna.

Skup prirodnih brojeva $\mathbf{N}$ (nulu ne računamo) je polugrupa s obzirom na operaciju zbrajanja. Možemo promatrati broj $n$ kao riječ koja se sastoji od $n$ simbola $\bullet$. Npr. $3 = \bullet\bullet\bullet$. Tada je zbrajanje prirodnih brojeva isto što i konkatenacija u $W(A)$ gdje je $A$ jednočlani skup $A = \{\bullet\}$. Npr. $2+3 = \bullet\bullet+\bullet\bullet\bullet = \bullet\bullet\bullet\bullet\bullet = 5$. U polugrupama riječi je redoslijed slova bitan, ali ako imamo samo jedno slovo na raspolaganju, onda ne možemo razlikovati poredak.

Monoid $(M,\cdot,e)$ je polugrupa $(M,\cdot)$ u kojoj postoji neutralni element, tj. element $e$ takav da $e\cdot m = e = m\cdot e$ za sve $m\in M$.

Neutralni element u monoidu je jedinstven zbog asocijativnosti (to nije točno za svaku magmu). Zaista, ako je $e$ neki lijevi neutralni element u polugrupi $M$, tj. $e\cdot m = m$ za svaki $m\in M$ i $e'$ neki desni neutralni element u polugrupi $M$, tj. $n\cdot e' = n$ za svaki $n\in M$, tada je $e' = e\cdot e' = e$. Prva jednakost vrijedi jer je $e$ neutralni slijeva, a druga jer je $e'$ neutralni zdesna. Dakle u polugrupi je svaki lijevi neutralni element jednak svakom desnom neutralnom elementu, pa su svi oni jednaki ako postoje lijevi i desni. Ako je posebno neki element obostrani neutralni element, takav je dakle neutralan.

Jednostavni primjer monoida je polugrupa riječi $(W_0(A), \cdot)$ gdje je $A$ neki skup simbola, koji zovemo alfabet, a $W_0(A)$ je skup svih riječi u zagradama gdje dozvoljavamo i praznu riječ (), tj. slogova (= konačnih nizova) simbola koje se mogu sastaviti iz alfabeta unutar jednog para zagrada, npr. (KNJI). Operacija je spajanje (konkatenacija) riječi, pri čemu ispustimo unutarnje zagrade. Npr. za alfabet možemo uzeti skup slova abecede pa će npr. (KNJI)$\cdot$(GA) = (KNJIGA). Lako se vidi da je ta operacija asocijativna i da je prazna riječ () neutralni element, npr. ()$\cdot$(WORD) = (WORD). Konkatenacija riječi nije komutativna. Npr.

(LAS)$\cdot$(TA) $=$ (LASTA) $\neq$ (TALAS) = (TA)$\cdot$(LAS).

Prirodni brojevi s nulom čine monoid $(\mathbb{N}_0,+)$ u odnosu na zbrajanje. Uvjerite se u to! Taj primjer se može tretirati, slično kao i gore, kao konkatenacija riječi u alfabetu s jednim slovom, pri čemu dozvoljavamo i praznu riječ pa je zgodno riječ staviti u vanjske zagrade.

Najvažnija klasa monoida su grupe.

category: zadarmat4