Links und Funktionen
Sprachumschaltung

Navigationspfad
Sie sind hier: Startseite / Lehre / SS 2017 / Logik und Diskrete Strukturen / Material / K06 Gruppen


Inhaltsbereich

K06 Gruppen

Algebraische Strukturen: Halbgruppen, Monoide, Gruppen

Plain Text icon K06_Gruppen.txt — Plain Text, 15 KB (15471 bytes)

Dateiinhalt

Persönliche Notizen zur Vorbereitung der LDS Vorlesung. Diese Notizen waren 
ursprünglich nicht zur Herausgabe gedacht und sind entsprechend mit Vorsicht 
zu genießen. Es wird dringend empfohlen, dass Buch zu verwenden:

Angelika Steger: Diskrete Strukturen. 
Band 1: Kombinatorik, Graphentheorie, Algebra.
2. Auflage, Springer 2007, 978-3-540-46660-4


=================================================
 Algebraische Strukturen (Buch Kapitel 5.1, 5.3)
=================================================

Anstatt Teilbarkeit, ggT, etc. immer wieder zu Wiederholen
suchen wir nun verallgemeinerte Strukturen. Wenn ein Beweis auf 
einer verallgemeinerten, abstrakten Struktur möglich ist,
dann gilt dieser Beweis gleich auch für alle spezielleren
Strukturen, welche zu der verallgemeinerten Struktur passen.

Definition: Signatur
  Eine _Signatur_ ist eine Liste von natürlichen Zahlen,
  welche die Stelligkeiten von _Operationen_ angibt.
  Operationen mit Stelligkeit 0 sind Konstanten.
  
Definition: Algebra
  Eine Algebra (A,f₁,…,fₖ) zur Signatur σ=(m₁,…,mₖ) besteht aus
  einer Menge A und Operationen  fᵢ mit Stelligkeit mᵢ, d.h.
  fᵢ: A×…×A→A, auch geschrieben fᵢ:A^(mᵢ)→A,
  d.h. eine Abbildung von mᵢ-vielen Argumenten aus A auf ein A.

Meist wird in der Sprechweise nicht mehr zwischen
der Menge D und der zugehörigen Algebra ⅅ=(D,f₁,…,fₖ) unterschieden.
Manchmal wird die Grundmenge D auch |ⅅ| geschrieben, 
oder als "Trägermenge (der Algebra)" bezeichnet.

Beispiele: 
  ({⊥,⊤},∧,∨,¬) hat Signatur (2,2,1)
  (ℕ,min,max)   hat Signatur (2,2)
  (ℝ,+,0)       hat Signatur (2,0)
  (ℝ,f₁(x,y)=0,f₂(x,y)=x²-y,f₃()=42) hat auch Signatur (2,2,0)
  
Achtung: Operationen dürfen nicht aus Menge herausführen! (Wertebreich=A)
              
Definition: Rechts-/Linksneutral 
  Sei A Algebra mit (u.a.) einer 2-stelligen Operation ○ als Infix.
  Ein Element a∈A ist _links-neutral_,  falls für alle x∈A gilt a○x=x
  Ein Element a∈A ist _rechts-neutral_, falls für alle x∈A gilt x○a=x
  Ein Element a∈A heisst _neutral_ bezüglich ○, falls a sowohl
  links-neutral als auch rechts-neutral ist.  
  
Lemma: Falls es in einer Algebra A zu einer 2-stelligen Operation ○ ein 
  links-neutrales Element a und ein rechts-neutrales Element b, 
  dann muss a=b gelten.
Beweis:
  a○b=b, da a links-neutral  ist.
  a○b=a, da b rechts-neutral ist.
  Also folgt a=a○b=b.
  □
Korollar: Neutrale Elemente sind eindeutig, d.h. 
  falls a und b neutral, dann folgt a=b.
  
