Mathematische Grundlagen

Gruppe

Definition: Sei M eine nichtleere Menge. Eine Verknüpfung auf M ist eine Abbildung

• : M kreuz M M,

die je zwei Elementen a, b Element M ein Element c Element M zuordnet. Die Schreibweise ist

a • b = c.

Wenn die Menge M endlich ist, lassen sich die Ergebniswerte der Verknüpfung in Form einer Verknüpfungstafel angeben.

Definition: Eine Verknüpfungstafel ist eine Tabelle, die für alle Elemente a, b Element M das Ergebnis der Verknüpfung a • b in Zeile a und Spalte b enthält.

Beispiel: Sei M die Menge boolesche Menge = {0, 1}. Auf sei eine Verknüpfung Exklusiv-Oder in folgender Weise definiert:

	0	1
0	0	1
1	1	0

Das Ergebnis von 1 Exklusiv-Oder 0 beispielsweise ergibt sich als Eintrag in Zeile 1 und Spalte 0, nämlich als 10 = 1.

Beispiel: Die Menge M sei die Menge natürliche Zahlen der natürlichen Zahlen. Dann sind + (Addition), · (Multiplikation) und "hoch" (Potenzierung) Verknüpfungen.

Welche Zahl das Ergebnis der Verknüpfung etwa von 5 + 3 oder von 7·4 oder von 2³ ist, müssen wir im allgemeinen ausrechnen (um 3 weiterzählen von 5 aus, die 7 viermal addieren, bzw. die 2 dreimal mit sich selbst multiplizieren). Schneller geht es, wenn wir die Verknüpfungstafeln der einstelligen Zahlen auswendig lernen (z.B. kleines Einmaleins). Für die Verknüpfung von größeren Zahlen gibt es die Rechenverfahren der Arithmetik (Kopfrechnen, schriftliches Addieren und Multiplizieren).

Eigenschaften von Verknüpfungen

Es kommt bei einer Verknüpfung im allgemeinen auf die Reihenfolge der Elemente an. Verknüpfungen, bei denen es nicht auf die Reihenfolge ankommt, heißen kommutativ.

Definition: Sei M eine Menge mit einer Verknüpfung • . Die Verknüpfung • heißt kommutativ, wenn für alle Elemente a, b Element M gilt

a • b = b • a.

Beispiel: Die oben angegebenen Verknüpfungen Exklusiv-Oder , + und · sind kommutativ. Die Verknüpfung "hoch" ist jedoch nicht kommutativ, denn es ist z.B. 2³ = 8, aber 3² = 9.

Wenn wir nicht nur zwei, sondern drei Elemente a, b, c miteinander verknüpfen wollen, gehen wir wie folgt vor: wir verknüpfen die ersten beiden Elemente, und das Ergebnis verknüpfen wir mit dem dritten Element (Auswertung von links nach rechts):

(a • b) • c.

Wir hätten jedoch auch erst das zweite und dritte Element verknüpfen und dann das erste Element mit diesem Ergebnis verknüpfen können (Auswertung von rechts nach links):

a • (b • c).

Welche Art der Auswertung ist die richtige? Nun, es stellt sich heraus, dass es bei vielen Verknüpfungen egal ist: in beiden Fällen kommt dasselbe Ergebnis heraus. Derartige Verknüpfungen heißen assoziativ.

In den anderen Fällen muss man sich auf eine Auswertungsart einigen, z.B. Auswertung von links nach rechts, oder durch Klammern die Reihenfolge der Auswertung vorschreiben.

Definition: Sei M eine Menge mit einer Verknüpfung • . Die Verknüpfung • heißt assoziativ, wenn für alle Elemente a, b, c Element M gilt

(a • b) • c = a • (b • c).

Beispiel: Die oben angegebenen Verknüpfungen Exklusiv-Oder , + und · sind assoziativ. Die Verknüpfung "hoch" ist jedoch nicht assoziativ, denn es ist z.B. (2²)^³ = 4³ = 64, aber 2^(2³) = 2⁸ = 256.

Aufgabe 1: Sei M die Menge ganze Zahlen der ganzen Zahlen. Welche Eigenschaften hat die Verknüpfung "–" (Subtraktion)?

assoziativ		ja		nein
kommutativ		ja		nein

