View
14
Download
0
Category
Preview:
Citation preview
Formale Grundlagen der Informatik 1/43
Formale Grundlagen der InformatikHerbstsemester 2018
Matthias Hamann
Lehrstuhl fur Theoretische InformatikUniversitat Mannheim
Algebraische Strukturen(Stand: 15.11.2018)
Formale Grundlagen der Informatik 2/43
Algebraische Strukturen
Operationen auf Mengen, Halbgruppen
Definition 10.1
Eine Abbildung ◦ : M ×M −→ M heißt Operation auf M.Schreibweise: x ◦ y fur ◦(x , y).
Die Operation ◦ heißt kommutativ, falls x ◦ y = y ◦ x fur allex , y ∈ M.
Die Operation ◦ heißt assoziativ, falls (x ◦ y) ◦ z = x ◦ (y ◦ z)(Schreibweise: = x ◦ y ◦ z) fur alle x , y , z ∈ M.
Ist ◦ : M ×M −→ M assoziativ, so heißt (M, ◦) Halbgruppe.
Beispiel fur eine nicht kommutative, nicht assoziative Operation auf N:
a ◦ b := ab.
Formale Grundlagen der Informatik 3/43
Algebraische Strukturen
Neutrale Elemente, Monoide
Definition 10.2
Sei (M, ◦) Halbgruppe. Ein Element e ∈ M heißt neutrales Element inM, falls
e ◦m = m ◦ e = m
fur alle m ∈ M.
Halbgruppen, die ein neutrales Element besitzen, heißen Monoide.
Lemma 10.3
Seien e, e′ neutrale Elemente im Monoid (M, ◦). Dann gilt e = e′.
Beweis: Nach Definition gilt e = e ◦ e′ = e′. �
Beispiel: Die ganzen Zahlen mit der Multiplikation bilden einen Monoid.Die geraden ganzen Zahlen mit der Multiplikation bilden eineHalbgruppe, die kein Monoid ist.
Formale Grundlagen der Informatik 4/43
Algebraische Strukturen
Inverse Elemente, Gruppen
Definition 10.4
Es sei (M, ◦) ein Monoid mit neutralem Element e und es sei m ∈ M. EinElement m′ ∈ M heißt inverses Element (oder Inverses) zu m, falls
m ◦m′ = m′ ◦m = e.
(M, ◦) heißt Gruppe, falls alle Elemente in M ein Inverses haben.
Lemma 10.5
Sind m1,m2 ∈ M Inverse zu m ∈ M, dann gilt m1 = m2.
Beweis: Es gilt m1 = m1 ◦ (m ◦m2) = (m1 ◦m) ◦m2 = m2. �
Formale Grundlagen der Informatik 5/43
Algebraische Strukturen
Die Gruppe M∗
Definition 10.6
Fur jeden Monoid (M, ◦) bezeichne M∗ ⊆ M die Menge aller Elemente inM, die ein Inverses haben.
Lemma 10.7
Fur jeden Monoid (M, ◦) gilt, dass (M∗, ◦) eine Gruppe ist.
Ubliche Schreibweise: (M, ◦)∗ fur (M∗, ◦).
Beweis: Zunachst gilt, dass das neutrale Element e von M in M∗ liegt,da e−1 = e.
Außerdem folgt aus m,m′ ∈ M∗, dass auch m ◦m′ ∈ M∗, da(m ◦m′)−1 = (m′)−1 ◦m−1 ∈ M, d. h., M∗ abgeschlossen gegenuber ◦.Zudem gilt, dass fur alle m ∈ M∗ auch m−1 in M∗ liegt, da(m−1)−1 = m. �
Formale Grundlagen der Informatik 6/43
Algebraische Strukturen
Beispiele Monoide, Gruppen
(N,+): Neutrales Element 0 und (N,+)∗ = ({0},+),d. h., Monoid, aber keine Gruppe.
(N, ·): Neutrales Element 1 und (N, ·)∗ = ({1}, ·),d. h., Monoid, aber keine Gruppe.
(Z,+): Neutrales Element 0 und (Z,+)∗ = (Z,+),d. h., Gruppe (und damit auch Monoid).
(Z, ·): Neutrales Element 1 und (Z, ·)∗ = ({1,−1}, ·),d. h., Monoid, aber keine Gruppe.
(Q, ·): Neutrales Element 1 und (Q, ·)∗ = (Q \ {0}, ·),d. h., Monoid, aber keine Gruppe.
(P(M),∩): Neutrales Element M, (P(M),∩)∗ = ({M},∩),d. h., Monoid, aber keine Gruppe.
(P(M),∪): Neutrales Element ∅, (P(M),∪)∗ = ({∅},∪),d. h., Monoid, aber keine Gruppe.
Formale Grundlagen der Informatik 7/43
Algebraische Strukturen
Gruppentafeln: Allgemeiner Aufbau
Gruppentafel von (M, ◦) mit M := {a, b, c , d}
(M, ◦) a b c d
a a ◦ a a ◦ b a ◦ c a ◦ db b ◦ a b ◦ b b ◦ c b ◦ dc c ◦ a c ◦ b c ◦ c c ◦ dd d ◦ a d ◦ b d ◦ c d ◦ d
Formale Grundlagen der Informatik 8/43
Algebraische Strukturen
Gruppentafeln: Beispiel (Z, ·)∗
Gruppentafel von (Z, ·)∗
(Z, ·)∗ −1 1
−1 1 −11 −1 1
Beachte: Die Gruppentafel von (Z, ·)∗ ist symmetrisch bezuglich derHauptdiagonale, da die Gruppe abelsch (d. h. die Verknupfung derGruppe kommutativ) ist.
Formale Grundlagen der Informatik 9/43
Algebraische Strukturen
Die Permutationsgruppe S(M)
Definition 10.8
Es sei M eine nichtleere Menge. Dann bezeichnet S(M) die Menge derPermutationen uber M, d. h. der bijektiven Abbildungen von M nach M.Fur n ∈ N+ und M = {1, . . . , n} wird S(M) auch mit Sn bezeichnet.
Erinnerung: |Sn| = n!.
Lemma 10.9
Sei M eine nichtleere Menge und bezeichne ◦ die Operation Kompositionauf S(M). Dann ist (S(M), ◦) eine (i.A. nicht kommutative) Gruppe mitneutralem Element idM : M −→ M.
Beweis: Die Hintereinanderausfuhrung ◦ von Abbildungen ist offenbarassoziativ. Man sieht auch leicht, dass die Identitat idM hier dieEigenschaft des neutralen Elements erfullt, und dass fur alle f : M −→ Mbijektiv die Umkehrabbildung f −1 das Inverse von f ist. �
Formale Grundlagen der Informatik 10/43
Algebraische Strukturen
Schreibweisen von Monoiden und Gruppen
Fur Monoide unterscheidet man die multiplikative Schreibweise(z. B. (M, ◦)) und die additive Schreibweise (z. B. (M,+)).
Bei der multiplikativen Schreibweise wird das neutrale Element auchals ’Eins’ bezeichnet und Inverse werden als m−1 geschrieben.
Bei der additiven Schreibweise wird das neutrale Element auch als’Null’ bezeichnet und Inverse werden als −m geschrieben.
Bei der multiplikativen Schreibweise wird m ◦m ◦ · · · ◦m mit kFaktoren auch als mk geschrieben.
Bei der additiven Schreibweise wird m + m + · · ·+ m mit kSummanden auch als k ·m geschrieben.
Formale Grundlagen der Informatik 11/43
Algebraische Strukturen
Vertraglichkeit von Operationen mit Aquivalenzrelationen
Definition 10.10
Es sei (M, ◦) eine Halbgruppe und R eine Aquivalenzrelation auf M. DieOperation ◦ heißt vertraglich mit R, falls fur alle x , y , x ′, y ′ ∈ M gilt:Aus x ∼R x ′ und y ∼R y ′ folgt x ◦ y ∼R x ′ ◦ y ′.
Lemma 10.11
Es sei (M, ◦) eine Halbgruppe und R eine Aquivalenzrelation, so dass ◦vertraglich mit R ist. Dann definiert ◦ folgende Halbgruppenstruktur(M/R, ◦) auf der Menge der Aquivalenzklassen M/R: Fur alle x , y ∈ Msei [x ]R ◦ [y ]R := [x ◦ y ]R .
Ist (M, ◦) ein Monoid mit neutralem Element e, so ist auch (M/R, ◦) einMonoid mit neutralem Element [e]R . Ist x ∈ (M, ◦)∗ und x−1 das Inversezu x , dann gilt [x ]R ∈ (M/R, ◦)∗ und [x−1]R ist das Inverse von [x ]R .
Formale Grundlagen der Informatik 12/43
Algebraische Strukturen
Zum Beweis von Lemma 10.11, Beispiel
Es ist zu zeigen, dass die Definition [x ]R ◦ [y ]R := [x ◦ y ]R der Operation◦ auf M/R uberhaupt sinnvoll ist, d. h., dass fur alle x ′ ∈ [x ]R undy ′ ∈ [y ]R gilt, dass x ′ ◦ y ′ ∈ [x ◦ y ]R . Dies folgt jedoch direkt aus derDefinition 10.10 der Vertraglichkeit von ◦ mit R.
Die Operation ◦ auf M/R ist assoziativ, da
([x ]R ◦ [y ]R) ◦ [z ]R = [x ◦ y ]R ◦ [z ]R = [(x ◦ y) ◦ z ]R
= [x ◦ (y ◦ z)]R = [x ]R ◦ [y ◦ z ]R = [x ]R ◦ ([y ]R ◦ [z ]R)
Die Aussagen bezuglich des neutralen Elements und moglicher Inversefolgen direkt aus den Definitionen. �
Wichtiges Beispiel:
Lemma 10.12
Die Operationen + und · auf Z sind fur alle m ≥ 2 vertraglich mit derMODm-Relation.
Formale Grundlagen der Informatik 13/43
Algebraische Strukturen
Beweis von Lemma 10.12
Wir bezeichnen Z/RMODm durch Zm = {[0], . . . , [m − 1]}.Wir fixieren beliebige ganze Zahlen x , y , x ′, y ′ ∈ Z mit x ≡ x ′ mod mund y ≡ y ′ mod m, d. h., es existieren ganze Zahlen a, b ∈ Z mitx ′ = x + a ·m und y ′ = y + b ·m.
Wir mussen zeigen, dass x + y ≡ x ′ + y ′ mod m und x · y ≡ x ′ · y ′mod m.
Das folgt aus
x ′ + y ′ = (x + a ·m) + (y + b ·m) = x + y + (a + b) ·m
und
x ′ · y ′ = (x + a ·m) · (y + b ·m)
= x · y + x · b ·m + a ·m · y + a ·m · b ·m.= x · y + (x · b + y · a + a · b ·m) ·m. �
Formale Grundlagen der Informatik 14/43
Algebraische Strukturen
Monoidstruktur auf Zm
Als Folgerung aus Lemma 10.11 und Lemma 10.12 erhalten wir dieMonoide (Zm,+) und (Zm, ·) mit
[i ] + [j ] = [i + j ] und [i ] · [j ] = [i · j ]
fur alle [i ], [j ] ∈ Zm.
Da (Z,+) eine Gruppe ist, ist auch (Zm,+) eine Gruppe mit
−[i ] = [m − i ]
fur alle [i ] ∈ Zm.
Die Monoide (Zm, ·) sind im Allgemeinen keine Gruppen.
Im Folgenden analysieren wir die Struktur von Gruppen vom Typ (Zm, ·)∗.
Formale Grundlagen der Informatik 15/43
Algebraische Strukturen
Gruppentafel von (Z6,+)
Gruppentafel von (Z6,+)
(Z6,+) [0] [1] [2] [3] [4] [5]
[0] [0] [1] [2] [3] [4] [5][1] [1] [2] [3] [4] [5] [0][2] [2] [3] [4] [5] [0] [1][3] [3] [4] [5] [0] [1] [2][4] [4] [5] [0] [1] [2] [3][5] [5] [0] [1] [2] [3] [4]
Beachte: Die Gruppentafel von (Z6,+) ist symmetrisch bezuglich der
Hauptdiagonale, da die Gruppe abelsch (d. h. die Verknupfung der Gruppe
kommutativ) ist.
Formale Grundlagen der Informatik 16/43
Algebraische Strukturen
Die Gruppe (Zm, ·)∗
Theorem 10.13
Fur alle m ∈ N+, m ≥ 2, gilt (Zm, ·)∗ = {[b] | ggT (m, b) = 1}.
Beweis: Fur alle [b], [y ] ∈ Zm gilt genau dann [y ] · [b] = [1], wenn
y · b − 1 = x ·m.
fur ein x ∈ Z, d. h.,
[b] ∈ (Zm, ·)∗ ⇐⇒ ∃x , y ∈ Z : x ·m + y · b = 1.
Das Theorem ergibt sich aus dem folgenden Lemma 10.14 und dem Fakt,dass 1 ein Teiler von m und b ist.
Formale Grundlagen der Informatik 17/43
Algebraische Strukturen
Lemma 10.14
Lemma 10.14
Der großte gemeinsame Teiler ggT (m, b) ist der einzige Teiler d von mund b, fur den ganze Zahlen x , y existieren, so dass x ·m + y · b = d .
Beweis: Es sei d ein Teiler von m und b, fur den ganze Zahlen x , yexistieren, so dass x ·m + y · b = d .
Es gilt d ≤ ggT (m, b).
Andererseits teilt ggT (m, b) die Zahl x ·m + y · b = d , da ggT (m, b) einTeiler von m und b ist, also ggT (m, b) ≤ d .
Das ergibt d = ggT (m, b). �
Beispiele:
(Z2, ·)∗ = {[1]},
(Z12, ·)∗ = {[1], [5], [7], [11]},
(Zp, ·)∗ = {[1], [2], [3], · · · , [p − 2], [p − 1]}, fur p Primzahl.
Formale Grundlagen der Informatik 18/43
Algebraische Strukturen
Gruppentafel von (Z14, ·)∗
Gruppentafel von (Z14, ·)∗
(Z14, ·)∗ [1] [3] [5] [9] [11] [13]
[1] [1] [3] [5] [9] [11] [13][3] [3] [9] [1] [13] [5] [11][5] [5] [1] [11] [3] [13] [9][9] [9] [13] [3] [11] [1] [5]
[11] [11] [5] [13] [1] [9] [3][13] [13] [11] [9] [5] [3] [1]
Beachte: Die Gruppentafel von (Z14, ·)∗ ist symmetrisch bezuglich derHauptdiagonale, da die Gruppe abelsch (d. h. die Verknupfung der Gruppekommutativ) ist.
Formale Grundlagen der Informatik 19/43
Algebraische Strukturen
Euklidischer Algorithmus zur ggT-Berechnung
Eingabe: m > b > 0
Ausgabe: ggT (m, b)
1 a0 ← m
2 a1 ← b
3 i ← 1
4 repeat
5 ai+1 ← ai−1 mod ai
6 i ← i + 1
7 until ai = 0
8 output ai−1
Formale Grundlagen der Informatik 20/43
Algebraische Strukturen
Euklidischer Algorithmus(Bsp.: Berechnung des ggT von 123 und 45)
Eingabe: m > b > 0
1 a0 ← m
2 a1 ← b
3 i ← 1
4 repeat
5 ai+1 ← ai−1 mod ai
6 i ← i + 1
7 until ai = 0
8 output ai−1
i 0 1 2 3 4 5 6
ai 123 45 33 12 9 3 0
Formale Grundlagen der Informatik 21/43
Algebraische Strukturen
Euklidischer Algorithmus, Korrektheit I
Beobachtung: Eingabe a0 > a1 liefert Folge
a0 > a1 > · · · > as−1 > as = 0,
wobei fur alle i , 1 ≤ i ≤ s − 1, ai+1 = ai−1 mod ai , d. h.,
ai+1 = ai−1 − di · ai mit di =
⌊ai−1ai
⌋. (1)
Behauptung: as−1 = ggT (a0, a1).
Lemma 10.15
as−1 teilt ai fur alle i ≤ s − 1.
Beweis: as−1 teilt as−1 und (wegen as = 0) auch as−2.Wegen Relation (1) teilt as−1 auch as−3 und as−4 usw., also auch a1 unda0. �
Formale Grundlagen der Informatik 22/43
Algebraische Strukturen
Euklidischer Algorithmus, Korrektheit II
Lemma 10.16
Fur alle i ≥ 0 existieren ganze Zahlen xi , yi ∈ Z mit ai = xi · a0 + yi · a1.
Beweis: Offensichtlich gilt x0 = 1, y0 = 0 und x1 = 0, y1 = 1.
Fur i ≥ 1 setzen wir di = b ai−1
aic.
Nach Definition gilt fur i ≥ 1, dass
ai+1 = ai−1 − di · ai .
Also folgt fur alle i ≥ 1, dass
xi+1 = xi−1 − di · xi und yi+1 = yi−1 − di · yi . �
Lemmata 10.15 und 10.16 (zusammen mit Lemma 10.14) beweisen dieBehauptung, dass as−1 = ggT (a0, a1).
Formale Grundlagen der Informatik 23/43
Algebraische Strukturen
Erweiterter Euklidischer Algorithmus
Eingabe: m > b > 0,
Ausgabe: ggT (m, b) und y mit y · b ≡ ggT (m, b) mod m.
1 y0 ← 0
2 y1 ← 1
3 a0 ← m
4 a1 ← b
5 i ← 1
6 repeat
7 ai+1 ← ai−1 mod ai
8 di ← bai−1/aic9 yi+1 ← yi−1 − di · yi
10 i ← i + 1
11 until ai = 0
12 output ai−1, yi−1
Formale Grundlagen der Informatik 24/43
Algebraische Strukturen
Beispiel Erweiterter Euklidischer Algorithmus
Eingabe: m = 147, b = 32
i 0 1 2 3 4 5 6
ai 147 32 19 13 6 1 0
di 4 1 1 2
yi 0 1 −4 5 −9 23
Ausgabe: ggT (m, b) = 1, y = 23
(Probe: −5 · 147 + 23 · 32 = −735 + 736 = 1; hier ware x = −5.)
Formale Grundlagen der Informatik 25/43
Algebraische Strukturen
Untergruppen
Definition 10.17
Sei G = (G , ◦) Gruppe mit neutralem Element e. Eine Teilmenge H ⊆ Gheißt Untergruppe von G , falls e ∈ H und (H, ◦) eine Gruppe mitneutralem Element e ist.
Lemma 10.18
Sei G = (G , ◦) Gruppe mit neutralem Element e. Eine Teilmenge H ⊆ Gist genau dann Untergruppe von G , wenn fur alle x , y ∈ H gilt, dassx ◦ y−1 ∈ H. (Beweis auf Ubungsblatt) �
Triviale Untergruppe {e} ⊆ G .
(Z,+) ⊆ (Q,+) ⊆ (R,+).
{1,−1} ⊆ (Q \ {0}, ·) ⊆ (R \ {0}, ·).
Sei a ∈ R \ {0}. {ai | i ∈ Z} ⊆ (R \ {0}, ·).
Formale Grundlagen der Informatik 26/43
Algebraische Strukturen
Ordnung von Elementen in Gruppen, I
Lemma 10.19
Sei G Gruppe und H,H ′ Untergruppen von G . Dann ist auch H ∩ H ′
Untergruppe von G . (Beweis auf Ubungsblatt) �
Das rechtfertigt (hinsichtlich Eindeutigkeit):
Definition 10.20
Sei G = (G , ◦) Gruppe mit neutralem Element e. Fur alle g ∈ Gbezeichne 〈g〉 die von g erzeugte Untergruppe, d. h. die kleinsteUntergruppe in G , die g enthalt.
Definition 10.21
Die Ordnung ordG (g) eines Elementes g ∈ G bezeichnet die kleinstenaturliche Zahl k > 0, so dass gk = e.
Falls gk 6= e fur alle k ∈ N+, so sei ordG (g) =∞.
Formale Grundlagen der Informatik 27/43
Algebraische Strukturen
Ordnung von Elementen in Gruppen, II
Lemma 10.22
Fur alle Gruppen G und g ∈ G gilt
〈g〉 ={gk | k ∈ N
}∪{(
g−1)k | k ∈ N
}, (2)
falls ordG (g) unendlich, und
〈g〉 ={e, g , g2, . . . , gordG (g)−1
}, (3)
falls ordG (g) endlich, d. h., |〈g〉| = ordG (g).
Beweis: Relation (2) ergibt sich direkt daraus, dass 〈g〉 (da Untergruppe)alle Potenzen gk von g und deren Inverse (g−1)k fur alle naturlichenZahlen k enthalten muss. Man beachte, dass e = g0 und (g−1)k = g−k .
Formale Grundlagen der Informatik 28/43
Algebraische Strukturen
Ordnung von Elementen in Gruppen, III
Fortsetzung Beweis: Sei nun n = ordG (g) endlich.
Ist n = 1, so gilt g = e und 〈g〉 = {e}.Ist n > 1, so haben alle k ∈ Z eine eindeutig bestimmte Darstellung
k = d · n + k ′
mit 0 ≤ k ′ ≤ n − 1, namlich d = bk/nc und k ′ = k mod n.
Also giltgk = gd·n+k′ = (gn)d ◦ gk′ = ed ◦ gk′ = gk′ .
Das heißt gk = gk mod n fur alle k ∈ Z und damit
〈g〉 = {e, g , g2, . . . , gn−1}.
Man beachte, dass fur alle s ∈ {0, . . . , n − 1} gilt:
(g s)−1 = gn−s . �
Formale Grundlagen der Informatik 29/43
Algebraische Strukturen
Zyklische Gruppen
Definition 10.23
Eine Gruppe G heißt zyklisch, falls ein Element g ∈ G existiert, so dassG = 〈g〉. In diesem Fall heißt g Erzeugendes von G .
Beispiele:
Die Gruppe (Z,+) = {k · 1 | k ∈ Z} ist zyklisch mit Erzeugendem 1(additive Schreibweise beachten!).
Die Gruppe (Zm,+) = {[0], [1], . . . , [m− 1]} ist fur alle naturlichen Zahlenm ≥ 2 zyklisch mit Erzeugendem [1] (additive Schreibweise beachten!).
Die Gruppen (Q, ·)∗ = (Q \ {0}, ·) und (R, ·)∗ = (R \ {0}, ·) sind nichtzyklisch.
Die Gruppe (Z5, ·)∗ = {[1], [2], [3], [4]} ist zyklisch mit den Erzeugenden[2] und [3] (→ Ubung).
Die Gruppe (Z12, ·)∗ = {[1], [5], [7], [11]} ist nicht zyklisch (→ Ubung).
Formale Grundlagen der Informatik 30/43
Algebraische Strukturen
Satz von Lagrange, Linksnebenklassen
Theorem 10.24 (Satz von Lagrange)
Sei (G , ◦) eine endliche Gruppe und H ⊆ G eine Untergruppe von G .Dann gilt: |H| teilt |G |.
Definition 10.25
Fur alle g , g ′ ∈ G gelte g ∼H g ′ g.d.w. ∃h ∈ H : g ◦ h = g ′.Fur jedes g ∈ G heißt die Menge
gH = {g ◦ h | h ∈ H}
die Linksnebenklasse von g bezuglich H.
Der Beweis von Theorem 10.24 folgt daraus, dass ∼H eineAquivalenzrelation auf G ist, deren Aquivalenzklassen dieLinksnebenklassen bezuglich H sind, und dass alle Linksnebenklassen dieKardinalitat |H| haben. �
Formale Grundlagen der Informatik 31/43
Algebraische Strukturen
Folgerungen I
Lemma 10.26
Sei (G , ◦) eine endliche Gruppe mit neutralem Element e. Dann gilt furalle g ∈ G , dass
ordG (g) teilt |G |
undg |G | = e.
Beweis: Die Aussage ordG (g) teilt |G | folgt direkt aus Theorem 10.24,da |〈g〉| = ordG (g). Damit existiert eine naturliche Zahl s mit|G | = ordG (g) · s, also
g |G | = gordG (g)·s =(gordG (g)
)s= es = e. �
Formale Grundlagen der Informatik 32/43
Algebraische Strukturen
Folgerungen II
Lemma 10.27 (Kleiner Satz von Fermat)
Sei p Primzahl. Dann gilt fur alle ganzen, zu p teilerfremden Zahlen a:
ap−1 ≡ 1 mod p.
Beweis: Aus ggT (p, a) = 1 folgt [a] ∈ (Zp, ·)∗. Da |Z∗p| = p − 1, gilt
[a]p−1 = [1] in (Zp, ·)∗, also ap−1 ≡ 1 mod p. �
Lemma 10.28
Es sei n ∈ N, n ≥ 2. (Zn,+) = {[0], [1], . . . , [n − 1]} bezeichne diezyklische Gruppe der Ordnung n (in additiver Schreibweise). Dann gilt furalle j , 0 ≤ j ≤ n − 1, dass
ordG ([j ]) =n
ggT (n, j).
Beweis: siehe Ubungsblatt.
Formale Grundlagen der Informatik 33/43
Algebraische Strukturen
Die Permutationsgruppe Sn
Erinnerung (vgl. Definition 10.8):
Definition 10.29
Fur alle naturlichen Zahlen n ≥ 1 bezeichne Sn die Menge allerPermutationen von {1, . . . , n}, d. h. die Menge der bijektivenAbbildungen von {1, · · · , n} in sich.
Lemma 10.30
(Sn, ◦) ist bezuglich der Komposition ◦ eine Gruppe, die fur n ≥ 3 nichtkommutativ ist.
Beweis: Das neutrale Element in Sn ist die Identitat id .
Das Inverse π−1 einer Permutation π ist deren Umkehrabbildung.
Außerdem gibt es in S3 Permutationen π, π′, fur die π ◦ π′ 6= π′ ◦ π.
(Beispiel: π mit π(1) = 2, π(2) = 1, π(3) = 3 undπ′ mit π′(1) = 1, π′(2) = 3, π′(3) = 2). �
Formale Grundlagen der Informatik 34/43
Algebraische Strukturen
Die Zyklendarstellung von Permutationen (I)
Die naheliegende Darstellung von Permutationen π ∈ Sn ist durch ihreWertetabelle π = {(i , π(i)) | i = 1, . . . , n}. Alternativ wird oft dieZyklendarstellung verwendet. Diese basiert auf
Lemma 10.31
Fur alle i , 1 ≤ i ≤ n, gibt es ein k , 1 ≤ k ≤ n, mit πk(i) = i , sprich:
∀i ∈ {1, . . . , n} : ∃k ∈ {1, . . . , n} : πk(i) = i .
Hierbei ist π0 = id und πk = π ◦ · · · ◦ π (k Faktoren).
Beweis: Wir betrachten die Folge (i , π(i), π2(i), . . .) und fixieren dasminimale k, 1 ≤ k ≤ n, fur das ein j , 0 ≤ j ≤ k − 1, mit πk(i) = πj(i)existiert. (Beachte: Ein solches k muss existieren, da die Zielmenge von πnur n Elemente umfasst.) Es muss j = 0 (also πk(i) = i) gelten, da sonstwegen π(πk−1(i)) = π(πj−1(i)) die Bijektivitat von π verletzt wurde. �
Formale Grundlagen der Informatik 35/43
Algebraische Strukturen
Die Zyklendarstellung von Permutationen (II)
Definition 10.32
Eine Permutation π ∈ Sn heißt Zyklus der Lange k , falls eine Folge(i1, . . . , ik) von paarweise verschiedenen Zahlen aus {1, . . . , n} existiert,so dass
π(ir ) = ir+1 fur 1 ≤ r ≤ k − 1,
π(ik) = i1,
π(i) = i fur alle i 6∈ {i1, . . . , ik}.Schreibweise: π = (i1, . . . , ik).
Zyklen (i1, . . . , ik) und (j1, . . . , js) heißen disjunkt, falls{i1, . . . , ik} ∩ {j1, . . . , js} = ∅.
Lemma 10.33
Fur disjunkte Zyklen Z ,Z ′ ∈ Sn gilt: Z ◦ Z ′ = Z ′ ◦ Z . �(Beweis trivial)
Formale Grundlagen der Informatik 36/43
Algebraische Strukturen
Die Zyklendarstellung von Permutationen (III)
Theorem 10.34
Fur jede Permutation π ∈ Sn existiert eine eindeutig bestimmte Mengepaarweise disjunkter Zyklen Z1, . . . ,Zt , so dass
π = Z1 ◦ · · · ◦ Zt
und jedes i , 1 ≤ i ≤ n, in genau einem dieser t Zyklen vorkommt.
Beweis: Wir erzeugen Z1 durch die Folge (1, π(1), π2(1), . . .) im Sinnevon Lemma 10.31. Nehmen jetzt an, dass die paarweise disjunktenZyklen Z1, . . . ,Zs bereits erzeugt sind und dass noch ein i , 1 ≤ i ≤ n,existiert, das in keinem dieser Zyklen vorkommt. Dann erzeugen wir Zs+1
durch die Folge (i , π(i), π2(i), . . .). Zs+1 ist offensichtlich disjunkt zujedem der bereits erzeugten, paarweise disjunkten Zyklen Z1, . . . ,Zs . �
Beispiel: π = {(1, 5), (2, 4), (3, 1), (4, 7), (5, 3), (6, 6), (7, 2)}Zyklendarstellung: (1, 5, 3)(2, 4, 7)(6)
Formale Grundlagen der Informatik 37/43
Algebraische Strukturen
Die Ordnung von Permutationen
Theorem 10.35
Fur alle n ≥ 1 und Permutationen π ∈ Sn gilt, dass
ordSn(π) = kgV (|Z1|, |Z2|, . . . , |Zt |) ,
wobei π = Z1 ◦ Z2 ◦ · · · ◦ Zt die eindeutig bestimmte Zyklendarstellungvon π ist und |Zj |, 1 ≤ j ≤ t, die Lange des Zyklus Zj bezeichnet.
Beweis: siehe Ubungsblatt.
Formale Grundlagen der Informatik 38/43
Algebraische Strukturen
Strukturerhaltende Abbildungen (Homomorphismen)
Definition 10.36
G = (G , ◦) und G ′ = (G ′,⊗) seien Gruppen mit neutralen Elementene, e′. Eine Abbildung f : G −→ G ′ heißt Gruppenhomomorphismus,falls f (e) = e′ und fur alle g , h ∈ G gilt:
f (g ◦ h) = f (g)⊗ f (h).
Die Gruppen G ,G ′ heißen isomorph (Schreibweise: G ∼ G ′), falls einbijektiver Gruppenhomomorphismus f : G −→ G ′ (ein sogenannterGruppenisomorphismus) existiert.
Lemma 10.37
Ist f : G −→ G ′ ein Gruppenhomomorphismus, dann giltf (g−1) = f (g)−1 fur alle g ∈ G . Ist f bijektiv, so giltordG (g) = ordG ′(f (g)) fur alle g ∈ G . (Beweis auf Ubungsblatt) �
Formale Grundlagen der Informatik 39/43
Algebraische Strukturen
Beispiele
Trivialbeispiel 1: Die Abbildung f : G −→ G ′ mit f (g) = e′ fur alleg ∈ G ist ein Gruppenhomomorphismus.
Trivialbeispiel 2: idG : G −→ G ist ein Gruppenisomorphismus.
f : (Z4,+) −→ (Z5, ·)∗ mit f ([0]) = [1], f ([1]) = [2], f ([2]) = [4],f ([3]) = [3] ist ein Gruppenisomorphismus. (selbst prufen!)
f : (Z,+) −→ (Q, ·)∗ mit f (k) = 2k ist einGruppenhomomorphismus. (selbst prufen!)
Lemma 10.38
Fur g ∈ (G , ◦) sei ordG (g) = k . Dann ist f : (Zk ,+) −→ 〈g〉 mitf ([j ]) = g j ein Gruppenisomorphismus.
Falls ordG (g) =∞, so ist f : (Z,+) −→ 〈g〉 mit f (j) = g j einGruppenisomorphismus. (Beweis auf Ubungsblatt) �
Formale Grundlagen der Informatik 40/43
Algebraische Strukturen
Karthesisches Produkt von Gruppen
Definition 10.39
Seien G = (G ,⊕) und G ′ = (G ′,⊗) Gruppen mit neutralen Elementene, e′. Dann bezeichnet (G ,⊕)× (G ′,⊗) das karthesische Produkt, d. h.die Gruppe mit der Gruppenoperation ◦, definiert durch
(g , g ′) ◦ (h, h′) = (g ⊕ h, g ′ ⊗ h′)
fur alle g , h ∈ G , g ′, h′ ∈ G ′.
Beispiel: Kleinsche Vierergruppe (Z2,+)× (Z2,+). (vgl. Folie 41)
Wichtiger Satz aus der Algebra:
Theorem 10.40
Jede endliche kommutative Gruppe G ist isomorph zu einer Gruppe derGestalt (Zm1 ,+)× · · · × (Zms ,+) fur naturliche Zahlen m1, . . . ,ms .(ohne Beweis hier) �
Formale Grundlagen der Informatik 41/43
Algebraische Strukturen
Beispiel: (Z12, ·)∗ ∼ (Z2,+)× (Z2,+)
(Z12, ·)∗ [1] [5] [7] [11]
[1] [1] [5] [7] [11]
[5] [5] [1] [11] [7]
[7] [7] [11] [1] [5]
[11] [11] [7] [5] [1]
(Z2,+)× (Z2,+) ([0], [0]) ([0], [1]) ([1], [0]) ([1], [1])
([0], [0]) ([0], [0]) ([0], [1]) ([1], [0]) ([1], [1])
([0], [1]) ([0], [1]) ([0], [0]) ([1], [1]) ([1], [0])
([1], [0]) ([1], [0]) ([1], [1]) ([0], [0]) ([0], [1])
([1], [1]) ([1], [1]) ([1], [0]) ([0], [1]) ([0], [0])
Die Abbildung f : (Z12, ·)∗ −→ (Z2,+)× (Z2,+), definiert durch
f ([1]) = ([0], [0]),
f ([5]) = ([0], [1]),
f ([7]) = ([1], [0]),
f ([11]) = ([1], [1]),
ist ein Gruppenisomorphismus.
Formale Grundlagen der Informatik 42/43
Algebraische Strukturen
Weitere Beispiele isomorphe Gruppen
Es gilt bspw. auch: (Z15, ·)∗ ∼ (Z2,+)× (Z4,+). (selbst prufen!)
Weiterer wichtiger Satz aus der Algebra:
Theorem 10.41
Fur alle Primzahlen p ist (Zp, ·)∗ zyklisch, d. h. isomorph zu (Zp−1,+).(ohne Beweis hier) �
Bemerkung: Fur Primzahlen p spielen die Gruppen (Zp, ·)∗ eineentscheidende Rolle im Bereich der asymmetrischen Kryptographie!Grundidee: Sei p eine große, offentlich bekannte Primzahl, [g ] einoffentlich bekanntes Erzeugendes in (Zp, ·)∗ und x ∈ {0, . . . , p − 1} eingeheimer Exponent. Wer x kennt, kann y = g x mod p effizientberechnen. Ein Angreifer, der y
”beobachtet“, musste jedoch x aus
g , p, y ermitteln, also den entsprechenden diskreten Logarithmusziehen. Hierfur sind (bei ausreichend großem p) keine effizientenAlgorithmen fur Nicht-Quantencomputer bekannt.
Formale Grundlagen der Informatik 43/43
Algebraische Strukturen
Universalitat der Permutationsgruppen
Theorem 10.42
Fur alle naturlichen Zahlen n ≥ 1 gilt, dass jede n-elementige Gruppe(G ,⊗) mit neutralem Element e isomorph zu einer Untergruppe in Sn ist.
Beweis: Wir ordnen jedem Gruppenelement g ∈ G eine Permutation πguber G zu. Fur alle h ∈ G sei
πg (h) = g ⊗ h.
Man sieht leicht ein, dassπe = idG
und dass fur alle g , g ′ ∈ G gilt, dass
πg ′⊗g = πg ′ ◦ πg ,
d. h., die Zuordnung ist eine injektiver Gruppenhomomorphismus. �
Recommended