Beispiele:
  ⊤ ist neutral bezüglich ∧
  ⊥ ist neutral bezüglich ∨
  0 ist neutral bezüglich +
  1 ist neutral bezüglich ∙
  0 ist neutral bezüglich max in Algebra (ℕ,min,max) 
    aber min hat in dieser Algebra kein neutrales Element 
    
Beispiel:
  Verbände kann man alternativ auch als Algebren mit zwei 
  zweistelligen Operation ⊓ (Infimum) und ⊔ (Supremum) definieren,
  welche den Gesetzen für Assoziativität, Kommutativität und 
  Absorption genügen (in Vorlesung war Relation ⊑ grundlegend
  gewählt worden, doch eine Relation ist keine Operation).    
    
Definition: assoziative Operation
  Eine zweistellige Operation ○ einer Algebra A heisst _assoziativ_, 
  falls für alle x,y,z∈A gilt x○(y○z)=(x○y)○z.
  
Für assoziative Operationen eignet sich die Infix-Notation, 
denn man kann einfach die Klammern weglassen und x○y○z schreiben.
(Wir setzen manchmal explizite Klammern zur Verdeutlichung einer Beweiskonstruktion.)

Definition: Halbgruppe
  Eine algebraische Struktur mit einer zweistelligen 
  assoziativen Operation ○ heisst _Halbgruppe_ (engl. semigroup).

Definition: Monoid
  Eine Halbgruppe mit einem neutralen Element e heisst _Monoid_.
  (Auch "Halbgruppe mit Eins" genannt, da das neutrale Element 
  oft mit "1" oder "e" (wie Einheit) bezeichnet wird.) 

Manchmal wird das neutrale Element in der Signatur aufgeführt, 
z.B. (ℤₙ,∙,1) mit Signatur (2,0). Da es nach obigen Lemma aber 
eindeutig sein muss, kann man es auch einfach berechnen, wenn 
es nicht mit angegeben wird. 

Definition: Links-/Rechtsinverse
  Ist M ein Monoid und a∈M so heisst x∈M _rechtsinvers_zu_a_ falls
  a○x=1. Analog: y∈M _Linksinverses_zu_a_ falls y○a=1.
  Ein z∈M heist _Inverses_zu_a_ falls z rechts- und linksinvers zu a ist. 
  
Lemma: Hat a ein Rechtsinverses x und ein Linksinverses y, so ist x=y.
Beweis: Es gilt x=1○x=(y○a)○x=y○(a○x)=y○1=y □

Korollar: Inverse sind eindeutig. 
Daher bezeichnet man das Inverse von a oft auch mit a⁻¹

Beispiel: Sei A eine Menge und M die Menge aller Abbildungen f:A→A. 
Eine zweistellige Operation ○ auf M ist definiert durch (f○g)(x)=f(g(x)), also Komposition für f,g∈M.
Man kann nachrechnen, dass (M,○) eine Halbgruppe ist. Weiterhin ist die Identitätsfunktion id(x)=x 
das neutrale Element zu ○, d.h. (M,○,id) ist ein Monoid. 
Es gilt: Ist f∈M injektiv, so hat f ein Linksinverses. 
         Ist f∈M surjektiv, so hat f ein Rechtsinverses.
         Ist f∈M bijektiv, so hat f ein Inverses. 
Zum Beispiel:
  A=ℕ, M=ℕ→ℕ, f(x)=⌊x/2⌋ ist surjektiv aber nicht injektiv, g(x)=2x ist injektiv aber nicht surjektiv
  g ist Rechtsinverses zu f, f ist Linksinverses zu g.         
         
Definition: Unterstruktur
  Für Algebra A=(A,f₁,…,fₙ) mit Signatur σ=(m₁,…,mₙ) dann ist eine
  Teilmenge U⊆A eine Unterstruktur von A, falls U unter den Operationen
  _abgeschlossen_ ist, d.h. 
  für alle i∈{1,…,n} und alle u₁,…,u_mₖ∈U gilt fᵢ(u₁,…,u_mᵢ)∈U.
  Man schreibt auch fᵢ|U für "fᵢ eingeschränkt auf U".
  (U,f₁|U,…,fₙ|U) ist dann insbesondere auch eine algebraische Struktur.
  
