- 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.
Inhaltsverzeichnis
Definitionen
Halbgruppe
Eine Halbgruppe
besteht aus einer Menge S und einer inneren zweistelligen Verknüpfung
die assoziativ ist, d. h. für alle
gilt
- a * (b * c) = (a * b) * c.
Man muss nicht voraussetzen, dass S 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
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 wie
(allgemeines Assoziativgesetz, Beweis: vollständige Induktion über n), man kann also für jede dieser Verknüpfungen einfach nur
schreiben.[1]
Unterhalbgruppe
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 U abgeschlossen ist bezüglich * , d. h. es gilt
für alle
.
nennt man dann auch Oberhalbgruppe von
.
Faktorhalbgruppe
Ist
eine Halbgruppe und
eine mit * verträgliche Äquivalenzrelation auf S, so bildet die Faktormenge S / R von S nach R zusammen mit der durch
definierten Verknüpfung
ebenfalls eine Halbgruppe. Diese Halbgruppe
heißt die Faktorhalbgruppe oder Quotientenhalbgruppe von
nach R. Die Verknüpfung
wird die durch die Äquivalenzrelation induzierte Verknüpfung oder die kanonische Verknüpfung der Faktorhalbgruppe genannt.
Halbgruppenhomomorphismus
Eine Abbildung
zwischen zwei Halbgruppen
und
heißt Halbgruppenhomomorphismus, wenn gilt:
für alle
. Ist aus dem Zusammenhang klar, das 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 S1 = S2, so heißt der Homomorphismus φ Endomorphismus von
und der Isomorphismus Automorphismus von
.
Eigenschaften
Es folgt eine Übersicht über grundlegende algebraische Eigenschaften, interpretiert und angewandt auf Halbgruppen. Genauere Informationen finden sich in den entsprechenden Hauptartikeln.
Kommutativität
Die Halbgruppe
heißt kommutativ oder auch abelsch, wenn
- b * a = a * b
für alle
gilt. Die Verknüpfung * selbst wird hierbei auch als kommutativ bezeichnet.
Idempotenz
Ein Element
einer Halbgruppe
heißt idempotent, wenn a * a = a gilt.
Sind alle Elemente der Halbgruppe
idempotent, so spricht man auch von einer idempotenten Halbgruppe oder einem Band.
Kürzbarkeit
Ein Element
heißt in
linkskürzbar, wenn für alle
gilt, bzw. rechtskürzbar, wenn für alle
gilt. Ist k 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 S linkskürzbar ist, oder rechtskürzbar, falls jedes Element aus S rechtskürzbar ist, und kürzbar, wenn alle Elemente aus S 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
Ein Element
einer Halbgruppe
heißt linksneutral, wenn für alle
gilt:
- e * a = a.
Ein linksneutrales Element e ist offensichtlich idempotent, aber ebenso linkskürzbar:
für alle
Umgekehrt ist in einer Halbgruppe (S, * ) auch jedes idempotente, linkskürzbare Element e linksneutral, denn für alle
gilt:
- e * e * a = e * a, also e * a = a.
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
In einer Halbgruppe
mit einem linksneutralen Element
ist ein Element
linksinvertierbar, wenn ein
existiert, so dass gilt:
- i * j = e.
Man nennt dann i ein Linksinverses von j. Linksinvertierbare Elemente
sind stets linkskürzbar, denn für alle
gilt:
Ist jedes Element in
linksinvertierbar, so ist auch jedes Element
rechtsinvertierbar, denn mit
- i * j = e und h * i = e für
folgt
- j * i = e * j * i = h * i * j * i = h * e * i = h * i = e.
Ebenso ist dann e rechtsneutral:
- j * e = j * i * j = e * j = j.
ist in diesem Fall also eine Gruppe, so dass alle Inversen eines Elements übereinstimmen.
Absorption
Ein Element
heißt linksabsorbierend in (S, * ), wenn für alle
gilt:
- o * a = o.
Jedes (links- oder rechts-)absorbierende Element ist idempotent und es gibt höchstens ein absorbierendes (d. h. links- und rechtsabsorbierendes) Element in einer Halbgruppe.
Beispiele
Zur Entstehung des Namens
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“[2] der abelschen Gruppe
der ganzen Zahlen, lag der Name Halbgruppe für diese 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
Für eine beliebige Menge X sei
die Menge aller Transformationen von X. Bezeichnet
die Komposition von Abbildungen
, also
, dann ist
eine Halbgruppe, die volle Transformationshalbgruppe über X. Idempotente Elemente in
sind z. B. für jedes
die konstanten Abbildungen
mit
für alle
, aber auch die identische Abbildung
auf X als neutrales Element. Unterhalbgruppen von
heißen Transformationshalbgruppen auf X.[4]
Anwendung
Formale Sprachen
Für eine beliebige Menge
sei
die kleenesche Hülle von X. Definiert man für alle
eine Multiplikation durch
dann ist
eine Halbgruppe, die freie Halbgruppe über X. Schreibt man die Elemente
einfach in der Form
, dann heißen die Elemente in X * Worte über dem Alphabet X,
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
Halbgruppen spielen auch eine Rolle in der Lösungstheorie partieller Differentialgleichungen. Sei
eine Familie beschränkter Transformationen
auf einem vollständigen metrischen Raum (X,d), d.h. zu jedem
existiert ein
mit
für alle
.
Insbesondere ist dann jedes At 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 At ist außerdem kontraktiv, falls
- d(At(x),At(y)) < d(x,y) ist für alle
.[7]
Die Halbgruppe
heißt gleichmäßig stetig, wenn für alle
At ein beschränkter linearer Operator auf einem Banach-Raum
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 k = 0 gewählt werden, nennt man
eine beschränkte einparametrige Halbgruppe.
Bitte weiterlesen unter stark stetige Halbgruppe.
Siehe auch
Einzelnachweise und Anmerkungen
- ↑ Mario Petrich: Introduction to Semigroups. S. 4. P.A. Grillet: Semigroups: An Introduction to the Structure Theory. S. 4f.
- ↑ Dass mit den negativen Zahlen eine „Hälfte“ der Menge der ganzen Zahlen fehle, mag zwar zunächst plausibel erscheinen, ist aber mathematisch nicht haltbar: In der Tat lässt sich die Menge der negativen Zahlen bijektiv auf die Menge aller ganzen Zahlen abbilden. Folglich gibt es „genauso viele negative wie ganze Zahlen“, nämlich abzählbar unendlich viele.
- ↑ vgl. Paul Lorenzen: Abstrakte Begründung der multiplikativen Idealtheorie. Math. Z. 45 (1939), 533–553.
- ↑ John Mackintosh Howie: Fundamentals of Semigroup Theory. S. 6. P.A. Grillet: Semigroups: An Introduction to the Structure Theory. S. 2.
- ↑ Udo Hebisch, Hanns Joachim Weinert: Halbringe: Algebraische Theorie und Anwendungen in der Informatik. S. 244.
- ↑ 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.
- ↑ Einar Hille: Methods in Classical and Functional Analysis. Addison-Wesley, Reading (Mass.) u.a. 1972. S. 165ff.
Literatur
- 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, Ohio, 1973, ISBN 0-675-09062-8.
Weblinks
- L. N. Shevrin: Semigroup. In: Michiel Hazewinkel (Hrsg.): Encyclopaedia of Mathematics. Springer-Verlag, Berlin 2002, ISBN 1-4020-0609-8.
- Eric W. Weisstein: Semigroup. In: MathWorld. (englisch)
- Tero Harju: Lecture Notes on Semigroups. Universität Turku 1996 (Skript)
Wikimedia Foundation.