Halbgruppe

algebraische Struktur mit assoziativer binärer Operation
(Weitergeleitet von Kommutative Halbgruppe)

In der Mathematik ist eine Halbgruppe eine algebraische Struktur bestehend aus einer Menge mit einer inneren zweistelligen Verknüpfung, die dem Assoziativgesetz genügt (also ein assoziatives Magma). Sie ist eine Verallgemeinerung einer Gruppe.

Definitionen

Bearbeiten

Halbgruppe

Bearbeiten

Eine Halbgruppe ist ein geordnetes Paar   bestehend aus einer Menge   und einer inneren zweistelligen Verknüpfung

 

die assoziativ ist, d. h. für alle   gilt

 .

Eine Halbgruppe unterscheidet sich daher von einer Gruppe darin, dass die zweistellige Verknüpfung hier nicht invertierbar sein muss und nicht zwingend ein neutrales Element existiert.

Es wird nicht vorausgesetzt, dass   nichtleer ist. Die leere Menge   bildet auch eine Halbgruppe bezüglich der leeren Verknüpfung

 ,

die leere oder triviale Halbgruppe   genannt wird.

Bemerkungen zur Notation

Bearbeiten

Häufig wird für die Verknüpfung   das Symbol   benutzt, man spricht dann von einer multiplikativ geschriebenen Halbgruppe. Wie auch bei der gewöhnlichen Multiplikation üblich, kann in vielen Situationen der Malpunkt   weggelassen werden.

Eine Halbgruppe lässt sich auch additiv notieren, indem für die Verknüpfung   das Symbol   benutzt wird, was man in der Regel nur für kommutative Halbgruppen tut.

Mit der Gültigkeit des Assoziativgesetzes lässt sich eine vereinfachte klammerfreie Notation einführen, denn sei

  für jedes  ,

dann haben alle Verknüpfungen von  , die sich nur in der Klammerung von   unterscheiden, das gleiche Ergebnis (allgemeines Assoziativgesetz, Beweis: vollständige Induktion über  ), man kann also für jede dieser Verknüpfungen einfach nur   schreiben.[1]

Unterhalbgruppe

Bearbeiten

Seien   eine Halbgruppe und  . Ist dann   eine Halbgruppe (  ist hier eine vereinfachte Schreibweise für die Einschränkung   von   auf  ), so heißt   Unterhalbgruppe von  . Genau dann ist   eine Unterhalbgruppe von  , wenn   abgeschlossen ist bezüglich  , d. h. es gilt

  für alle  .

  nennt man dann auch Oberhalbgruppe von  .

Faktorhalbgruppe

Bearbeiten

Ist   eine Halbgruppe und   eine mit   verträgliche Äquivalenzrelation auf  , so bildet die Faktormenge   von   nach   zusammen mit der durch

 

definierten Verknüpfung   ebenfalls eine Halbgruppe. Diese Halbgruppe   heißt die Faktorhalbgruppe oder Quotientenhalbgruppe von   nach  . Die Verknüpfung   wird die durch die Äquivalenzrelation induzierte Verknüpfung oder die kanonische Verknüpfung der Faktorhalbgruppe genannt.

Halbgruppenhomomorphismus

Bearbeiten

Eine Abbildung   zwischen den Trägermengen zweier Halbgruppen   und   heißt Halbgruppenhomomorphismus, wenn gilt:

 

für alle  . Ist aus dem Zusammenhang klar, dass es sich um einen Homomorphismus zwischen Halbgruppen handelt, so lässt man den Zusatz Halbgruppen- auch weg. Je nachdem, ob   injektiv oder surjektiv oder beides ist, heißt der Homomorphismus   Mono-, Epi- bzw. Isomorphismus. Gilt   so heißt der Homomorphismus   Endomorphismus von   und der Isomorphismus Automorphismus von  .

Eigenschaften

Bearbeiten

Es folgt eine Übersicht über grundlegende algebraische Eigenschaften, interpretiert und angewandt auf Halbgruppen. Genauere Informationen finden sich in den entsprechenden Hauptartikeln.

Kommutativität

Bearbeiten

Die Halbgruppe   heißt kommutativ oder auch abelsch, wenn

 

für alle   gilt. Die Verknüpfung   selbst wird hierbei auch als kommutativ bezeichnet.

Über eine nach Alexander Grothendieck benannte Konstruktion lässt sich zu einer gegebenen kommutativen Halbgruppe eine Gruppe konstruieren, die Grothendieck-Gruppe. Für die durch die Addition von natürlichen Zahlen gegebene kommutative Halbgruppe fällt die Grothendieck-Gruppe mit der üblichen Konstruktion der ganzen Zahlen zusammen.