Beispiele: 
  ① (ℕ,+) ist Unterstruktur von (ℤ,+)
  ② ({2n|n∈ℕ},+) ist Unterstruktur von (ℕ,+),
  aber ({2n+1|n∈ℕ},+) ist keine Unterstruktur von (ℕ,+).

Definition: Homomorphismus
  Für Algebren (A,f₁,…,fₙ) und (B,g₁,…,gₙ) mit gleicher Signatur σ=(m₁,…,mₙ) 
  heisst eine Funktion h:A→B _Homomorphismus_, wenn für alle a₁,…,a_mᵢ∈A gilt:
  h(fᵢ(a₁,…,a_mᵢ)) = gᵢ(h(a₁),…,h(a_mᵢ))
  Man sagt auch "h veträgt sich mit den Operationen der beiden Algebren".
  Falls A=B, so spricht man von einem _Endomorphismus_.
  
Beispiele:
  ③ Ist U Unterstruktur von A, so ist h:U→A definiert durch
  h(x)=x trivialerweise ein Homomorphismus.
  
  ④ h:ℤ → ℤₘ      (also ganze Zahlen modulo m)
    n ↦ n mod m
  ist Homomorphismus von (ℤ,+,∙) nach (ℤₘ,+ₘ,∙ₘ);
  wobei +ₘ,∙ₘ jeweils Addition/Multiplikation modulo m.
  
Definition: Isomorphismus
  Ein bijektiver Homomorphismus von (A,f₁,…,fₙ) nach (B,g₁,…,gₙ) heisst
  _Isomorphismus_. Ist A=B so spricht man von einem _Automorphismus_.
  
  Existiert ein Isomorphismus von A und B, so bezeichnet man die beiden 
  Algebren A und B als _isomorph_.
  
Lemma: Ist h:A→B ein Isomorphismus, so ist die Umkehrfunktion h⁻¹ 
  wieder ein Homomorphismus.
  Beweis=Übung

Beispiele:
  ⑤ h(n)= n↦-n ist Automorphismus für (ℤ,+,∙)
  ⑥ h(x)= e^x ist Isomorphismus von (ℝ,+) mach (ℝ⁺,∙), denn 
     e^(a+b)=e^a∙e^b und log ist Umkehrfunktion
  ⑦ h: ℤ_(m₁∙…∙mₖ) → ℤₘ₁×…×ℤₘₖ mit m₁,…,mₖ paarweise teilerfremd, 
     definiert durch h(n)↦(n mod m₁,…,n mod mₖ) ist Isomorphismus 
  zwischen (ℤ_(m₁∙…∙mₖ),+ mod m₁∙…∙mₖ,∙ mod m₁∙…∙mₖ) und 
    (ℤₘ₁×…×ℤₘₖ, + koponentenweise modulo mᵢ, ∙ koponentenweise modulo mᵢ);
    dies folgt aus dem Chinesischen Restsatz.
  
Lemma: Ein Isomorphismus bildet neutrale Elemente auf neutrale Elemente ab;
       sowie Inverse auf Inverse.
Beweis: Sei h:A→B ein Isomorphismus. Zeige b○h(e)=b für alle b∈B und e∈A neutral in A. 
Es gilt b○h(e)=h(h⁻¹(b))○h(e)=h(h⁻¹(b)○e)=h(h⁻¹(b))=b. 
Analog gilt h(e)○b=h(e)○h(h⁻¹(b))=h(e○h⁻¹(b))=h(h⁻¹(b))=b.
Beweis für Inverse=Übung
□

  
Prinzip: Sind A,B isomorph, so haben A und B dieselben 
(vernünftig formulierten) Eigenschaften; d.h. Gesetze lassen sich übertragen.



