Die graue Theorie zu Beginn

Diese Eckpunkte, die wir festhalten wollen, sind die sogenannten Gruppenaxiome. Sie beschreiben fünf wesentliche Eigenschaften eines Konzeptes von "Multiplikation" oder "Addition".

 

Eine Hierarchie mathematischer Strukturen

Wir gehen zunächst davon aus, dass wir eine Menge G (wie "Gruppe") gegeben haben, deren Elemente wir mit einer solchen verallgemeinerten Multiplikation irgendwie verbasteln wollen. Für so eine Menge definiert man nun folgende Axiome: Sei G eine Menge. \ll(E)\darkblue\ array(Existenz und Wohldefiniertheit einer Verknüpfung)__ \ll()Eine Verknüpfung__ ist eine Abbildung opimg(\circ): G\times\ G\to\ G. \(Zur genaueren Abgrenzung spricht man manchmal präziser auch von einer inneren, binären Verknüpfung.\) \ll()Sie ordnet also einem Paar von Elementen von G ein weiteres Element von G zu. Diese Verknüpfung soll unsere "Multiplikation" modellieren. Daher schreiben wir sie auch in einer Notation, die an die Multiplikation erinnert: Statt wie bei anderen Abbildungen üblich opimg(\circ)(a,b) zu schreiben, schreiben wir a\circ\ b für das Bild von (a,b) unter der Abbildung opimg(\circ). \ll(A)\darkblue\ array(Assoziativität)__ \ll()Die Verknüpfung opimg(\circ) heißt assoziativ__, falls \ll()\forall a,b,c\in\ G: a\circ(b\circ\ c)=(a\circ\ b)\circ\ c \ll()gilt. Dieses Axiom sagt uns also, dass unsere Verknüpfung mit der gewöhnlichen Multiplikation von Zahlen die Eigenschaft gemein hat, dass wir in komplizierteren Termen umklammern dürfen, wie wir wollen. Und weil wir das dürfen, ist uns die Klammerung so egal, dass wir sie bei assoziativen Verknüpfungen in den meisten Fällen gleich gänzlich weglassen. \ll(N)\darkblue\ array(Neutrales Element)__ \ll()Man sagt, e\in\ G sei ein array(neutrales Element)__ der Verknüpfung, falls \ll()\forall g\in\ G: e\circ\ g=g=g\circ\ e \ll()gilt. \ll()Auch dies wird von der Multiplikation reeller Zahlen erfüllt, denn für die reelle Zahl e=1 gilt diese Eigenschaft. Aufgrund dessen heißt ein neutrales Element oft auch "Einselement" oder kurz "Eins" der Verknüpfung. Dadurch erklären sich auch die üblichen Bezeichnungsweisen wie e oder 1 für solch ein Element. \ll()Wir werden vorerst bei der Bezeichnung e bleiben, aber gebräuchlicher ist 1. Für einen Einsteiger kann es ungewohnt sein, wenn verschiedene Dinge \(wie etwa die reelle Zahl 1 und neutrale Elemente von beliebigen anderen Verknüpfungen\) mit derselben Bezeichnung versehen werden wie hier. Daher ist es zum Eingewöhnen vielleicht nicht die schlechteste Lösung, zunächst bei e zu bleiben und nach der Eingewöhnungsphase zu 1 zu wechseln. \ll(I)\darkblue\ array(Inverse Elemente)__ \ll()Eine weitere Forderung, die man an die Verknüpfung stellen kann, ist die, dass jedes Element g\in\ G ein sogenanntes array(inverses Element)__ g'\in\ G besitzt. Darunter ist folgendes zu verstehen: \ll()\forall g\in\ G \exists g'\in\ G: g\circ\ g'=g'\circ\ g=e \ll()e meint dabei das neutrale Element, dessen Existenz im vorherigen Axiom gefordert wurde. Wir werden später einsehen, dass es nur ein einziges neutrales Element geben kann, daher benötigt man keinen klärenden Zusatz wie "inverse Elemente bzgl. e", um zwischen verschiedenen neutralen Elementen zu unterscheiden. \ll()Hier muss man zum ersten Mal Vorsicht walten lassen beim Vergleich mit der bekannten Multiplikation von reellen Zahlen, denn nicht alle reellen Zahlen erfüllen diese Forderung. Die \(einzige\) Ausnahme ist bekanntlich die Zahl g=0, denn, egal welches g'\in\IR wir betrachten, es ist stets 0*g'=0 != 1. \ll()Alle anderen reellen Zahlen erfüllen dies jedoch. \ll(K)\darkblue\ array(Kommutativität)__ \ll()Die Verknüpfung heißt kommutativ__ oder auch abelsch__, falls \ll()\forall g,h\in\ G: g\circ\ h=h\circ\ g \ll()gilt. \ll()Dies wird von der uns bekannten Multiplikation reeller Zahlen wieder uneingeschränkt erfüllt. Ein Paar (G, opimg(\circ)) wird eine \darkblue\ array(Gruppe)__\black genannt, falls es EANI erfüllt, d.h., wenn opimg(\circ) eine Verknüpfung ist (E), die assoziativ (A) ist, ein neutrales Element besitzt (N) und bzgl. derer jedes Element ein inverses Element hat (I). Falls (G, opimg(\circ)) zusätzlich auch K erfüllt, spricht man von einer \darkblue\ array(kommutativen Gruppe)__\black bzw. einer \darkblue\ array(abelschen Gruppe)__\black. Je nachdem, welche dieser Axiome erfüllt sind und welche nicht, vergibt man verschiedene weitere Namen für solche Strukturen: Erfüllt (G, opimg(\circ)) nur E, so nennt man dies \darkblue\ Gruppoid__\black oder \darkblue\ Magma__\black. Da "Gruppoid" eine zweite, wichtigere Bedeutung hat, ist der Begriff Magma im Zweifelsfall vorzuziehen. Jedoch ist eine Struktur, die keinerlei nützliche Eigenschaften hat, zu unspannend, um großartig darüber zu reden, daher tritt das sowieso selten in Erscheinung. Erfüllt (G, opimg(\circ)) EA, so spricht man von einer \darkblue\ Halbgruppe__\black. Erfüllt (G, opimg(\circ)) EAN, so spricht man von einem \darkblue\ Monoid__\black. Sowohl Halbgruppen als auch Monoide können natürlich zusätzlich auch K erfüllen. Man nennt das ggf. dann eine kommutative\/abelsche Halbgruppe bzw. einen kommutativen\/abelschen Monoid. Am Ende der Fahnenstange steht dann, wie schon gesagt, mit EANI bzw. EANIK die (kommutative) Gruppe. Noch ein Wort zur Notation: Mathematiker sind notorische Faulpelze und schreiben daher meist nichts mit auf, was sich vermeiden lässt. Wenn man sich an die Definitionen und Konzepte, die durch die Gruppenaxiome gegeben sind, erst einmal gewöhnt hat, geht man in der Regel schnell zu abkürzenden Notationen über. So ist es üblich, bis auf begründete Ausnahmen jede Gruppenverknüpfung entweder mit dem gewohnten Multiplikationspunkt \(d.h. in der Form a*b\) oder \- was besonders bei abelschen Gruppen üblich ist \- mit einem Plus \(d.h. in der Form a+b\) zu schreiben. Man sagt auch, dass die Gruppe "multiplikativ" bzw. "additiv geschrieben" sei. Bei multiplikativer Notation verzichtet man dann sogar darauf, überhaupt ein Verknüpfungssymbol zu benutzen und schreibt nur noch ab für die Verknüpfung von a mit b. Es ist aber wichtig, dass das ein rein kosmetischer Unterschied ist, denn wie immer sind Namen nur Schall und Rauch. Es kommt einzig und allein darauf an, was unsere Verknüpfung für Eigenschaften hat oder nicht hat, und nicht darauf, ob wir sie mit opimg(\circ), opimg(*), \+, \* oder irgendwie anders bezeichnen.

 

