Monoid

Monoid (Axiome EAN)

berührt die Spezialgebiete

Mathematik Abstrakte Algebra Gruppentheorie Theoretische Informatik Automatentheorie

ist Spezialfall von

Magma (Mathematik) (Axiom E) Halbgruppe (EA)

umfasst als Spezialfälle

kommutatives Monoid (EANK) natürliche Zahlen (N,+) reelle Zahlen (R,·) Gruppe (EANI) Abelsche Gruppe (EANIK) Halbring (Monoid bzgl. + und *)

In der abstrakten Algebra ist ein Monoid eine Menge mit einer klammerfrei notierbaren Verknüpfung und einem neutralen Element. Ein Beispiel sind die natürlichen Zahlen mit der Addition und der Zahl 0 als neutralem Element.

Definition

Ein Monoid ist ein Tripel $(M,*,e)$ bestehend aus einer Menge $M$, einer inneren zweistelligen Verknüpfung $*:M\times M\to M,\;(a,b)\mapsto a*b$ und einem ausgezeichneten Element $e\in M$ mit den folgenden Eigenschaften:

1. Assoziativität der Verknüpfung:

$\forall a,b,c\in M:(a*b)*c=a*(b*c)$

2. e ist neutrales Element:

$\forall a\in M:e*a=a*e=a$

Ein Monoid ist also eine Halbgruppe mit neutralem Element.

Wenn aus dem Kontext ersichtlich ist, welches das neutrale Element ist, wird ein Monoid oft auch verkürzt als Paar $(M,*)$ geschrieben.

Die Assoziativität (Teil 1. der Definition) rechtfertigt das Weglassen von Klammern: Für den binären Operator * ist der Term "a * b * c" zunächst mehrdeutig. Weil aber das Ergebnis bezüglich der durch Klammerung festgelegten Auswertungsreihenfolge invariant ist, kann man hier auf die Klammern verzichten.

Beispiele und Gegenbeispiele

$(\mathbb {N} _{0},+,0)$	ist ein Monoid
$(\mathbb {N} ,\cdot ,1)$	ist ein Monoid. Damit ist $(\mathbb {N} _{0},+,0,\cdot ,1)$ ein Halbring.
$(\mathbb {Z} ,+,0)$	(die Menge der ganzen Zahlen mit der Addition) ist ein Monoid
$(\mathbb {Z} ,-,0)$	ist kein Monoid, da die Subtraktion nicht assoziativ ist.
$(\mathbb {R} ^{n,n},\cdot ,E)$	(die Menge der n×n-Matrizen mit der Einheitsmatrix E) ist ein nichtkommutatives Monoid.
$(\mathbb {R} ^{3},\times ,{\vec {0}})$	(der dreidimensionale reelle Raum mit dem Vektorprodukt) ist kein Monoid, da das Assoziativgesetz verletzt ist: Bezeichnen wir mit $e_{i}$ den i-ten Einheitsvektor, so ist $(e_{1}\times e_{1})\times e_{2}=0$, aber $e_{1}\times (e_{1}\times e_{2})=e_{2}$.
$(n{\mathbb {Z} },+,0)$	(die Menge der Vielfachen der ganzen Zahl n mit der Addition) ist ein Monoid.
$({\mathbb {Q}}_{+},+,0)$	(die Menge der nichtnegativen rationalen Zahlen mit der Addition) ist ein Monoid.
$({\mathbb {Q} }_{+}^{*},\cdot ,1)$	(die Menge der positiven rationalen Zahlen mit der Multiplikation) ist ein Monoid. Damit ist $({\mathbb {Q}}_{+},+,0,\cdot ,1)$ ein Halbring (sogar ein Halbkörper).
$({\mathcal {P}}(X),\cap ,X)$	(die Potenzmenge einer Menge X mit dem Schnittmengenoperator) ist ein kommutatives Monoid.

Jede Gruppe ist ein Monoid, aber ein Monoid hat im Gegensatz zur Gruppe nicht notwendigerweise inverse Elemente.

Untermonoid

Eine Teilmenge $U\subseteq M$ eines Monoids $(M,*,e)$, die das neutrale Element $e$ enthält und bezüglich der Verknüpfung $*$ von $M$ abgeschlossen ist (d.h. für alle $u,v\in U$ ist auch $u*v\in U$) heißt Untermonoid von $M$.

Monoid-Homomorphismus

Ein Monoid-Homomorphismus ist definiert als eine Abbildung $f:A\to B$ zwischen zwei Monoiden $\left(A,+_{A},0_{A}\right)$, $\left(B,+_{B},0_{B}\right)$, für die gilt:

• $\forall x,y\in A:f(x+_{A}y)=f(x)+_{B}f(y)$,
• $f\left(0_{A}\right)=0_{B}$.

Es handelt sich hier also um eine Abbildung, die mit den Verknüpfungen in A und B verträglich ist und das neutrale Element von A auf das neutrale Element von B abbildet. Ein Monoid-Homomorphismus ist im Sinne der abstrakten Algebra ein Homomorphismus zwischen Monoiden.

Das Bild $f\left(A\right)$ eines Monoid-Homomorphismus $f:A\to B$ ist ein Untermonoid des Zielmonoids B.

Ist der Monoid-Homomorphismus $f:A\to B$ bijektiv, dann nennt man ihn einen Monoid-Isomorphismus und die Monoide A und B isomorph.

Freies Monoid

Ein Monoid $\left(M,*,\varepsilon \right)$ heißt frei, wenn eine nichtleere Teilmenge $B\subset M\backslash \{\varepsilon \}$ existiert und es zu jedem $p\in M\backslash \{\varepsilon \}$ genau eine natürliche Zahl $n>1$ und ein Tupel $(b_{1},b_{2},\ldots ,b_{n})$ von Elementen aus $B$ gibt, so daß

 $p=b_{1}*b_{2}*\ldots *b_{n}$

gilt. B heißt dann Basis (Erzeuger) des Monoids.

Ist A irgendeine Menge, dann bildet die Menge aller endlichen Folgen in der Menge A mit dem Hintereinanderschreiben der Folgen als Verknüpfung und der leeren Folge $\varepsilon$ als neutralem Element ein Monoid, $(A^{*},\circ ,\varepsilon )$. Dieses Monoid nennt man "das von A erzeugte freie Monoid". Ist die Menge A endlich, dann spricht man meist vom Alphabet A und von Zeichenketten über diesem Alphabet.

Das freie Monoid A* über einer Menge A spielt in vielen Bereichen der theoretischen Informatik eine Rolle (z.B. Automatentheorie, formale Sprache, regulärer Ausdruck). Siehe auch den Artikel über die Kleenesche Hülle für einen verwandten Begriff.

Das freie Monoid A* über A erfüllt folgende universelle Eigenschaft: Ist M ein Monoid und $f\colon A\to M$ eine beliebige Funktion, dann gibt es genau einen Monoid-Homomorphismus $T\colon A^{*}\to M$ mit $T(a)=f\left(a\right)$ für alle $a\in A$. M ist somit isomorph zum freien Monoid A*. Solche Homomorphismen werden in der theoretischen Informatik zur Definition formaler Sprachen (als Teilmengen von A*) genutzt.

Hat ein Monoid $\left(M,*,1\right)$ eine Teilmenge A, so dass sich jedes Element von M eindeutig bis auf die Reihenfolge der Faktoren als Produkt von Elementen aus A darstellen lässt, dann nennt man M frei kommutativ mit dem Erzeuger A. Ein solches Monoid ist notwendig kommutativ. Ein freies Monoid mit einem wenigstens zweielementigen Erzeuger ist nicht kommutativ.

Das freie Monoid ist wie die freie Gruppe ein Beispiel eines freien Objekts in der Kategorientheorie.

Beispiele

• Für eine Menge A ist die Menge $\operatorname {Abb_{fin}} (A,{\mathbb {N}}_{0})$ aller Abbildungen von A in die nichtnegativen ganzen Zahlen, die nur an endlich vielen Stellen einen Wert ungleich 0 annehmen, mit der komponentenweisen Addition ein kommutatives Monoid. Es ist frei kommutativ mit den Elementarfunktionen $\chi _{a}(x)=\delta _{a,x}$ als Erzeuger (dabei ist $\delta _{a,x}$ ein Kronecker-Delta).
• Das Nullmonoid $\left({0},+,0\right)$ ist frei mit der leeren Menge als Erzeuger. Das Monoid $(\mathbb {N} _{0},+,0)$ ist frei mit dem einzigen Erzeuger {1}. Beide Monoide sind auch frei kommutativ mit dem genannten Erzeuger.
• Das Monoid $(\mathbb {N} ,{\cdot },1)$ ist frei kommutativ über der Menge der Primzahlen, es ist aber kein freies Monoid.
• Buchstaben bilden eine Basis B (Alphabet) des Monoids (M, °, e), wobei ° die Verkettung von Wörtern bezeichnet.