Im Folgenden bezeichnen wir eine Menge M, auf der eine Verknüpfung • definiert ist mit (M, • ). Wir betrachten nun Eigenschaften solcher Mengen. Je nach dem, welche von insgesamt vier Eigenschaften erfüllt sind, bilden diese Mengen unterschiedliche mathematische Strukturen. Die einfachste dieser Strukturen ist die Halbgruppe. Bei einer Halbgruppe wird lediglich verlangt, dass die Verknüpfung assoziativ ist.

Definition: Eine Menge mit einer assoziativen Verknüpfung ist eine Halbgruppe.

Beispiel: Sei A ein Alphabet und A⁺ die Menge der nichtleeren Wörter über dem Alphabet. Auf A⁺ sei die Verkettung von Wörtern als Verknüpfung • definiert. Zwei Wörter werden verkettet, indem sie einfach hintereinander geschrieben werden, z.B.

ab • aacc = abaacc.

Die Verknüpfung ist offensichtlich assoziativ. Die Menge A⁺ mit der Konkatenation als Verknüpfung bildet daher eine Halbgruppe.

Die Menge der natürlichen Zahlen mit der Addition ( natürliche Zahlen , +) ist eine Halbgruppe. Ebenso ist (, ·) eine Halbgruppe.

Definition: Eine Halbgruppe (M, • ) ist ein Monoid, wenn sie ein neutrales Element enthält. Ein Element e Element M heißt neutrales Element, wenn für alle a Element M gilt

e • a = a • e = a.

Das neutrale Element wird auch als Nullelement oder als Einselement bezeichnet, je nach dem, ob die Verknüpfung als Addition oder als Multiplikation verstanden wird.

Beispiel: Die Menge A* der Wörter über einem Alphabet A (einschließlich des leeren Wortes ε) mit der Verkettung als Verknüpfung ist ein Monoid. Das leere Wort ε ist das neutrale Element, denn es gilt

ε • w = w • ε = w für alle Wörter w Element A*.

Sei X eine Menge und (X) die Potenzmenge von X, d.h. die Menge aller Teilmengen von X. Dann ist (X) mit der Vereinigung von Mengen vereinigt als Verknüpfung und der leeren Menge leere Menge als neutralem Element ein Monoid.

Die Menge der natürlichen Zahlen mit der Multiplikation ( natürliche Zahlen , ·) ist ein Monoid mit der 1 als neutralem Element. Die Menge der natürlichen Zahlen einschließlich der Null mit der Addition (₀, +) ist ein Monoid. Die Null ist das neutrale Element bezüglich der Addition. Ferner ist ( boolesche Menge , Exklusiv-Oder ) ein Monoid mit der 0 als neutralem Element.

Satz: Sei (M, • ) ein Monoid. Dann ist das neutrale Element eindeutig bestimmt, d.h. es gibt nicht mehrere neutrale Elemente in (M, • ).

Beweis: Seien e und f neutrale Elemente. Dann gilt

f = e • f = e,

denn f = e • f, weil e neutral ist, und e • f = e, weil f neutral ist.

Im Folgenden schreiben wir ein Monoid M mit Verknüpfung • und neutralem Element e als Tripel (M, • , e). So sind beispielsweise ( Potenzmenge (X), vereinigt , leere Menge ), ( natürliche Zahlen , ·, 1), (₀, +, 0) sowie ( boolesche Menge , Exklusiv-Oder , 0) Monoide.

Definition: Ein Monoid (M, • , e) ist eine Gruppe, wenn es zu jedem Element a Element M ein inverses Element in M gibt. Ein Element a' Element M heißt invers zu a Element M, wenn

a • a' = e

ist, d.h. wenn die Verknüpfung von a und a' das neutrale Element e ergibt.

Beispiel: Die Menge der ganzen Zahlen mit der Addition ( ganze Zahlen , +, 0) ist eine Gruppe. Zu jeder Zahl a ist -a das inverse Element.

Die Menge ( boolesche Menge , Exklusiv-Oder , 0) ist eine Gruppe. Die 0 und die 1 sind jeweils zu sich selbst invers.

Satz: Sei (M, • , e) eine Gruppe. Für jedes a Element M gilt: wenn a' zu a invers ist, dann auch a zu a'.

Beweis: Sei zunächst a'' das zu a' inverse Element, d.h. a' • a'' = e. Dann ist

a

a • e

a • a' • a''

e • a''

a''

d.h. a = a'' ist zu a' invers.