Die bunte Praxis

 

Beispiele für Gruppen

\darkred\ array(EANIK \- gewöhnliche Zahlen)__ Wir haben bereits während der Definition der Gruppenaxiome gesehen, dass die Menge der von Null verschiedenen reellen Zahlen alle fünf Axiome erfüllt, d.h., (\IR\\\{0}, opimg(*)) ist eine abelsche Gruppe. Das gilt, wie wir wissen, genauso für die Multiplikation komplexer und rationaler Zahlen, d.h., (\IC\\\{0}, opimg(*)) und (\IQ\\\{0}, opimg(*)) sind ebenfalls abelsche Gruppen. Man schreibt abkürzend auch \IQ^opimg(\times), \IR^opimg(\times) und \IC^opimg(\times) für diese Gruppen. \(Manchmal wird auch ein Stern statt eines Kreuzes benutzt.\) Es muss jedoch nicht immer die Multiplikation sein. Wir können uns ganz leicht klarmachen, dass auch die Addition Gruppen aus \IQ, \IR und \IC macht, denn ... \ll(E)\ ... die Addition ist eine Abbildung \IR\times\IR\to\IR, ... \ll(A)\ ... die assoziativ ist, denn dass für reelle Zahlen \ll()\forall a,b,c\in\IR: a+(b+c)=(a+b)+c \ll()gilt, ist uns schon aus der Schule und noch davor bestens bekannt, ... \ll(N) ... die mit der reellen Zahl 0 ein neutrales Element hat, da \ll()\forall a\in\IR: a+0=a=0+a \ll()gilt, ... \ll(I)\ ... die zu jeder reellen Zahl a mit der reellen Zahl -a ein Inverses bereithält, da \ll()\forall a\in\IR: a+(-a)=0=(-a)+a \ll()ist und ... \ll(K)\ ... die bekanntlich auch kommutativ ist, denn auch \ll()\forall a,b\in\IR: a+b=b+a \ll()kennen und benutzen wir alle bereits seit vielen Jahren. Im Wesentlichen dasselbe Argument funktioniert natürlich auch für (\IQ,+), für (\IC,+) und auch für (\IZ,+). Bei letzterem klappt das analoge Vorgehen mit der Multiplikation jedoch nicht \(siehe weiter unten\). \darkred\ array(EANI \- Affine Abbildungen)__ Ein sehr einfaches Beispiel einer Gruppe, die jedoch nicht kommutativ ist, sind sogenannte \darkblue\ array(affine Abbildungen)__\black \IR\to\IR, d.h. Abbildungen der Form x\mapsto\ ax+b, wobei a,b reelle Zahlen sind und a!=0 ist. Wir setzen also als zugrunde liegende Menge G:=Aff(\IR):=menge(f:\IR\to\IR | f ist affin). Als Verknüpfung benutzen wir die Hintereinanderausführung von Abbildungen, d.h., für zwei Abbildungen f,g:\IR\to\IR definieren wir f\circ\ g als die Abbildung f\circ g:=cases(\IR\to\IR;x\mapsto\ f(g(x))) Wir prüfen nach, dass es sich dabei um eine Gruppe handelt: \ll(E)Die Verknüpfung ist so definiert, dass aus zwei affinen Abbildungen f,g:\IR\to\IR \(etwa mit f(x)=ax+b und g(x)=cx+d\) wieder eine Abbildung f\circ\ g:\IR\to\IR wird. Ist f\circ\ g jedoch wieder eine affine Abbildung? Wir überprüfen das: Für alle x\in\IR gilt: | | (f\circ\ g)(x) = f(g(x)) , nach Definition | | =f(cx+d) , in g eingesetzt | | =a(cx+d)+b , in f eingesetzt | | =(ac)x+(ad+b) \ll()Da nun a und c nach Voraussetzung ungleich 0 sind, ist auch ac!=0, d.h., f\circ\ g hat ebenfalls die Gestalt, die affine Abbildungen definieren. \ll(A)Es gilt allgemein für alle Abbildungen f,g,h, die man überhaupt hintereinander ausführen kann, dass diese Hintereinanderausführung assoziativ ist: \ll()((f\circ g)\circ h)(x) = (f\circ g)(h(x)) = f(g(h(x))) = f((g\circ h)(x)) = (f\circ (g\circ h))(x) \ll()Dabei wurde in jedem Schritt nur die Definition der Hintereinanderausführung benutzt. \ll(N)Wenn man irgendeinen Ausdruck in die Abbildung \IR\to\IR, e(x):=x einsetzt, dann kommt derselbe Ausdruck wieder heraus, d.h., es gilt \ll()f(e(x))=f(x) => f\circ\ e=f \ll()und \ll()e(f(x))=f(x) => e\circ\ f=f. \ll()Also ist die Abbildung e, die auch \darkblue\ array(identische Abbildung)__\black oder kurz \darkblue\ array(Identität)__\black genannt und als \id_\IR geschrieben wird, ein neutrales Element für die Hintereinanderausführung von Abbildungen. \ll(I)Um zu bestimmen, ob alle affinen Abbildungen f: \IR\to\IR inverse affine Abbildungen haben, schreiben wir uns zunächst auf, was das heißt: Wenn g eine inverse Abbildung wäre, so müssten f\circ g=e und also auch \ll()\forall x\in\IR: x=e(x)=(f\circ\ g)(x)=f(g(x)) \ll()wahr sein. Wenn wir also g(x) mit y abkürzen, dann müssen wir x=f(y) nach y auflösen, um herauszufinden, wie g denn aussähe, falls es tatsächlich ein Inverses zu f gäbe. Das Auflösen ist einfach: \ll()x=ay+b <=> y=1/a\.(x-b) = 1/a\.x-b/a \ll()Wenn es überhaupt eine inverse Abbildung g von f gäbe, dann müsste sie \ll()g(x)=1/a\.x-b/a \ll()erfüllen. Das ist bis jetzt aber nur ein Verdacht, denn wir haben ja angenommen, dass g ein Inverses von f ist, um dieses Resultat zu erhalten. Um jetzt nachzuprüfen, dass f wirklich ein Inverses hat, gehen wir den Weg rückwärts: Wir definieren__ g:\IR\to\IR durch die obige Gleichung \(und erkennen jetzt, weshalb wir eingangs a!=0 gefordert haben, nämlich damit diese Definition einen Sinn ergibt\) und prüfen nach, ob die Eigenschaft, die inverse Element definiert, wahr ist: | | (f\circ g)(x) = f(g(x)) | | =f(1/a\.x-b/a) | | =a(1/a\.x-b/a)+b | | =(x-b)+b | | =x=e(x) => f\circ\ g=e | | (g\circ f)(x) = g(f(x)) | | =g(ax+b) | | =1/a\.(ax+b)-b/a | | =(x+b/a)-b/a | | =x=e(x) => g\circ\ f=e \ll()Also ist g tatsächlich das Inverse von f. Damit haben wir festgestellt, dass (Aff(\IR), opimg(\circ)) tatsächlich eine Gruppe definiert. Wir überzeugen uns jetzt noch davon, dass dies eine nichtabelsche Gruppe ist: Dazu müssen wir zwei affine Abbildungen f_1, f_2 finden, sodass f_1\circ\ f_2!=f_2\circ\ f_1 ist. Es ist beinahe egal, welche Abbildungen man da nun tatsächlich wählt, fast alle Paare werden funktionieren und wenn man zufällig eines auswählt, hat man gute Chancen, dass es klappt. Ich wähle zufällig f_1(x)=2x+1 und f_2(x)=3x-4 und rechne nach, dass dieses Paar tatsächlich zu der Ungleichheit führt: (f_1\circ\ f_2)(x) = f_1(3x-4) | | =2(3x-4)+1 | | =6x-7 (f_2\circ\ f_1)(x) = f_2(2x+1) | | =3(2x+1)-4 | | =6x-1 Setzt man nun x=0 in beide Gleichungen ein, sieht man, dass (f_1\circ\ f_2)(0)=-7!=-1=(f_1\circ\ f_2)(0) ist, d.h., f_1\circ\ f_2 und f_2\circ\ f_1 sind verschiedene Abbildungen. \(Man beachte, dass man tatsächlich eine Zahl einsetzen muss, denn nur weil zwei Abbildungsvorschriften verschieden sind, heißt das nicht, dass die Abbildungen auch verschieden sind, denn man kann ja ein und dieselbe Funktion durchaus auch mit verschiedenen Abbildungsvorschriften beschreiben.\) \darkred\ array(EANI \- Symmetrische Gruppen)__ Völlig analog lässt sich beweisen, dass Sym(M):=menge(f:M\to M | f ist bijektiv) für jede Menge M zusammen mit der Hintereinanderausführung von Abbildungen eine Gruppe ist. Die Argumente für E, A und N sind dieselben wie eben. Das neutrale Element ist wie eben die \darkblue\ array(Identität)__\black, d.h.: id_M:=cases(M\to M;m\mapsto\ m) Jede bijektive Abbildung f:M\to\ M hat eine Umkehrabbildung f^(-1): M\to\ M, die hier als Inverses dient. Ist speziell M=menge(1,2,...,n), so schreibt man auch S_n statt Sym(M).

 