Gruppen
=======

Definition: Gruppe
Eine _Gruppe_ ist ein Monoid, in dem jedes Element ein Inverses besitzt. 
Das eindeutige Inverse von x wird meist mit x⁻¹ (multiplikativ) oder -x (additiv) bezeichnet.

Beispiele:
  ① (ℤ,+) neutrales Element ist 0 und Inverses von a ist -a
  ② (ℝ\{0},∙) mit 1 als neutralem Element, x⁻¹=1/x
  
Satz: Sei M ein Monoid, die Menge aller Elemente, welche 
  ein Inverses besitzen, bilden als Unterstruktur eine Gruppe. 
  (Bemerkenswerterweise führt die Operation also nicht aus der Menge heraus!)
Beweis: Es sei G≝{ m∈M | ∃x∈M.m○x=x○m=1}.
  Für alle m₁,m₂∈G mit Inversen m₁⁻¹ und m₂⁻¹
  ist auch m₁○m₂∈G, denn (m₂⁻¹○m₁⁻¹) ist das Inverse:
  (m₂⁻¹○m₁⁻¹)○m₁○m₂=m₂⁻¹○(m₁⁻¹○m₁)○m₂=m₂⁻¹○1○m₂=m₂⁻¹○m₂=1.
  Damit ist G unter ○ abgeschlossen und somit Unterhalbgruppe von M
  Wegen 1○1=1 folgt auch 1∈G und damit ist G ein Untermonoid von M.
  Da per Definition jedes Element in G ein Inverses in G besitzt,
  ist G eine Gruppe.
  □
  
Beispiele:  
  ③ Alle bijektive Funktionen einer Menge auf sich selbst
  (Permutationen) bilden immer eine Gruppe: Alle Funktionen einer 
  Mengen bilden ein Monoid, alle invertierbaren Funktionen einer 
  Menge bilden damit ein Untermonoid und damit eine Gruppe 
  (da ja alle verbleibenden Funktionen invertierbar sind).
  (Permutationen auf n Elementen wird mit "Symmetrische Gruppe Sₙ" bezeichnet.)
  ④ (ℤₚ\{0},∙ₚ) für p prim ist eine Gruppe, 
  und auch  ℤₙ*=({ a∈ℤₙ\{0} | ggT(a,n)=1}, ∙ₙ).   
  Begründung für Erstes: Abschluß und 1 ist klar; 
  Inverses zu x∈ℤₚ existiert: finde mit 
  erweitertem Euklidischem Algorithmus s,t mit s∙x+t∙p=1=ggT(x,p) 
  dann ist (s mod p) das Inverse zu x.
  
Definition: kommutative Gruppe
  Ein Gruppe (G,∙) heisst _abelsch_ oder _kommutativ_, 
  falls für alle Gruppenelemente x,y∈G gilt x∙y=y∙x.

Bsp.: ④ ist abelsch, aber ③ ist nicht abelsch


Satz: Für jede Gruppe G und x,y,a,b,c ∈ G gilt:
  ① (x⁻¹)⁻¹=x
  ② (aⁱ)⁻¹= (a⁻¹)ⁱ
  ③ a∙c=b∙c ⇒ a=b
  ④ c∙a=c∙b ⇒ a=b
  ⑤ a∙x=b   ⇔ x=a⁻¹∙b
  ⑥ x∙a=b   ⇔ x=b∙a⁻¹
  
