Mathematik für Informatik I Vorlesungsskripte PDF

Mathematik für Informatik I Dr. Stefan Meggendorfer Vorlesungs-Skript Wintersemester 2024/25 19. Dezember 2024 Vorwort Dieses Skript ist während der Vorlesung Mathematik für Informatik I am mathe- matischen Institut der Universität Heidelberg im Wintersemesters 20...

Mathematik für Informatik I Dr. Stefan Meggendorfer Vorlesungs-Skript Wintersemester 2024/25 19. Dezember 2024 Vorwort Dieses Skript ist während der Vorlesung Mathematik für Informatik I am mathe- matischen Institut der Universität Heidelberg im Wintersemesters 2024/25 entstanden. Im Wesentlichen behandelt die Vorlesung eine Einführung der linearen Algebra, mit einem spezifischen Hinblick auf die Anwendung in der Informatik. Dazu werden alle nötigen mathematischen Begri↵e und Konzepte didaktisch aufbereitet und auf Basis logischer Schlussfolgerungen eingeführt. In der Vorlesung wird nur ein gewisser Teil der hier aufgeführten Beweise explizit vorgestellt, um den Blick stärker auf Beispiele und Anwendungen legen zu können. Nichtsdestotrotz sind die Beweise Teil des Skriptes, damit interessierte Studentinnen und Studenten hier auch in gewissem Maße ein Nachschlage- werk zum Selbststudium zur Hand haben. Beweise werden in der Vorlesung insbesondere zu Anfang ausgeführt, um die Studierenden an den Formalismus der modernen Ma- thematik zu gewöhnen und ihnen das Handwerkszeug zur Bearbeitung mathematischer Problemstellungen zu geben. Zum Anderen werden Beweise später immer dann aus- geführt, wenn sie zum Verständnis der Konzepte einen Beitrag liefern oder aber einen konstruktiven Zugang zur Theorie bieten. Dabei ist das Erlernen des mathematischen Formalismus ein Hauptanliegen in dieser Einführungsvorlesung, da er die Grundlage zum Verständnis der verschiedenen Konzepte und Begri↵e des weiterführenden Studi- ums liefert. Nicht nur in den mathematischen Anwendungsfeldern wie der Statistik und Stochastik, dem wissenschaftliches Rechnen, oder der Geometrie, sondern auch in der theoretischen Informatik, der Algorithmik, und vielem mehr. i Inhaltsverzeichnis 1 Grundlagen 1 1.1 Definition, Satz, Beweis............................ 1 1.2 Naive Aussagenlogik.............................. 2 1.3 Beweisarten................................... 7 1.4 Prädikatenlogik................................. 9 1.5 Naive Mengenlehre............................... 11 1.6 Vollständige Induktion............................. 16 1.7 Relationen.................................... 17 1.8 Abbildungen.................................. 22 2 Gruppen, Ringe und Körper 31 2.1 Gruppen..................................... 32 2.1.1 Restklassen............................... 37 2.2 Ringe...................................... 43 2.3 Körper...................................... 46 2.4 Exkurs...................................... 47 2.4.1 Der Körper der komplexen Zahlen.................. 47 2.4.2 Der Ring der Polynome........................ 50 3 Vektorräume 61 3.1 Vektorräume.................................. 61 3.2 Untervektorräume............................... 63 3.3 Linearkombinationen und Erzeugnis..................... 65 3.4 Lineare Unabhängigkeit............................ 68 3.5 Basis....................................... 71 3.6 Dimension.................................... 74 3.7 Exkurs: Geraden im Rn............................ 77 3.8 Matrizen..................................... 81 4 Lineare Abbildungen 95 4.1 Lineare Abbildungen.............................. 95 4.2 Bild, Fasern und Kern............................. 100 4.2.1 Affine Unterräume........................... 104 4.3 Lineare Gleichungssysteme........................... 105 4.4 Lineare Abbildungen und Matrizen...................... 112 4.5 Berechnung der inversen Matrix........................ 116 4.6 Beispiele linearer Abbildungen........................ 120 iii Inhaltsverzeichnis 4.7 Basiswechsel................................... 123 5 Innenprodukträume 55 5.1 Bilinearformen................................. 55 5.2 Orthogonalität................................. 55 5.3 Orthonormalbasen............................... 55 5.4 Selbstadjungierte, isometrische (und normale) Operatoren......... 55 5.5 Spektralsätze.................................. 55 5.6 Ausblick zum wissenschaftlichen Rechnen.................. 55 Literaturverzeichnis 57 Stichwortverzeichnis 57 iv 1 Grundlagen In diesem Kapitel werden grundlegende Begri↵e, Symbole und Strukturen der Mathematik eingeführt.1 Nachdem der grundsätzliche Aufbau mathematischer Texte in Abschnitt 1.1 bespro- chen wurde, starten wir mit einer Einführung in die (naive) Logik in Abschnitte 1.2 bis 1.4 und in die (naive) Mengenlehre in Abschnitte 1.5 und 1.6 um eine mathematische Sprache, Schlussfolgerungen und die grundsätzliche Behandlung mathematischer Frage- stellungen zu ermöglichen. Anschließend werden in Abschnitt 1.7 Relationen eingeführt, um Beziehungen innerhalb von Mengen zu betrachten, und Abbildungen in Abschnitt 1.8, um Beziehungen zwischen verschiedenen Mengen zu analysieren. 1.1 Definition, Satz, Beweis Mathematische Texte bestehen hauptsächlich aus Definitionen, Sätzen und Beweisen. Mit Hilfe dieser Struktur können Begri↵e und Ergebnisse klar und logisch aufgebaut werden. Mit einer Definition wird ein Begri↵ bestimmt, d.h. seine definierenden Eigenschaften beschrieben. Ein Satz beschreibt ein Ergebnis, bzw. eine Aussage und wird in einem zugehörigen Beweis auf Basis der Logik nachvollziehbar gemacht. Ein Satz besteht immer aus einer oder mehreren Voraussetzungen und beinhaltet eine wahre Schlussfolgerung. Insbesondere müssen alle unbekannten Größen eingeführt werden. Beweise enden in diesem Skript immer mit einem kleinem Quadrat ⇤, können in anderen Texten aber auch mit #, oder qed (”quod erat demonstrandum”, lateinisch für ”was zu beweisen war”) enden. Im Folgenden ein Beispiel wie Definitionen, Sätze und Beweise aufgeschrieben werden: Definition. Eine gerade Zahl ist eine natürliche Zahl n, die durch zwei teilbar ist, d.h. es gibt eine natürliche Zahl m, so dass n = 2m. Satz. Sei n eine gerade Zahl. Dann ist auch n2 eine gerade Zahl. Beweis. Eine gerade Zahl n ist durch zwei teilbar, also gibt es eine natürliche Zahl m, 1 Kapitel 1 orientiert sich weitestgehend an dem Vorlesungsmanuskript , sowie an dem Buch. Beide geben eine gute Einführung in die lineare Algebra mit vielen hilfreichen Beipielen. 1 1 Grundlagen so dass n = 2m. Durch einsetzen ergibt sich n2 = (2m)2 = 4m2 = 2(2m2 ). Aus den Rechenregeln für natürliche Zahlen folgt, dass 2m2 eine natürliche Zahl ist. Also ist n2 wieder eine durch zwei teilbare natürliche Zahl und damit eine gerade Zahl. Sätze können noch verschiedene andere Bezeichnungen haben, wie z.B. Lemma, Ko- rollar, Folgerung, Theorem oder Proposition, abhängig davon, in welchem Kontext sie in einem mathematischen Text vorkommen. Ein Lemma ist ein sogenannter Hilfssatz. Lemmata beschreiben im Normalfall kei- ne eigenständigen relevanten Resultate, sind aber ein hilfreiches Hilfsmittel in der Be- weisführung von anderen Sätzen, um deren Beweis zu strukturieren und an geeigneten Stellen abzukürzen, damit die eigentliche Beweisidee nicht in einer Vielzahl technischer Einzelschritte untergeht. Nichtsdestotrotz können Lemmata manchmal auch wichtige Resultate enthalten (wie z.B. im Fall des Fundamentallemma der Variationsrechnung). Ein Korollar ist eine direkte, d.h. unmittelbare/o↵ensichtliche Folgerung aus einer Definition oder einem Satz. Unmittelbar bedeuted hier, dass keine vielen Teilschritte zum Beweis eines Korollars nötig sind. Dies ist oft sehr subjektiv und abhängig vom Autor des Textes. Manche Resultate werden in Texten als Theorem bezeichnet, wenn sie besonders wichtig für das Thema sind. Davon abgesehen ist ein Theorem einfach nur ein anderes Wort für einen Satz (englisch: ”theorem”). Zuletzt wird mit einer Proposition meist ein Resultat bezeichnet, das bereits in einem anderen Werk bewiesen worden ist. Propositionen finden sich z.B. in aktuellen Forschungsartikeln oder auch in Büchern, wenn die Urheberschaft von Aussagen anderer Autoren hervorgehoben werden soll. All diese Bezeichnungen für Sätze werden teilweise von verschiedenen Autoren un- terschiedlich benutzt werden. Dies ist sehr individuell, was nicht zuletzt auch an den Gepflogenheiten innerhalb der einzelnen mathematischen Teilgebiete liegt. Darüber hinaus ist ein Axiom eine Aussage, die wir ohne Beweis als Grundsatz voraussetzen – also eine Aussage, die wir grundsätzlich als gegeben hinnehmen, wie z.B. die Existenz der natürlichen Zahlen N = {1, 2, 3,...}, oder dass auf eine natürliche Zahl immer eine weitere natürliche Zahl folgt (das ist eines der sogenannten Peano- Axiome). Axiome werden so sparsam wie möglich eingeführt. 1.2 Naive Aussagenlogik Wir führen an dieser Stelle die Logik nur in einer naiven Form ein. Das bedeutet, dass wir hier die sprachliche Vorstellung von Logik verwenden anstatt einer strikt axiomatisch aufgebauten mathematischen Logik, da eine solche den Umfang einer eigenen Vorlesung hat und den didaktischen Aufbau in dieser Einführungsveranstaltung (von leicht zu schwer und von einfach zu komplex) eher stören würde. Interessierten Studierenden sei aber eine Vorlesung zur mathematischen Logik oder aber das Studium weiterführender Literatur empfohlen. 2  1.2 Naive Aussagenlogik Wir beginnen mit der Einführung von Aussagen und Wahrheitswerten. Definition 1.1. Eine Aussage ist ein feststellender Satz, dem genau einer der Wahrheitswerte wahr (w) oder falsch (f ) zugeordnet werden kann. Beispiel 1.2. Wir betrachten die folgenden Sätze A, B, C und D und diskutieren jeweils ihren Wahrheitswert: A: 7 ist eine Primzahl. B: 5 ist gerade. C: Draußen ist die Straße nass. D: Der Mont Blanc ist der höchste Berg Europas. Den Aussagen A und B können wir einfach einen der Wahrheitswerte zuordnen, A ist wahr, B ist falsch. Hier handelt es sich um mathematische Aussagen, von denen wir annehmen können, dass sie entweder wahr oder falsch sind. C und D müssen erst in der realen Welt überprüft werden und können zum Beispiel jetzt wahr und in Zukunft falsch sein. Das hängt auch insbesondere an der Art der Messung oder der Definition der Begri↵e ab (ab wann gilt eine Straße als nass, wo genau liegen die Grenzen Europas). Wir beschäftigen uns in dieser Vorlesung ausschließlich mit solchen (mathematischen) Aussagen, die entweder wahr oder falsch sind. Aus einfachen Aussagen kann man durch logische Verknüpfungen (sogenannte Junkto- ren) kompliziertere Aussagen bilden. Definition 1.3. Ein Junktor ist eine logische Verknüpfung zwischen Aussa- gen. Kompliziertere Aussagen, die mit Junktoren verknüpft wurden, nennen wir For- meln. Wir werden in diesem Abschnitt die folgenden Junktoren einführen: Negation ¬ UND-Verknüpfung ^ ODER-Verknüpfung _ Implikation ) Äquivalenz , Bemerkung 1.4. Mithilfe von Klammern lässt sich eine Formel gruppieren und die Reihenfolge der Auswertungen angeben. Seien A, B zwei Aussagen, dann wird bei der logisch verknüpften Aussage ¬(A _ B) zunächst der Wahrheitsgehalt von A _ B ermittelt und erst anschließend negiert. 3 1 Grundlagen Die Angabe des Wahrheitswertes einer Formel erfolgt durch Wahrheitstafeln, die den Wahrheitswert der zusammengesetzten Aussage aus den Wahrheitswerten der Ein- zelaussagen liefern. Im Folgenden seien A, B zwei Aussagen. Definition 1.5 (Negation (NICHT-Verknüpfung)). Symbol: ¬ A ¬A Wahrheitstafel: w f f w Beispiel 1.6. A: 7 ist eine Primzahl (w) ¬A: 7 ist keine Primzahl (f ) Definition 1.7 (Konjunktion (UND-Verknüpfung)). Symbol: ^ A B A^B w w w Wahrheitstafel: w f f f w f f f f Definition 1.8 (Disjunktion (ODER-Verknüpfung)). Symbol: _ A B A_B w w w Wahrheitstafel: w f w f w w f f f Beispiel 1.9. A: 7 ist eine Primzahl (w) B: 5 ist gerade (f ) A ^ B: 7 ist eine Primzahl und 5 ist gerade (f ) A _ B: 7 ist keine Primzahl oder 5 ist gerade (w) Bemerkung 1.10. Bei _ (ODER-Verknüpfung) handelt es sich um ein einschließen- des oder. Der Ausdruck Entweder A oder B korrespondiert zu (A _ B) ^ (¬(A ^ B)). 4  1.2 Naive Aussagenlogik Definition 1.11 (Implikation). Symbol: ) A B A)B w w w Wahrheitstafel: w f f f w w f f w Sprechweise: A impliziert B, aus A folgt B, A ist eine hinreichende Bedingung für B (ist A ) B wahr, dann folgt aus A wahr, dass auch B wahr ist), B ist eine notwendige Bedingung für A (ist A ) B wahr, dann kann A nur dann wahr sein, wenn auch B wahr ist). Beispiel 1.12. Es seien m, n natürliche Zahlen. A: m ist gerade B: m · n ist gerade Dann ist für alle natürlichen Zahlen m, n die Implikation A ) B wahr, denn: (Wir nehmen eine Fallunterscheidung vor nach m, n gerade bzw. ungerade) 1. Fall: m gerade, n gerade. A wahr, B wahr. Also A)B wahr. 2. Fall: m gerade, n ungerade. A wahr, B wahr. Also A)B wahr. 3. Fall: m ungerade, n gerade. A falsch, B wahr. Also A)B wahr. 4. Fall: m ungerade, n ungerade. A falsch, B falsch. Also A)B wahr. Definition 1.13 (Äquivalenz (GENAU-DANN-WENN-Verknüpfung)). Symbol: , A B A,B w w w Wahrheitstafel: w f f f w f f f w Sprechweise: A gilt genau dann, wenn B gilt, A ist hinreichend und notwendig für B. 5 1 Grundlagen Satz 1.14. Die Aussagen A,B und (A ) B) ^ (B ) A) sind gleichbedeutend. Beweis. Es gilt die Wahrheitstafel A B A,B A)B B)A (A ) B) ^ (B ) A) w w w w w w w f f f w f f w f w f f f f w w w w Da die Wahrheitswerte von A , B und (A ) B) ^ (B ) A) jeweils paarweise gleich sind, folgt die Behauptung. Beispiel 1.15. Es sei n eine ganze Zahl. A: n 2>1 B: n>3 Für alle ganzen Zahlen n ist die Äquivalenz A , B wahr, denn: n 2>1 ) n>3 und n>3 ) n 2 > 1. Seien C, D zwei weitere Aussagen. C: n>0 D: n2 > 0 Für n = 1 ist die Äquivalenz C , D falsch (C falsch, D wahr). Für alle ganzen Zahlen n gilt zumindest die Implikation C ) D. 6  1.3 Beweisarten Korollar 1.16 (Eigenschaften von Junktoren). Seien A, B, C Aussagen. Für die eingeführten logischen Operatoren gelten die folgenden Eigenschaften: a) Reflexivität: A)A b) Transitivität: (A ) B) ^ (B ) C) ) (A ) C) c) Kommutativität: (A ^ B) , (B ^ A) (A _ B) , (B _ A) d) Assoziativität: ((A ^ B) ^ C) , (A ^ (B ^ C)) ((A _ B) _ C) , (A _ (B _ C)) e) De-morgansche Regeln: ¬(A ^ B) , (¬A _ ¬B) ¬(A _ B) , (¬A ^ ¬B) 1.3 Beweisarten Mathematische Sätze sind in Form wahrer Implikationen formuliert. Beweise liefern die Begründung, warum diese Implikationen wahr sind. Die Durchführung eines Beweises, also die Verifikation der Implikationen, kann dabei auf verschiedene Weisen geschehen, wie der folgende Satz 1.17 besagt. Satz 1.17 (Beweismethoden für die Implikation A ) B). Die folgenden Be- weismethoden sind äquivalent zueinander: direkter Beweis (A ) B) Beweis durch Kontraposition (¬B ) ¬A) Widerspruchsbeweis ¬(A ^ ¬B) Beweis. Die Beweismethoden sind äquivalent zueinander, da in der folgenden Wahrheits- tafel die Wahrheitswerte jeweils paarweise gleich sind: 7 1 Grundlagen A B ¬A ¬B A)B ¬B ) ¬A ¬(A ^ ¬B) w w f f w w w w f f w f f f f w w f w w w f f w w w w w Beispiel 1.18. Seien m, n natürliche Zahlen und A, B Aussagen, die wie folgt definiert sind: A: m2 < n2 B: m < n Wir werden mithilfe der verschiedenen Beweismethoden zeigen, dass die Implikation A ) B für alle natürlichen Zahlen m, n wahr ist. a) Direkter Beweis: m2 A : m2 < n2 ) 0 < n2 m2 ) 0 < (n m) (n + m) | {z } >0 +m ) 0 3) , 9 natürliche Zahl n : n  3 (w) Spezielle Beweistechniken für Existenz- und Allaussagen: Beispiel: Angabe eines Beispiels, um zu zeigen, dass eine Existenzaussage wahr ist. Gegenbeispiel: Angabe eines Gegenbeispiels, um zu zeigen, dass eine Allaussage falsch ist. Beispiel 1.26. Angabe eines Beispiels, um Existenzaussage zu beweisen: Die Aussage 9 natürliche Zahl n : n > 5 ist wahr, denn für n = 7 ist die Aussage n > 5 wahr. Angabe eines Gegenbeispiels, um Allaussage zu widerlegen: Die Aussage 8 natürlichen Zahlen n : n  5 ist falsch, denn für n = 7 ist die Aussage n  5 falsch. 10  1.5 Naive Mengenlehre 1.5 Naive Mengenlehre Definition 1.27 (Mengenbegri↵ nach Cantor). Eine Menge ist eine Zusammen- fassung von bestimmten, wohlunterschiedenen Objekten unserer Anschauung oder unseres Denkens (die Elemente genannt werden) zu einem Ganzen. Wir schreiben: x 2 M, falls x ein Element der Menge M ist. x2/ M, falls x kein Element der Menge M ist. Zwei Mengen heißen gleich, wenn sie die gleichen Elemente besitzen. Die Angabe von Mengen geschieht durch: Auflistung der Elemente in geschweiften Klammern: M = {...} Beschreibung der Elemente durch Eigenschaften: M = {x : E(x)} (Die Menge besteht aus allen Elemente x, für die die Aussage E(x) wahr ist) Beispiel 1.28. M = {2, 4, 6, 8}, N = {n : n ist eine natürliche Zahl, n ist gerade und 1 < n < 10}. Es gilt M = N. Bemerkung 1.29. Bei der Definition von Mengen kommt es nicht auf die Reihenfolge der angegebenen Elemente an. Es gilt {1, 2, 3} = {3, 1, 2}. Außerdem sind Elemente wohlunterschieden, d.h. {1, 2, 2} = {1, 2}. Oft wird anstatt des Doppelpunkts auch ein senkrechter Strich verwendet: M = {x | E(x)}. Definition 1.30 (leere Menge). Die leere Menge ; enthält keine Elemente. Wir schreiben auch ; = {}. 11 1 Grundlagen Beispiel 1.31. {n : n ist natürliche Zahl und n < 5} = ; Definition 1.32 (Kardinalität). Eine endliche Menge ist eine Liste mit endlich vielen Elementen. Eine unendliche Menge ist eine Menge, die nicht endlich viele Elemente besitzt. Die Kardinalität |M | einer Menge M beschreibt die Anzahl der Elemente von M und ist definiert als ( n, falls M eine endliche Menge ist und n Elemente enthält, |M | = 1, falls M nicht endlich ist. Beispiel 1.33. Bei endlichen Mengen lässt sich die Kardinalität durch Zählen der Ele- mente angeben |{7, 11, 16}| = 3. Die einfachste unendliche Menge ist die Menge der natürlichen Zahlen N = {0, 1, 2, 3,...} mit Kardinalität |N| = 1. Definition 1.34 (Zahlbereiche). N = {0, 1, 2, 3,...} (Menge der natürlichen Zahlen) Z = {0, 1, 1, 2, 2,...} (Menge der ganzen Zahlen) nm o Q= : m, n 2 Z, n 6= 0 (Menge der rationalen Zahlen) n R (Menge der reellen Zahlen) Bemerkung 1.35. Die Definition von R ist nicht mehr so einfach möglich wie es bei den ganzen oder den rationalen Zahlen ist. Für die formale Einführung verweisen wir an dieser Stelle auf die Analysis. 12  1.5 Naive Mengenlehre Definition 1.36 (Teilmenge). Eine Menge A heißt Teilmenge einer Menge B (A ⇢ B), genau dann wenn Für alle x 2 A gilt: x 2 B (d.h. jedes Element von A ist auch ein Element von B). A heißt echte Teilmenge von B (A ( B), genau dann wenn A⇢B und A 6= B. A B A⇢B Bemerkung 1.37. Die Wahl der Symbole ⇢ und ( für ”Teilmenge” und ”echte Teil- menge” ist nicht einheitlich in der Literatur. Andere Autoren benutzen z.B. auch die Notation ✓ und ⇢. Bemerkung 1.38. Die leere Menge ; ist Teilmenge jeder Menge. Beispiel 1.39. ;⇢N⇢Z⇢Q⇢R (gilt auch mit () Korollar 1.40. O↵enbar gilt für Mengen: A=B , A⇢B und B⇢A Um also zu zeigen, dass A = B ist, zeigt man: Jedes Element aus A liegt in B, und jedes Element aus B liegt in A. 13 1 Grundlagen Definition 1.41. Seien A, B Mengen. Der Durchschnitt A \ B von A und B ist definiert als A \ B = {x : x 2 A und x 2 B}. Die Vereinigung A [ B von A und B ist definiert als A [ B = {x : x 2 A oder x 2 B}. Die Di↵erenz A \ B von A und B ist definiert als A \ B = {x : x 2 A und x 2 / B}. Wenn B ⇢ A, dann nennt man A \ B auch das Komplement von B in A. A B A B Durchschnitt A \ B Vereinigung A [ B A B A B Di↵erenz A \ B Komplement A \ B Beispiel 1.42. Seien A = {2, 3, 5, 7} und B = {3, 4, 6, 7}. Dann ist A [ B = {2, 3, 4, 5, 6, 7}, A \ B = {3, 7}, A \ B = {2, 5}. Satz 1.43. Seien A, B, C Mengen. Dann gelten die beiden Distributivgesetze für Mengenoperationen A \ (B [ C) = (A \ B) [ (A \ C), A [ (B \ C) = (A [ B) \ (A [ C). Beweis. Wir beschränken uns auf den Beweis des ersten Distributivgesetzes. Es ist zu zeigen, dass A \ (B [ C) ⇢ (A \ B) [ (A \ C) und (A \ B) [ (A \ C) ⇢ A \ (B [ C). 14  1.5 Naive Mengenlehre a) ()) Sei x 2 A \ (B [ C). Dann ist x 2 A und x 2 B [ C. Eine Fallunterscheidung liefert: 1. Fall: x 2 A und x 2 B ) x 2 A \ B ) x 2 (A \ B) [ (A \ C). 2. Fall: x 2 A und x 2 C ) x 2 A \ C ) x 2 (A \ B) [ (A \ C). Damit ist gezeigt: x 2 A \ (B [ C) ) x 2 (A \ B) [ (A \ C). b) (() Sei x 2 (A \ B) [ (A \ C). ) x 2 A \ B oder x 2 A \ C ) (x 2 A und x 2 B) oder (x 2 A und x 2 C) ) x 2 A und x 2 B [ C ) x 2 A \ (B [ C). Satz 1.44. Seien A, B Mengen. Dann gilt A[B =B , A⇢B Beweis. Wir zeigen ) und (. a) ()) Es gelte A [ B = B. Zu zeigen ist A ⇢ B (d.h. x 2 A ) x 2 B). Sei x 2 A ) x 2 A oder x 2 B ) x 2 A [ B = B. b) (() Es gelte A ⇢ B. Zu zeigen ist A [ B = B (d.h. A [ B ⇢ B und B ⇢ A [ B). A⇢B 1) Sei x 2 A [ B ) x 2 A oder x 2 B ) x 2 B. 2) B ⇢ A [ B klar. Definition 1.45 (Tupel). Ein n-Tupel (x1 ,..., xn ) ist eine geordnete Liste aus n mathematischen Objekten x1 ,..., xn. Zwei n-Tupel (x1 ,..., xn ) und (x01 ,..., x0n ) sind per Definition genau dann gleich, wenn ihre Elemente paarweise gleich sind, d.h. (x1 ,..., xn ) = (x01 ,..., x0n ) , x1 = x01 ,... , xn = x0n. 15 1 Grundlagen Definition 1.46 (Produkt). Seien A, B Mengen. Dann heißt A ⇥ B = {(a, b) : a 2 A, b 2 B} das kartesische Produkt von A und B. Für das Produkt von gleichen Mengen schreibt man auch A2 = A ⇥ A und allgemeiner An = A ⇥ · · · ⇥ A = {(a1 ,... , an ) : ai 2 A, i 2 {1,... , n}} | {z } n mal für das Produkt von n 2 N gleichen Mengen A. Beispiel 1.47. {1, 2} ⇥ {1, 3, 4} = {(1, 1), (1, 3), (1, 4), (2, 1), (2, 3), (2, 4)}, R2 = R ⇥ R = {(x, y) : x, y 2 R}. Definition 1.48 (Potenzmenge). Sei A eine Menge. Die Potenzmenge von A ist definiert durch P(A) = {M : M ⇢ A}. (Die Potenzmenge von A ist also die Menge aller Teilmengen von A.) Beispiel 1.49. P({1, 2, 3}) = {;, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}} 1.6 Vollständige Induktion Als nächstes behandeln wir das Prinzip der vollständigen Induktion, das auf dem Induktionsaxiom basiert und ein wichtiges Hilfsmittel für Beweise ist.2 Es wird als sogenanntes Axiom formuliert, also ein Satz, den wir ohne Beweis als Grundsatz vor- aussetzen. Axiom 1.50 (Induktionsaxiom). Sei M ⇢ N eine Teilmenge mit den folgenden Eigenschaften: a) 0 2 M. b) n 2 M ) n + 1 2 M. Dann ist M = N. 2 Das Prinzip der vollständigen Induktion ist Teil der sogenannten Peano-Axiome, wie man z.B. nachlesen kann in H.D. Ebbinghaus et al: Zahlen. Springer 1983. 16  1.7 Relationen Satz 1.51 (Prinzip der vollständigen Induktion). Für jedes n 2 N sei eine Aussage A(n) gegeben. Die Aussagen A(n) gelten für alle n 2 N, wenn man folgendes zeigen kann: a) (Induktionsanfang) A(0) ist wahr. b) (Induktionsschritt) Für jedes n gilt: A(n) ) A(n + 1). Beweis. Setze M = {n 2 N : A(n) ist wahr}. Wegen des Induktionsanfanges ist 0 2 M , wegen des Induktionsschrittes gilt: n 2 M ) n + 1 2 M. Aus dem Induktionsaxiom folgt also, dass M = N ist, d.h. A(n) ist wahr für alle n 2 N. Beispiel 1.52. Wir zeigen mit Hilfe des Prinzips der vollständigen Induktion, dass die Aussage n(n + 1) A(n) : 1 +... + n = 2 für alle n 2 N gilt. Induktionsanfang: Die Aussage A(1) ist wahr, denn 1 = 1(1+1) 2. Induktionsschritt: Wir zeigen, dass A(n) ) A(n + 1) wahr ist. Es gelte A(n), d.h. wir nehmen an, dass 1+...+n = n(n+1) 2 wahr ist. Dann betrachten wir A(n + 1): n(n + 1) n(n + 1) + 2(n + 1) (n + 1)(n + 2) 1 +... + n + (n + 1) = + (n + 1) = = , 2 2 2 d.h. A(n + 1) ist wahr. Aus dem Prinzip der vollständigen Induktion (Satz 1.51) folgt also, dass die Aussage A(n) für alle n 2 N gilt. Bemerkung 1.53. Die Definition der natürlichen Zahlen ist nicht einheitlich in der Literatur. Sie werden sowohl mit 0 als auch mit 1 beginnend definiert. Für das Indukti- onsaxiom ist das aber unerheblich, da es nur wichtig ist ein erstes Element zu haben. 1.7 Relationen Definition 1.54 (Relation). Sei M eine Menge und a, b 2 M. Eine Relation ⇠ auf M ist eine Teilmenge R ⇢ M ⇥ M. Wir schreiben a ⇠ b , (a, b) 2 R. In Worten: a steht in Relation zu b. Für Elemente, die nicht in Relation stehen, definieren wir das Zeichen ⌧ durch a ⌧ b , (a, b) 2 / R. 17 1 Grundlagen Bemerkung 1.55. Eine Relation auf M stellt eine Beziehung zwischen den Elementen von M her. Für alle a, b 2 M gilt entweder a ⇠ b oder a ⌧ b, denn entweder ist (a, b) 2 R oder (a, b) 2 / R. Beispiel 1.56. Sei M = {1, 2, 3}. Durch R = {(1, 1), (1, 2), (3, 3)} ⇢ M ⇥ M ist eine Relation auf M gegeben. Es gilt dann 1 ⇠ 1, 1 ⇠ 2, 3 ⇠ 3. Aber z.B. auch: 1 ⌧ 3, 2 ⌧ 1, 2 ⌧ 2. Definition 1.57. Sei M eine Menge. Eine Relation ⇠ auf M heißt reflexiv , Für alle a 2 M gilt: a ⇠ a. symmetrisch , Für alle a, b 2 M gilt: a ⇠ b ) b ⇠ a. antisymmetrisch , Für alle a, b 2 M gilt: a ⇠ b und b ⇠ a ) a = b. transitiv , Für alle a, b, c 2 M gilt: a ⇠ b und b ⇠ c ) a ⇠ c. total , Für alle a, b 2 M gilt: a ⇠ b oder b ⇠ a. Beispiel 1.58. Sei M die Menge der Studierenden der IMI 1-Volesung. a) Für a, b 2 M sei a ⇠ b definiert durch: a hat denselben Vornamen wie b. Dann ist ⇠ reflexiv, symmetrisch, nicht antisymmetrisch, transitiv, nicht total. b) Für a, b 2 M sei a ⇠ b definiert durch: Die Matrikelnummer von a ist  als die Matrikelnummer von b. Dann ist ⇠ reflexiv, nicht symmetrisch, antisymmetrisch, transitiv, total. c) Für a, b 2 M sei a ⇠ b definiert durch: a sitzt auf dem Platz rechts von b. Dann ist ⇠ nicht reflexiv, nicht symmetrisch, nicht antisymmetrisch, transitiv, nicht total. Definition 1.59. Sei M eine Menge. Eine Relation ⇠ auf M heißt Halbordnung , ⇠ ist reflexiv, antisymmetrisch und transitiv. Totalordnung , ⇠ ist eine Halbordnung und total. In diesen Fällen sagt man auch: Das Tupel (M, ⇠) ist eine halbgeordnete bzw. totalgeordnete Menge. 18  1.7 Relationen Beispiel 1.60.  auf N ist eine Totalordnung. Sei M = P({1, 2, 3}). ⇢ ist auf M eine Halbordnung, aber keine Totalordnung (es ist z.B. weder {1} ⇢ {3} noch {3} ⇢ {1}) Bemerkung 1.61. Wegen der Analogie zu  auf N bezeichnen wir Halbordnungen in der Regel mit . Definition 1.62. Sei (M, ) eine halbgeordnete Menge und a 2 M. a heißt größtes Element von M , Für alle x 2 M gilt: x  a. a heißt kleinstes Element von M , Für alle x 2 M gilt: a  x. Satz 1.63. Sei (M, ) eine halbgeordnete Menge. Dann gilt: Existiert in M ein größtes (bzw. kleinstes) Element, so ist dieses eindeutig bestimmt. Beweis. Es seien a, b 2 M größte Elemente von M. Dann gilt: x  a für alle x 2 M , also auch b  a. Außerdem gilt: x  b für alle x 2 M , also auch a  b. Aus der Antisymmetrie folgt also, dass a = b sein muss. Der Beweis für die Eindeutigkeit des kleinsten Elements folgt analog. Bemerkung 1.64. Satz 1.63 sagt nichts darüber aus, ob ein größtes (oder kleinstes) Element in M überhaupt existiert. Beispiel 1.65. a) In (N, ) ist 0 das kleinste Element, ein größtes gibt es nicht. b) ({{1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}}, ⇢) ist eine halbgeordnete Menge ohne größtes Ele- ment und ohne kleinstes Element. Definition 1.66. Sei (M, ) eine halbgeordnete Menge. Ein Element a 2 M heißt maximales Element von M , Für alle X 2 M gilt: a  x ) a = x. minimales Element von M , Für alle X 2 M gilt: x  a ) a = x. Notation: max M bezeichnet das maximale Element von M , min M bezeichnet das minimale Element von M. Beispiel 1.67. Betrachte die halbgeordnete Menge ({{1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}}, ⇢). Dann gilt: 19 1 Grundlagen {1, 2}, {1, 3}, {2, 3} sind maximale Elemente und {1}, {2}, {3} sind minimale Elemente. Satz 1.68. Sei (M, ) eine halbgeordnete Menge und a 2 M. Dann gilt: Ist a ein größtes (bzw. kleinstes) Element von M , dann ist a ein maximales (bzw. minimales) Element von M. Beweis. Sei a ein größtes Element von M. Wir müssen zeigen, dass für alle x 2 M gilt: a  x ) a = x. Dafür wählen wir x 2 M mit a  x. Da a ein größtes Element von M ist, gilt auch x  a. Aus der Antisymmetrie folgt also a = x. Da die Wahl von x beliebig ist, folgt die Aussage für alle x 2 M. Der Beweis für das kleinste Element folgt analog. Definition 1.69 (Äquivalenzrelation). Sei M eine Menge. Eine Relation ⇠ auf M heißt Äquivalenzrelation , ⇠ ist reflexiv, symmetrisch und transitiv. In diesem Fall sagen wir für a ⇠ b auch: a ist äquivalent zu b. Definition 1.70 (Äquivalenzklasse). Sei M eine Menge und ⇠ eine Äquivalenzrelation auf M. Die Äquivalenzklasse [a] von a 2 M ist definiert durch [a] = {b 2 M : b ⇠ a}. Elemente aus [a] nennt man auch Vertreter oder Repräsentanten von [a]. Beispiel 1.71. Sei M die Menge aller Personen, die in Deutschland leben. Wir definieren für a, b 2 M : a ⇠ b , a und b sind im selben Jahr geboren. ⇠ ist eine Äquivalenzrelation. Jérôme Boateng wurde 1988 geboren. [Jérôme Boateng] = {p : p ist im selben Jahr geboren wie Jérôme Boateng} = {p : p wurde 1988 geboren} Weitere Vertreter von [Jérôme Boateng] sind z.B. Mesut Özil, oder Mats Hummels. Also ist [Jérôme Boateng] = [Mesut Özil] = [Mats Hummels] Man sieht an diesem Beispiel, dass die Menge M komplett in verschiedene Äquivalenz- klassen zerfällt: 20  1.7 Relationen geb. 1905... geb. 1988... geb. 2014 Jede Person ist in genau einer Äquivalenzklasse enthalten. Je zwei Äquivalenzklassen sind entweder gleich oder disjunkt (haben leeren Durchschnitt). Satz 1.72. Sei M eine Menge und ⇠ eine Äquivalenzrelation auf M. Dann gilt: a) Jedes Element von M liegt in genau einer Äquivalenzklasse. b) Je zwei Äquivalenzklassen sind entweder gleich oder disjunkt. Man sagt auch: Die Äquivalenzklassen bzgl. ⇠ bilden eine Partition oder Zerle- gung von M. Beweis. a) Sei a 2 M. Zu zeigen: Es gibt genau eine Äquivalenzklasse, in der a liegt. 1) (Existenz) Zunächst einmal gibt es eine Äquivalenzklasse, in der a liegt, denn: Es gilt, dass a 2 [a], da a ⇠ a. 2) (Eindeutigkeit) Ist a 2 [b] und a 2 [c], dann ist [b] = [c] (d.h. a kann in höchstens einer Äquivalenzklasse liegen), denn: Seien b, c 2 M mit a 2 [b] und a 2 [c], dann folgt aus der Definition der Äquivalenz- klassen, dass a ⇠ b und a ⇠ c ) b ⇠ a und a ⇠ c, wobei wir im letzten Schritt die Symmetrie von ⇠ ausgenutzt haben. Aus der Transitivität erhalten wir schließlich b ⇠ c. Es bleibt zu zeigen, dass [b] = [c]. Dazu zeigen wir, dass [b] ⇢ [c] und [c] ⇢ [b]. ([b] ⇢ [c]): Sei x 2 [b] ) x ⇠ b. Da b ⇠ c und wegen der Transitivität folgt x ⇠ c und daher x 2 [c]. ([c] ⇢ [b]): Sei x 2 [c] ) x ⇠ c. Da c ⇠ b und wegen der Transitivität folgt x ⇠ b und daher x 2 [b]. b) Sind b, c 2 M mit [b] \ [c] 6= ;, dann existiert ein a 2 [b] \ [c], und es folgt wie in Beweisteil 2): [b] = [c]. Für b, c 2 M gitl also entweder [b] \ [c] = ; oder [b] = [c]. 21 1 Grundlagen Definition 1.73. Sei M eine Menge und ⇠ eine Äquivalenzrelation auf M. Dann definieren wir die Faktormenge M/⇠ von M nach ⇠ (auch Quotientenmenge genannt) als die Menge der Äquivalenzklassen, d.h. M/⇠ = {[a] : a 2 M }. Beispiel 1.74. Sei M = {1, 2, 3, 1, 2, 3}. Sei weiter der Betrag |x| einer Zahl x definiert als ( x, falls x 0, |x| = x, sonst. Für a, b 2 M setzen wir a ⇠ b , |a| = |b|. Dies ist eine Äquivalenzrelation auf M. Es ist = {1, 1}, = {2, 2}, = {3, 3}. Somit gilt M/⇠ = {, , } = {{1, 1}, {2, 2}, {3, 3}} Bemerkung 1.75. Der Übergang zu Äquivalenzklassen soll (für ein jeweils gegebenes Problem) irrelevante Informationen abstreifen. 1.8 Abbildungen Zur Beschreibung von Beziehungen zwischen Mengen verwendet man Abbildungen. Definition 1.76 (Abbildung). Seien X, Y Mengen. Eine Abbildung f von X nach Y ist eine Vorschrift, die jedem x 2 X genau ein Element aus Y zuordnet, welches man mit f (x) bezeichnet. Notation: f : X ! Y, x 7! f (x) Zwei Abbildungen f : X ! Y und g : X ! Y sind gleich, wenn f (x) = g(x) für alle x 2 X gilt. X heißt die Definitionsmenge von f , Y heißt die Zielmenge von f. Beispiel 1.77. a) f : R ! R, x 7! x2 22  1.8 Abbildungen b) f : R ! R2 , x 7! (x, x + 1) p c) f : R2 ! R, (x, y) 7! x2 + y 2 d) Sei X eine Menge. Die Abbildung idX : X ! X, x 7! x heißt die Identität (oder auch identische Abbildung) auf X. e) Seien I, X Mengen. Eine über I indizierte Familie von Elementen von X ist eine Abbildung x : I ! X, i 7! x(i) = xi Wir schreiben für die Familie auch kurz (xi )i2I und nennen I die Indexmenge der Familie. f ) Ein Spezialfall von e) sind Folgen: Sei I = N und X = R. (xi )i2N nennt man eine Folge reeller Zahlen. Bemerkung 1.78. Über den Begri↵ der Familie lassen sich z.B. die Konstruktionen Vereinigung, Durchschnitt und Produkt aus Abschnitt 1.5 verallgemeinern. Insbe- sondere können diese Mengenoperationen nun auch für unendlich viele Mengen definiert werden. Sei (Mi )i2I eine Folge von Mengen, dann ist [ Mi = {x : Es gibt ein i 2 I mit x 2 Mi } (Vereinigung), i2I \ Mi = {x : Für alle i 2 I ist x 2 Mi } (Durchschnitt), i2I Y Mi = {(xi )i2I : xi 2 Mi für alle i 2 I} (Produkt). i2I Definition 1.79 (Graph). Für eine Abbildung f : X ! Y ist der Graph von f definiert als die Menge f = {(x, f (x)) 2 X ⇥ Y }. Bemerkung 1.80. Mithilfe des Graphen von f lassen sich Abbildungen oft durch eine Skizze veranschaulichen. Beispiel 1.81. 23 1 Grundlagen y y 2 (x, f (x)) 4 (x, f (x)) 1 3 x 2 2 1 1 2 1 1 2 x 3 2 1 0 1 2 3 f (x) = x f (x) = x2 Definition 1.82. Seien X, Y Mengen und f : X ! Y eine Abbildung. Sind x 2 X, y 2 Y mit y = f (x), dann nennen wir y das Bild von x unter f , und wir nennen x ein Urbild von y unter f. Bemerkung 1.83. Das Bild einer Abbildung ist nach Definition eindeutig bestimmt. Urbilder von Abbildungen sind im Allgemeinen jedoch nicht eindeutig bestimmt, d.h. Urbilder sind keine Abbildungen im Sinne der Definition. Außerdem besitzt im Allge- meinen auch nicht jedes Element aus der Zielmenge ein Urbild. Beispiel 1.84. Betrachte z.B. f : R ! R, x 7! x2. Dann ist 4 = f (2) = f ( 2), d.h. 2 und 2 sind Urbilder von 4 unter f. Weiter gilt, dass das Element 5 kein Urbild unter f hat, denn es existiert kein x 2 R mit x2 = 5. Definition 1.85. Seien X, Y Mengen, f : X ! Y eine Abbildung und A ⇢ X, B ⇢ Y Teilmengen. Dann ist die Bildmenge von A unter f definiert als f (A) = {f (a) : a 2 A}, und die Urbildmenge von B unter f ist definiert durch 1 f (B) = {x 2 A : f (x) 2 B}. Es gilt: f (A) ⇢ Y und f 1 (B) ⇢ X. 24  1.8 Abbildungen Beispiel 1.86. Sei f : R ! R, x 7! x2. Dann gilt: f ({1, 2, 3}) = {1, 4, 9}, 1 f ({4}) = {2, 2}, 1 f ({ 5}) = ;, 1 f ({4, 5}) = {2, 2}, f (R) = x2 : x 2 R = {x 2 R : x 0} = R 0. Definition 1.87 (Restriktion). Seien X, Y Mengen, f : X ! Y eine Abbil- dung und M ⇢ X eine Teilmenge. Dann ist die Restriktion f |M (oder Ein- schränkung) von f auf M definiert durch f |M : M ! Y, x 7! f (x). Bemerkung 1.88. Die Restriktion f |M unterscheidet sich von f nur durch den einge- schränkten Definitionsbereich. Definition 1.89 (Komposition). Seien X, Y, Z Mengen und f : X ! Y , g : Y ! Z Abbildungen. Dann ist die Komposition g f (oder auch Ver- knüpfung oder Hintereinanderausführung) von f und g definiert durch g f : X ! Z, x 7! (g f )(x) = g(f (x)). Beispiel 1.90. Sei f : R ! R, x 7! x2 , und sei g : R ! R, x 7! x + 1. Dann gilt g f : R ! R, x 7! g(f (x)) = g(x2 ) = x2 + 1. Satz 1.91. Seien X, Y, Z, W Mengen und f : X ! Y , g : Y ! Z, h : Z ! W Abbildungen. Dann gilt: h (g f ) = (h g) f, d.h. die Verknüpfung von Abbildungen ist assoziativ. Beweis. Ist x 2 X so gilt: (h (g f ))(x) = h((g f )(x)) = h(g(f (x))) = (h g)(f (x)) = ((h g) f )(x). 25 1 Grundlagen Bemerkung 1.92. Die Komposition von Abbildungen ist im Allgemeinen nicht kommu- tativ, d.h. für Abbildungen f : X ! Y , g : Y ! X gilt im Allgemeinen, dass g f 6= f g. Besonders wichtigen Eigenschaften von Abbildungen geben wir eigene Namen. Definition 1.93. Seien X, Y Mengen. Eine Abbildung f : X ! Y heißt injektiv , Für alle x1 , x2 2 X gilt: f (x1 ) = f (x2 ) ) x1 = x2 , Für alle x1 , x2 2 X gilt: x1 6= x2 ) f (x1 ) 6= f (x2 ) surjektiv , Für jedes y 2 Y existiert ein x 2 X mit f (x) = y , f (X) = Y bijektiv , f ist injektiv und surjektiv Beispiel 1.94. a) Die Abbildung f : R ! R, x 7! x2 ist nicht injektiv, denn f (2) = f ( 2), aber 2 6= 2. nicht surjektiv, denn es existiert kein x 2 R mit f (x) = 1. nicht bijektiv b) Die Abbildung f : R 0 ! R, x 7! x2 ist injektiv, denn für x1 , x2 2 R 0 gilt: f (x1 ) = f (x2 ) ) x21 = x22 ) x1 = x2. Die letzte Implikation gilt, da x1 , x2 0. nicht surjektiv, denn es existiert kein x 2 R 0 mit f (x) = 1. nicht bijektiv c) Die Abbildung f : R 0 ! R 0 , x 7! x2 ist injektiv (wie bei b)) p p surjektiv, denn für x 2 R 0 ist f ( x) = ( x)2 = x. bijektiv Für Abbildungen zwischen beliebigen Mengen werden wir nachfolgend Eigenschaften herleiten, um die Begri↵e Injektivität, Surjektivität und Bijektivität zu charakterisieren und um eine sinnvolle Grundlage für die Definition von Umkehrabbildungen vorzuberei- ten. Im Spezialfall von Abbildungen zwischen endlichen Mengen ist die Situation noch leichter: Hier sind die Begri↵e injektiv, surjektiv und bijektiv austauchbar wie wir in Satz 1.96 durch geschicktes Abzählen der Mengen sehen werden. Um dies zeigen zu können, benötigen wir zunächst die folgende Definition. 26  1.8 Abbildungen Definition 1.95. Zwei Mengen X und Y heißen gleichmächtig genau dann, wenn es eine bi- jektive Abbildung f : X ! Y gibt. Eine Menge X heißt abzählbar unendlich genau dann, wenn X und N gleichmächtig sind. Satz 1.96 (Charakterisierung bijektiver Abbildungen zwischen endlichen Mengen). Seien M, N endliche Mengen mit |M | = |N | und f : M ! N. Dann sind folgende Aussagen äquivalent: a) f ist injektiv. b) f ist surjektiv. c) f ist bijektiv. Beweis. Anstatt zu zeigen, dass a), b) und b) , c), benutzen wir als Beweismethode die Implikationskette: a)) b)) c)) a). a) ) b): Sei f injektiv. Dann gilt, dass |f (M )| = |M | = |N |. Da f (M ) ⇢ N folgt f (M ) = N , also ist f surjektiv. b) ) c): Sei f surjektiv, d.h. f (M ) = N. (Der Beweis erfolgt als Widerspruchsbeweis) Angenommen f ist nicht bijektiv ) f ist nicht injektiv ) Es existieren m1 , m2 2 M mit f (m1 ) = f (m2 ) ) |f (M )| < |M | = |N | Dies ist im Widerspruch zu f (M ) = N. Also folgt, dass f bijektiv ist. c) ) a): trivial. Satz 1.97 (Charakterisierung injektiver und surjektiver Abbildungen). Seien X, Y Mengen und f : X ! Y eine Abbildung. Dann gilt: a) f ist injektiv , Es existiert g : Y ! X mit g f = idX. b) f ist surjektiv , Es existiert g : Y ! X mit f g = idY. Beweis. 3 3 Der Beweis von Satz 1.97 b) benutzt das sogenannte Auswahlaxiom: Ist I eine Indexmenge S und (Mi )i2I eine Familie von nichtleeren Mengen, dann gibt es eine Abbildung : I ! i2I Mi mit (i) 2 Mi für alle i 2 I. 27 1 Grundlagen a) ()) Sei f injektiv. Dann gibt es zu jedem y 2 f (X) genau ein x 2 X mit f (x) = y, und wir definieren g(y) = x. Ist x0 2 X beliebig, so definieren wir weiter g(y) = x0 für alle y 2 Y \ f (X). Das ergibt eine Abbildung g : Y ! X mit g f = idX. (() Sei g : Y ! X gegeben mit g f = idX. Ist f (x1 ) = f (x2 ) für x1 , x2 2 X, so gilt x1 = idX (x1 ) = g(f (x1 )) = g(f (x2 )) = idX (x2 ) = x2. Also ist f injektiv. b) ()) Sei f surjektiv. Zu jedem y 2 Y wählen wir ein festes x 2 X mit f (x) = y und setzen g(y) = x. Die so erklärte Abbildung g : Y ! X hat die Eigenschaft f g = idY. (() Sei g : Y ! X gegeben mit f g = idY. Für alle y 2 Y ist y = idY (y) = f (g(y)), also Bild von g(y). Damit ist f surjektiv. Satz 1.98. Seien X, Y, Z Mengen und f : X ! Y , g : Y ! Z Abbildungen. Dann gilt: Sind f und g injektiv (bzw. surjektiv, bzw. bijektiv), dann ist auch g f injektiv (bzw. surjektiv, bzw. bijektiv). Beweis. Beweis als Übung. Satz 1.99 (Charakterisierung bijektiver Abbildungen). Seien X, Y Mengen und f : X ! Y eine Abbildung. Dann sind folgende Aussagen äquivalent: a) f ist bijektiv. b) Zu jedem y 2 Y gibt es genau ein x 2 X mit f (x) = y. c) Es gibt genau eine Abbildung g : Y ! X mit g f = idX und f g = idY. Beweis. Anstatt zu zeigen, dass a), b) und b) , c), benutzen wir als Beweismethode die Implikationskette: a)) b)) c)) a). a)) b): Sei f bijektiv: zu zeigen: Ist y 2 Y , dann existiert genau ein x 2 X mit f (x) = y. Existenz: folgt aus der Surjektivität von f Eindeutigkeit: Seien x1 , x2 2 X mit f (x1 ) = y und f (x2 ) = y. Dann folgt aus der Injektivität von f f (x1 ) = f (x2 ) ) x1 = x2. b)) c): Zu jedem y 2 Y existiere genau ein x 2 X mit f (x) = y. zu zeigen: Es existiert genau eine Abbildung g : Y ! X mit g f = idX und f g = idY. 28  1.8 Abbildungen Existenz: Wir definieren g : Y ! X, y 7! x mit f (x) = y (x ist das nach Voraussetzung eindeutig bestimmte Element mit f (x) = y). Dann gilt für x 2 X (g f )(x) = g(f (x)) = g(y) = x, d.h. g f = idX. Für y 2 Y gilt weiter (f g)(y) = f (g(y)) = g(x) = y, also f g = idY. Eindeutigkeit: Es seien g1 , g2 : Y ! X mit gi f = idX , f gi = idY für i 2 {1, 2}. Dann folgt durch Einsetzen und mithilfe der Assoziativität der Komposition (Satz 1.91), dass g1 = g1 idY = g1 (f g2 ) = (g1 f ) g2 = idX g2 = g2. c)) a): Wegen der Voraussetzung in c) existiert g : Y ! X mit g f = idX und f g = idY. Dann folgt aus zweimaliger Anwendung von Satz 1.97, dass f injektiv und f surjektiv ist. Also ist f bijektiv. Satz 1.99 motiviert die folgende Definition. Definition 1.100 (Umkehrabbildung). Seien X, Y Mengen und f : X ! Y eine bijektive Abbildung. Sei weiter g : Y ! X die eindeutig bestimmte Abbildung, so dass g f = idX und f g = idY. Dann bezeichnen wir mit g die Umkehrabbildung f 1 von f und definieren sie durch 1 1 f : Y ! X, y 7! x = f (y) mit y = f (x). (In Worten: y wird abgebildet auf das eindeutig bestimmte Element x 2 X mit f (x) = y.) Bemerkung 1.101. Beachte, dass mit f 1 zweierlei Konzepte gemeint sein können: entweder die Umkehrabbildung von f (falls existent), oder die Urbildmenge einer Teilmenge B ⇢ Y unter f. Beispiel 1.102. In Beispiel 1.94 c) haben wir gesehen, dass die Abbildung f :R 0 !R 0, x 7! x2 bijektiv ist. Die Umkehrabbildung ist gegeben durch 1 p f :R 0 !R 0, x 7! x. 29 2 Gruppen, Ringe und Körper Die Rechenoperationen der Addition in den ganzen, rationalen oder reellen Zahlen, sowie die Multiplikation der von Null verschiedenen rationalen oder reellen Zahlen unterliegen weitestgehend übereinstimmenden Rechenregeln. Es gilt z.B. (a + b) + c = a + (b + c) und (a · b) · c = a · (b · c). Weiter gibt es Zahlen, die sich neutral bei der Anwendung dieser Operationen verhalten und eine gegebene Zahl nicht verändern, 0+a=a und 1 · a = a. Und schließlich gibt es zu jeder Zahl eine Zahl, so dass wir durch die Rechenoperation das neutrale Element erhalten, 1 ( a) + a = 0 und · a = 1. a Ausgehend von diesen Beobachtungen lassen sich allgemeine Konzepte ableiten und in Form von Regeln aufschreiben. Bei dieser abstrakten Betrachtungsweise stehen die Rechengesetze im Vordergrund: Nicht womit man rechnet ist wesentlich, sondern wie man rechnet.1 Damit kommen wir nun zur Einführung der Gruppen in Abschnitt 2.1, welche die Eigen- schaften von Rechenregeln bzgl. einer Rechenoperation auf einer Menge in Abschnitt 2.1 untersucht. Abschnitte 2.2 und 2.3 beschäftigen sich dann mit der Kombination verschie- dener Rechenoperationen auf einer Menge, was uns zum Konzept der Ringe und der Körper führt. In Abschnitt 2.4 machen wir schließlich einen Exkurs in die komplexen Zahlen und die Polynome, die jeweils ein nicht-triviales Beispiel für einen Körper, sowie einen Ring liefern. 1 Diese Motivation in das Thema ”Gruppen” stammt aus [6, 2 Gruppen]. Der Rest des Abschnitts folgt weitestgehend [2, Kapitel 1.2] mit Beispielen aus [6, 2 Gruppen] 31 2 Gruppen, Ringe und Körper 2.1 Gruppen Definition 2.1. Sei G eine Menge und ⇤ eine Verknüpfung mit ⇤ : G ⇥ G ! G, (a, b) 7! ⇤(a, b) = a ⇤ b. Das Tupel (G, ⇤) heißt Gruppe, wenn folgende Axiome erfüllt sind: (G1) Für alle a, b, c 2 G gilt (a ⇤ b) ⇤ c = a ⇤ (b ⇤ c). (Assoziativgesetz) (G2) Es gibt ein e 2 G (neutrales Element oder Einselement), so dass für alle a 2 G gilt e ⇤ a = a. (G3) Zu jedem a 2 G gibt es ein a0 2 G (inverses Element von a) mit a0 ⇤ a = e. Eine Gruppe (G, ⇤) heißt abelsche Gruppe (oder kommutative Gruppe), wenn zusätzlich gilt: (G4) Für alle a, b 2 G gilt a⇤b=b⇤a (Kommutativgesetz) Beispiel 2.2. a) (Z, +), (Q, +) und (R, +) bilden jeweils eine abelsche Gruppe, die sogenannte additive Gruppe der ganzen, rationalen und reellen Zahlen. Das neutrale Element 0 heißt in diesem Fall Nullelement und das Inverse von a wird mit a bezeichnet und heißt Negatives. b) Sei M ⇤ = M \ {0} die Menge M ohne Null. (Q⇤ , ·) und (R⇤ , ·) bilden jeweils eine abelsche Gruppe, die sogennante multiplikative Gruppe der rationalen und der reellen Zahlen. Das neutrale Element ist 1 und das inverse Element von a wird mit a 1 oder a1 bezeichnet. c) (Z, ·) bildet keine Gruppe, da es z.B. keine Zahl a0 2 Z gibt, so dass a0 · 2 = 1. Bemerkung 2.3. Beim Nachweis der Gruppenaxiome muss man zunächst sicherstellen, dass die Ver- knüpfung ⇤ wohlgestellt ist, dass also die Abbildung von beliebigen Elementen aus der Menge (a, b) 2 G ⇥ G ein eindeutig bestimmtes Element der Menge a ⇤ b 2 G ergibt. Ist das Assoziativgesetz erfüllt, kann man bei mehrfachen Verknüpfungen die Klam- 32  2.1 Gruppen mern weglassen a ⇤ b ⇤ c = (a ⇤ b) ⇤ c = a ⇤ (b ⇤ c). Man schreibt die Verknüpfung a ⇤ b meistens als Multiplikation a · b, oder nur ab. Satz 2.4. Ist (G, ⇤) eine Gruppe, so gilt: a) Das neutrale Element e 2 G ist eindeutig bestimmt und es gilt für alle a 2 G a ⇤ e = a. b) Das Inverse Element a0 2 G ist für jedes a 2 G eindeutig bestimmt und es gilt für alle a 2 G a ⇤ a0 = e. c) Es gilt für alle a, b 2 G (a0 )0 = a und (a ⇤ b)0 = b0 ⇤ a0. d) Für alle a, x, y 2 G gelten die folgenden Kürzungsregeln: a⇤x=a⇤y ) x=y und x ⇤ a = y ⇤ a ) x = y. Beweis. Beweis von b): Zu a0 2 G gibt es nach (G3) ein a00 2 G mit a00 ⇤ a0 = e. Unter Beachtung von (G2) und (G1) folgt: a ⇤ a0 = e ⇤ (a ⇤ a0 ) = (a00 ⇤ a0 ) ⇤ (a ⇤ a0 ) = a00 ⇤ (a0 ⇤ (a ⇤ a0 )) = a00 ⇤ ((a0 ⇤ a) ⇤ a0 ) = a00 ⇤ (e ⇤ a0 ) = a00 ⇤ a0 = e. (2.1) Eindeutigkeit von a0 : Sei ã0 2 G ein evtl. anderes inverses Element von a mit ã0 ⇤ a = e. Dann gilt mithilfe von Gleichung (2.1): ã0 = ã0 ⇤ e = ã0 ⇤ (a ⇤ a0 ) = (ã0 ⇤ a) ⇤ a0 = e ⇤ a0 = a0. Beweis von a): Aus b) folgt: a ⇤ e = a ⇤ (a0 ⇤ a) = (a ⇤ a0 ) ⇤ a = e ⇤ a = a. (2.2) Eindeutigkeit von e: Sei ẽ 2 G ein evtl. anderes neutrales Element mit ẽ ⇤ a = a. Dann gilt insbesondere ẽ ⇤ e = e. Außerdem gilt wegen Gleichung (2.2), dass ẽ ⇤ e = ẽ. Daraus folgt also ẽ = ẽ ⇤ e = e. 33 2 Gruppen, Ringe und Körper Beweis von c): Aus a ⇤ a0 = e folgt, dass a ein inverses Element von a0 ist, also gilt a = (a0 )0. Weiter gilt: (b0 ⇤ a0 ) ⇤ (a ⇤ b) = b0 ⇤ ((a0 ⇤ a) ⇤ b) = b0 ⇤ (e ⇤ b) = b0 ⇤ b = e. Also ist b0 ⇤ a0 ein Inverses von a ⇤ b, d.h. (a ⇤ b)0 = b0 ⇤ a0. Beweis von d): Sei a ⇤ x = a ⇤ y gegeben. Dann folgt x = e ⇤ x = (a0 ⇤ a) ⇤ x = a0 ⇤ (a ⇤ x) = a0 ⇤ (a ⇤ y) = (a0 ⇤ a) ⇤ y = e ⇤ y = y. Die zweite Gleichung folgt analog mithilfe von b). Satz 2.5. Sei X eine Menge und S(X) = {f : X ! X : f ist bijektiv}. Dann ist (S(X), ) eine Gruppe, die sogenannte symmetrische Gruppe. Beweis. a) Die Komposition ist wohldefiniert, d.h. für f, g 2 S(X) ist f g 2 S(X). Das folgt aus Satz 1.98. b) Nach Satz 1.91 ist assoziativ: f (g h) = (f g) h für alle f, g, h 2 S(X). c) idX ist neutral: idX 2 S(X) und idX f = f für alle f 2 S(X). d) Existenz von Inversen: f 2 S(X) ) f bijektiv ) Es existiert eine Umkehrabbildung f 1 2 S(X) zu f , für diese gilt: f f 1 = idX , d.h. f 1 ist invers zu f bzgl.. 34  2.1 Gruppen Definition 2.6 (Permutationen). Für n 2 N sei Sn = S({1,..., n}) = {⇡ : {1,..., n} ! {1,..., n} : ⇡ ist bijektiv}. (Sn , ) heißt Permutationsgruppe. Elemente aus Sn heißen Permutationen. Wir schreiben Permutationen ⇡ 2 Sn in der Form ✓ ◆ 1 2 ··· n ⇡= ⇡(1) ⇡(2) · · · ⇡(n) und definieren die Verknüpfung ⇡ für ⇡, 2 Sn durch ✓ ◆ ✓ ◆ 1 2 ··· n 1 2 ··· n ⇡ = ⇡(1) ⇡(2) · · · ⇡(n) (1) (2) · · · (n) ✓ ◆ 1 2 ··· n =. ⇡( (1)) ⇡( (2)) · · · ⇡( (n)) Beispiel 2.7. In S3 ist ✓ ◆ ✓ ◆ ✓ ◆ 1 2 3 1 2 3 1 2 3 = 1 3 2 3 2 1 2 3 1 ✓ ◆ ✓ ◆ ✓ ◆ 1 2 3 1 2 3 1 2 3 = 3 2 1 1 3 2 3 1 2 d.h. (S3 , ) ist nicht abelsch. Als nächstes analysieren wir Beziehungen zwischen Gruppen und führen strukturer- haltende Abbildungen ein. Definition 2.8. Sei (G, ⇤) eine Gruppe mit Verknüpfung ⇤ und U ⇢ G eine nichtleere Teilmenge. U heißt Untergruppe, wenn für a, b 2 U auch a⇤b2U und a0 2 U. Satz 2.9. Sei (G, ⇤) eine Gruppe und (U, ⇤) eine Untergruppe mit U ⇢ G. Dann ist U mit der Verknüpfung ⇤ aus G wieder eine Gruppe. Man nennt die Verknüpfung ⇤ in U die von G induzierte Verknüpfung. Beweis. Die induzierte Verknüpfung ist assoziativ, weil sie aus G kommt. Da es ein a 2 U gibt, ist das Inverse a0 2 U , und damit auch a ⇤ a0 = e 2 U. 35 2 Gruppen, Ringe und Körper Beispiel 2.10. Für a, m 2 Z sei a + mZ = {a + mq : q 2 Z}. Zum Beispiel ist für m = 2 0 + 2Z die Menge der geraden Zahlen und 1 + 2Z die Menge der ungeraden Zahlen. a) Für jedes m 2 Z ist die Menge mZ = 0 + mZ eine Untergruppe von (Z, +), da mq1 + mq2 = m(q1 + q2 ) 2 mZ und mq = m( q) 2 mZ für alle q1 , q2 , q 2 Z. b) Für alle a 6= 0 und |m| < a ist a + mZ keine Untergruppe von (Z, +), da 0 2 / a + mZ. Definition 2.11. Seien (G, ⇤) und (H, ·) Gruppen mit Verknüpfungen ⇤ und ·. Eine Abbildung ':G!H heißt Homomorphismus (von Gruppen), wenn '(a ⇤ b) = '(a) · '(b) für alle a, b 2 G. Ein Homomorphismus heißt Isomorphismus, wenn er bijektiv ist. Sprechweise: G und H sind homomorph bzw. isomorph. Satz 2.12. Sei ' : G ! H ein Homomorphismus von Gruppen. Dann gilt: a) '(eG ) = eH , wenn eG 2 G und eH 2 H die neutralen Elemente bezeichnen. b) '(a0 ) = '(a)0 für alle a 2 G. c) Ist ' ein Isomorphismus, so ist auch die Umkehrabbildung ' 1 : H ! G ein Isomorphismus. Beweis. a) folgt aus der Kürzungsregel in H, da eH · '(eG ) = '(eG ) = '(eG ⇤ eG ) = '(eG ) · '(eG ); und daraus ergibt sich b), weil 1 1 eH = '(eG ) = '(a ⇤ a) = '(a ) · '(a). Zum Beweis von c) nehmen wir c, d 2 H. Ist c = '(a) und d = '(b), so ist 1 1 1 '(a ⇤ b) = '(a) · '(b) = c · d, also ' (c · d) = a ⇤ b = ' (c) ⇤ ' (d). 36  2.1 Gruppen Bemerkung 2.13. Isomorphe Gruppen sind im Prinzip nicht zu unterscheiden, da sie strukturell gleich sind und nur die Bezeichnung ihrer Elemente unterschiedlich ist.2 Beispiel 2.14. a) ' : Z ! Z, a 7! 2a ist ein Homomorphismus von (Z, +) nach (Z, +), denn '(a + b) = 2(a + b) = 2a + 2b = '(a) + '(b) für alle a, b 2 Z. ' ist aber kein Isomorphismus, da ' nicht surjektiv ist (1 2 / '(Z)). b) ' : Z ! Z, a 7! a + 1 ist kein Homomorphismus von (Z, +) nach (Z, +), denn '(2 + 6) = '(8) = 9, aber '(2) + '(6) = 3 + 7 = 10. für alle a, b 2 Z. c) exp : R ! R>0 , x 7! exp(x) = ex ist ein Isomorphismus von (R, +) nach (R>0 , ·), denn exp(a + b) = exp(a) · exp(b) für alle a, b 2 R und exp ist bijektiv (vgl. z.B. Analaysis 1-Vorlesung3 ). 2.1.1 Restklassen Im täglichen Leben verwendet man regelmäßig das Rechnen mit Restklassen wie z.B. bei der Bestimmung von Uhrzeiten die Rechnung ”modulo 24”: 22Uhr + 7h = 5Uhr. Wir wollen dies nun mathematisch präzisieren und verallgemeinern. Dazu beginnen wir mit der Einführung der Division mit Rest. Die Division a/b von einer ganzen Zahl a 2 Z durch eine ganze Zahl b 2 Z mit b 6= 0 ergibt nur dann als Ergebnis eine ganze Zahl, wenn a teilbar ist durch b. Dabei ist Teilbarbeit definiert durch: Definition 2.15 (Teilbarkeit). Seien a, b 2 Z mit b 6= 0. a heißt teilbar durch b, wenn es eine ganze Zahl q 2 Z gibt, so dass a = q · b. Man nennt b und q Teiler von a. Allgemeiner gilt die Division mit Rest: 2 Siehe zum Beispiel [8, Kapitel 3.1]. 3 Siehe z.B. Analysis 1 von Otto Forster, S. 120f. Die Bijektivität folgt aus der Monotonie von exp(x). 37 2 Gruppen, Ringe und Körper Satz 2.16 (Division mit Rest). Für zwei ganze Zahlen a, b 2 Z mit b 1 gibt es eindeutig bestimmte Zahlen q, r 2 Z, so dass a=q·b+r und 0  r < |b|. a Man nennt q den Quotient und bezeichnet ihn mit b und r den Rest bei der Division durch b. a Beweis. Wir benutzen die rationalen Zahlen und ihre Anordnung. Zu b 2 Q betrachtet man die Menge n ao X= x2Z : x ⇢ Z. b Da X nach oben beschränkt ist, gibt es ein größtes Element q 2 X. In der üblichen Notation ist a q=b c b der ganzzahlige Anteil von ab. Da q  a b < q + 1 folgt mit r=a b · q, dass a r 0 q= < 1, also 0  r < b. b b Beispiel 2.17. 13 Ist a = 13 und b = 3, so ist der gemeine Bruch“ 3 nicht ganz, als gemischter ” ” Bruch“ ist 13 1 1 =4 =4+ 3 3 3 Das kann man auch ohne Nenner in Z schreiben als 13 = 4 · 3 + 1, d.h. a = q · b + r mit 0  r < b. Ist dagegen a = 13 und b = 3, so ist es üblich 13 2 = 5+ oder 13 = 5·3+2 3 3 auszudrücken mit 0  r = 2 < b = 3. 38  2.1 Gruppen Motiviert durch die Division mit Rest, betrachten wir die folgende Relation auf Z. Satz 2.18. Seien n 2 N und a, b 2 Z. Dann ist durch a⇠b , Es existiert ein q 2 Z mit a b = qn eine Äquivalenzrelation auf Z gegeben. Anstelle von a ⇠ b schreiben wir auch a ⌘ b (mod n) und sagen: ”a ist kongruent b modulo n”. (Für n = 0 ist die Kongruenz die Gleichheit.) Beweis. ⌘ ist reflexiv: Für a 2 Z ist a ⌘ a (mod n), denn a a = 0 = 0 · n. ⌘ ist symmetrisch: Seien a, b 2 Z mit a ⌘ b (mod n) ) Es existiert ein q 2 Z mit a b = q · n 2 Z ) b a = ( q) · n ) b ⌘ a (mod n). ⌘ ist transitiv: Es seien a, b, c 2 Z mit a ⌘ b (mod n), b ⌘ c (mod n). ) Es existieren q1 , q2 2 Z mit a b = q1 · n, b c = q2 · n ) a c = (a b) + (b c) = q1 n + q2 n = (q1 + q2 )n ) a ⌘ c (mod n). Satz 2.19. Sei n 2 N. Die Äquivalenzklasse von a 2 Z ist gegeben durch a = {b 2 Z : b ⌘ a (mod n)} = a + nZ und heißt die Restklasse von a modulo n, wobei a + nZ = {a + nq : q 2 Z}. Beweis. a = {b 2 Z : b ⌘ a (mod n)} = {b 2 Z : Es existiert q 2 Z mit b a = qn} = {b 2 Z : Es existiert q 2 Z mit b = a + qn} = a + nZ 39 2 Gruppen, Ringe und Körper Satz 2.20. Die Menge aller Restklassen modulo n wird Z/nZ bezeichnet (”Z modulo nZ”). Es gilt: Z/nZ = 0, 1,... , n 1 und die Restklassen 0, 1,... , n 1 sind paarweise verschieden. Beweis. Z/nZ = 0, 1,... , n 1 , denn: Ist a 2 Z beliebig, dann liefert die Division mit Rest durch n: Es gibt q, r 2 Z mit a = qn + r, 0  r < n ) a r = qn ) a ⌘ r (mod n) ) a = r, d.h. jede Restklasse ist von der Form r mit r 2 {0,... , n 1}. Die Restklassen 0, 1,... , n 1 sind paarweise verschieden, denn: Seien a, b 2 {0, 1,... , n 1} mit a = b ) a ⌘ b (mod n) ) Es existiert q 2 Z mit a b = qn ) |a b| = |q|n Wäre q 6= 0 ) |q| 1, wegen q 2 Z ) |a b| n zu a, b 2 {0, 1,... , n 1} Also: q = 0, d.h. a = b. Beispiel 2.21. Wir betrachten den Fall n = 3: a ⌘ b (mod 3) , Es existiert q 2 Z mit a b = 3q. Es gilt zum Beipsiel: 11 ⌘ 5 (mod 3), denn 11 5=6=2·3 7 6⌘ 2 (mod 3), denn 7 2 = 5 und es existiert kein q 2 Z mit 5 = 3q. 40  2.1 Gruppen Restklassen: 0 = {a 2 Z : a ⌘ 0 (mod 3)} = {a 2 Z : Es existiert q mit a = 3q} = 3Z = {..., 9, 6, 3, 0, 3, 6, 9,...} 1 = {a 2 Z : a ⌘ 1 (mod 3)} = {a 2 Z : Es existiert q mit a 1 = 3q} = 1 + 3Z = {..., 8, 5, 2, 1, 4, 7,...} 2 = {a 2 Z : a ⌘ 2 (mod 3)} = {a 2 Z : Es existiert q mit a 2 = 3q} = 2 + 3Z = {..., 7, 4, 1, 2, 5, 8,...} 3 = {a 2 Z : a ⌘ 3 (mod 3)} = {a 2 Z : Es existiert q mit a 3 = 3q} = {a 2 Z : Es existiert q mit a = 3(q + 1)} = 3Z = 0 4 = 1, 5 = 2, 1 = 2, etc. Also zerfällt Z in die Restklassen Z 0 1 2 Definition 2.22. Sei n 2 N. Für a, b 2 Z/nZ definieren wir die Verknüpfung + (Addition) durch a + b = a + b. Wir nennen (Z/nZ, +) die zyklische Gruppe. Satz 2.23. (Z/nZ, +) ist eine abelsche Gruppe. Beweis. a) Die Verknüpfung + ist wohldefiniert: Problem: Die Addition verwendet Vertreter von Restklassen. In Z/5Z ist z.B. 3 + 4 = 3 + 4 = 7 = 2. Aber man könnte auch rechnen: 3 + 4 = 8 + 9 = 8 + 9 = 17 = 2. Wir müssen also nachweisen, dass die Wahl der Vertreter keinen Einfluss auf das Ergebnis hat, d.h. die Verknüpfung ist ”vertreterunabhängig”: 41 2 Gruppen, Ringe und Körper Seien a1 , a2 , b1 , b2 2 Z mit a1 = a2 und b1 = b2 ) a1 ⌘ a2 (mod n), b1 ⌘ b2 (mod n) ) Es existieren q1 , q2 2 Z mit a1 a2 = q1 n, b1 b2 = q 2 n ) (a1 + b1 ) (a2 + b2 ) = (a1 a2 ) + (b1 b2 ) = q1 n + q2 n = (q1 + q2 )n ) a1 + b1 ⌘ a2 + b2 (mod n) ) a 1 + b1 = a 2 + b2 b) (Z/nZ, +) ist eine abelsche Gruppe: Assoziativgesetz: Für alle a, b, c 2 Z ist (?) # (a + b) + c = a + b + c = (a + b) + c = a + (b + c) = a + b + c = a + (b + c), wobei wir bei (?) das Assoziativgesetz von (Z, +) ausgenutzt haben. 0 ist neutrales Element: Für alle a 2 Z ist 0 + a = 0 + a = a, da 0 das neutrale Element von (Z, +) ist. a ist Inverses von a: Für alle a 2 Z ist a + a = ( a) + a = 0, da a das inverse Element von a in (Z, +) ist. Kommutativgesetz: Für alle a, b 2 Z ist (??) # a+b=a+b = b+a=b+a wobei wir bei (??) das Kommutativgesetz von (Z, +) ausgenutzt haben. Beispiel 2.24. Wir fassen die Ergebnisse der Verknüpfung ”+” in einer sogenannten Verknüpfungstafel zusammen: + 0 1 2 3 + 0 1 2 0 0 1 2 3 0 0 1 2 n = 3: n = 4: 1 1 2 3 0 1 1 2 0 2 2 3 0 1 2 2 0 1 3 3 0 1 2 42  2.2 Ringe 2.2 Ringe In diesem Abschnitt beschäftigen wir uns mit der Kombination verschiedener Rechen- operationen auf einer Menge. Definition 2.25 (Ringaxiome). Sei R eine Menge zusammen mit zwei Ver- knüpfungen + : R ⇥ R ! R, (a, b) 7! a + b · : R ⇥ R ! R, (a, b) 7! a · b (R, +, ·) heißt Ring, wenn folgendes gilt: (R1) R zusammen mit der Addition + ist eine abelsche Gruppe. (R2) Die Multiplikation · ist assoziativ. (R3) Es gelten die Distributivgesetze, d.h. für alle a, b, c 2 R gilt a · (b + c) = a · b + a · c und (a + b) · c = a · c + b · c Der Ring (R, +, ·) heißt kommutativ, wenn zusätzlich gilt: (R4) Für alle a, b 2 R gilt a · b = b · a. Bemerkung 2.26. Neutrales Element der Addition: 0 2 R heißt Nullelement, wenn 0 + a = a für alle a 2 R. Neutrales Element der Multiplikation: 1 2 R heißt Einselement, wenn 1·a = a·1 = a für alle a 2 R. Ein Ring hat immer eine 0, aber nicht immer eine 1. Wie üblich soll zur Einsparung von Klammern die Multiplikation stärker binden als die Addition (”Punkt vor Strich”). Wir schreiben häufig verkürzend: ”Ring R” statt ”Ring (R, +, ·)”. Beispiel 2.27. a) (Z, +, ·) ist ein kommutativer Ring. b) (Q, +, ·) ist ein kommutativer Ring. c) (R, +, ·) ist ein kommutativer Ring. d) Der Nullring ({0}, +, ·) mit 0 + 0 = 0, 0 · 0 = 0 ist ein kommutativer Ring (hier ist Nullelement=Einselement=0). Wir bezeichnen den Nullring kurz mit 0. e) (2Z, +, ·) ist ein kommutativer Ring (ohne Eins). f ) Ausblick: Die Menge aller n ⇥ n-Matrizen bildet mit der komponentenweisen Addition und der Matrizenmultiplikation einen Ring mit Einselement (die Identitätsmatrix), der nicht kommutativ ist. 43 2 Gruppen, Ringe und Körper Satz 2.28. In einem Ring R gelten die folgenden Rechenregeln: a) Ist 0 2 R das Nullelement, so gilt für alle a 2 R 0 · a = a · 0 = 0. b) Für alle a, b 2 R gilt a · ( b) = a · b = ( a) · b. c) Wenn ein Ring R mindestens zwei Elemente enthält (also R 6= 0), dann ist 1 6= 0. Beweis. a) Für 0, a 2 R gilt 0 · a = (0 + 0) · a = 0 · a + 0 · a, wobei wir im letzten Schritt die Kürzungsregel aus Satz 2.4 angewendet haben. a·0 = 0 folgt analog. b) Sei 0, a, b 2 R. Aus Punkt a) folgt 0 = 0 · b = (( a) + a) · b = ( a) · b + a · b. mit der Kürzungsregel aus Satz 2.4, folgt also a · b = ( a) · b. a · ( b) = a · b folgt analog. c) Beweis durch Kontraposition: Sei 1 = 0. Dann gilt wegen Punkt a) für alle a 2 R, dass a = 1 · a = 0 · a = 0. Also ist R = 0. Satz 2.29. Sei n 2 N. Für a, b 2 Z/nZ setzen wir a + b = a + b und a · b = a · b. Dann ist (Z/nZ, +, ·) ein kommutativer Ring, den wir Restklassenring nennen und kurz mit Z/nZ bezeichnen. Beweis. Beispiel 2.30. Verknüpfungstafeln für Z/nZ. 44  2.2 Ringe + 0 1 2 · 0 1 2 0 0 1 2 0 0 0 0 n = 3: 1 1 2 0 1 0 1 2 2 2 0 1 2 0 2 1 + 0 1 2 3 · 0 1 2 3 0 0 1 2 3 0 0 0 0 0 n = 4: 1 1 2 3 0 1 0 1 2 3 2 2 3 0 1 2 0 2 0 2 3 3 0 1 2 3 0 3 2 1 In Z/4Z ist 2 · 2 = 0, aber 2 6= 0. Definition 2.31. Ein Ring R heißt nullteilerfrei, wenn für alle a, b 2 R gilt: a·b=0 ) a = 0 oder b = 0. Korollar 2.32. Ist R nullteilerfrei, so gilt für x, y, a 2 R mit a 6= 0 die Kürzungsregel x·a=y·a , x = y, denn dann ist (x y) · a = 0. Satz 2.33. Der Restklassenring Z/pZ ist für p 2 genau dann nullteilerfrei, wenn p eine Primzahl ist. Beweis. Ist p keine Primzahl, also p = k · l mit 1 < k < p und 1 < l < p,so ist k, l 6= 0, aber 0 = p = k · l. Ist umgekehrt p Primzahl und k · l = 0, so ist k·l =r·p für ein r 2 Z. Also hat entweder k oder l einen Primfaktor p, d.h. k = 0 oder l = 0. Analog zu den Gruppen kann man auch für Ringe Teilmengen und Homomorphismen (strukturerhaltende Abbildungen) betrachten und somit beurteilen, ob sich die Rechen- regeln eines Ringes auf andere Mengen übertragen lassen. Definition 2.34. Ist R ein Ring und U ⇢ R eine Teilmenge, so heißt U Unter- ring, wenn U bezüglich der Addition Untergruppe ist (also entsprechend Definiti- on 2.8 für a, b 2 U auch a + b 2 U und a 2 U ), und bezüglich der Multiplikation für a, b 2 U auch a · b 2 U. 45 2 Gruppen, Ringe und Körper Beispiel 2.35. nZ ⇢ Z ist für n 2 N ein Unterring. Definition 2.36. Sind (R, +, ·) und (S, , ) Ringe, so heißt eine Abbildung ' : R ! S ein Homomorphismus (von Ringen), wenn für alle a, b 2 R gilt: '(a + b) = '(a) '(b) und '(a · b) = '(a) '(b). Beispiel 2.37. Z ! Z/nZ, a 7! a + nZ, ist für n 2 N ein Homomorphismus. 2.3 Körper Kommutative Ringe, die zusätzlich zur Addition auch bzgl. der Multiplikation eine abel- sche Gruppe bilden, nennen wir Körper. Es gelten die gewohnten Rechenregeln wie wir sie z.B. von den rationalen oder reellen Zahlen gewohnt sind. Insbesondere sind Körper nullteilerfrei. Die definierenden Eigenschaften sind in Form der Körperaxiome in der folgenden Definition zusammengefasst. Definition 2.38 (Körperaxiome). Sei K eine Menge zusammen mit zwei Ver- knüpfungen + : K ⇥ K ! K, (a, b) 7! a + b · : K ⇥ K ! K, (a, b) 7! a · b Das Tripel (K, +, ·) (oder auch kurz K) heißt Körper, wenn folgendes gilt: (K1) K zusammen mit der Addition + ist eine abelsche Gruppe. (K2) K ⇤ = K \ {0} zusammen mit der Multiplikation · ist eine abelsche Gruppe. (K3) Es gelten die Distributivgesetze, d.h. für alle a, b, c 2 K gilt a · (b + c) = a · b + a · c und (a + b) · c = a · c + b · c Satz 2.39. In einem Körper K gelten die folgenden Rechenregeln (dabei sind a, b, x, y 2 K beliebig): a) 1 6= 0 (also hat ein Körper mindestens zwei Elemente). b) 0 · a = a · 0 = 0. c) a · b = 0 ) a = 0 oder b = 0. d) a( b) = (ab) und ( a)( b) = ab. e) x · a = y · a und a 6= 0 ) x = y. Beweis. Beispiel 2.40. 46  2.4 Exkurs a) (Q, +, ·) ist ein Körper. b) (R, +, ·) ist ein Körper. c) Z/pZ ist ein Körper, wenn p eine Primzahl ist (das folgt aus Satz 2.33 und dem folgenden Satz 2.41). Er heißt Primkörper Fp. + 0 1 · 0 1 F2 : 0 0 1 0 0 0 1 1 0 1 0 1 + 0 1 2 · 0 1 2 0 0 1 2 0 0 0 0 F3 : 1 1 2 0 1 0 1 2 2 2 0 1 2 0 2 1 d) Der Körper der komplexen Zahlen C ist ein Körper (! IMI 2). Satz 2.41. Ein nullteilerfreier, kommutativer Ring K mit endlich vielen Elemen- ten und Einselement ist ein Körper. Beweis. 2.4 Exkurs In diesem kurzen Exkurs konstruieren wir den Körper der komplexen Zahlen und führen den Ring der Polynome ein. Beides dient als Vorbereitung für die spätere Betrachtung von Eigenwertproblemen. 2.4.1 Der Körper der komplexen Zahlen Die Idee, komplexe Zahlen einzuführen, liegt in der Lösbarkeit der Gleichung x2 = 1 begründet, welche in R keine Lösung hat. Geht man zu den komplexen Zahlen als einen auf der Menge R⇥R konstruierten Körper über, so bekommt man nicht nur die Lösbarkeit von der Nullstellengleichung x2 + 1 = 0, sondern sogar, dass jedes Polynom eine Nullstelle in den komplexen Zahlen hat. Dies ist der sogenannte Fundamentalsatz der Algebra. Zur Konstruktion der komplexen Zahlen C führt man in der reellen Ebene R ⇥ R eine Addition und Multiplikation ein. 4 4 Die naheliegende Frage, warum das im Rn mit n > 2 nicht mehr so geht, wird z.B. in H.D. Ebbinghaus et al: Zahlen. Springer 1992 behandelt. 47 2 Gruppen, Ringe und Körper Definition 2.42. Die Menge R ⇥ R = {(a, b) : a, b 2 R} zusammen mit den Verknüpfungen + und · definiert durch (a, b, c, d 2 R) (a, b) + (c, d) = (a + c, b + d) und (a, b) · (c, d) = (ac bd, ad + cb) bildet einen Körper mit (0, 0) als neutralem Element der Addition, ( a, b) als Negativem von (a, b), (1, 0) als neutralem Element der Multiplikation und dem multiplikativen Inversen gegeben durch ✓ ◆ 1 a b (a, b) = ,. a 2 + b 2 a 2 + b2 Das Tripel (R ⇥ R, +, ·) nennen wir den Körper der komplexen Zahlen und bezeichnen ihn mit C. Beweis. Der Nachweis der Körperaxiome wird als Übungsaufgabe gestellt. Bemerkung 2.43. Die Abbildung R ! R⇥R = C, a 7! (a, 0), ist injektiv. Da außerdem (a, 0) + (a0 , 0) = (a + a0 , 0) und (a, 0) · (a0 , 0) = (a · a0 , 0), braucht man zwischen R und R ⇥ {0} = {(a, b) 2 C : b = 0} bzgl. Addition und Multi- plikation nicht zu unterscheiden. Man kann also R mit R ⇥ {0} ”identifizieren” und R als Teilmenge von C betrachten. Dies wird noch einleuchtender durch folgende übliche Konventionen. 48  2.4 Exkurs Definition 2.44. Man definiert die imaginäre Einheit als i = (0, 1). Dann ist i2 = 1, und für jedes (a, b) 2 C gilt (a, b) = (a, 0) + (0, b) = a + bi. Für = (a, b) = a + bi 2 C nennt man Re( ) = a 2 R den Realteil und Im( ) = b 2 R den Imaginärteil. Weiter nennen wir =a bi 2 C die zu konjugiert komplexe Zahl. Satz 2.45. Es gelten folgende Rechenregeln für die komplexe Konjugation: Für alle , µ 2 C ist +µ= +µ ·µ= ·µ 2R, = Für = a + bi 2 C gilt · = (a + bi) · (a bi) = a2 + b2 2 R 0 Beweis. Definition 2.46. Der Absolutbetrag | | einer komplexen Zahl 2 C ist definiert durch p p | |= · = a 2 + b2. 49 2 Gruppen, Ringe und Körper Satz 2.47. Seien , µ 2 C. Für den Absolutbetrag gilt | · µ| = | | · |µ| und die Dreiecksungleichung | + µ|  | | + |µ| Beweis. Bemerkung 2.48. Vorsicht! Die in den reellen Zahlen R vorhandene -Relation lässt sich nicht in sinnvoller Weise auf C fortsetzen. Für komplexe Zahlen kann man daher i.A. nur die Absolutbeträge vergleichen, d.h. für , µ 2 C ist | |  |µ| oder |µ|  | |. 2.4.2 Der Ring der Polynome In diesem Abschnitt führen wir den Ring der Polynome ein und betrachten die Lösbarkeit von Polynomgleichungen, die auf die Frage der Existenz von Nullstellen zurückgeführt werden kann. Die wichtigste Existenzaussage für Nullstellen von Polynomen macht dabei der sogenannte Fundamentalsatz der Algebra. An dieser Stelle führen wir zwei Definitionen für die spätere Verwendung ein, die haupt- sächlich eine vereinfachte Darstellung mathematischer Rechenausdrücke erlauben: die Potenz und das Summensymbol. Definition 2.49. Sei n 2 N und X eine Menge, auf der eine assoziative Multi- plikation · mit Eins definiert ist. Die Potenz xn einer Zahl x 2 X ist definiert als xn = 1 · x | · {z... · x}. n mal x wird dabei Basis gennant, n der Exponent. Negative Exponenten sind für x 6= 0 über die folgende Gleichung definiert n x · xn = 1. Beispiel 2.50. a) 53 = 5 · 5 · 5. b) Für x 2 R ist x0 = 1. c) Für n 2 N und rationale (oder reelle) Zahlen x 2 Q (oder x 2 R) ist n 1 x =. xn 50  2.4 Exkurs Definition 2.51. Sei n 2 N und (A, +) eine abelsche Gruppe. DieP Summe von n Zahlen a0 ,..., an 1 2 A schreibt sich mit dem Summensymbol (Sigma) als n X1 ai = a0 +... + an 1. i=0 Etwas allgemeiner definieren wir die Summe von n Elementen ai 2 A mit i 2 I für eine (endliche) Indexmenge I = {i0 ,..., in 1 } ⇢ N durch in X X1 ai = ai = ai0 +... + ain 1. i2I i=i0 Beispiel 2.52. a) Sei ai = i + 1. Dann ist 9 X 9 X ai = (i + 1) = 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10 = 55. i=0 i=0 P10 b) i=1 i = 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10 = 55 c) Sei ai = 2 · i und I = {1, 3, 6, 7, 8}, dann ist X ai = a1 + a3 + a6 + a7 + a8 = 2 · 1 + 2 · 3 + 2 · 6 + 2 · 7 + 2 · 8 = 50. i2I Definition 2.53. Sei K ein Körper und t eine Unbestimmte.a Ein Polynom mit Koeffizienten in K (oder Polynom über K) ist ein formaler Ausdruck der Gestalt f (t) = a0 + a1 t +... + an tn wobei a0 ,..., an 2 K. Meist schreibt man statt f (t) nur f. Sind alle Koeffizienten ai = 0, so spricht man vom Nullpolynom und schreibt f = 0. Man nennt f normiert, wenn an = 1 a Eine Unbestimmte soll dabei einfach ein Buchstabe sein, für den man alles einsetzen darf, was sinnvoll ist. Definition 2.54. Mit K[t] bezeichnen wir die Menge aller Polynome über K. 51 2 Gruppen, Ringe und Körper Definition 2.55. Der Grad eines Polynoms f ist erklärt als ( 1, falls f = 0, deg(f ) = max{i 2 N : ai 6= 0}, sonst Beispiel 2.56. f (t) = 3 + 5t 2t2 ist ein Polynom über R vom Grad 2, da deg(f ) = max{0, 1, 2} = 2. f (t) = 32 + 7t + t5 ist ein normiertes Polynom über Q vom Grad 5, da deg(f ) = max{0, 1, 5} = 5. f (t) = 0 ist das Nullpolynom und vom Grad 1. Sei f 2 K[t]. Dann ist für 2 K auch n f ( ) = a0 + a1 +... + an 2 K. Beispiele: 1 2 – Für f (t) = 2 + 3t2 2 Q[t] ist f ( 12 ) = 2 + 3 · 2 = 11 4 2 Q. 2 – Für f (t) = 1 + t2 2 F3 [t] ist f (2) = 1 + 2 · 2 = 0 2 F3. Definition 2.57. Sei K ein Körper. Zwei Polynome f, g 2 K[t] mit f = a0 + a1 t +... + an tn und g = b0 + b1 t +... + bn tm sind genau dann gleich, wenn deg f = deg g und ai = bi für alle i = 0,..., n. Definition 2.58. Sei K ein Körper und seien f, g 2 K[t] mit f = f (t) = a0 + a1 t +... + an tn und g = g(t) = b0 + b1 t +... + bm tm. Auf K[t] definieren wir die Addition + durch f + g = (a0 + b0 ) + (a1 + b1 )t +... + (an + bn )tn , wobei wir hier ohne Bedenken der Allgemeinheit annehmen können, dass m = n (falls m < n setzen wir bm+1 =.. = bn = 0). Die Definition der Multiplikation · ist gegeben durch X f · g = c0 + c1 t +... + cn+m tn+m mit ck = a i bj. i+j=k Insbesondere ist c 0 = a 0 b0 , c 1 = a 0 b 1 + a 1 b0 , c2 = a0 b2 + a1 b1 + a2 b0 ,..., cn+m = an bm. Ist f · g = h, so nennt man f und g Teiler von h. 52  2.4 Exkurs Satz 2.59. Sei K ein Körper. Dann gilt für alle f, g 2 K[t] deg(f + g)  max{deg(f ), deg(g)}, deg(f · g) = deg(f ) + deg(g). Dabei setzt man formal für n 2 N: 1 < n, n + ( 1) = 1= 1 + n und ( 1) + ( 1) = 1 Beweis. Wenn f = 0 oder g = 0, dann sind beide Aussagen klar. Seien also f 6= 0 und g 6= 0 gegeben durch f = a0 + a1 t +... + an tn und g = b0 + b1 t +... + bm tm mit an 6= 0 und bm 6= 0 (also insbesondere deg(f ) = n und deg(g) = m). a) Wir setzen k = max{deg(f ), deg(g)}. Dann ist f + g = (a0 + b0 ) + (a1 + b1 )t +... + (ak + bk )tk. Also gilt deg(f + g)  k, da es sein könnte, dass ak + bk = 0. b) Es ist f · g = a0 b0 +... + an bm tn+m mit an bm 6= 0. Also ist deg(f · g) = n + m = deg(f ) + deg(g). Satz 2.60. Die Menge K[t] aller Polynome über dem Körper K ist zusammen mit den oben definierten Verknüpfungen ein kommutativer Ring ohne Nullteiler. Man nennt K[t] den Polynomring über K. Beweis. a) Der Nachweis der Ringaxiome erfolgt durch Nachrechnen und überträgt sich direkt aus den Eigenschaften des Körpers K. b) K[t] enthält keine Nullteiler (Beweis durch Kontraposition): Wenn f 6= 0 und g 6= 0, dann ist deg(f ) 0 und deg(g) 0, also folgt deg(f · g) = deg(f ) + deg(g) 0, und schließlich f · g 6= 0. Bemerkung 2.61. Der Mangel eines Ringes gegenüber einem Körper ist der, dass man im Allgemeinen nicht dividieren kann, d.h. keine Inversen existieren. Bei ganzen Zahlen hat man als Ersatz eine Teilung mit Rest, die ganz analog auch für Polynome erklärt werden kann. 53 2 Gruppen, Ringe und Körper Satz 2.62 (Polynomdivision). Sei K ein Körper und seien f, g 2 K[t] mit g 6= 0. Dann exisitieren eindeutig bestimmte Polynome q, r 2 K[t] mit f =q·g+r und deg(r) <