Monoid

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 11. september 2021; checks kræver 2 redigeringer .

En monoid er en semigruppe med et neutralt element . Mere detaljeret er en monoid et sæt , hvorpå der er givet en binær associativ operation , normalt kaldet multiplikation , og hvori der er et element, således at for enhver . Elementet kaldes enheden og betegnes ofte . Hver monoid har præcis én 1. $M$ $e$ $ex=x=xe$ $x\i M$ $e$ $en$

Monoider opstår i forskellige områder af matematikken ; for eksempel kan monoider opfattes som kategorier fra et enkelt objekt. Således generaliserer monoider egenskaber ved funktionssammensætning . Monoider bruges også i datalogi og i teorien om formelle sprog .

Eksempler

Hver gruppe er en monoid.
Sættet af alle afbildninger af et vilkårligt sæt i sig selv er en monoid med hensyn til driften af sekventiel udførelse (sammensætning) af afbildninger. Enheden er den identiske kortlægning . $S$
Sættet af endomorfismer af enhver universel algebra er en monoid med hensyn til superpositionsoperationen , og enheden er identitetsendomorfismen. $EN$
Enhver semigruppe S kan omdannes til en monoid ved blot at tilføje et element e og definere e*s = s = s*e for alle s ∈ S.
De ikke-negative tal ( naturlige tal og nul) danner en kommutativ monoid (monoid med en kommutativ operation ) i både multiplikation og addition.
Mættet af alle endelige strenge med elementer fra alfabetet Σ danner en monoid, normalt betegnet med Σ ∗ . Operationen er defineret som strengsammenkædning .
Fix en monoid M . Så danner sættet af alle funktioner fra et fast sæt i M en monoid; hvis enhed er en funktion, der afbilder hele sættet til enheden M , er operationen defineret punktvis.
En liste med en sammenkædningsoperation og den tomme liste som det neutrale element.
Ordbog. Det neutrale element er en tom ordbog. Operationen er foreningen af ordbøger efter nøgle, hvis nøglen er lig for værdierne, skal fletteoperationen defineres (bemærk: hvis operationen af flette værdier er ikke-kommutativ, så vil sammenlægningen af ordbøger også være ikke -kommutativ). For eksempel kan du definere en fletoperation som
- tilføje tal
- sammenkæde strenge
- sammenkæde lister
- for indlejrede ordbøger skal du udføre handlingen rekursivt

For eksempel ordbøger

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

kan kombineres til

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

Egenskaber

Enhver monoid kan repræsenteres som monoiden af alle endomorfismer af en eller anden universel algebra .

For ethvert element i en monoid kan man definere nulgraden som Da monoid er et specialtilfælde af semigruppen , så defineres en naturlig grad for dens elementer . Gradegenskaberne forbliver gyldige for . $a^{0}=e,\forall a$ ${\displaystyle a^{m+n}=a^{m}a^{n},(a^{m})^{n}=a^{mn))$ $\mathbb {N} \cup \{0\}$

Man kan introducere definitionen af et invertibelt element af en monoid: x er invertibelt, hvis der eksisterer et element y sådan, at xy = yx = e . Hvis y og z er to elementer med denne egenskab, så ved associativitet y = ( zx ) y = z ( xy ) = z , derfor er det omvendte element entydigt defineret [1] (det betegnes normalt x -1 ). Sættet af alle inverterbare elementer i en monoid danner en (muligvis triviel ) gruppe.

På den anden side kan ikke alle monoider indlejres i en gruppe. For eksempel er det meget muligt, at der er elementer a og b i en monoid , således at ab = a og b ikke er et neutralt element. Hvis denne monoid var en delmængde af en gruppe, kunne vi gange begge sider af ligheden med en −1 til venstre, og vi ville få en modsigelse. En monoid M siges at have annulleringsegenskaben , hvis, for nogen af dens elementer, og . En kommutativ monoid med annulleringsegenskaben kan indlejres i en gruppe ved hjælp af Grothendieck-gruppekonstruktionen . Dette generaliserer den måde, hvorpå den additive gruppe af heltal kan rekonstrueres ud fra den additive gruppe af naturlige tal. $ab=ac\Rightarrow b=c$ $ba=ca\Rightarrow b=c$

En endelig monoid med annulleringsegenskaben er altid en gruppe. Faktisk, lad x være et vilkårligt element i en sådan monoid. Det følger af Dirichlet-princippet, at x n = x m for nogle m > n > 0. Men så indebærer annulleringsegenskaben, at x m − n = e , hvor e er enheden. Derfor x * x m − n −1 = x m − n −1 * x = e , så x er invertibel.

En homomorfi fra en monoid M til en monoid N er en funktion sådan, at (for enhver x og y fra M ) og . $f\kolon M\til N$ $f(xy)=f(x)\cdot f(y)$ $f(e)=e$

Relation til kategoriteori

Aksiomerne for en monoid falder sammen med dem, der gælder for sammensætningen af morfismer af et objekt i en kategori , det vil sige, at monoider kan betragtes som kategorier fra et objekt.

På samme måde er monoide homomorfismer nøjagtigt funktioner mellem de tilsvarende kategorier. [2] Denne konstruktion definerer en ækvivalens mellem kategorien af (små) monoider Mon og en komplet underkategori i Kat .

Der er også en kategorisk forestilling om en monoid , som generaliserer egenskaberne af en monoid til en vilkårlig monoid kategori . For eksempel er en monoid i kategorien sæt den sædvanlige monoid defineret ovenfor, mens en monoid i kategorien abelske grupper er en associativ ring med identitet.

Se også

Noter

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

Litteratur

Jacobson, Nathan (2009), Grundlæggende algebra 1 (2. udgave), Dover - ISBN 978-0-486-47189-1 .