Beweis:  
  ①: Es gilt x⁻¹∙x=e und x∙x⁻¹=e. Damit ist x ein 
  Inverses von x⁻¹, aber da Inverse eindeutig sind, 
  ist x das Inverse von x⁻¹.
  ②: Per Induktion über i: 
  (a⁻¹)ⁱ∙aⁱ=(a⁻¹)⁽ⁱ⁻¹⁾∙(a⁻¹∙a)∙a⁽ⁱ⁻¹⁾= (a⁻¹)⁽ⁱ⁻¹⁾∙a⁽ⁱ⁻¹⁾=1
  ③: a∙c=b∙c ⇒ a∙c∙c⁻¹=b∙c∙c⁻¹ ⇒ a=b
  ④: analog zu ③
  ⑤: a∙x=b ⇒ a⁻¹∙a∙x=a⁻¹∙b ⇒ e∙x=a⁻¹∙b
     e∙x=a⁻¹∙b ⇒ x=a⁻¹∙b
  ⑥: analog zu ⑤
  □
    
Definition: Ordnung von Elementen
  Sei a∈G, G eine Gruppe. Die _Ordnung_ von a, 
  geschrieben ord(a), ist die kleinste Zahl k>0, 
  so dass aᵏ=1; gibt es kein k, so setzen wir ord(a)=∞.

Bsp.: 
  * In (ℤ,+) gilt ord(1)=∞.
  * In ℤ₉* gilt ord(2)=6, da 2⁶=2∙2∙2∙2∙2∙2=64 und 64 mod 9 = 1
   
Lemma:
  Ist G eine endliche Gruppe, so hat jedes g∈G eine
  endliche Ordnung.
Beweis:
  Da die Gruppe endlich ist, muss es in der 
  Folge 1,a,a²,a³,a⁴,a⁵,… irgendwann eine Wiederholung geben.
  O.b.d.A sei aⁱ=aʲ mit i<j∈ℕ. Es gilt (a⁻¹)ⁱ∙aⁱ=1 
  also auch 1=(a⁻¹)ⁱ∙aʲ = a⁽ʲ⁻ⁱ⁾. Damit ist ord(a)≤j-i.
  □
  
Lemma: 
  Ist aᵏ=1 für k>0, so gilt ord(a)|k.
Beweis:
  Wir schreiben k=q∙ord(a)+r mit 0≤r<ord(a).
  1 = aᵏ = a^(q∙ord(a)+r) = a^(q∙ord(a))∙a^r = (a^ord(a))^q∙a^r = 1∙a^r.
  Damit haben wir a^r=1 und r<ord(a). Da per Definition 
  die Ordnung ja die kleinste Potenz i ist, für die a^i=1 gilt, folgt r=0.
  
Definition: Untergruppe
  Eine Untergruppe U einer Gruppe G ist eine Unteralgebra, welche 
  ebenfalls eine Gruppe ist (d.h. jedes u∈U hat ein Inverses in U).
  
Beispiel: 
  (ℕ,+) ist Unteralgebra von (ℤ,+), aber keine Untergruppe.

Lemma:
  Jede Unteralgebra U einer endlichen Gruppe G ist eine Untergruppe.
Beweis:
  Für ein b∈U muss bᵏ∈U für alle k∈ℕ gelten, da U als Unteralgebra 
  bezüglich ∙ abgeschlossen sein muss. Nach dem vorangegangenen Lemma 
  hat jedes Element einer endlichen Gruppe eine endliche Ordnung:
    1 = b^(ord(b)) = b^(ord(b)-1)∙b = b⁻¹∙b
  Also muss 1∈U und b⁻¹∈U gelten.  
  □

Lemma:
  Ist H eine Untergruppe von G, so definiert 
  { (a,b) | a⁻¹∙b∈H für a,b∈G } eine Äquivalenzrelation ~ auf G.
Beweis:
  Reflexivität: a~b ⇔ a⁻¹∙a∈H ⇔ 1∈H
  Symmetrie: a~b ⇔ a⁻¹∙b∈H ⇔ b⁻¹∙a∈H ⇔ b~a,
  da b⁻¹∙a das (eindeutige) Inverse von a⁻¹∙b in G bzw. H ist.
  Transitivität: Es sei a~b und b~c, d.h.
  a⁻¹∙b∈H und b⁻¹∙c∈H. Damit muss aber 
  (a⁻¹∙b)∙(b⁻¹∙c)∈H gelten, also auch b⁻¹∙c∈H wegen Assoziativität von ∙.
  □
  