Gegenbeispiele

\darkred\ array(EAN \- Monoide, die keine Gruppen sind)__ Wir haben festgestellt, dass Multiplikation und Addition bei uns bekannten Zahlen sich oft wie \(kommutative\) Gruppen verhalten. Das gilt jedoch nicht uneingeschränkt. Die Tatsache, dass man nicht durch 0 teilen darf, ist uns schon aufgefallen. Es geht jedoch auch schlimmer: So ist (\IZ\\\{0\}, opimg(*)) im Gegensatz zu (\IQ\\\{0\}, opimg(*)) ein \(kommutativer\) Monoid aber keine Gruppe. Das liegt daran, dass ganze Zahlen ungleich -1, 0, +1 keine Inversen in \IZ haben \(Dass sie Inverse in \IQ haben, widerspricht dem nicht! Das Axiom der inversen Elemente fordert ja ganz explizit, dass für alle g\in\ G ein array(g'\in\ G)__ mit der entsprechenden Eigenschaft existiert, d.h., man darf die vorgegebene Menge nicht verlassen\). Das sieht man wie folgt: Wäre ab=1 und a,b\in\IZ, so ist abs(a)>=1 und abs(b)>=1, da es sich ja um ganze Zahlen ungleich 0 handelt. Wäre nun abs(a)>1, so würde das abs(ab)=1 widersprechen \(analog mit b\). Also kann nur abs(a)=abs(b)=1, d.h. a=b=+-1 sein. Ganze Zahlen wie +- 2, +- 3, ... haben also keine ganzzahligen Inversen. Mit einem ähnlichen Argument kann man sich auch überzeugen, dass (\IN,+) ein kommutativer Monoid ist, aber keine Gruppe, da außer dem neutralen Element 0 keine natürliche Zahl ein Inverses in \IN hat. \(Bei mir und den meisten anderen Algebraikern ist 0 eine natürliche Zahl. \IN erst bei 1 beginnen zu lassen, macht die Algebra nur unnötig kompliziert!\) Wenn wir in obigem Beispiel Aff(\IR) die Forderung a!=0 fallen lassen, dann stimmen die Beweise für E, A und N natürlich ganz genauso, denn dort wurde a!=0 ja kein einziges Mal benutzt. Auch K ist immer noch falsch, denn das Beispiel funktioniert ganz genauso. Damit haben wir auch ein Beispiel für einen Monoid gefunden, der weder kommutativ noch eine Gruppe ist. Allgemeiner ist für jede Menge X die Menge Abb(X) aller Abbildungen X\to\ X ein Monoid. Dieser Monoid ist genau dann eine Gruppe und kommutativ, wenn abs(X)\in\ menge(0,1) ist. \darkred\ array(EA \- Halbgruppen)__ Indem man statt (\IN,+) einfach (\IN_(>0),+) betrachtet, also das neutrale Element 0 entfernt, kann man sich eine Halbgruppe schaffen, die kein Monoid mehr ist, denn wenn a und b beide positive natürliche Zahlen sind, dann ist a+b>a \and a+b>b, d.h., die für ein neutrales Element notwendige Bedingung \forall a\in\IN_(>0): a+e=a kann für kein Element von \IN_(>0) erfüllt werden. Vorsicht: Allein dadurch, dass man ein neutrales Element aus einer Halbgruppe entfernt, kommt man noch nicht automatisch zu einem Gegenbeispiel. Es gibt Beispiele, wo der "Rest" wieder ein Monoid ist, d.h. ein neues Element plötzlich neutral wird. \darkred\ array(E \- Verknüpfungen ohne Alles)__ Das Kreuzprodukt von Vektoren aus dem \IR^3 ist ein Beispiel für eine Verknüpfung, die weder assoziativ oder kommutativ ist noch ein neutrales Element hat. \(Von inversen Elementen zu sprechen ist natürlich gar nicht sinnvoll, weil man ein neutrales Element braucht, um dieses Axiom überhaupt zu formulieren.\) Das sieht man schon an den allereinfachsten Vektoren: Für e_x:=(1,0,0), e_y:=(0,1,0), e_z:=(0,0,1) gilt: e_x \cross e_y = e_z e_y \cross e_x =-e_z e_x\cross(e_x\cross e_y) = e_x\cross e_z = -e_y (e_x\cross e_x)\cross e_y = 0 \cross e_y = 0 \forall v\in\IR^3: v\cross v =0 Die ersten beiden Gleichungen zeigen, dass opimg(\cross) nicht kommutativ ist, die dritte und vierte zeigen, dass es nicht assoziativ ist, und die letzte zeigt, dass kein Vektor neutral sein kann, denn wäre e\in\IR^3 neutral, so müsste ja insbesondere e\cross\ e=e sein, d.h. e=0. e=0 erfüllt aber beispielsweise die notwendige Gleichung e_x\cross\ 0=e_x nicht. Natürlich sind solche Verknüpfungen nicht unwichtig, nur weil sie sich nicht den fünf Gruppenaxiomen unterordnen. Sie kommen halt nur in anderen Fragestellungen vor und haben dort ihre Daseinsberechtigung. Nur untersucht man diese nicht \(immer\) mit den Mitteln der Gruppentheorie.

 

Kleingeld- und Uhrenarithmetik

Die Frage, welche Gruppe jetzt den Rechenbeispielen der Einleitung einen sinnvollen Rahmen verleiht, steht natürlich weiterhin im Raum. Darauf wollen wir nun eine Antwort finden. Beide Beispiele basieren auf demselben Prinzip, das man so zusammenfassen kann: Wenn zwei natürliche Zahlen, z.B. zwei Stundenzahlen oder zwei Centbeträge, gegeben sind, so ist die Verknüpfung von beidem dadurch gegeben, dass man die Zahlen erst wie gewohnt addiert. Falls das Ergebnis größer oder gleich einer vorgegebene Grenze (z.B. 24 Stunden oder 500 Cent) ist, so wird diese Grenzzahl wieder subtrahiert. Diese Zahl ist größer oder gleich 0 und kleiner als die vorgegebene Grenze und wird als das Ergebnis der Rechnung benutzt. Dieses Prinzip läuft unter dem Stichwort "modulo rechnen" natürlich mit beliebigen Grenzen ab. Eine mögliche Definition der \darkblue\ array(Addition modulo n)__\black \(wobei n eine positive, natürliche Zahl sei\) ist die folgende: \(Wir werden in einem weiteren Kapitel jedoch sehen, dass dies aus theoretischer Sicht nicht die sinnvollste ist. Sie ist jedoch zum konkreten Rechnen oder zum Programmieren sehr gut einsetzbar.\) \darkred\ Definition: Ist x\in\IN, so definiere: x MOD n:=x-n\.floor(x/n) Dabei meint floor(opimg(*)) die Abrunden-Funktion, d.h., floor(r) ist die größte ganze Zahl, die kleiner oder gleich r ist. Um x MOD n zu bestimmen, kann man also folgende Anleitung benutzen: Bestimme das größte Vielfache von n, das noch kleiner oder gleich x ist, und subtrahiere es von x. Für Zahlen a,b,c\in\ menge(0,1,...,n-1) definiere die Addition modulo n durch: a opimg(\oplus)_n b := (a+b) MOD n Wieder umgangssprachlich formuliert: Addiere erst wie gewohnt und reduziere dann modulo n. Ich behaupte nun, dass die Menge G_n:=menge(0,1,...,n-1) zusammen mit der Verknüpfung opimg(\oplus)_n eine Gruppe ist. Das nur zu behaupten reicht selbstverständlich nicht, es muss bewiesen werden: \ll(E)Ist noch relativ einfach: Wenn a\in\ G_n und b\in\ G_n sind, dann ist a opimg(\oplus)_n b nach Definition schon einmal eine ganze Zahl. Wegen n\.floor(x/n)<=n\.x/n=x ist x MOD n stets größer oder gleich 0. Da n\.floor(x/n) das größte__ Vielfache von n ist, das kleiner oder gleich x ist, muss außerdem x-n\.floor(x/n) < n sein, d.h. kleiner oder gleich n-1. Damit ist gezeigt, dass für alle a,b\in\ G_n auch a opimg(\oplus)_n b\in\ G_n ist, dass opimg(\oplus)_n also eine wohldefinierte Verknüpfung ist. \ll(K)Die Assoziativität verschieben wir auf das Ende und schauen uns zunächst die Kommutativität an: Da a opimg(\oplus)_n b mittels der gewöhnlichen Summe a+b definiert wurde, sollte die Verknüpfung kommutativ werden. Wir prüfen das nach: \ll()a opimg(\oplus)_n b=(a+b)-n\.floor((a+b)/n)=(b+a)-n\.floor((b+a)/n)=b opimg(\oplus)_n a \ll()Also ist opimg(\oplus)_n kommutativ wie vermutet. \ll(N)Sehen wir uns nun das neutrale Element an. Wenn man einmal raten müsste, wie das neutrale Element einer Verknüpfung aussieht, die als "Addition" bezeichnet und durch "Addiere erst und tue dann etwas mit dem Ergebnis." definiert wurde, dann kommt man relativ schnell darauf, dass der einzig naheliegende Kandidat für das neutrale Element 0 ist. Prüfen wir nach, ob das stimmt: \ll(N)\forall a\in\ G_n: 0 opimg(\oplus)_n a = (0+a)-n\.floor((0+a)/n) = a-n\.floor(a/n) \ll()Da nun nach Voraussetzung a\in\ G_n ist, ist 0<=a0 ist n-a das Inverse. \ll()Das prüfen wir nach: Wenn 0n-a>0, d.h. n-a\in G_n. Damit haben wir also schon einmal keinerlei Probleme. Auch die Rechnung macht uns keine Schwierigkeiten: \ll()a opimg(\oplus)_n (n-a)=a+n-a-n\.floor((a+n-a)/n)=n-n\.floor(n/n)=n-n*1=0 \ll()Aufgrund der Kommutativität ist auch (n-a) opimg(\oplus)_n a=0. \ll(A)Der letzte Punkt auf unserer Agenda ist nun die Assoziativität. Dafür müssen wir eine winzige Vorüberlegung über die Abrundungsfunktion floor(opimg(*)) machen: Egal, welche reelle Zahl x man dort einsetzt, da floor(opimg(*)) immer auf die nächstkleinere ganze Zahl abrundet, ändert sich nicht viel, wenn wir um eine ganze Zahl verschieben, d.h.: \ll()\forall x\in\IR \forall k\in\IZ: floor(k+x)=k+floor(x) \ll()Das benutzen wir jetzt, um die Assoziativität nachzurechnen: Für alle a,b,c\in G_n gilt: | | (a opimg(\oplus)_n b) opimg(\oplus)_n c = (a+b MOD n) opimg(\oplus)_n c | | = (a+b-n\.floor((a+b)/n)) opimg(\oplus)_n c | | = a+b-n\.floor((a+b)/n)+c-n\.floor((a+b-n\.floor((a+b)/n)+c)/n) | | = a+b+c-n\.floor((a+b)/n)-n\.floor((a+b+c)/n-floor((a+b)/n)) | | = a+b+c-n\.floor((a+b)/n)-n\.floor((a+b+c)/n)+n\.floor((a+b)/n) | | = a+b+c-n\.floor((a+b+c)/n) \ll()Wertet man a opimg(\oplus)_n (b opimg(\oplus)_n c) genauso aus, so erhält man dasselbe Ergebnis. Das zeigt, dass a opimg(\oplus)_n (b opimg(\oplus)_n c)=(a opimg(\oplus)_n b) opimg(\oplus)_n c ist, d.h., opimg(\oplus)_n ist assoziativ. Damit ist also bewiesen, dass (G_n, opimg(\oplus)_n) eine abelsche Gruppe ist. Ich möchte anmerken, dass die Notation, die ich für diese Gruppe und ihre Verknüpfung verwendet habe, weit weg davon ist, irgendwie verbreitet, manchmal üblich oder außerhalb dieses Beispiels nur ein einziges Mal verwendet worden zu sein. Wir werden in einem späteren Kapitel noch eine alternative Konstruktion kennenlernen, die uns im Wesentlichen dieselbe Gruppe liefert und mit \IZ\/n\IZ bezeichnet wird. Dies ist die Standardbezeichnung. Um diese beiden Konstruktionen aber nicht zu vermischen, solange wir noch nicht wissen, dass sie im Wesentlichen identisch sind, habe ich mich hier entschieden, eine andere Bezeichnung zu wählen.

 

Wieder Theorie: Ein paar Beweise als Grundlage

Es lohnt sich, einen genaueren Blick auf die Axiome zu werfen. Wenn man ein paar Übungsaufgaben macht und öfter einmal nachweist, dass dieses oder jenes eine Gruppe ist, dann fällt einem vielleicht auf, dass viel Arbeit dabei ist, die zwar in den Axiomen gefordert wird, aber in den Beispielen für Gruppen eigentlich nicht notwendig erscheint.

 

Einseitig- und Eindeutigkeit

Nun ist es so, dass man sehr oft doppelten Aufwand hat, um zu zeigen, dass das \(vermutete\) neutrale Element e wirklich e*x=x und__ x*e=x für alle x\in\ G erfüllt. Es scheint, als würde dort immer nur ein und dieselbe Rechnung auf zwei verschiedene Weisen aufgeschrieben. Derselbe Verdacht drängt sich einem beim Nachprüfen der Definition eines inversen Elements auf. Es stellt sich also die Frage, ob es wirklich sein muss, dass man immer beide Varianten der jeweiligen Gleichung überprüfen muss. Gibt es vielleicht eine Gruppe, wo die eine Variante stets funktioniert, die andere jedoch nicht? Außerdem fällt auf, dass in den Axiomen nur gefordert wurde, dass es ein__ \(was ja auf Mathematisch stets "mindestens ein" meint\) neutrales Element gibt und pro Gruppenelement ein Inverses. Hier stellt sich die Frage, ob es vielleicht der Fall sein könnte, dass es (genau ein)__ neutrales Element und für Gruppenelemente genau ein Inverses gibt. Beide Fragen wollen wir in diesem Abschnitt beantworten und dabei gleich den Umgang mit den Gruppenaxiomen in Beweisen einüben. \darkred\ Definition Seien X eine Menge und opimg(*): X\times\ X\to\ X eine Verknüpfung auf dieser. Wir definieren dann: Ein Element e\in\ X heißt \darkblue\ linksneutral__\black, falls \forall x\in X: e*x=x gilt, und \darkblue\ rechtsneutral__\black, falls gilt: \forall x\in X: x* e=x Sei e\in X ein rechts\- oder linksneutrales Element. Ein y\in\ X heißt \darkblue\ array(linksinvers zu x)__\black, falls y*x=e gilt, und entsprechend \darkblue\ array(rechtsinvers zu x)__\black, falls x*y=e gilt. Korrekterweise müsste man eigentlich sagen, dass es sich um ein Links\- bzw. Rechtsinverses array(bzgl. e)__ handelt, solange wir noch nicht bewiesen haben, dass neutrale Elemente eindeutig bestimmt sind. Ein neutrales Element \(ohne Seitenangabe\) ist nach dieser Definition ein Element, das links\- und__ rechtsneutral ist, ein inverses Element von x ist eines, das links\- und__ rechtsinvers zu x ist. Man spricht deshalb zur Klarstellung auch manchmal von "beidseitig" neutralen bzw. inversen Elementen. \darkred\ Lemma: Eindeutigkeit von neutralen Elementen Sei X eine Menge und opimg(*): X\times\ X\to\ X eine Verknüpfung auf X. Ist e_R ein rechts\- und e_L ein linksneutrales Element, so gilt bereits e_R=e_L. \blue\ Beweis: Wir werten dazu e_L*e_R auf zwei verschiedene Weisen aus: Es gilt e_L*e_R = e_R, denn e_L ist linksneutral. Es gilt jedoch auch e_L*e_R = e_L, denn e_R ist rechtsneutral. \blue\ q.e.d. Wie folgt aus diesem Lemma nun die Eindeutigkeit von neutralen Elementen? Ein neutrales Element ist stets von beiden Seiten neutral. Wenn also e und e' neutral sind, ist e rechts\- und e' linksneutral \(und auch umgekehrt natürlich\) und laut Lemma deshalb e=e'. Wichtig ist aber, dass es überhaupt ein rechts\- und__ ein linksneutrales Element gibt. Man betrachte dafür folgendes Beispiel: \darkred\ Beispiel: Betrachte eine beliebige Menge X mit mehr als einem Element und definiere darauf eine Verknüpfung durch \forall a,b\in X: a\*b:=b. Diese Verknüpfung ist stets assoziativ, denn es gilt: \forall a,b,c\in X: (a\*b)\*c = c = a\*c = a\*(b\*c) Die Definition ist so gewählt, dass tatsächlich jedes__ Element von X linksneutral ist. Es kann also durchaus viele verschiedene linksneutrale Elemente geben. Das Lemma sagt uns nur, dass dieser obskure Fall höchstens dann eintreten kann, wenn gleichzeitig kein__ Element rechtsneutral ist. Indem man umgekehrt a\*b:=a definiert, erhält man ein Beispiel einer Struktur, die zwar assoziativ ist, aber viele rechtsneutrale und kein linksneutrales Element besitzt. \darkred\ Lemma: Eindeutigkeit von Inversen Sei (X, opimg(*)) ein Monoid und x\in\ X ein beliebiges Element. Ist a_R ein rechts\- und a_L ein linksinverses Element zu x, dann gilt a_R=a_L. \blue\ Beweis: Der Trick ist erneut, ein Produkt auf zwei verschiedene Weisen auszuwerten. Diesmal ist das das Produkt a_L*x*a_R. Bezeichne das neutrale Element \(jetzt wirklich "das" neutrale Element, weil wir jetzt wissen, dass es eindeutig bestimmt ist\) mit e. Zum einen gilt a_L*(x*a_R) = a_L*e = a_L, weil a_R rechtsinvers zu x und e rechtsneutral ist. Zum anderen gilt jedoch auch (a_L* x)*a_R = e*a_R = a_R, weil a_L linksinvers zu x und e linksneutral ist. Weil (X, opimg(*)) das Assoziativgesetz erfüllt, ist aber a_L*(x*a_R) = (a_L*x)*a_R, d.h. a_R=a_L. \blue\ q.e.d. Weil das inverse Element zu einem festen x also eindeutig bestimmt ist, kann man sich dafür eine Bezeichnung einfallen lassen, die nur von x abhängt. Üblich ist dafür x^(-1) bei multiplikativ geschriebenen und -x bei additiv geschriebenen Verknüpfungen. Man beachte aber, dass wir in diesem Beweis \(im Gegensatz zu vorher\) ausdrücklich die Assoziativität und die Eigenschaften des neutralen Elements benutzt haben. Wenn man auf Assoziativität verzichtet und\/oder nur ein einseitig neutrales Element fordert, dann gilt die Eindeutigkeit inverser Elemente i.A. nicht mehr. \(Gleich wird es ein Beispiel dafür geben.\) Was ist nun mit der Frage, ob man den Beweisaufwand reduzieren kann? Folgender Satz zeigt uns, dass man das sehr wohl kann, solange man vorsichtig ist: \darkred\ Lemma: Abgeschwächte Gruppenaxiome Sei G eine Menge. Folgende drei Aussagen sind äquivalent: \ll(i)(G, opimg(*)) ist eine Gruppe, d.h. erfüllt EANI. \ll(ii)(G, opimg(*)) erfüllt | | (E) $ opimg(*) ist eine Abbildung G\times\ G\to G. | | (A) $ opimg(*) ist assoziativ. | | (NL) $Es existiert ein linksneutrales Element e_L\in\ G. | | (IL) $Jedes g\in\ G hat ein linksinverses Element g'\in\ G. \ll(iii)(G, opimg(*)) erfüllt | | (E) $ opimg(*) ist eine Abbildung G\times\ G\to G. | | (A) $ opimg(*) ist assoziativ. | | (NR) $Es existiert ein rechtsneutrales Element e_R\in\ G. | | (IR) $Jedes g\in\ G hat ein rechtsinverses Element g'\in\ G. \blue\ Beweis: Wir zeigen nur, dass die ersten beiden Aussagen äquivalent sind, dass die erste und die dritte äquivalent sind, beweist man völlig analog. Natürlich ist in jeder Gruppe NL und IL erfüllt, das sagen uns schon die Definitionen. Wir müssen also nur die Umkehrung zeigen. Zunächst überzeugen wir uns jetzt davon, dass jedes zu x\in\ G linksinverse Element x' auch rechtsinvers ist. Wähle dafür ein linksinverses Element x'' von x' \(\!\). Dann gilt für alle x\in\ G: x*x' = e_L*(x*x') da e_L linksneutral ist | | = (x''*x')*(x*x') da x'' linksinvers zu x' | | = x''*((x'*x)*x') mehrmals Assoziativgesetz | | = x''*(e_L*x') da x' linksinvers zu x | | = x''*x' da e_L linksneutral | | = e_L da x'' linksinvers zu x' Also folgt aus E, A, NL und IL die volle Stärke von I. Das nutzen wir jetzt wiederum, um auch N in voller Form zu zeigen: Für alle x\in\ G gibt es ein \(jetzt beidseitiges!\) Inverses x' und es gilt somit: x*e_L = x*(x'*x) da x' linksinvers zu x | | = (x*x')*x Assoziativgesetz | | = e_L*x da x' auch rechtsinvers zu x | | = x da e_L linksneutral \blue\ q.e.d. Unsere Antwortet lautet also: Ja, man kann die Beweisarbeit um die Hälfte reduzieren beim Existenznachweis von neutralen und inversen Elementen, solange man sich auf eine Seite \(Rechts oder Links\) festlegt. An folgendem Beispiel sehen wir, dass eine Struktur mit E, A, NL und IR \(und wieder völlig analog auch E, A, NR und IL\) keine__ Gruppe zu sein braucht. Die Seiten mischen darf man also nicht. \darkred\ Beispiel: Wir betrachten wie vorhin eine beliebige Menge X mit mindestens zwei Elementen und der Verknüpfung \forall a,b\in X: a\*b:=b darauf. Wählen wir nun ein festes e\in\ X, so ist dieses linksneutral, wie vorhin festgestellt. Die Definition der Verknüpfung sagt uns, dass a\*e=e ist, d.h., dass jedes Element von X ein Rechtsinverses bzgl. e hat.

 

Einfache Rechenregeln

Mit den Axiomen und der Eindeutigkeit von neutralen und inversen Elementen kann man nun sehr einfache Rechenregeln beweisen, die völlig einleuchtend sind und daher immer ohne Kommentar verwendet werden: \darkred\ Lemma: Sei G eine Gruppe. Wir bezeichnen wie üblich das neutrale Element mit 1 und das Inverse von x\in\ G mit x^(-1). Mit diesen Bezeichnungen gilt: \ll(i)1^(-1) = 1 \ll(ii)\forall x\in\ G: (x^(-1))^(-1) = x \ll(iii)\forall x,y\in\ G: (xy)^(-1) = y^(-1) x^(-1) Man beachte, dass im dritten Punkt die Reihenfolge der Faktoren vertauscht wird beim Invertieren. Das ist wichtig und sollte stets beachtet werden. Da die gewöhnlichen Rechenoperationen für reelle Zahlen kommutativ sind, kann man die Gleichung für reelle Zahlen ohne schlechtes Gewissen auch als (xy)^(-1) = x^(-1) y^(-1) schreiben. Da wir jedoch wissen, dass Gruppen auch nichtkommutativ sein können, muss in allen allgemeinen Beweisen stets die Reihenfolge der Faktoren beachtet werden. \blue\ Beweis: Da 1 neutral ist, gilt 1*1=1. Dies ist nun aber auch die Gleichung, die das Inverse von 1 charakterisiert und wir wissen, dass es nur ein einziges Element von G gibt, das diese Gleichung erfüllt \(nämlich eben das Inverse von 1\). Also muss 1^(-1) = 1 sein. Das Inverse von x erfüllt nach Definition die beiden Gleichungen xx^(-1) = 1 = x^(-1)\.x. Dies sind nun jedoch auch genau die beiden Gleichungen, die das Inverse von x^(-1) zu erfüllen hat. Wieder aufgrund der Eindeutigkeit inverser Elemente muss also (x^(-1))^(-1) = x sein. Auch hier wenden wir erneut die Eindeutigkeit des Inversen an. (xy)^(-1) ist dasjenige Element von G, welches 1 ergibt, wenn man es mit xy multipliziert. Wir prüfen also, ob y^(-1)\.x^(-1) diese Eigenschaft hat: (xy)(y^(-1)\.x^(-1)) = x(yy^(-1))x^(-1) = x1x^(-1) = xx^(-1) = 1 Also stimmt es: (xy)^(-1) = y^(-1) x^(-1). \blue\ q.e.d. Man beachte, dass man, wollte man denselben Beweis für x^(-1)\.y^(-1) führen, in dieser Rechnung die Reihenfolge von Faktoren vertauschen müsste. In einer nichtkommutativen Gruppe ist das i.A. nicht möglich, also würde ein solcher Beweis nicht funktionieren. In der Tat ist es so, dass kommutative Gruppen die einzigen sind, die diese andere Inversengleichung erfüllen: \darkred\ Satz: Sei G eine Gruppe. Es gilt: G ist kommutativ <=> \forall x,y\in\ G: (xy)^(-1) = x^(-1)\.y^(-1). Dies zu beweisen ist auch immer eine beliebte Übungsaufgabe zur Gruppentheorie. Fast jeder Student, der Gruppentheorie hatte, musste diese Aufgabe oder eine ähnliche mindestens einmal lösen. \blue\ Beweis: \blue\ => Ist G kommutativ, so wissen wir bereits, dass (xy)^(-1) = y^(-1)\.x^(-1) = x^(-1)\.y^(-1) gilt. \blue\ <== Ist umgekehrt diese Eigenschaft gegeben, so benutzen wir obiges Lemma und schreiben xy = (x^(-1))^(-1)\.(y^(-1))^(-1). Wenden wir jetzt die gegebene Eigenschaft für Inverse an, so erhalten wir (x^(-1))^(-1)\.(y^(-1))^(-1) = (x^(-1)\.y^(-1))^(-1), was sich mit dem Lemma erneut umformen lässt zu (x^(-1)\.y^(-1))^(-1) = (y^(-1))^(-1)\.(x^(-1))^(-1) = yx. Also gilt wie behauptet xy=yx für alle x,y\in\ G. \blue\ q.e.d.

 

Potenzen

Eine weitere Gelegenheit, den Umgang mit den Gruppenaxiomen zu üben, ist die Beschäftigung mit Potenzen. Wir können in einer Gruppe ja nicht nur zwei Elemente multiplizieren, sondern beliebig viele Elemente: g_1*g_2*g_3*g_4 ist ohne Probleme möglich. \(Da wir das Assoziativgesetz haben, ist es uns sogar egal, wie wir dies klammern.\) Um speziell für Produkte der Form g*g*g*..., die recht häufig vorkommen, abkürzende Schreibenweisen benutzen zu können, führen wir Potenzen ein nach dem Muster der schon bekannten Potenzen gewöhnlicher Zahlen: \darkred\ array(Definition: Potenzen mit ganzzahligem Exponenten)__ Sei (X, opimg(*)) eine Gruppe und x\in\ X beliebig. Wir definieren x^0:=1, x^(n+1):=x^n* x für alle n\in\IN. Für negative Exponenten definieren wir: x^(-n-1):=x^(-n)*x^(-1) für alle n\in\IN. Die Definition folgt dem gewohnten Muster der Potenzgesetze, die wir kennen. Das folgende Lemma zeigt, dass auch die meisten anderen uns bekannten Potenzgesetze erfüllt sind: \darkred\ array(Lemma: Potenzgesetze)__ Sei (X, opimg(*)) eine Gruppe und x\in\ X beliebig. Es gilt: \ll(i)\forall n,m\in\IZ: x^(n+m)=x^n* x^m \ll(ii)\forall n,m\in\IZ: x^(nm)=(x^n)^m Insbesondere schließt die zweite Aussage x^(-n) = (x^n)^(-1) = (x^(-1))^n mit ein. Der Beweis kann sehr einfach sein, wenn man sich "Pünktchen-Beweise" erlaubt. Ein formeller Beweis wartet jedoch mit winzigen Fallen auf, in die man leicht tappen kann: \blue\ Beweis: Der Beweis wird, wie gesagt, durch Induktion geführt. Wir entscheiden uns für Induktion nach m. Der Induktionsanfang ist sehr einfach, denn \forall n\in\IZ: x^(n+0)=x^n=x^n*1=x^n*x^0 ist nach Definition wahr. Für den Induktionsschritt zeigen wir zunächst, dass die Behauptung für alle n\in\IZ und m=1 wahr ist. Die Gleichung x^(n+1) = x^n*x ist zwar für n>=0, aber nicht für n<0 durch die Definition gesichert. Es gilt dann jedoch für n>=0 x^(-n) = x^(-n+1-1) array(\small\ Def.;\normal\=;\small $)\normal x^(-n+1)*x^(-1) => x^(-n+1) = x^(-n)*x. Jetzt überzeugen wir uns genauso, dass die Behauptung für m=-1 wahr ist. Für n<=0 ist das wieder per Definition gegeben und für n>0 gilt: x^n = x^(n-1+1) array(\small\ Def.;\normal\=;\small $)\normal x^(n-1)*x => x^(n-1) = x^n * x^(-1). \lr(*)\forall n\in\IZ: x^(n+1) = x^n* x $ $ \forall n\in\IZ: x^(n-1) = x^n* x^(-1). Nehmen wir nun an, dass \forall n\in\IZ: x^(n+m) = x^n*x^m wahr ist. Dann folgt für alle n\in\IZ: x^(n+(m+-1)) = x^((n+m)+- 1) | | = x^(n+m)*x^(+-1) nach \ref(*) | | = (x^n*x^m)*x^(+-1) nach I.V. | | = x^n*(x^m*x^(+-1)) Assoziativität) | | = x^n*x^(m+-1) nochmal \ref(*) Also ist die Aussage auch für m+-1 wahr. Per Induktion folgt, dass sie für alle m\in\IZ wahr ist. Auch für die zweite Aussage überzeugen wir uns zuerst von der Gültigkeit des Induktionsanfangs m=0: \forall n\in\IZ: (x^n)^0 = 1 = x^0 = x^(n*0) Gut, bis dahin keine Probleme. Genau wie vorher prüfen wir die Fälle m=1 und m=-1. Für m=1 ist das sofort klar, denn nach Definition ist \forall n\in\IZ: (x^n)^1 = x^n = x^(n*1). Für m=-1 wenden wir die Definition des Inversen und die schon bewiesene Gleichung an: x^(-n)* x^n = x^(-n+n) = x^0 = 1 => x^(-n) = (x^n)^(-1) Zusammenfassend gilt also schon einmal: \lr(*)\forall n\in\IZ: (x^n)^(+-1) = x^(+-n) Und das nutzen wir jetzt für den Induktionsschluss. Falls \forall n\in\IZ: (x^n)^m = x^(nm) bereits gilt, folgt für alle n\in\IZ: x^(n(m+-1)) = x^(nm+-n) | | = x^(nm)*x^(+-n) siehe oben | | = (x^n)^m*x^(+-n) I.V. | | = (x^n)^m*(x^n)^(+-1) nach \ref(*) | | =(x^n)^(m+-1) siehe oben Also folgt per Induktion die Gültigkeit der zu zeigenden Gleichung \forall m\in\IZ. \blue\ q.e.d. Der Beweis ist natürlich nicht auf Gruppen beschränkt. Die Definitionen und Potenzgesetze gelten auch unter geringeren Voraussetzungen, wenn man die Exponenten entsprechend einschränkt. So ist etwa die Definition x^0:=1, x^(n+1):=x^n*x in allen Monoiden sinnvoll. Selbst auf die neutralen Elemente kann man verzichten, wenn man x^1:=x, x^(n+1):=x^n*x definiert. Auch dann gelten die beiden Potenzgesetze x^(n+m)=x^n* x^m, $ (x^n)^m = x^(nm) immer noch für alle Exponenten, für die die Ausdrücke sinnvoll sind, d.h. für n,m\in\IN bei Monoiden und n,m\in\IN_(>0) bei Halbgruppen. Die Beweise sind jeweils exakt dieselben wie oben skizziert, nur dass man eben auf die Verwendung von Inversen verzichtet und ggf. den Induktionsanfang auf m=1 statt m=0 festlegt.

 

Abschluss

Das soll es bis hierher zur Definition und zum Umgang mit Gruppen gewesen sein. Es ist nur ein winziger Einblick in die Gruppentheorie gewesen, aber ich hoffe, trotzdem den einen oder anderen für mehr interessiert zu haben, denn mehr wird es geben. (mfg)^(-1)*Gockel