Quelltext der Seite Halbgruppe

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

== Definitionen ==
=== Halbgruppe ===
Eine ''Halbgruppe'' ist ein geordnetes Paar <math>(H,*)</math> bestehend aus einer Menge <math>H</math> und einer inneren zweistelligen Verknüpfung

: <math>* \colon\, H\times H \to H,\, (a,b) \mapsto a*b,</math>

die assoziativ ist, d.&nbsp;h. für alle <math>a,b,c \in H</math> gilt

: <math>a*(b*c) = (a*b)*c</math>.
Eine Halbgruppe unterscheidet sich daher von einer [[Gruppe (Mathematik)|Gruppe]] darin, dass die zweistellige Verknüpfung hier nicht [[#Invertierbarkeit und Inverses|invertierbar]] sein muss und nicht zwingend ein [[#Neutrales Element|neutrales Element]] existiert.

Es wird nicht vorausgesetzt, dass <math>H</math> nichtleer ist. Die leere Menge <math>\emptyset</math> bildet auch eine Halbgruppe bezüglich der leeren [[Verknüpfung (Mathematik)|Verknüpfung]]

: <math>\emptyset\colon\, \emptyset\times\emptyset \rightarrow \emptyset</math>,

die ''leere'' oder ''triviale Halbgruppe'' <math>(\emptyset,\times)</math> genannt wird.

=== Bemerkungen zur Notation ===
Häufig wird für die Verknüpfung <math>*</math> das Symbol <math>\cdot</math> benutzt, man spricht dann von einer multiplikativ geschriebenen Halbgruppe. Wie auch bei der gewöhnlichen [[Multiplikation]] üblich, kann in vielen Situationen der Malpunkt <math>\cdot</math> weggelassen werden.

Eine Halbgruppe lässt sich auch additiv notieren, indem für die Verknüpfung <math>*</math> das Symbol <math>+</math> benutzt wird, was man in der Regel nur für [[Kommutativgesetz|kommutative]] Halbgruppen tut.

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

: <math>a_1*\cdots*a_n := (a_1*\cdots*a_{n-1})*a_n</math> für jedes <math>n \geq 3</math>,

dann haben alle Verknüpfungen von <math>a_1,\ldots,a_n</math>, die sich nur in der Klammerung von <math>a_1*\cdots*a_n</math> unterscheiden, das gleiche Ergebnis (''allgemeines Assoziativgesetz'', Beweis: [[vollständige Induktion]] über <math>n</math>), man kann also für jede dieser Verknüpfungen einfach nur <math>a_1*\cdots*a_n</math> schreiben.<ref>Mario Petrich: ''Introduction to Semigroups.'' S. 4. P.A. Grillet: ''Semigroups: An Introduction to the Structure Theory.'' S. 4f.</ref>

=== Unterhalbgruppe ===
Seien <math>\boldsymbol S = (S,*)</math> eine Halbgruppe und <math>U \subseteq S</math>. Ist dann <math>\boldsymbol U := (U,*)</math> eine Halbgruppe (<math>*</math> ist hier eine vereinfachte Schreibweise für die [[Einschränkung (Mathematik)|Einschränkung]] <math>*|_{U\times U}</math> von <math>*</math> auf <math>U\times U</math>), so heißt <math>\boldsymbol U</math> '''Unterhalbgruppe'''<!--Weiterleitungslemmata bitte fett lassen.--> von <math>\boldsymbol S</math>. Genau dann ist <math>\boldsymbol U</math> eine Unterhalbgruppe von <math>\boldsymbol S</math>, wenn <math>U</math> [[Abgeschlossenheit (algebraische Struktur)|abgeschlossen]] ist bezüglich <math>*</math>, d.&nbsp;h. es gilt

: <math>a*b \in U</math> für alle <math>a,b \in U</math>.

<math>\boldsymbol S</math> nennt man dann auch ''Oberhalbgruppe'' von <math>\boldsymbol U</math>.

=== Faktorhalbgruppe ===
Ist <math>\boldsymbol S = (S,*)</math> eine Halbgruppe und <math>R\subseteq S\times S</math> eine mit <math>*</math> [[Verträglichkeit (Mathematik)|verträgliche]] [[Äquivalenzrelation]] auf <math>S</math>, so bildet die [[Faktormenge (Mathematik)|Faktormenge]] <math>S/R</math> von <math>S</math> nach <math>R</math> zusammen mit der durch

: <math>[a] {\;*}_{R\;} [b] := [a*b]</math>

definierten Verknüpfung <math>{\;*}_{R\;}</math> ebenfalls eine Halbgruppe. Diese Halbgruppe <math>\boldsymbol S/R = \left(S/R,*_R\right)</math> heißt die '''Faktorhalbgruppe''' oder '''Quotientenhalbgruppe''' <!--Weiterleitungslemmata bitte fett lassen.--> von <math>\boldsymbol S</math> nach <math>R</math>. Die Verknüpfung <math>{\;*}_{R\;}</math> wird die ''durch die Äquivalenzrelation induzierte Verknüpfung'' oder die ''kanonische Verknüpfung der Faktorhalbgruppe'' genannt.

=== Halbgruppenhomomorphismus ===
Eine Abbildung <math>\varphi\colon\, S_1\rightarrow S_2</math> zwischen den Trägermengen zweier Halbgruppen <math>\boldsymbol S_1 = (S_1,*_1)</math> und <math>\boldsymbol S_2 = (S_2,*_2)</math> heißt ''Halbgruppen[[homomorphismus]]'', wenn gilt:

: <math>\operatorname{\varphi}(a *_1 b)=\operatorname{\varphi}(a)*_2 \operatorname{\varphi}(b)</math>

für alle <math>a,b \in S_1</math>. 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 <math>\varphi</math> [[Injektive Funktion|injektiv]] oder [[Surjektive Funktion|surjektiv]] oder [[Bijektive Funktion|beides]] ist, heißt der Homomorphismus <math>\varphi</math> ''Mono-, Epi-'' bzw. ''Isomorphismus.'' Gilt <math>S_1 = S_2,</math> so heißt der Homomorphismus <math>\varphi</math> ''Endomorphismus'' von <math>\boldsymbol S_1</math> und der Isomorphismus ''Automorphismus'' von <math>\boldsymbol S_1</math>.

== 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 <math>\boldsymbol S = (S,*)</math> heißt ''[[Kommutativität|kommutativ]]'' oder auch ''[[Abelsche Gruppe|abelsch]]'', wenn

: <math>b*a = a*b</math>

für alle <math>a,b \in S</math> gilt. Die Verknüpfung <math>*</math> 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ürliche Zahl|natürlichen Zahlen]] gegebene kommutative Halbgruppe fällt die Grothendieck-Gruppe mit der üblichen Konstruktion der [[Ganze Zahl|ganzen Zahlen]] zusammen.