Bemerkung: a~b ⇔ Es gibt ein h∈H mit a∙h=b
  
Definition: Nebenklassen
  Für eine Untergruppe H einer Gruppe G heißt 
    b∙H ≝ { b∙h | h∈H } 
  _linke_Nebenklasse_von_H_in_G_ und analog 
    H∙b ≝ { h∙b | h∈H } 
  _rechte_Nebenklasse_von_H_in_G_
  
Lemma:
  Die linken Nebenklassen sind Äquivalenzklassen zur Relation ~,
  denn a⁻¹∙b∈H ⇔ a∙H=b∙H:
Beweis:
  Es sei a~b, also a⁻¹∙b∈H. Wegen der  Gruppeneigenschaft von H
  gilt auch (a⁻¹∙b)⁻¹=b⁻¹∙a∈H.
  Sei nun x∈a∙H, dann gilt x=a∙h für ein h∈H.  
  Sei h'=(b⁻¹∙a)∙h. Es gilt h'∈H.
  x=a∙h=b∙b⁻¹∙a∙h=b∙h' also gilt x∈b∙H.
  Umgekehrt sei nun a∙H=b∙H. Für jedes x=a∙h gibt es also 
  ein h' mit x=b∙h'. 
  Aus a∙h = b∙h' folgt a⁻¹∙a∙h = h = a⁻¹∙b∙h' und damit 
  bereits a⁻¹∙b∈H, denn a⁻¹∙b=h∙h'⁻¹.
  □
  
Lemma: 
  Ist G endlich, so haben alle Nebenklassen zu einer 
  Untergruppe H die gleiche Kardinalität.
Beweis: 
  Angabe einer Bijektion 
  a∙H -f-> b∙H
  x ↦ b∙a⁻¹∙x 
  mit Umkehrfunktion y↦a∙b⁻¹∙y
  □
  
Korollar "Satz von Lagrange":
  Die Kardinalität einer Nebenklasse ist ein Teiler 
  der Kardinalität der Gruppe;
  insbesondere gilt das die Kardinalität einer Untergruppe 
  die Kardinalität der Gruppe teilt, wegen H=1∙H.
  
Lemma:  
  Ist a∈G und G endlich, so bildet
    H = {aⁱ| 0<i≤ord(a)}
  eine Untergruppe von G der Kardinalität ord(a).  
  (Man nennt diese auch die von a erzeugte zyklische Untergruppe.)
Beweis:
  aⁱ∙aʲ=aⁱ⁺ʲ=a^(i+j mod ord(a))
  (weil i+j=q∙ord(a)+(i+j mod ord(a)) und a^ord(a)=1)
  Inverses zu a: a^(ord(a)-1)=a⁻¹.
  □

Die zyklisch erzeugte Untergruppe von a ist isomorph zu (ℤ_ord(a),+)

Anwendung des Satzes von Lagrange ergibt:
  * Die Ordnung jedes Elements a ist ein Teiler von |G|
  * a^|G|=1, da |G| ein Vielfaches von ord(a) ist, also 
    a^|G|=(a^ord(a))^q für ein q mit |G|=q∙ord(a)
  * Satz von Euler (siehe K04):
    Für alle a,m ∈ ℕ gilt a^φ(m)≡1 (mod m) 
    wobei φ(n)≝ |ℤₙ*| (eulersche Phi-Funktion)
  * Kleiner Satz von Fermat (siehe K04), ein 
    Spezialfall des Satzes von Euler: 
    Für a∈ℕ und p prim gilt a^(p-1)≡1 (mod p), 
    denn es gilt φ(p)=p-1.
  
 

Artikelaktionen


Funktionsleiste