Halbgruppen
Wir betrachten nun Aussagen, die in operationalen Strukturen gelten oder nicht gelten. Man spricht auch von Gesetzen oder Axiomen für diese Strukturen. Die Situation entspricht den relationalen Strukturen, bei denen wir Eigenschaften wie reflexiv, antisymmetrisch oder transitiv untersucht haben.
Wir beginnen mit einer fast unverzichtbaren Eigenschaft:
Definition (Halbgruppe, Assoziativgesetz)
Eine operationale Struktur (H, ∘) heißt assoziativ oder eine Halbgruppe, falls gilt:
∀a, b, c ∈ H a ∘ (b ∘ c) = (a ∘ b) ∘ c.(Assoziativgesetz)
Das Assoziativgesetz besagt kurz und bündig: Wir dürfen Klammern weglassen. Damit können wir einfach
a ∘ b ∘ c, a ∘ b ∘ c ∘ d, …
schreiben, denn jede Klammerung derartiger Terme führt zum gleichen Element der Halbgruppe. So gilt etwa
(a ∘ b) ∘ (c ∘ d) = a ∘ ((b ∘ c) ∘ d) für alle a, b, c, d ∈ H,
wie eine mehrfache Anwendung des Assoziativgesetzes zeigt.
Das Assoziativgesetz vereinfacht unsere Terme, hat aber im Hinblick auf Operationstafeln leider keine direkte anschauliche Bedeutung. Jedoch lässt sich Folgendes festhalten: Seien a, b ∈ A. Dann gilt für alle c ∈ A, dass
ℓa(ℓb(c)) = ℓa(b ∘ c) = a ∘ (b ∘ c) = (a ∘ b) ∘ c = ℓa ∘ b(c),
ra(rb(c)) = ra(c ∘ b) = (c ∘ b) ∘ a = c ∘ (b ∘ a) = rb ∘ a(c).
Damit gilt also
ℓa ∘ ℓb = ℓa ∘ b und ra ∘ rb = rb ∘ a,
wobei der jeweils erste Kringel die Komposition von Transformationen bezeichnet und der Kringel im Index jeweils die Operation auf A. Lesen wir die Zeilen und Spalten der Operationstafel von ∘ als Transformationen, so bedeutet dieses Ergebnis: Die Zeile von a ∘ b ist die Komposition der Zeile von a mit der Zeile von b, und die Spalte von b ∘ a ist die Komposition der Spalte von a mit der Spalte von b. Das ist immer noch nicht besonders anschaulich, aber immerhin haben wir einen Zusammenhang zwischen der Operation der Halbgruppe auf A und der Komposition auf der Transformationsstruktur AA ans Licht gebracht.
Bevor wir Beispiele für Halbgruppen betrachten, führen wir noch einen weiteren eng verwandten Strukturtyp ein.