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 i0, so gilt ord(a)|k. Beweis: Wir schreiben k=q∙ord(a)+r mit 0≤r 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