Monoid

En monoid är inom abstrakt algebra ett par ${\displaystyle (M,*)}$ (ofta säger man bara ${\displaystyle M}$ och menar hela monoiden), där ${\displaystyle M}$ är en mängd och ${\displaystyle *}$ är en binär operator på ${\displaystyle M}$, vilken lyder följande regler:

• slutenhet: för alla ${\displaystyle a,b}$ i ${\displaystyle M}$, är ${\displaystyle a*b}$ i ${\displaystyle M}$ (detta följer egentligen direkt ur att * är en binär operator, och behöver inte specificeras separat)
• neutralt element: det finns ett element ${\displaystyle e}$ i ${\displaystyle M}$, så att för alla ${\displaystyle a}$ i ${\displaystyle M}$, ${\displaystyle a*e=e*a=a}$.
• associativitet: * är en associativ operator; det vill säga, ${\displaystyle (a*b)*c=a*(b*c)}$ för alla ${\displaystyle a,b,c}$ i ${\displaystyle M}$.

Med andra ord är en monoid en semigrupp med ett neutralt element.

En kommutativ monoid eller abelsk monoid är en monoid där operatorn även är kommutativ, dvs.:

• ${\displaystyle a*b=b*a}$ för alla ${\displaystyle a,b}$ i ${\displaystyle M}$.

${\displaystyle (D,*)}$ sägs vara en submonoid till en monoid ${\displaystyle (M,*)}$ om ${\displaystyle D}$ är en delmängd till ${\displaystyle M}$, ${\displaystyle D}$ innehåller det neutrala elementet och för alla ${\displaystyle a,b}$ i ${\displaystyle D}$ så ligger även ${\displaystyle a*b}$ i ${\displaystyle D}$. ${\displaystyle (D,*)}$ är då även monoid i sig själv.

Exempel[redigera | redigera wikitext]

Naturliga talen[redigera | redigera wikitext]

De naturliga talen, ${\displaystyle \mathbb {N} }$, med additionsoperatorn ${\displaystyle +}$ bildar en abelsk monoid ${\displaystyle (\mathbb {N} ,+)}$ med det neutrala elementet 0.

Man kan också bilda en monoid med multiplikationsoperatorn ${\displaystyle (\mathbb {N} ,*)}$, som även den är abelsk, med det neutrala elementet 1.

Strängar[redigera | redigera wikitext]

Mängden av alla ändliga strängar över ett alfabet bildar en monoid med konkatenering som operator och den tomma strängen som neutralt element.

Monoidhomomorfier[redigera | redigera wikitext]

En homomorfi mellan två monoider, ${\displaystyle (M,*)\,}$ och ${\displaystyle (N,\cdot )}$, är en funktion ${\displaystyle f:M\to N}$ som uppfyller:

• ${\displaystyle f(x*y)=f(x)\cdot f(y)}$
• ${\displaystyle f(e)=e'\,}$

där ${\displaystyle e}$ och ${\displaystyle e'}$ är neutrala element för ${\displaystyle (M,*)\,}$ respektive ${\displaystyle (N,\cdot )}$.

Om en monoidhomomorfi är bijektiv kallas den för isomorfi, och två monoider som har en monoidisomorfi mellan sig kallas isomorfa.

Se även[redigera | redigera wikitext]

• Slå upp monoid i ordlistan Wiktionary.
  Ordbok