Halbgruppe

Eine Halbgruppe ${\displaystyle {\boldsymbol {S}}=(S,*)}$ besteht aus einer Menge ${\displaystyle S}$ und einer inneren zweistelligen Verknüpfung

${\displaystyle *\colon \,S\times S\to S,\,(a,b)\mapsto a*b,}$

die assoziativ ist, d. h. für alle ${\displaystyle a,b,c\in S}$ gilt

${\displaystyle a*(b*c)=(a*b)*c}$.

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 ${\displaystyle S}$ nichtleer ist. Die leere Menge ${\displaystyle \emptyset }$ bildet auch eine Halbgruppe bezüglich der leeren Verknüpfung

${\displaystyle \emptyset \colon \,\emptyset \times \emptyset \rightarrow \emptyset }$,

die leere oder triviale Halbgruppe ${\displaystyle (\emptyset ,\times )}$ genannt wird.

Bemerkungen zur Notation

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

Eine Halbgruppe lässt sich auch additiv notieren, indem für die Verknüpfung ${\displaystyle *}$ das Symbol ${\displaystyle +}$ 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

${\displaystyle a_{1}*\cdots *a_{n}:=(a_{1}*\cdots *a_{n-1})*a_{n}}$ für jedes ${\displaystyle n\geq 3}$,

dann haben alle Verknüpfungen von ${\displaystyle a_{1},\ldots ,a_{n}}$, die sich nur in der Klammerung von ${\displaystyle a_{1}*\cdots *a_{n}}$ unterscheiden, das gleiche Ergebnis (allgemeines Assoziativgesetz, Beweis: vollständige Induktion über ${\displaystyle n}$), man kann also für jede dieser Verknüpfungen einfach nur ${\displaystyle a_{1}*\cdots *a_{n}}$ schreiben.

Unterhalbgruppe

Seien ${\displaystyle {\boldsymbol {S}}=(S,*)}$ eine Halbgruppe und ${\displaystyle U\subseteq S}$. Ist dann ${\displaystyle {\boldsymbol {U}}:=(U,*)}$ eine Halbgruppe (${\displaystyle *}$ ist hier eine vereinfachte Schreibweise für die Einschränkung ${\displaystyle *|_{U\times U}}$ von ${\displaystyle *}$ auf ${\displaystyle U\times U}$), so heißt ${\displaystyle {\boldsymbol {U}}}$ Unterhalbgruppe von ${\displaystyle {\boldsymbol {S}}}$. Genau dann ist ${\displaystyle {\boldsymbol {U}}}$ eine Unterhalbgruppe von ${\displaystyle {\boldsymbol {S}}}$, wenn ${\displaystyle U}$ abgeschlossen ist bezüglich ${\displaystyle *}$, d. h. es gilt

${\displaystyle a*b\in U}$ für alle ${\displaystyle a,b\in U}$.

${\displaystyle {\boldsymbol {S}}}$ nennt man dann auch Oberhalbgruppe von ${\displaystyle {\boldsymbol {U}}}$.

Faktorhalbgruppe

Ist ${\displaystyle {\boldsymbol {S}}=(S,*)}$ eine Halbgruppe und ${\displaystyle R\subseteq S\times S}$ eine mit ${\displaystyle *}$ verträgliche Äquivalenzrelation auf ${\displaystyle S}$, so bildet die Faktormenge ${\displaystyle S/R}$ von ${\displaystyle S}$ nach ${\displaystyle R}$ zusammen mit der durch

${\displaystyle [a]{\;*}_{R\;}[b]:=[a*b]}$

