Monoid

algebraische Struktur mit einer assoziativen binären Operation und einem neutralen Element

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 Addition und der Zahl 0 als neutralem Element. Ein Monoid, in dem jedes Element invertierbar ist, heißt Gruppe.

DefinitionBearbeiten

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 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 NotationBearbeiten

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

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.

Beispiele und GegenbeispieleBearbeiten

  ist ein Monoid.
  ist ein Monoid. Damit ist   ein Dioid.
  ist kein Monoid, da   unter Division nicht abgeschlossen ist und da die Division nicht assoziativ ist.
  (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.
  (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 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.

UntermonoidBearbeiten

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-HomomorphismusBearbeiten

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 MonoidBearbeiten

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.

BeispieleBearbeiten

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

LiteraturBearbeiten

  • Dirk Hachenberger: Mathematik für Informatiker. 2. Auflage. Pearson Studium, München 2008, ISBN 978-3-8273-7320-5, Abschnitt 6.1.