Monoid

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 11 september 2021; kontroller kräver 2 redigeringar .

En monoid är en halvgrupp med ett neutralt element . Närmare bestämt är en monoid en uppsättning på vilken en binär associativ operation ges , vanligtvis kallad multiplikation , och där det finns ett element så att för någon . Elementet kallas enheten och betecknas ofta . Varje monoid har exakt en 1. $M$ $e$ $ex=x=xe$ $x\i M$ $e$ $ett$

Monoider uppstår inom olika områden av matematiken ; till exempel kan monoider ses som kategorier från ett enda objekt. Således generaliserar monoider egenskaperna hos funktionssammansättningen . Monoider används också inom datavetenskap och i teorin om formella språk .

Exempel

Varje grupp är en monoid.
Uppsättningen av alla mappningar av en godtycklig uppsättning i sig själv är en monoid med avseende på driften av sekventiell exekvering (sammansättning) av mappningar. Enheten är identisk mappning . $S$
Uppsättningen av endomorphisms av någon universell algebra är en monoid med avseende på superposition operation , och enheten är identitetendomorphism. $A$
Vilken semigrupp S som helst kan omvandlas till en monoid genom att helt enkelt lägga till ett element e och definiera e*s = s = s*e för alla s ∈ S.
De icke-negativa talen ( naturliga tal och noll) bildar en kommutativ monoid (monoid med en kommutativ operation ) i både multiplikation och addition.
Mängden av alla finita strängar med element från alfabetet Σ bildar en monoid, vanligtvis betecknad med Σ ∗ . Operationen definieras som strängkonkatenering .
Fixa en monoid M . Då bildar mängden av alla funktioner från en fast mängd i M en monoid; vars enhet är en funktion som mappar hela uppsättningen till enheten M definieras operationen punktvis.
En lista med en sammanlänkningsoperation och den tomma listan som neutralt element.
Lexikon. Det neutrala elementet är en tom ordbok. Operationen är föreningen av ordböcker efter nyckel, om nyckeln är lika för värdena, måste sammanslagningsoperationen definieras (observera: om operationen av sammanslagningsvärden är icke-kommutativ, kommer sammanslagningen av ordböcker också att vara icke-kommutativ -kommutativ). Du kan till exempel definiera en sammanfogningsoperation som
- lägga till siffror
- sammanfoga strängar
- sammanfoga listor
- för kapslade ordböcker, utför operationen rekursivt

Till exempel ordböcker

{"a" => 2, "b" => "cd", "c" => [1, 2], "d" => {"e" => 1}, "f" => 1} {"a" => 3, "b" => "e", "c" => [3], "d" => {"e" => 2}, "g" => 1}

kan kombineras till

{"a" => 5, "b" => "cde", "c" => [1, 2, 3], "d" => {"e" => 3}, "f" => 1 , "g" => 1}

Egenskaper

Vilken monoid som helst kan representeras som monoiden av alla endomorfismer av någon universell algebra .

För vilket element som helst av en monoid kan man definiera nollgraden som Eftersom monoiden är ett specialfall av halvgruppen , definieras en naturlig grad för dess element. Examensegenskaperna gäller för . $a^{0}=e,\forall a$ ${\displaystyle a^{m+n}=a^{m}a^{n},(a^{m})^{n}=a^{mn))$ $\mathbb {N} \cup \{0\}$

Man kan införa definitionen av ett inverterbart element i en monoid: x är inverterbart om det finns ett element y så att xy = yx = e . Om y och z är två element med denna egenskap, då genom associativitet y = ( zx ) y = z ( xy ) = z , därför är det inversa elementet unikt definierat [1] (det betecknas vanligtvis x −1 ). Uppsättningen av alla inverterbara element i en monoid bildar en (möjligen trivial ) grupp.

Å andra sidan kan inte varje monoid bäddas in i en grupp. Till exempel är det mycket möjligt att det finns element a och b i en monoid så att ab = a och b inte är ett neutralt element. Om denna monoid var en delmängd av någon grupp, skulle vi kunna multiplicera båda sidor av likheten med en −1 till vänster och vi skulle få en motsägelse. En monoid M sägs ha annulleringsegenskapen om, för något av dess element, och . En kommutativ monoid med avbrytningsegenskapen kan bäddas in i en grupp med hjälp av Grothendieck-gruppkonstruktionen . Detta generaliserar sättet på vilket den additiva gruppen av heltal kan rekonstrueras från den additiva gruppen av naturliga tal. $ab=ac\Rightarrow b=c$ $ba=ca\Rightarrow b=c$

En finit monoid med annulleringsegenskapen är alltid en grupp. Låt x vara ett godtyckligt element i en sådan monoid. Det följer av Dirichlet-principen att x n = x m för vissa m > n > 0. Men då innebär annulleringsegenskapen att x m − n = e , där e är enheten. Därför x * x m − n −1 = x m − n −1 * x = e , så x är inverterbart.

En homomorfism från en monoid M till en monoid N är en funktion sådan att (för alla x och y från M ) och . $f\kolon M\till N$ $f(xy)=f(x)\cdot f(y)$ $f(e)=e$

Relation till kategoriteori

Axiomen för en monoid sammanfaller med de som gäller sammansättningen av morfismer av ett objekt i en kategori , det vill säga monoider kan betraktas som kategorier från ett objekt.

På liknande sätt är monoida homomorfismer exakt funktioner mellan motsvarande kategorier. [2] Denna konstruktion definierar en ekvivalens mellan kategorin (små) monoider Mon och en komplett underkategori i Kat .

Det finns också en kategorisk föreställning om en monoid , som generaliserar egenskaperna hos en monoid till en godtycklig monoid kategori . Till exempel är en monoid i kategorin uppsättningar den vanliga monoiden som definieras ovan, medan en monoid i kategorin abelska grupper är en associativ ring med identitet.

Se även

Anteckningar

↑ Jacobson, I.5. sid. 22
↑ Awodey, Steve (2006). kategoriteori. Oxford Logic Guides 49. Oxford University Press. sid. 10. ISBN 0-19-856861-4 . Zbl 1100.18001.

Litteratur

Jacobson, Nathan (2009), Basic algebra 1 (2nd ed.), Dover - ISBN 978-0-486-47189-1 .

Länkar

Hazewinkel, Michiel, red. (2001), Monoid , Encyclopedia of Mathematics, Springer - ISBN 978-1-55608-010-4