Cayley-Tafeln und Light's Assoziativitätstest


Zur Definition einer Verknüpfung * auf einer kleinen endlichen Menge G benutzt man oft die Form einer Tabelle, eine Methode die auf Arthur Cayley zurückgeht, der sie erstmals bei der Beschreibung von Gruppen einsetzte. Daher werden diese Verknüpfungstafeln auch oft Cayley-Tafeln genannt.

Dabei schreibt man die Elemente der Menge G in einer festen Reihenfolge als Kopfzeile und Kopfspalte einer quadratischen Tabelle und schreibt an den Schnittpunkt der mit dem Element a beschrifteten Zeile und der mit dem Element b beschrifteten Spalte dasjenige Element von G hin, das sich bei der Verknüpfung a*b ergeben soll.


So kann man etwa auf der Menge G = {e, a, b, c, d} die Verknüpfung * wie folgt definieren:

*
e a b c d
e
a
b
c
d
e a b c d
a e d b c
b c a d e
c d e a b
d b c e a

Nun kann man beispielsweise aus dem Eintrag "b" in der mit "a" beschrifteten Zeile und der mit "c" beschrifteten Spalte ablesen, daß a*c = b gelten soll.


Einige Eigenschaften der Verknüpfung * kann man leicht aus der Cayley-Tafel ablesen:

Die Kommutativität zeigt sich an der Symmetrie der Tafel zur "Hauptdiagonalen", die von links oben nach rechts unten verläuft. Sie ist im obigen Beispiel nicht gegeben, da etwa a*c = b aber c*a = d gilt.

Die Idempotenz eines Elementes zeigt sich an seinem Auftreten auf der Hauptdiagonalen an der durch das Element selbst bestimmten Zeile und/oder Spalte. Damit ist auch die Idempotenz der Verknüpfung einfach zu erkennen. Im angegebenen Beispiel ist nur das Element e idempotent.

Ein neutrales Element macht sich dadurch bemerkbar, daß in "seiner" Zeile und "seiner" Spalte die Kopfzeile bzw. die Kopfspalte wiederholt wird. Dies ist im obigen Beispiel genau für das Element e der Fall.

Die Linkskürzbarkeit bzw. Rechtskürzbarkeit eines Elementes erkennt man daran, daß in "seiner" Zeile bzw. "seiner" Spalte jedes Element von G höchstens (und damit wegen der Endlichkeit von G genau) einmal auftritt. Sie ist im obigen Beispiel für alle Elemente gegeben und daher handelt es sich um eine Quasigruppe, wegen des neutralen Elementes also sogar um eine Loop.


Am schwierigsten zu prüfen ist die Assoziativität. Dies geschieht etwa durch den folgenden Assoziativitätstest nach F. W. Light.

Für jedes Element y von G ist zu prüfen, ob für alle x, z gilt

v(x,z) = x*(y*z) = (x*y)*z = v'(x,z),

d. h., ob die beiden durch v und v' definierten Verknüpfungen auf G übereinstimmen. Man schreibt also im Prinzip für jedes y die Verknüpfungstafel für v(x,z)=x*(y*z) und für v'(x,z)=(x*y)*z nebeneinander und vergleicht sie anschließend. Zur Aufstellung der Tafel für v(x,z) muß einfach nur in der Tafel für * die Spalte des Elemente "z" durch die Spalte des Elementes "y*z" ersetzt werden. Zur Aufstellung der Tafel für v'(x,z) muß entsprechend nur in der Tafel für * die Zeile des Elemente "x" durch die Zeile des Elementes "x*y" ersetzt werden. Dabei kann man sich das explizite Hinschreiben der Tafel für v'(x,z) sparen und nur nachschauen, ob die hinzuschreibende Zeile für v'(x,z) schon in der betreffenden Zeile für v(x,z) steht. Ist dies einmal nicht der Fall, hat man die Assoziativität von * bereits widerlegt und auch ein Gegenbeispiel gefunden.


In dem konkreten Beispiel von oben verläuft etwa der Test für y=a wie folgt: Man stellt die Tafel für v(x,z)=x*(a*z) auf, indem man als Kopfzeile die Zeile von "a" aus der Tafel für * nimmt. Dies sind die "Spaltenindizes" a*z. Die Kopfspalte läßt man zunächst noch leer! Nun schreibt man unter jedes Element der Kopfzeile die zugehörige Spalte aus der Tafel für *. Damit ist die Tafel bis auf die Kopfspalte ausgefüllt.

a
a e d b c
a e d b c
e a c d b
c b e a d
d c b e a
b d a c e

In diese Kopfspalte schreibt man nun die Spalte von "a" aus der Tafel von *. Dies sind die "Zeilenindizes" x*a. Jetzt muß man prüfen, ob die Zeile hinter jedem Element der Kopfspalte die Zeile dieses Elementes aus der Tafel von * ist. Dies entspricht dem Vergleich mit der Tafel von v'(x,z)=(x*a)*z.

a
a e d b c
a
e
c
d
b
a e d b c
e a c d b
c b e a d
d c b e a
b d a c e

In dem Beispiel stimmt dies erstmals nicht in der Zeile von e=(a*a) und der Spalte von d=(a*b). Dort steht nämlich ein c und es müßte ein b stehen. Man sieht also, daß (a*a)*b = e*b = b nicht gleich a*(a*b) = a*d = c ist und die Verknüpfung * daher nicht assoziativ. Es handelt sich also um eine echte Loop, die keine Gruppe ist.


Natürlich leisten heutige Computerprogramme das Testen auf Assoziativität bedeutend schneller als dieser Test "per Hand".