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.

Teil 3. der Definition rechtfertigt das Weglassen von Klammern: Da * ein binärer Operator ist, darf streng genommen "a * b * c" nicht geschrieben werden. Weil aber wegen der Assoziativität keine Verwechslungsgefahr besteht (egal welchen Teilausdruck man zuerst bestimmt, das Ergebnis ist dasselbe), können Klammern nach evtl. Vereinbarung weggelassen werden.

Ein Beispiel für einen Monoid ist die Menge der natürlichen Zahlen mit der Addition (im folgenden gilt die 0 als natürliche Zahl):

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

Die Addition führt nicht aus den natürlichen Zahlen heraus, + ist assoziativ und 0 ist das neutrale Element. Die Assoziativität erlaubt die Schreibweise "a + b + c".

Inhaltsverzeichnis

1 Beispiele und Gegenbeispiele

2 Untermonoid

3 Monoid-Homomorphismus

4 Freies Monoid

Beispiele und Gegenbeispiele

$(\mathbb{N}, -, 0)$	ist kein Monoid, weil die Abgeschlossenheit nicht erfüllt ist: 1-5=-4 ist keine natürliche Zahl
$(\mathbb{Z}, -, 0)$	ist kein Monoid, da zwar die Abgeschlossenheit erfüllt ist, aber die Subtraktion nicht assoziativ ist. Dabei ist $\mathbb{Z}$ ist die Menge der ganzen Zahlen.
$(\mathbb{N}, +, 0)$	ist ein Monoid
$(\mathbb{Z}, +, 0)$	ist ein Monoid
$(\mathbb{N}, \cdot, 0)$	ist kein Monoid, da das neutrale Element der normalen Zahlenmultiplikation 1 ist und nicht 0.
$(\mathbb{N}, \cdot, 1)$	ist ein Monoid
$(\mathbb{R}^{n,n}, \cdot, E)$	ist ein nichtkommutativer Monoid. Dabei ist $\mathbb{R}^{n,n}$ die Menge der n×n-Matrizen und E die Einheitsmatrix.
$(\mathbb{R}^3, \times, \vec{0})$	ist kein Monoid da das Assoziativgesetz nicht erfüllt ist (es gibt $\vec{a},\vec{b},\vec{c}\in\Bbb{R}^3$ für die $(\vec{a}\times\vec{b})\times\vec{c}\neq\vec{a}\times(\vec{b}\times\vec{c})$ gilt) und weil $\vec{0}$ kein neutrales Element bzgl. des Kreuzproduktes ist.
$(\Bbb{R}^3,+,\vec{0})$	ist ein Monoid
$(n\Bbb{Z},+,0)$	ist ein Monoid. Dabei ist $n\Bbb{Z}$ die Menge der Vielfachen der ganzen Zahl n.
$(\Bbb{P},\cdot,1)$	ist kein Monoid wegen $1\notin\Bbb{P}$ und weil die Abgeschlossenheit nicht erfüllt ist. Dabei ist $\mathbb{P}$ die Menge der Primzahlen.
$(\Bbb{Q}_{\;\ge 0},+,0)$	ist ein Monoid. Dabei ist $\Bbb{Q}_{\;\ge 0}$ die Menge der positiven rationalen Zahlen.
$(\Bbb{Q}_{\;\ge 0},\cdot,1)$	ist ein Monoid
$(\mathcal{P}(X),\cap,X)$	ist ein kommutativer Monoid. Dabei ist $\mathcal{P}(X)$ die Potenzmenge von X.

Jede Gruppe ist ein Monoid.

Jedes Monoid ist eine Halbgruppe.

Untermonoid

Eine Teilmenge U eines Monoids $(M, + ,0)$ , die das neutrale Element 0 enthält und bezüglich der Verknüpfung + von M abgeschlossen ist, heißt Untermonoid von M. Formal:

Sei

$(M, + ,0)$ ein Monoid,
$U \subseteq M$ mit $0 \in U$ ,
$\forall u_0 \in U, u_1 \in U: (u_0 + u_1) \in U$ (Abgeschlossenheit).

Dann wird durch

$(u_0 \oplus u_1) := (u_0 + u_1)$ für alle $u_0 \in U, u_1 \in U$

eine zweistellige Verknüpfung $\oplus$ auf U definiert, so dass

$(U, \oplus, 0)$ ein Monoid ist.

Das Monoid $(U, \oplus, 0)$ heißt dann Untermonoid von $(M, + ,0)$ .

Monoid-Homomorphismus

Ein Monoid-Homomorphismus ist definiert als eine Abbildung $f : A - > B$ zwischen zwei Monoiden $(A, + A,0 A)$ , $(B, + B,0 B)$ , für die gilt:

$\forall u_1, u_2 \in A: f(u_1 +_A u_2) = f(u_1) +_B f(u_2)$ ,
$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 der "Wertemonoids" 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 $ε$ 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: S \to M$ eine beliebige Funktion, dann gibt es genau einen Monoid-Homomorphismus $T: A* \to M$ mit $T (s) = f (s)$ für alle $s \in S$ .

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*.

Das Nullmonoid $(0, + ,0)$ ist frei mit der leeren Menge als Erzeuger. Das Monoid $(\mathbb{N}, +, 0)$ ist frei mit dem einzigen Erzeuger {1}.

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

Monoid

Beispiele und Gegenbeispiele

Untermonoid

Monoid-Homomorphismus

Freies Monoid

See also: Monoid, Abelsche Gruppe, Abgeschlossenheit, Abstrakte Algebra, Assoziativität, Automatentheorie, Bijektivität, Bildmenge, Einheitsmatrix, Folge (Mathematik)