Monoid

Monoid (Axiome EAN)

berührt die Spezialgebiete

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)

In der abstrakten Algebra ist ein Monoid ein Tripel aus einer Menge M, einer zweistelligen Verknüpfung * auf M und einem ausgezeichneten Element e aus M, geschrieben als (M, *, e), mit den folgenden Eigenschaften:

1. Wohldefiniertheit der Verknüpfung:

\forall a,b\in M:a*b\in M

2. e ist neutrales Element:

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

3. Assoziativität der Verknüpfung:

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

Ein Monoid ist also eine Halbgruppe mit neutralem Element.

Oft wird ein Monoid auch lediglich als Paar geschrieben, ohne explizit das neutrale Element mit aufzuführen, also in der Form (M, *). Das heißt aber nicht, dass ein neutrales Element nicht existiert.

Die Assoziativität (Teil 3. 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.

Ein Beispiel für einen Monoid ist die Menge der nichtnegativen ganzen Zahlen mit der Addition:

(\mathbb {N} _{0},+,0)

Die Addition führt nicht aus den nichtnegativen ganzen Zahlen heraus und ist assoziativ; 0 ist das neutrale Element.

Beispiele und Gegenbeispiele

$(\mathbb {N} _{0},+,0)$	ist ein Monoid
$(\mathbb {Z} ,+,0)$	(die Menge der ganzen Zahlen mit der Addition) ist ein Monoid
$(\mathbb {Z} ,-,0)$	ist kein Monoid, da zwar die Abgeschlossenheit erfüllt ist, aber die Subtraktion nicht assoziativ ist.
$(\mathbb {N} ,\cdot ,1)$	ist ein Monoid
$(\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.
$({\mathcal {P}}(X),\cap ,X)$	(die Potenzmenge einer Menge X mit dem Schnittmengenoperator) ist ein kommutatives Monoid.

Jede Gruppe ist ein Monoid.

Untermonoid

Eine Teilmenge $U\subseteq M$ eines Monoids $(M,+,0)$ , die das neutrale Element 0 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 $(A,+_{A},0_{A})$ , $(B,+_{B},0_{B})$ , für die gilt:

$\forall x,y\in A:f(x+_{A}y)=f(x)+_{B}f(y)$ ,
$f(0_{A})=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(A)$ 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

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 $\epsilon$ als neutralem Element ein Monoid, $(A^{*},\circ ,\epsilon )$ . 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(a)$ für alle $a\in A$ .

Allgemein nennt man ein Monoid (M, *, 1) frei, wenn es eine Teilmenge A besitzt, so dass sich jedes Element von M eindeutig darstellen lässt als Produkt von Elementen aus A (auch die Reihenfolge der Faktoren wird unterschieden). Die Menge A heißt Erzeuger des Monoids. M ist isomorph zum freien Monoid A*. Ein freies Monoid mit einem wenigstens zweielementigen Erzeuger ist nicht kommutativ.

Hat ein Monoid (M, *, 1) 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.

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 $({0},+,0)$ 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.

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