Freie Halbgruppen und Monoide

Eine Halbgruppe $(S,*)$ heißt gleichteilbar, wenn für alle $s,t,u,v$ in $S$ aus $s*t\; =\; u*v$ folgt, daß ein $x$ aus $S1$ existiert mit $s\; =\; u\; *\; x$ und $x\; *\; t\; =\; v$, oder ein $y$ aus $S1$ mit $u\; =\; s\; *\; y$ und $t\; =\; y\; *\; v$.

Jede Gruppe und jede freie Halbgruppe sind gleichteilbar.

Im Fall einer Gruppe setze man $x\; =\; u-1*\; s$ oder $y\; =\; s-1*\; u$. Im Fall einer freien Halbgruppe $F$_A sei $s*t\; =\; u*v\; =\; a$₁...a_n mit $a$_i aus $A$. Dann gibt es Indizes $k,l$ aus $\{\; 0,1,...,n\; \}$ mit $s\; =\; a$₁...a_k, t = a_k+1...a_n und $u\; =\; a$₁...a_l, v = a_l+1...a_n. Im Fall sei $x\; =\; a$_l+1...a_k, sonst $y\; =\; a$_k+1...a_l, was für $k\; =\; l$ das leere Wort sein darf. Dann lassen sich die behaupteten Gleichungen nachrechnen.

Die algebraische Bedeutung freier Halbgruppen (und Monoide) wird durch die folgenden Überlegungen deutlich.

a) Ist $$ : A S eine beliebige Abbildung von $A$ in eine Halbgruppe $(S,*)$, dann existiert ein eindeutig bestimmter Homomorphismus $$^* : A⁺ S mit $$^*(a) = (a) für alle $a$ aus $A$.

Ist nämlich $$^* ein solcher Homomorphismus, so folgt

(2)

$$^*(a₁...a_n) = ^*(a₁)*...*^*(a_n) = (a₁)*...*(a_n)

für alle $a$₁...a_n aus $A+$, d. h. $$^* ist durch $$ eindeutig bestimmt. Definiert man andererseits $$^* gemäß $$^*(a₁...a_n) = (a₁)*...*(a_n), so ist es offensichtlich ein Homomorphismus.

b) Daher sind die oben konstruierten Monoide $A+$ freie Halbgruppen über $A$ im Sinn der folgenden abstrakten Definition.

Eine beliebige Halbgruppe $(F,*)$ heißt eine freie Halbgruppe über $A$, wenn es eine Abbildung $$ : A F gibt und für jede Halbgruppe $(S,*)$ und jede Abbildung $$ : A S einen eindeutig bestimmten Homomorphismus $$^*: F S, der $$^* o = erfüllt.

c) Für jedes Alphabet $A$ gibt es bis auf Isomorphie genau eine freie Halbgruppe über $A$.

Ist zunächst $(F,*)$ eine freie Halbgruppe mit der Abbildung $$ : A F und setzt man $(S,*)\; =\; (F,*)$ sowie $$ = , so ist der eindeutig bestimmte Homomorphismus $$^* offensichtlich die identische Abbildung auf $F$. Ist nun $(F\text{'},*)$ eine weitere freie Halbgruppe mit der Abbildung $$' : A F und setzt man $(S,*)\; =\; (F\text{'},*)$ sowie $$ = ', so gibt es genau einen Homomorphismus $$^*: F F' mit $$^* o = '. Vertauscht man die Rollen von $F$ und $F\text{'}$, so erhält man einen eindeutig bestimmten Homomorphismus $$'^*: F' F mit $$'^* o ' = . Es folgen $$'^* o ^* o = und $$^* o '^* o ' = '. Daher sind die eindeutig bestimmten Homomorphismen $$^* o '^* und $$'^* o ^* die identischen Abbildungen auf $F\text{'}$ bzw. $F$, d. h. sowohl $$^* als auch $$'^* sind Isomorphismen.

d) Eine Halbgruppe $(S,*)$ ist genau dann eine freie Halbgruppe, wenn jedes Element von $S$ sich eindeutig als Produkt von Elementen aus $S\; \backslash \; S2$ darstellen läßt.

Offensichtlich hat jede Halbgruppe $S\; =\; A+$ diese Eigenschaft, denn dann ist $S\; \backslash \; S2=\; A$, da $S2$ aus genau den Worten mit einer Länge größer als 1 besteht. Sei umgekehrt $(S,*)$ eine Halbgruppe mit dieser Eigenschaft und $A\; =\; S\; \backslash \; S2$ sowie $$ : A T eine Abbildung in eine beliebige Halbgruppe. Für $s$ in $S$ sei $s\; =\; a$₁...a_n die eindeutige Darstellung mit Elementen aus $A.$ Definiere $$^* : S T durch $$^*(s) = (a₁)...(a_n). Dann ist offensichtlich $$ der eindeutig bestimmte Homomorphismus auf $S$, der $$ fortsetzt. Also ist $S$ eine freie Halbgruppe.

e) Sei $$ : A⁺ S ein Halbgruppenhomomorphismus und $$ :T S ein surjektiver Halbgruppenhomomorphismus. Dann gibt es einen Homomorphismus $$^*: A⁺ T mit $$ = o ^*.

Wähle dazu für jedes $a$ aus $A$ ein Element $$(a) aus der nichtleeren Menge $$^-1((a)) willkürlich aus. Dies ist möglich, da $$ surjektiv ist. Also ist $$ : A T eine Abbildung, die sich nach a) zu einem Homomorphismus $$^* : A⁺ T fortsetzen läßt. Für alle $a$₁...a_n aus $A+$ gilt dann aber $$(a₁...a_n) = (a₁)... (a_n) = ((a₁))... ((a_n)) = ((a₁)... (a_n)) = (^*(a₁...a_n)).