Definition: Eine Gruppe (M, • , e) heißt abelsche Gruppe (nach N.H. Abel), wenn die Verknüpfung • kommutativ ist, d.h. wenn für alle Elemente a, b Element M gilt

a • b = b • a.

Beispiel: ( ganze Zahlen , +, 0) ist abelsche Gruppe.

Die Menge aller Permutationen von n Elementen mit der Komposition (Hintereinanderausführung von Abbildungen) als Verknüpfung ist eine Gruppe, jedoch keine abelsche Gruppe.

Eine Gruppe ist zunächst eine Menge M, auf der eine Verknüpfung • definiert ist. Eine Verknüpfung ist eine Abbildung von M kreuz M in M. Es müssen darüber hinaus drei Eigenschaften erfüllt sein, diese heißen die Gruppenaxiome:

die Verknüpfung ist assoziativ,
es gibt ein neutrales Element,
jedes Element hat ein inverses Element.

Bei einer abelschen Gruppe gilt zusätzlich:

die Verknüpfung ist kommutativ.

Gruppen können aus endlich vielen oder unendlich vielen Elementen bestehen. Die folgenden Definitionen und Sätze gelten teils nur für endliche Gruppen, teils für alle Gruppen.

Definition: Sei (G, • , e) eine Gruppe. Eine Teilmenge H enthalten G heißt Untergruppe von G, wenn (H, • , e) eine Gruppe ist.

Beispiel: Die Menge der geraden Zahlen ist eine Untergruppe von ( ganze Zahlen , +, 0).

Satz: (Untergruppenkriterium für endliche Gruppen)

Sei (G, • , e) eine endliche Gruppe. Dann bildet jede nichtleere Teilmenge H enthalten G, die unter der Verknüpfung • abgeschlossen ist, eine Untergruppe von G. D.h. es gilt

H ist Untergruppe von G genau dann wenn H enthalten G und H ungleich leere Menge und für alle a, b Element H : a • b Element H.

Definition: Sei (G, • , e) eine Gruppe. Die k-te Potenz eines Elementes a Element G ist induktiv wie folgt definiert:

a^k =

`e`	für `k` = 0
`a` • `a`^k-1	für alle `k`

Es ist also a^k = a • ... • a (k-mal).

Mithilfe des vorigen Satzes lässt sich eine Untergruppe einer endlichen Gruppe G erzeugen, indem alle Potenzen eines einzelnen Elementes a Element G gebildet werden. D.h. a wird mit sich selbst verknüpft, das Ergebnis wiederum mit a usw., solange, bis nichts Neues mehr hinzukommt.

Definition: Sei (G, • , e) eine endliche Gruppe und a Element G. Die von a erzeugte Untergruppe ist

spitze Klammer auf a spitze Klammer zu = { a^k | k Element natürliche Zahlen }.

Das Element a ist das erzeugende Element von spitze Klammer auf a spitze Klammer zu .

Beispiel: Die Untergruppen von ( ganze Zahlen ₆, +, 0) sind

= {0}

= {1, 2, 3, 4, 5, 0}

= {2, 4, 0}

= {3, 0}

Ein wichtiges Beweishilfsmittel ist der folgende Satz von Lagrange:

Satz: Sei (G, • , e) eine endliche Gruppe und (H, • , e) eine Untergruppe von G. Dann gilt

|H| ist Teiler von |G|.

Aus dem Satz folgt, dass eine echte Untergruppe einer endlichen Gruppe G höchstens halb so viele Elemente haben kann wie G.

Definition: Sei (G, • , e) eine Gruppe. Die Ordnung ord(a) eines Elementes a Element G ist die kleinste Zahl k Element natürliche Zahlen , für die gilt

a^k = e.

Satz: Sei (G, • , e) eine endliche Gruppe und a Element G. Dann gilt

ord(a) = | spitze Klammer auf a spitze Klammer zu |.

Beweis: Sei k = ord(a), d.h. die kleinste natürliche Zahl, für die gilt a^k = e. Dann sind die von a erzeugten Elemente a¹, a², ..., a^k alle verschieden. Denn wäre aⁱ = a^j mit 1 kleiner gleich i < jk, so wäre a^j-i = e, wobei j-i < k, im Widerspruch dazu, dass k die kleinste Zahl ist mit a^k = e.

Ebenso ist klar, dass ab a^k+1 = a^k • a = e • a = a keine neuen Elemente mehr hinzukommen. Somit hat spitze Klammer auf a spitze Klammer zu genau k Elemente.