definierten Verknüpfung ${\displaystyle {\;*}_{R\;}}$ ebenfalls eine Halbgruppe. Diese Halbgruppe ${\displaystyle {\boldsymbol {S}}/R=\left(S/R,*_{R}\right)}$ heißt die Faktorhalbgruppe oder Quotientenhalbgruppe von Fehler beim Parsen (SVG (MathML kann über ein Browser-Plugin aktiviert werden): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „http://localhost:6011/de.wikipedia.org/v1/“:): {\boldsymbol S} nach ${\displaystyle R}$. Die Verknüpfung ${\displaystyle {\;*}_{R\;}}$ wird die durch die Äquivalenzrelation induzierte Verknüpfung oder die kanonische Verknüpfung der Faktorhalbgruppe genannt.

Halbgruppenhomomorphismus

Eine Abbildung ${\displaystyle \varphi \colon \,S_{1}\rightarrow S_{2}}$ zwischen den Trägermengen zweier Halbgruppen ${\displaystyle {\boldsymbol {S}}_{1}=(S_{1},*_{1})}$ und ${\displaystyle {\boldsymbol {S}}_{2}=(S_{2},*_{2})}$ heißt Halbgruppenhomomorphismus, wenn gilt:

${\displaystyle \operatorname {\varphi } (a*_{1}b)=\operatorname {\varphi } (a)*_{2}\operatorname {\varphi } (b)}$

für alle ${\displaystyle a,b\in S_{1}}$. 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 ${\displaystyle \varphi }$ injektiv oder surjektiv oder beides ist, heißt der Homomorphismus ${\displaystyle \varphi }$ Mono-, Epi- bzw. Isomorphismus. Gilt ${\displaystyle S_{1}=S_{2},}$ so heißt der Homomorphismus ${\displaystyle \varphi }$ Endomorphismus von ${\displaystyle {\boldsymbol {S}}_{1}}$ und der Isomorphismus Automorphismus von ${\displaystyle {\boldsymbol {S}}_{1}}$.

Kommutativität

Die Halbgruppe ${\displaystyle {\boldsymbol {S}}=(S,*)}$ heißt kommutativ oder auch abelsch, wenn

${\displaystyle b*a=a*b}$

für alle ${\displaystyle a,b\in S}$ gilt. Die Verknüpfung ${\displaystyle *}$ 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

Ein Element ${\displaystyle a\in S}$ einer Halbgruppe ${\displaystyle {\boldsymbol {S}}=(S,*)}$ heißt idempotent, wenn ${\displaystyle a*a=a}$ gilt.

Sind alle Elemente der Halbgruppe ${\displaystyle {\boldsymbol {S}}}$ idempotent, so spricht man auch von einer idempotenten Halbgruppe oder einem Band.

Kürzbarkeit

Ein Element ${\displaystyle k\in S}$ heißt in ${\displaystyle {\boldsymbol {S}}=(S,*)}$ linkskürzbar, wenn für alle ${\displaystyle a,b\in S}$

${\displaystyle k*a=k*b\implies a=b}$

gilt, bzw. rechtskürzbar, wenn für alle ${\displaystyle a,b\in S}$

${\displaystyle a*k=b*k\implies a=b}$

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

${\displaystyle {\boldsymbol {S}}}$ heißt linkskürzbar, falls jedes Element aus ${\displaystyle S}$ linkskürzbar ist, oder rechtskürzbar, falls jedes Element aus ${\displaystyle S}$ rechtskürzbar ist, und kürzbar, wenn alle Elemente aus ${\displaystyle S}$ kürzbar sind. Eine endliche, kürzbare Halbgruppe ist eine Gruppe.

Neutrales Element

Ein Element ${\displaystyle e\in S}$ einer Halbgruppe ${\displaystyle {\boldsymbol {S}}=(S,*)}$ heißt linksneutral, wenn für alle ${\displaystyle a\in S}$ gilt:

${\displaystyle e*a=a}$.

Ein linksneutrales Element ${\displaystyle e}$ ist offensichtlich idempotent, aber ebenso linkskürzbar:

${\displaystyle e*a=e*b\implies a=e*a=e*b=b}$

für alle ${\displaystyle a,b\in S.}$ Umgekehrt ist in einer Halbgruppe ${\displaystyle (S,*)}$ auch jedes idempotente, linkskürzbare Element ${\displaystyle e}$ linksneutral, denn für alle ${\displaystyle a\in S}$ gilt:

${\displaystyle e*e*a=e*a,}$ also ${\displaystyle 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 ${\displaystyle {\boldsymbol {S}}}$ 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 ${\displaystyle {\boldsymbol {S}}}$. Eine Halbgruppe mit neutralem Element nennt man auch Monoid.

Invertierbarkeit und Inverses

In einer Halbgruppe ${\displaystyle (S,*)}$ mit einem linksneutralen Element ${\displaystyle e\in S}$ ist ein Element ${\displaystyle j\in S}$ linksinvertierbar, wenn ein ${\displaystyle i\in S}$ existiert, so dass gilt:

${\displaystyle i*j=e}$.

Man nennt dann ${\displaystyle i}$ ein Linksinverses (auch Linksinverse, f.) von ${\displaystyle j}$. Linksinvertierbare Elemente ${\displaystyle j\in S}$ sind stets linkskürzbar, denn für alle ${\displaystyle a,b\in S}$ gilt:

${\displaystyle j*a=j*b\implies a=e*a=i*j*a=i*j*b=e*b=b.}$

Ist jedes Element in ${\displaystyle S}$ linksinvertierbar, so ist auch jedes Element ${\displaystyle j\in S}$ rechtsinvertierbar, denn mit

${\displaystyle i*j=e}$ und ${\displaystyle h*i=e}$ für ${\displaystyle i,h\in S}$ folgt

${\displaystyle j*i=e*j*i=h*i*j*i=h*e*i=h*i=e.}$

Ebenso ist dann ${\displaystyle e}$ rechtsneutral:

${\displaystyle j*e=j*i*j=e*j=j}$.

${\displaystyle (S,*)}$ ist in diesem Fall also eine Gruppe, so dass alle Inversen eines Elements übereinstimmen.

Schwache Inverse

Gibt es in einer Halbgruppe ${\displaystyle (S,*)}$ zu einem ${\displaystyle i\in S}$ ein ${\displaystyle j\in S}$ mit

${\displaystyle j*i*j=j,}$

so wird dieses ${\displaystyle j}$ als schwache Inverse (oder schwaches Inverses) von ${\displaystyle i}$ bezeichnet. Ein solches ${\displaystyle j}$ ist dann gleichzeitig ein reguläres Element (engl. regular) in ${\displaystyle S.}$

Absorption

Ein Element ${\displaystyle o\in S}$ heißt linksabsorbierend in ${\displaystyle (S,*)}$, wenn für alle ${\displaystyle a\in S}$ gilt:

${\displaystyle o*a=o}$.

Jedes links- oder rechtsabsorbierende Element ist idempotent. Es gibt höchstens ein absorbierendes Element in einer Halbgruppe, denn gäbe es zwei absorbierende Elemente ${\displaystyle o_{1},o_{2}}$, dann gälte ${\displaystyle o_{1}=o_{1}*o_{2}=o_{2}}$.

Zur Entstehung des Namens

Die Menge ${\displaystyle \mathbb {N} _{0}=\{0,1,\ldots \}}$ der natürlichen Zahlen bildet mit der gewöhnlichen Addition eine kommutative und kürzbare Halbgruppe ${\displaystyle (\mathbb {N} _{0},+)}$, die keine Gruppe ist. Da hier die negativen Zahlen fehlen, also die „Hälfte“ der abelschen Gruppe ${\displaystyle (\mathbb {Z} ,+)}$ 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, später setzte sich dann die obige Definition allgemein durch.

${\displaystyle (\mathbb {N} ,+),(\mathbb {N} _{0},\cdot )}$ und ${\displaystyle (\mathbb {N} ,\cdot )}$ 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 ${\displaystyle X}$ sei ${\displaystyle {\mathcal {T}}_{X}:=\{\tau \mid \tau \colon X\rightarrow X\}}$ die Menge aller Funktionen von ${\displaystyle X}$. Bezeichnet ${\displaystyle \circ }$ die Komposition von Abbildungen ${\displaystyle \sigma ,\tau \in {\mathcal {T}}_{X}}$, also ${\displaystyle \tau \circ \sigma \colon \,x\mapsto \tau (\sigma (x))}$, dann ist ${\displaystyle ({\mathcal {T}}_{X},\circ )}$ eine Halbgruppe, die volle Transformationshalbgruppe über ${\displaystyle X}$. Idempotente Elemente in ${\displaystyle {\mathcal {T}}_{X}}$ sind z. B. für jedes ${\displaystyle a\in X}$ die konstanten Abbildungen ${\displaystyle \operatorname {c} _{a}\colon X\rightarrow X}$ mit ${\displaystyle \operatorname {c} _{a}(x)=a}$ für alle ${\displaystyle x\in X}$, aber auch die identische Abbildung ${\displaystyle \operatorname {id} _{X}}$ auf ${\displaystyle X}$ als neutrales Element. Unterhalbgruppen von ${\displaystyle ({\mathcal {T}}_{X},\circ )}$ heißen Transformationshalbgruppen auf ${\displaystyle X}$.

Formale Sprachen

Für eine beliebige Menge ${\displaystyle X\neq \emptyset }$ sei

${\displaystyle X^{*}:=\bigcup _{n\in \mathbb {N} _{0}}X^{n}}$

die kleenesche Hülle von ${\displaystyle X}$. Definiert man für alle ${\displaystyle (x_{1},\ldots ,x_{n}),(y_{1},\ldots ,y_{m})\in X^{*}}$ eine Multiplikation durch

${\displaystyle (x_{1},\ldots ,x_{n})\cdot (y_{1},\ldots ,y_{m})=(x_{1},\ldots ,x_{n},y_{1},\ldots ,y_{m}),}$

dann ist ${\displaystyle (X^{*},\cdot )}$ eine Halbgruppe und ebenfalls ein Monoid, die freie Halbgruppe über ${\displaystyle X}$. Schreibt man die Elemente ${\displaystyle (x_{1},\ldots ,x_{n})\in X^{*}}$ einfach in der Form ${\displaystyle x_{1}\ldots x_{n}}$, dann heißen die Elemente in ${\displaystyle X^{*}}$ Worte über dem Alphabet ${\displaystyle X}$, ${\displaystyle \varepsilon$ :=(\,)=\{\,\}} ist das leere Wort und die Multiplikation ${\displaystyle \cdot }$ bezeichnet man als Konkatenation. 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.

Funktionalanalysis, Partielle Differentialgleichungen

Halbgruppen spielen auch eine Rolle in der Lösungstheorie partieller Differentialgleichungen. Sei ${\displaystyle (A_{t})_{t\geq 0}:=(A_{t})_{t\in [0,\infty )}}$ eine Familie beschränkter Transformationen ${\displaystyle A_{t}\colon \,X\rightarrow X}$ auf einem vollständigen metrischen Raum ${\displaystyle (X,d)}$, d. h. zu jedem ${\displaystyle t\in [0,\infty )}$ existiert ein ${\displaystyle m_{t}\in [0,\infty )}$ mit

${\displaystyle d(A_{t}(x),A_{t}(y))\leq m_{t}\cdot d(x,y)}$ für alle ${\displaystyle x,y\in X}$.

Insbesondere ist dann jedes ${\displaystyle A_{t}}$ stetig und ${\displaystyle S:=\{A_{t}\mid t\in [0,\infty )\}}$ bildet eine kommutative Halbgruppe ${\displaystyle (S,\circ )}$ mit neutralem Element ${\displaystyle \operatorname {id} _{X}}$, wenn gilt:

${\displaystyle A_{0}=\operatorname {id} _{X}}$ und

${\displaystyle A_{t+s}=A_{t}\circ A_{s}}$ für alle ${\displaystyle t,s\geq 0}$.

Die Funktion ${\displaystyle (A_{t})_{t\geq 0}}$ ist ein Halbgruppenhomomorphismus von ${\displaystyle ([0,\infty ),+)}$ nach ${\displaystyle (S,\circ )}$ und wird eine einparametrige Halbgruppe von Operatoren genannt (siehe auch: kontinuierliches dynamisches System). Ein ${\displaystyle A_{t}}$ ist außerdem kontraktiv, falls

${\displaystyle d(A_{t}(x),A_{t}(y))<d(x,y)}$ ist für alle ${\displaystyle x,y\in X,x\neq y}$.

Die Halbgruppe ${\displaystyle (A_{t})_{t\geq 0}}$ heißt gleichmäßig stetig, wenn für alle ${\displaystyle t\geq 0}$ ${\displaystyle A_{t}}$ ein beschränkter linearer Operator auf einem Banachraum ${\displaystyle (X,\|.\|_{X})}$ ist und gilt:

${\displaystyle \lim _{t\downarrow 0}\|A_{t}-\operatorname {id} _{X}\|=0,}$

wobei ${\displaystyle \|\cdot \|}$ die Operatornorm bezeichne.

Die Halbgruppe ${\displaystyle (A_{t})_{t\geq 0}}$ heißt stark stetig, wenn für alle ${\displaystyle x\in X}$ die Abbildung

${\displaystyle [0,\infty )\to X,\,t\mapsto A_{t}(x),}$

stetig ist; dann existieren ${\displaystyle k,m\in \mathbb {R} }$ mit ${\displaystyle m\geq 1}$ so, dass

${\displaystyle \|A_{t}(x)\|_{X}\leq me^{kt}\|x\|_{X}}$

gilt. Kann ${\displaystyle k=0}$ gewählt werden, nennt man ${\displaystyle (A_{t})_{t\geq 0}}$ eine beschränkte einparametrige Halbgruppe.