Idempotenz

Bearbeiten

Ein Element   einer Halbgruppe   heißt idempotent, wenn   gilt.

Sind alle Elemente der Halbgruppe   idempotent, so spricht man auch von einer idempotenten Halbgruppe oder einem Band.

Kürzbarkeit

Bearbeiten

Ein Element   heißt in   linkskürzbar, wenn für alle  

 

gilt, bzw. rechtskürzbar, wenn für alle  

 

gilt. Ist   sowohl links- als auch rechtskürzbar, so heißt es zweiseitig kürzbar oder einfach nur kürzbar.

  heißt linkskürzbar, falls jedes Element aus   linkskürzbar ist, oder rechtskürzbar, falls jedes Element aus   rechtskürzbar ist, und kürzbar, wenn alle Elemente aus   kürzbar sind. Eine endliche, kürzbare Halbgruppe ist eine Gruppe.

Hinweis: In den folgenden Definitionen wird nur die linksseitige Variante stellvertretend für die entsprechende rechts- und beidseitige Variante aufgeführt; die rechts- und beidseitigen Varianten sind analog definiert.

Neutrales Element

Bearbeiten

Ein Element   einer Halbgruppe   heißt linksneutral, wenn für alle   gilt:

 .

Ein linksneutrales Element   ist offensichtlich idempotent, aber ebenso linkskürzbar:

 

für alle   Umgekehrt ist in einer Halbgruppe   auch jedes idempotente, linkskürzbare Element   linksneutral, denn für alle   gilt:

  also  

Gibt es in einer Halbgruppe sowohl ein links- als auch ein rechtsneutrales Element, so sind diese identisch und somit neutral. In einer Halbgruppe   gibt es höchstens ein neutrales Element (ansonsten entweder nur links- oder nur rechtsneutrale oder weder noch), man spricht dann von dem neutralen Element von  . Eine Halbgruppe mit neutralem Element nennt man auch Monoid.

Invertierbarkeit und Inverses

Bearbeiten

In einer Halbgruppe   mit einem linksneutralen Element   ist ein Element   linksinvertierbar, wenn ein   existiert, so dass gilt:

 .

Man nennt dann   ein Linksinverses (auch Linksinverse, f.) von  . Linksinvertierbare Elemente   sind stets linkskürzbar, denn für alle   gilt:

 

Ist jedes Element in   linksinvertierbar, so ist auch jedes Element   rechtsinvertierbar, denn mit

  und   für   folgt
 

Ebenso ist dann   rechtsneutral:

 .

  ist in diesem Fall also eine Gruppe, so dass alle Inversen eines Elements übereinstimmen.

Schwache Inverse

Bearbeiten

Gibt es in einer Halbgruppe   zu einem   ein   mit

 

so wird dieses   als schwache Inverse (oder schwaches Inverses) von   bezeichnet.[2] Ein solches   ist dann gleichzeitig ein reguläres Element (engl. regular) in  

Absorption

Bearbeiten

Ein Element   heißt linksabsorbierend in  , wenn für alle   gilt:

 .

Jedes links- oder rechtsabsorbierende Element ist idempotent. Es gibt höchstens ein absorbierendes Element in einer Halbgruppe, denn gäbe es zwei absorbierende Elemente  , dann gälte  .

Beispiele

Bearbeiten

Zur Entstehung des Namens

Bearbeiten

Die Menge   der natürlichen Zahlen bildet mit der gewöhnlichen Addition eine kommutative und kürzbare Halbgruppe  , die keine Gruppe ist. Da hier die negativen Zahlen fehlen, also die „Hälfte“ der abelschen Gruppe   der ganzen Zahlen, lag der Name Halbgruppe für diese mathematische Struktur nahe. Tatsächlich wurde in der Vergangenheit der Begriff „Halbgruppe“ für ein nach den oben gegebenen Definitionen kommutatives, kürzbares Monoid verwendet,[3] später setzte sich dann die obige Definition allgemein durch.

  und   bilden Beispiele für kommutative Halbgruppen mit verschiedenen Eigenschaften bezüglich neutraler und absorbierender Elemente sowie der Kürzbarkeit.

Transformationshalbgruppen

Bearbeiten

Für eine beliebige Menge   sei   die Menge aller Funktionen von  . Bezeichnet   die Komposition von Abbildungen  , also  , dann ist   eine Halbgruppe, die volle Transformationshalbgruppe über  . Idempotente Elemente in   sind z. B. für jedes   die konstanten Abbildungen   mit   für alle  , aber auch die identische Abbildung   auf   als neutrales Element. Unterhalbgruppen von   heißen Transformationshalbgruppen auf  .[4]

