Monoid
En monoid är inom abstrakt algebra ett par <math>(M,*)</math> (ofta säger man bara <math> M </math> och menar hela monoiden), där <math>M</math> är en mängd och <math>*</math> är en binär operator på <math>M</math>, vilken lyder följande regler:
- slutenhet: för alla <math>a, b</math> i <math>M</math>, är <math>a*b</math> i <math>M</math> (detta följer egentligen direkt ur att * är en binär operator, och behöver inte specificeras separat)
- neutralt element: det finns ett element <math>e</math> i <math>M</math>, så att för alla <math>a</math> i <math>M</math>, <math>a*e = e*a = a</math>.
- associativitet: * är en associativ operator; det vill säga, <math>(a*b)*c = a*(b*c)</math> för alla <math>a, b, c</math> i <math>M</math>.
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.:
- <math>a*b = b*a</math> för alla <math>a,b</math> i <math> M </math>.
<math> (D,*) </math> sägs vara en submonoid till en monoid <math> (M,*) </math> om <math> D </math> är en delmängd till <math> M </math>, <math> D </math> innehåller det neutrala elementet och för alla <math> a, b </math> i <math> D </math> så ligger även <math> a*b </math> i <math> D </math>. <math>(D, *)</math> är då även monoid i sig själv.
Exempel
[redigera | redigera wikitext]Naturliga talen
[redigera | redigera wikitext]De naturliga talen, <math>\mathbb{N}</math>, med additionsoperatorn <math> + </math> bildar en abelsk monoid <math>(\mathbb{N}, +)</math> med det neutrala elementet 0.
Man kan också bilda en monoid med multiplikationsoperatorn <math>(\mathbb{N}, *)</math>, 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, <math>(M, *)\,</math> och <math>(N, \cdot )</math>, är en funktion <math>f:M \to N</math> som uppfyller:
- <math>f(x*y) = f(x) \cdot f(y)</math>
- <math>f(e) = e'\,</math>
där <math>e</math> och <math>e'</math> är neutrala element för <math>(M, *)\,</math> respektive <math>(N, \cdot )</math>.
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]- Fil:Wiktionary small.svg Slå upp monoid i ordlistan Wiktionary.
