Monoïde

Voor het gelijknamige begrip uit de categorietheorie, zie Monoïde (categorietheorie).

In de abstracte algebra, een deelgebied van de wiskunde, is een monoïde een algebraïsche structuur die bestaat uit een verzameling die is uitgerust met een enkele associatieve binaire operatie en een neutraal element, ook wel eenheids- of identiteitselement genoemd.

Algebraïsche structuren
van magma naar groep

■ met delen

■ met inverse

■ met identiteit

■ associatief

Een voorbeeld van een monoïde is de verzameling van de natuurlijke getallen met de operatie optellen en het getal 0 als neutraal element.

Een monoïde heeft meer algebraïsche structuur dan een halfgroep, omdat in een halfgroep het bestaan van een neutraal element niet is vereist. Een monoïde wordt daarom wel als een unitaire halfgroep aangeduid. Iedere groep is weer een monoïde, een monoïde waarin ieder element een inverse heeft. Iedere groep is annuleerbaar, een monoïde hoeft dat niet te zijn.

Definitie

Onder een monoïde $(M,*)$ verstaat men een niet-lege verzameling $M$ met daarop een associatieve binaire operatie: $*:M\times M\to M$ en een voor deze bewerking neutraal element $e$, die dus voldoen aan de volgende axioma's:

• Associativiteit: voor alle $a,b,c\in M$ geldt $(a*b)*c=a*(b*c)$
• Neutraal element: er is een element $e\in M$ waarvoor geldt dat $e*a=a*e=a$ voor alle $a\in M$.

Als een operatie expliciet moet worden gemaakt, kan een monoïde worden aangegeven door het paar $(M,*)$. Het is gebruikelijk om $a*b$ in plaats van $*(a,b)$ te schrijven voor het resultaat van de bewerking $*$ toegepast op de elementen $a,b\in M$.

Enkele voorbeelden

• De natuurlijke getallen $\mathbb {N}$ vormen een commutatieve monoïde $(\mathbb {N} ,+)$ onder de optelling met neutraal element nul en $(\mathbb {N} ,*)$ onder de vermenigvuldiging $*$ met neutraal element een. Een deelmonoïde van $\mathbb {N}$ onder optelling wordt een numerieke monoïde genoemd.
• De gehele getallen met de optelling, genoteerd als $(\mathbb {Z} ,+)$, is een monoïde met 0 als neutraal element.
• Functiecompositie
• Iedere groep is een monoïde en iedere abelse groep een commutatieve monoïde.
• Een halfgroep $S$ kan in een monoïde worden veranderd door een element $e$, dat niet in $S$ voorkomt toe te voegen en vervolgens $e*e=e$ en $s*e=e*s=s$ te definiëren voor iedere $s\in S$.
• Ieder singleton $\{x\}$ geeft aanleiding tot een uit een element bestaande, triviale monoïde. Deze monoïde is voor een vaste $x$ uniek, aangezien de axioma's van de monoïde vereisen dat $x*x=x$.
• Ieder begrensd halfrooster is een idempotente commutatieve monoïde.

Vrije monoïde

De vrije monoïde van een verzameling $V$ is de monoïde die bestaat uit de verzameling van alle eindige rijen van nul of meer elementen van $V$, met concatenatie, het achter elkaar zetten, als operatie, en de rij van nul elementen als neutraal element.

In de context van een tekenset $V$, een verzameling schrifttekens zoals letters, cijfers en leestekens is de vrije monoïde de verzameling (eindige) tekenreeksen bij deze tekenset. In relatie tot computers wordt een tekenset vaak besproken in combinatie met de tekencodering.

Toepassing in de informatica

Monoïden komen in aantal deelgebieden van de wiskunde voor. In de meetkunde representeert een monoïde het concept van een functiecompositie. Dit idee is geabstraheerd in de categorietheorie, waar de monoïde een categorie met een object is. Monoïden worden ook gebruikt om een stevige algebraïsche fundering te geven aan de informatica.