Monoid

algebraische Struktur mit einer assoziativen binären Operation und einem neutralen Element
(Weitergeleitet von Freies Monoid)

In der abstrakten Algebra ist ein Monoid eine algebraische Struktur bestehend aus einer Menge mit einer klammerfrei notierbaren (assoziativen) Verknüpfung und einem neutralen Element. Ein Beispiel sind die natürlichen Zahlen mit der Multiplikation und der Zahl 1 als neutralem Element. Ein Monoid, in dem jedes Element invertierbar ist, heißt Gruppe.

Definition

Bearbeiten

Ein Monoid ist ein Tripel   bestehend aus einer Menge  , einer inneren zweistelligen Verknüpfung

 

und einem ausgezeichneten Element   mit den folgenden Eigenschaften bezüglich der angegebenen Verknüpfung:

  1. Assoziativität der Verknüpfung:
     
  2.   ist ein neutrales Element:
     

Ein Monoid ist also eine Halbgruppe mit neutralem Element. Jede Gruppe ist ein Monoid, aber ein Monoid hat im Gegensatz zur Gruppe nicht notwendigerweise inverse Elemente.

Bemerkungen zur Notation

Bearbeiten

In einem Monoid ist das neutrale Element eindeutig bestimmt. Wenn aus dem Kontext ersichtlich ist, welches das neutrale Element ist, wird ein Monoid oft auch verkürzt als Paar   geschrieben. Dies entspricht allerdings nicht der Normalform für (heterogene und) universelle Algebren, da das Axiom für das Neutralelement dann einen – zu vermeidenden – Existenzquantor erfordert.

Häufig wird für die Verknüpfung   das Symbol   benutzt, man spricht dann von einem multiplikativ geschriebenen Monoid. Das neutrale Element heißt dann Einselement und wird durch   symbolisiert. Wie auch bei der gewöhnlichen Multiplikation üblich, kann in vielen Situationen der Malpunkt weggelassen werden.

Ein Monoid lässt sich auch additiv notieren, indem für die Verknüpfung   das Symbol   benutzt wird. Das neutrale Element heißt dann Nullelement und wird durch   symbolisiert. Additiv geschriebene Monoide sind üblicherweise kommutativ.

Beispiele und Gegenbeispiele

Bearbeiten
  ist ein Monoid.
  ist ein Monoid. Damit ist   ein (Bewertungs-)Halbring.
  (die Menge der ganzen Zahlen mit der Addition) ist ein Monoid.
  ist kein Monoid, da die Subtraktion nicht assoziativ ist.
  (die Menge der n×n-Matrizen mit der üblichen Matrizenmultiplikation und der Einheitsmatrix E) ist ein nichtkommutatives Monoid.
  (der dreidimensionale reelle Raum mit dem Vektorprodukt) ist kein Monoid, da das Assoziativgesetz verletzt ist: Bezeichnen wir mit   den i-ten Einheitsvektor, so ist  , aber  .
  (die Menge der Vielfachen der ganzen Zahl n mit der Addition) ist ein Monoid (sogar eine Gruppe).
  (die Menge der nichtnegativen rationalen Zahlen mit der Addition) ist ein Monoid.
  (die Menge der positiven rationalen Zahlen mit der Multiplikation) ist ein Monoid. Damit ist   ein Halbring (sogar ein Halbkörper).
  (die Menge der positiven rationalen Zahlen mit der Division) ist kein Monoid, da die Division nicht assoziativ ist.
  (die Potenzmenge einer Menge X mit dem Schnittmengenoperator) ist ein kommutatives Monoid.
  die Wörter über dem Alphabet   bilden mit der Konkatenation   und dem leeren Wort  , das sogenannte Wortmonoid.
  die Endomorphismen eines Objekts   in einer beliebigen Kategorie  , d. h. die Morphismen  . Jedes Monoid lässt sich so als Kategorie mit genau einem (beliebigen) Objekt auffassen.

Untermonoid

Bearbeiten

Eine Teilmenge   eines Monoids  , die das neutrale Element   enthält und bezüglich der Verknüpfung   von   abgeschlossen ist (d. h., für alle   ist auch  ), heißt Untermonoid von  .

Monoid-Homomorphismus

Bearbeiten

Ein Monoid-Homomorphismus ist definiert als eine Abbildung   zwischen zwei Monoiden  ,  , für die gilt:

  •  ,
  •  .

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

Das Bild   eines Monoid-Homomorphismus   ist ein Untermonoid des Zielmonoids  .

Ist der Monoid-Homomorphismus   bijektiv, dann nennt man ihn einen Monoid-Isomorphismus und die Monoide   und   isomorph.

Freies Monoid

Bearbeiten

Ein Monoid   heißt frei, wenn es eine Teilmenge   gibt, so dass sich jedes Element von   eindeutig als endliches Produkt von Elementen aus   darstellen lässt.   heißt dann Basis (Erzeuger) des Monoids.

Ist   irgendeine Menge, dann bildet die Menge   aller endlichen Folgen in   mit dem Hintereinanderschreiben der Folgen als multiplikative Verknüpfung   und der leeren Folge als neutralem Element   das Monoid  . Dieses Monoid nennt man das von   erzeugte freie Monoid. Ist die Menge   endlich, dann spricht man meist vom Alphabet   und von Worten oder Wörtern über diesem Alphabet; man erhält das bereits erwähnte Wortmonoid.

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

Das freie Monoid   über   erfüllt folgende universelle Eigenschaft: Ist   ein Monoid und   eine beliebige Funktion, dann gibt es genau einen Monoid-Homomorphismus   mit   für alle  . Solche Homomorphismen werden in der theoretischen Informatik zur Definition formaler Sprachen (als Teilmengen von  ) genutzt.

Hat ein Monoid   eine Teilmenge  , so dass sich jedes Element von   eindeutig bis auf die Reihenfolge der Faktoren als Produkt von Elementen aus   darstellen lässt, dann nennt man   frei kommutativ mit dem Erzeuger  . Ein solches Monoid ist notwendig kommutativ.   ist in diesem Fall die Menge der Multimengen die Elemente von   enthalten. 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

Bearbeiten
  • Das Monoid   ist sowohl frei als auch frei kommutativ mit dem Erzeuger  .
  • Für eine Menge   ist die Menge   aller Abbildungen von   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   als Erzeuger (dabei ist   ein Kronecker-Delta).
  • Das Nullmonoid   ist sowohl frei als auch frei kommutativ mit der leeren Menge als Erzeuger.
  • Das Monoid   ist frei kommutativ über der Menge der Primzahlen, es ist aber kein freies Monoid.
  • Die Kleenesche Hülle   ist das von dem Alphabet   bezüglich der Konkatenation frei erzeugte Monoid.

Literatur

Bearbeiten
  • Dirk Hachenberger: Mathematik für Informatiker. 2. Auflage. Pearson Studium, München 2008, ISBN 978-3-8273-7320-5, Abschnitt 6.1.
Bearbeiten
Wiktionary: Monoid – Bedeutungserklärungen, Wortherkunft, Synonyme, Übersetzungen