=== Idempotenz ===
{{Hauptartikel|Idempotenz}}
Ein Element <math>a \in S</math> einer Halbgruppe <math>\boldsymbol S = (S,*)</math> heißt ''idempotent'', wenn <math>a*a = a</math>
gilt.

Sind alle Elemente der Halbgruppe <math>\boldsymbol S</math> idempotent, so spricht man auch von einer idempotenten Halbgruppe oder einem [[Band (Mathematik)|Band]].

=== Kürzbarkeit ===

Ein Element <math>k \in S</math> heißt in <math>\boldsymbol S = (S,*)</math> [[Kürzbarkeit|linkskürzbar]], wenn für alle <math>a,b \in S</math>

: <math>k*a = k*b \implies a = b</math>

gilt, bzw. rechtskürzbar, wenn für alle <math>a,b \in S</math>

: <math>a*k = b*k \implies a = b</math>

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

<math>\boldsymbol S</math> heißt ''linkskürzbar'', falls jedes Element aus <math>S</math> linkskürzbar ist, oder ''rechtskürzbar'', falls jedes Element aus <math>S</math> rechtskürzbar ist, und ''kürzbar'', wenn alle Elemente aus <math>S</math> kürzbar sind. Eine endliche, kürzbare Halbgruppe ist eine [[Gruppentheorie|Gruppe]].