Anwendung

Bearbeiten

Formale Sprachen

Bearbeiten

Für eine beliebige Menge   sei

 

die kleenesche Hülle von  . Definiert man für alle   eine Multiplikation durch

 

dann ist   eine Halbgruppe und ebenfalls ein Monoid, die freie Halbgruppe über  . Schreibt man die Elemente   einfach in der Form  , dann heißen die Elemente in   Worte über dem Alphabet  ,   ist das leere Wort und die Multiplikation   bezeichnet man als Konkatenation.[5] In der theoretischen Informatik setzt man in der Regel voraus, dass ein Alphabet endlich ist, Teilmengen der kleeneschen Hülle eines Alphabets mit dem leeren Wort nennt man formale Sprachen.[6]

Funktionalanalysis, Partielle Differentialgleichungen

Bearbeiten

Halbgruppen spielen auch eine Rolle in der Lösungstheorie partieller Differentialgleichungen. Sei   eine Familie beschränkter Transformationen   auf einem vollständigen metrischen Raum  , d. h. zu jedem   existiert ein   mit

  für alle  .

Insbesondere ist dann jedes   stetig und   bildet eine kommutative Halbgruppe   mit neutralem Element  , wenn gilt:

  und
  für alle  .

Die Funktion   ist ein Halbgruppenhomomorphismus von   nach   und wird eine einparametrige Halbgruppe von Operatoren genannt (siehe auch: kontinuierliches dynamisches System). Ein   ist außerdem kontraktiv, falls

  ist für alle  .[7]

Die Halbgruppe   heißt gleichmäßig stetig, wenn für alle     ein beschränkter linearer Operator auf einem Banachraum   ist und gilt:

 

wobei   die Operatornorm bezeichne.

Die Halbgruppe   heißt stark stetig, wenn für alle   die Abbildung

 

stetig ist; dann existieren   mit   so, dass

 

gilt. Kann   gewählt werden, nennt man   eine beschränkte einparametrige Halbgruppe.

Siehe auch

Bearbeiten

Literatur

Bearbeiten
  • Pierre Antoine Grillet: Semigroups: An Introduction to the Structure Theory. Marcel Dekker, New York 1995, ISBN 0-8247-9662-4.
  • Udo Hebisch, Hanns Joachim Weinert: Halbringe: Algebraische Theorie und Anwendungen in der Informatik. B.G. Teubner, Stuttgart 1993, ISBN 3-519-02091-2.
  • John F. Berglund, Hugo D. Junghenn, Paul Milnes: Analysis on Semigroups: Function Spaces, Compactifications, Representations. John Wiley & Sons, New York et al. 1989, ISBN 0-471-61208-1.
  • John M. Howie: Fundamentals of Semigroup Theory. Oxford University Press, Oxford 1995, ISBN 0-19-851194-9.
  • Mario Petrich: Introduction to Semigroups. Bell & Howell, Columbus OH 1973, ISBN 0-675-09062-8.
Bearbeiten
Wiktionary: Halbgruppe – Bedeutungserklärungen, Wortherkunft, Synonyme, Übersetzungen

Einzelnachweise und Anmerkungen

Bearbeiten
  1. Mario Petrich: Introduction to Semigroups. S. 4. P.A. Grillet: Semigroups: An Introduction to the Structure Theory. S. 4f.
  2. John Fountain: Semigroups, Algorithms, Automata and Languages. Hrsg.: Gracinda M. S. Gomes. World Scientific, 2002, ISBN 978-981-277-688-4, An introduction to covers for semigroups, S. 167–168 (google.com). preprint
  3. Paul Lorenzen: Abstrakte Begründung der multiplikativen Idealtheorie. In: Math. Z., 45, 1939, S. 533–553.
  4. John Mackintosh Howie: Fundamentals of Semigroup Theory. S. 6. P.A. Grillet: Semigroups: An Introduction to the Structure Theory. S. 2.
  5. Udo Hebisch, Hanns Joachim Weinert: Halbringe: Algebraische Theorie und Anwendungen in der Informatik. S. 244.
  6. John E. Hopcroft, Jeffrey Ullman: Einführung in die Automatentheorie, formale Sprachen und Komplexitätstheorie. 2. Auflage. Addison-Wesley, Bonn / München 1990, ISBN 3-89319-181-X, S. 1 (englisch, Originaltitel: Introduction to automata theory, languages and computation.).
  7. Einar Hille: Methods in Classical and Functional Analysis. Addison-Wesley, Reading MA u. a. 1972. S. 165ff.