{| {{Bausteindesign5}}
| '''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 <math>e \in S</math> einer Halbgruppe <math>\boldsymbol S = (S,*)</math> heißt [[Neutrales Element|linksneutral]], wenn für alle <math>a \in S</math> gilt:

: <math>e*a = a</math>.

Ein linksneutrales Element <math>e</math> ist offensichtlich idempotent, aber ebenso linkskürzbar:

: <math>e*a = e*b \implies a = e*a = e*b = b</math>

für alle <math>a,b \in S.</math> Umgekehrt ist in einer Halbgruppe <math>(S,*)</math> auch jedes idempotente, linkskürzbare Element <math>e</math> linksneutral, denn für alle <math>a \in S</math> gilt:

: <math>e*e*a = e*a,</math> also <math>e*a = a.</math>

Gibt es in einer Halbgruppe sowohl ein links- als auch ein rechtsneutrales Element, so sind diese identisch und somit neutral. In einer Halbgruppe <math>\boldsymbol S</math> 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 <math>\boldsymbol S</math>. Eine Halbgruppe mit neutralem Element nennt man auch ''[[Monoid]]''.

=== Invertierbarkeit und Inverses ===
In einer Halbgruppe <math>(S,*)</math> mit einem linksneutralen Element <math>e \in S</math> ist ein Element <math>j \in S</math> [[Inverses Element|linksinvertierbar]], wenn ein <math>i \in S</math> existiert, so dass gilt:

: <math>i*j = e</math>.

Man nennt dann <math>i</math> ein [[Inverses Element|Linksinverses]] (auch Linksinverse, ''f.'') von <math>j</math>. Linksinvertierbare Elemente <math>j \in S</math> sind stets linkskürzbar, denn für alle <math>a,b \in S</math> gilt:

: <math>j*a = j*b \implies a = e*a = i*j*a = i*j*b = e*b = b.</math>

Ist jedes Element in <math>S</math> linksinvertierbar, so ist auch jedes Element <math>j \in S</math> rechtsinvertierbar, denn mit

: <math>i*j = e</math> und <math>h*i = e</math> für <math>i,h \in S</math> folgt
: <math>j*i = e*j*i = h*i*j*i = h*e*i = h*i = e.</math>

Ebenso ist dann <math>e</math> rechtsneutral:

: <math>j*e = j*i*j = e*j = j</math>.

<math>(S,*)</math> ist in diesem Fall also eine [[Gruppe (Mathematik)|Gruppe]], so dass alle Inversen eines Elements übereinstimmen.

=== Schwache Inverse ===
Gibt es in einer Halbgruppe <math>(S,*)</math> zu einem <math>i\in S </math> ein <math>j\in S</math> mit
: <math>j*i*j = j , </math>
so wird dieses <math>j </math> als ''schwache Inverse'' (oder ''schwaches Inverses'') von <math>i </math> bezeichnet.<ref name="Gomes2002">{{Literatur|Hrsg=Gracinda M. S. Gomes|Titel=Semigroups, Algorithms, Automata and Languages|Online=https://books.google.com/books?id=IL58mAsfXOgC&pg=PA167|Jahr=2002|Verlag=World Scientific|ISBN=978-981-277-688-4|Seiten=167–168|Autor=John Fountain|Kapitel=An introduction to covers for semigroups}} [http://www-users.york.ac.uk/~jbf1/coimbra2.pdf preprint]</ref> Ein solches <math>j </math> ist dann gleichzeitig ein ''reguläres'' Element (engl. ''regular'') in <math>S . </math>

=== Absorption ===
Ein Element <math>o \in S</math> heißt [[Absorbierendes Element|linksabsorbierend]] in <math>(S,*)</math>, wenn für alle <math>a \in S</math> gilt:

: <math>o*a = o</math>.

Jedes links- oder rechtsabsorbierende Element ist idempotent. Es gibt höchstens ein absorbierendes Element in einer Halbgruppe, denn gäbe es zwei absorbierende Elemente <math>o_1, o_2</math>, dann gälte <math>o_1 = o_1*o_2 = o_2</math>.

== Beispiele ==
=== Zur Entstehung des Namens ===
Die Menge <math>\mathbb N_0 = \{0, 1, \ldots\}</math> der [[Natürliche Zahl|natürlichen Zahlen]] bildet mit der gewöhnlichen Addition eine kommutative und kürzbare Halbgruppe <math>(\mathbb N_0, +)</math>, die keine Gruppe ist. Da hier die negativen Zahlen fehlen, also die „Hälfte“ der abelschen Gruppe <math>(\mathbb Z,+)</math> 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,<ref>[[Paul Lorenzen]]: ''Abstrakte Begründung der multiplikativen Idealtheorie''. In: ''Math. Z.'', 45, 1939, S. 533–553.</ref> später setzte sich dann die obige Definition allgemein durch.

<math>(\mathbb{N}, +), (\mathbb{N}_0, \cdot)</math> und <math>(\mathbb{N}, \cdot)</math> 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 <math>X</math> sei <math>\mathcal T_X := \{\tau \mid \tau\colon X\rightarrow X\}</math> die Menge aller [[Funktion (Mathematik)|Funktionen]] von <math>X</math>. Bezeichnet <math>\circ</math> die [[Komposition (Mathematik)|Komposition]] von Abbildungen <math>\sigma,\tau \in \mathcal T_X</math>, also <math>\tau \circ \sigma\colon\, x \mapsto \tau(\sigma(x))</math>, dann ist <math>(\mathcal T_X,\circ)</math> eine Halbgruppe, die ''volle Transformationshalbgruppe'' über <math>X</math>. Idempotente Elemente in <math>\mathcal T_X</math> sind z.&nbsp;B. für jedes <math>a \in X</math> die konstanten Abbildungen <math>\operatorname{c}_a\colon X\rightarrow X</math> mit <math>\operatorname{c}_a(x) = a</math> für alle <math>x \in X</math>, aber auch die identische Abbildung <math>\operatorname{id}_X</math> auf <math>X</math> als neutrales Element. Unterhalbgruppen von <math>(\mathcal T_X,\circ)</math> heißen ''Transformationshalbgruppen'' auf <math>X</math>.<ref>[[John Mackintosh Howie]]: ''Fundamentals of Semigroup Theory.'' S. 6. P.A. Grillet: ''Semigroups: An Introduction to the Structure Theory.'' S. 2.</ref>

== Anwendung ==
=== Formale Sprachen ===
Für eine beliebige Menge <math>X \neq \emptyset</math> sei

: <math>X^* := \bigcup_{n \in \mathbb N_0} X^n</math>

die ''[[kleenesche Hülle]]'' von <math>X</math>. Definiert man für alle <math>(x_1, \ldots, x_n), (y_1, \ldots, y_m) \in X^*</math> eine Multiplikation durch

: <math>(x_1, \ldots, x_n) \cdot (y_1, \ldots, y_m) = (x_1, \ldots, x_n, y_1, \ldots, y_m),</math>

dann ist <math>(X^*, \cdot)</math> eine Halbgruppe und ebenfalls ein [[Monoid]], die ''freie Halbgruppe'' über <math>X</math>. Schreibt man die Elemente <math>(x_1, \ldots, x_n) \in X^*</math> einfach in der Form <math>x_1 \ldots x_n</math>, dann heißen die Elemente in <math>X^*</math> [[Wort (Theoretische Informatik)|Worte]] über dem [[Alphabet (Informatik)|Alphabet]] <math>X</math>, <math>\varepsilon := (\,) = \{\,\}</math> ist das [[Leeres Wort|leere Wort]] und die Multiplikation <math>\cdot</math> bezeichnet man als [[Konkatenation (Wort)|Konkatenation]].<ref>[[Udo Hebisch]], Hanns Joachim Weinert: ''Halbringe: Algebraische Theorie und Anwendungen in der Informatik.'' S. 244.</ref> In der [[Theoretische Informatik|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 Sprache]]n''.<ref>{{BibISBN|389319181X|Seite=1}}</ref>

=== Funktionalanalysis, Partielle Differentialgleichungen ===
Halbgruppen spielen auch eine Rolle in der Lösungstheorie [[Partielle Differentialgleichung|partieller Differentialgleichungen]]. Sei <math>(A_t)_{t\geq 0} := (A_t)_{t\in [0,\infty)}</math> eine [[Familie (Mathematik)|Familie]] beschränkter Transformationen <math>A_t\colon\, X\rightarrow X</math> auf einem vollständigen [[Metrischer Raum|metrischen Raum]] <math>(X,d)</math>, d.&nbsp;h. zu jedem <math>t \in [0,\infty)</math> existiert ein <math>m_t \in [0,\infty)</math> mit

: <math>d(A_t(x),A_t(y)) \leq m_t\cdot d(x,y)</math> für alle <math>x,y \in X</math>.

Insbesondere ist dann jedes <math>A_t</math> [[Stetige Funktion|stetig]] und <math>S := \{A_t\mid t\in [0,\infty)\}</math> bildet eine kommutative Halbgruppe <math>(S,\circ)</math> mit neutralem Element <math>\operatorname{id}_X</math>, wenn gilt:

: <math>A_0 = \operatorname{id}_X</math> und

: <math>A_{t+s} = A_t\circ A_s</math> für alle <math>t,s \geq 0</math>.

Die [[Familie (Mathematik)|Funktion]] <math>(A_t)_{t\geq 0}</math> ist ein Halbgruppenhomomorphismus von <math>([0,\infty),+)</math> nach <math>(S,\circ)</math> und wird eine ''einparametrige Halbgruppe von Operatoren'' genannt (siehe auch: kontinuierliches [[dynamisches System]]). Ein <math>A_t</math> ist außerdem kontraktiv, falls

: <math>d(A_t(x),A_t(y)) < d(x,y)</math> ist für alle <math>x,y \in X, x \neq y</math>.<ref>[[Einar Hille]]: ''Methods in Classical and Functional Analysis''. Addison-Wesley, Reading MA u.&nbsp;a. 1972. S. 165ff.</ref>

Die Halbgruppe <math>(A_t)_{t\geq 0}</math> heißt ''gleichmäßig stetig'', wenn für alle <math>t\geq 0</math> <math>A_t</math> ein beschränkter [[linearer Operator]] auf einem [[Banachraum]] <math>(X,\|.\|_X)</math> ist und gilt:

: <math>\lim_{t\downarrow0} \|A_t - \operatorname{id}_X\| = 0,</math>

wobei <math>\|\cdot\|</math> die [[Operatornorm]] bezeichne.

Die Halbgruppe <math>(A_t)_{t\geq 0}</math> heißt ''[[Stark stetige Halbgruppe|stark stetig]]'', wenn für alle <math>x\in X</math> die Abbildung

: <math>[0,\infty) \to X,\, t \mapsto A_t(x),</math>

stetig ist; dann existieren <math>k,m \in \R</math> mit <math>m \geq 1</math> so, dass

: <math>\|A_t(x)\|_X \leq me^{kt}\|x\|_X</math>

gilt. Kann <math>k = 0</math> gewählt werden, nennt man <math>(A_t)_{t\geq 0}</math> eine ''beschränkte einparametrige Halbgruppe''.

{{Siehe auch|stark stetige Halbgruppe}}

== Siehe auch ==
* [[Inverse Halbgruppe]]

== 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 OH 1973, ISBN 0-675-09062-8.

== Weblinks ==
{{Wiktionary}}
* {{EoM|Autor=[[Lev Shevrin]]|Titel=Semigroup|Url=http://eom.springer.de/S/s084110.htm|id=}}
* {{MathWorld |id=Semigroup |title=Semigroup}}
* Tero Harju: [http://users.utu.fi/harju/semigroups/semigroups.pdf ''Lecture Notes on Semigroups''.] (PDF; 454&nbsp;kB). Universität Turku, 1996 (Skript)

== Einzelnachweise und Anmerkungen ==
<references />

[[Kategorie:Mathematischer Grundbegriff]]
[[Kategorie:Algebraische Struktur]]
[[Kategorie:Gruppentheorie]]
[[Kategorie:Funktionalanalysis]]