Lineare Algebra (Informatik) Skript PDF

Lineare Algebra (Informatik) Dr. Paula Reichert 20. Dezember 2024 Inhaltsverzeichnis 1 Einführung 2 1.1 Historische Einführun...

Lineare Algebra (Informatik) Dr. Paula Reichert 20. Dezember 2024 Inhaltsverzeichnis 1 Einführung 2 1.1 Historische Einführung................................. 2 1.2 Euklidische Mathematik................................ 3 2 Grundbegriffe 7 2.1 Logik........................................... 7 2.2 Vollständige Induktion................................. 11 2.3 Mengenlehre....................................... 15 2.4 Relationen........................................ 21 2.5 Abbildungen (Funktionen)............................... 24 2.6 Unendliche Mengen................................... 28 3 Gruppen, Ringe, Körper 32 3.1 Gruppen......................................... 32 3.2 Ringe.......................................... 35 3.3 Körper.......................................... 37 4 Vektorräume und lineare Abbildungen 41 4.1 Vektorräume...................................... 41 4.2 Lineare Abbildungen.................................. 44 4.3 Untervektorräume................................... 47 4.4 Matrizen......................................... 49 4.5 Erzeugendensystem, lineare Unabhängigkeit, Basis................. 59 4.6 Dimension........................................ 64 1 1 Einführung Die (lineare) Algebra beschäftigt sich mit dem Lösen von (linearen) Gleichungssystemen und den damit verbundenen Rechenoperationen. Herkunft des Begriffs: Das Wort „Algebra” stammt aus dem Arabischen von al-ǧabr, zu deutsch in etwa „Ergänzen”. Das Wort war ursprünglich Teil des Titels eines berühmten Mathematikbuchs von al-Chwarizmi (9. Jhd., Bagdad). Der vollständige Titel lautet: al-Kitab al-Muchtasar fi hisab al-dschabr wa-l-muqabala „Das kurz gefasste Buch über die Rechenverfahren durch Ergänzen und Ausgleichen" 1.1 Historische Einführung Frühgeschichte in Babylon (Gebiet des heutigen Irak) und Ägypten: Babylonier (ca. 2000 v. Chr.): Gleichungssysteme der folgenden Form werden in erster Näherung gelöst. Hier sind a, b gegeben, x, y gesucht:  x+y =a ⇒ x2 − ax + b = 0 x·y =b Dies entspricht dem Lösen quadratischen Gleichungen, aber: keine irrationalen Zahlen, keine negativen Zahlen, nur erste Näherung. Ägypter (ca. 1700 v. Chr.): Lineare Gleichungen der Form x+a·x=b x+c·x+d·x=e mit a, b, c, d, e gegeben, x gesucht, werden mit geometrischen Methoden gelöst. Höhepunkt der Entwicklung im antiken Griechenland: Pythagoreer (ca. 600 v. Chr.): Entdeckung der Existenz inkommensurabler Strecken und damit irrationaler Zahlen durch Hippasos von Metapont. Euklid (ca. 300 v. Chr.): Verfasst die 13 Bücher der „Elemente". Dies bleibt das Standardwerk der Geometrie und Arithmetik bis ins 19. Jhd (und das am zweitmeisten verbreitetste Buch nach √ der Bibel). Euklid wird u.a. der Beweis der Irrationalität von 2 zugeschrieben. Diophantes (zwischen 100 v. Chr. und 300 n. Chr.): Verfasst die 13 Bücher der „Arithmetica", von denen nur noch sechs überliefert sind. Löst die Arithmetik und Algebra von der Geometrie ab. 2 Es folgt eine Weiterentwicklung der Mathematik im arabisch-persischen und indischen Raum mit Höhepunkt im 7. - 9. Jahrhundert. Moderne Entwicklung: Erst in der Renaissance im Italien des 16. Jahrhunderts kommt es wieder zu einer Weiterent- wicklung der Mathematik (und aller anderer Wissenschaften) im europäischen Raum. Ab dem 18. Jhd. bestimmen bedeutende Mathematiker wie Euler, Lagrange, Gauss, Galois, Abel, Jor- dan, Hölder, Lie, Killing, Cartan, Grassmann, Hamilton, Clifford, Cauchy, Ricci, Levi-Civita die weitere Entwicklung. Aussicht für diese Vorlesung (kurzes Intermezzo): Wir werden uns in diesem Semester mit li- nearen Gleichungssytemen der folgenden Art beschäftigen. Hier sind a11 ,..., amn und y1 ,..., ym gegeben und x1 ,..., xn gesucht. a11 x1 + a12 x2 +... + a1n xn = y1 a21 x1 + a22 x2 +... + a2n xn = y2... am1 x1 + am2 x2 +... + amn xn = ym Dieses Gleichungssystem kann man auch schreiben als:      a11 a12... a1n x1 y1  a21 a22... a2n   x2   y2       .. .  = .  .  . . .  .    am1 am2... amn xn ym Oder in Kurzschreibweise: A·x=y Dabei ist A = (aij )i=1,...,m, eine m × n Matrix (m Zeilen, n Spalten), x ist ein Spaltenvektor mit j=1,...,n n Komponenten und y ein Spaltenvektor mit m Komponenten. 1.2 Euklidische Mathematik Im antiken Griechenland (vertreten insbesondere durch Euklid) basieren Zahlen und Rechenope- rationen auf der geometrischen Anschauung. Mathematische Beweise werden über die Geometrie √ geführt. Wir betrachten einen Beweis der Irrationalität von 2. Definition 1.2.1 (Inkommensurabilität). Zwei Strecken heißen inkommensurabel, wenn sie kein gemeinsames Maß besitzen. Sie heißen kommensurabel, wenn sie ein gemeinsames Maß besitzen. Besitzen zwei Strecken ein gemeinsames Maß, so besitzen sie ein größtes gemeinsames Maß und dieses ist eindeutig. Beweis: Wechselwegnahme/euklidischer Algorithmus. 3 Definition 1.2.2 (ggT). Das größte gemeinsame Maß zweier natürlicher Zahlen ist der ggT (größter gemeinsamer Teiler ). Der Euklidische Algorithmus zur Konstruktion des größten gemeinsamen Maßes ist die sogenann- te Wechselwegnahme. Betrachte dazu zwei Strecken X und Y. Sei o. B. d. A. Y ≤ X. Um das gemeinsame Maß (bzw. bei natürlichen Zahlen X, Y den ggT) zu bestimmen, trage Y so oft auf X ab, bis ein Rest r1 bleibt, 0 ≤ r1 < Y. Wenn r1 = 0, dann gilt: Y = ggT (X, Y ). Wenn r1 > 0, trage r1 auf Y so oft ab, bis ein Rest r2 bleibt, 0 ≤ r2 < r1. Wenn r2 = 0, dann gilt: r1 = ggT (X, Y ). Wenn r2 > 0, trage r2 auf r1 so oft ab, bis ein Rest r3 bleibt usw. Damit ergibt sich das folgendes Gleichungssystem (mit ni ∈ N ∀i = 0,..., k, Y = r0 ): X = n0 Y + r1 Y = n1 r1 + r2 r1 = n2 r2 + r3... rk−1 = nk rk + rk+1 Falls rk+1 = 0 ⇒ rk = ggT (X, Y ). Die Wechselwegnahme ist eine eindeutiges Charakterisierung des Verhältnisses X/Y durch die natürlichen Zahlen n0 , n1 ,..., nk : X r1 1 1 1 1 = n0 + = n0 + Y = n0 + r2 = n0 + 1 =... = n0 + 1 Y Y n 1 + r1 n1 + r n1 + 1 r 1 n2 + r3 n2 + 2...+ n1 k Falls der Kettenbruch abbricht, sind X und Y kommensurabel. Falls nicht, sind X und Y in- kommensurabel. Definition 1.2.3 (Irrationale Zahl). Das Verhältnis zweier inkommensurabler Strecken ist eine irrationale Zahl, das Verhältnis zweier kommensurabler Strecken eine rationale Zahl. Beispiel 1.2.1. Kettenbruchdarstellung von 5 3 und ggT (5, 3). 5=1·3+2 3=1·2+1 2=2·1+0 5 1 ⇒ =1+ 1 3 1+ 2 und ggT (5, 3) = 1. Wir betrachten im Folgenden den Beweis der Inkommensurabilität von Seite und Diagonale im √ Quadrat. Daraus folgt die Irrationalität von 2. 4 Satz 1.2.1 (Diagonale im Quadrat). Seite und Diagonale eines Quadrats sind inkommensurabel. Beweis. Mittels Wechselwegnahme trage man die Seite a des Quadrats an der Diagonalen d ab. Dabei bleibt ein Rest a1 (d.h. d = a + a1 ). An dieser Stelle fällt man das Lot auf d. Die Strecke, die sich von dort bis zum Schnittpunkt mit der Seite a ergibt, hat die Länge a1 (gleichschenkliges Dreieck!). Die Strecke bildet nach Konstruktion die Seite eines kleineren Quadrats mit Diagonale d1. Dabei bildet d1 einen Abschnitt der Seite a mit a = a1 +d1 (man beachte das Drachenviereck, an dem man erkennt, dass a − d1 = a1 !). Nun beginnt die ganze Konstruktion von vorne (nur diesmal am kleineren Quadrat). Man trage also nun a1 an d1 ab. Dabei bleibt ein Rest a2 (d.h. a = 2a1 + a2 ). Dieser bildet nach Konstruktion die Seite eines noch kleineren Quadrats mit Diagonale d2 usw. Diese Konstruktion kann endlos fortgesetzt werden; sie bricht niemals ab. Zur geometrischen Konstruktion: siehe Tafel bzw. Übung. Insbesondere gilt gemäß Konstruktion (mit k ∈ N0 , a = a0 , d = d0 ): a1 = d0 − a0 d1 = a0 − a1... ak = dk−1 − ak−1 dk = ak−1 − ak... Für die Wechselwegnahme gilt gemäß Konstruktion (mit rk = ak ): d0 = 1 · a0 + a1 a0 = 2 · a1 + a2 a1 = 2 · a2 + a3... ak−2 = 2 · ak−1 + ak... Daraus folgt: d 1 =1+ a 2 + 2+ 1 1 2+... √ Um zu sehen, dass diese Kettenbruchdarstellung der Zahl 2 entspricht, brauchen wir den Satz von Pythagoras. Satz 1.2.2 (Satz des Pythagoras). Seien a, b, c die Seiten eines rechtwinkligen Dreiecks. Dabei sei c die Seite, die dem rechten Winkel gegenüberliegt. Dann gilt: a2 + b2 = c2. 5 Beweis. Z. B. von Euklid (Übung). Aus dem Satz von Pythagoras folgt, dass im gleichschenkligen rechtwinkligen Dreieck gilt: d2 √ d a2 + a2 = d2 ⇔ 2a2 = d2 ⇔ 2= ⇔ 2≡. a2 a √ Aus dem Satz des Pythagoras erkennen wir also, dass die Zahl 2 genau dem Verhältnis aus Diagonale und Seite im Quadrat entspricht (wie Euklid ja feststellte, sind reelle Zahlen Verhält- nisse von Strecken). Wichtig ist dabei: Egal von welcher Länge a das Quadrat ist, das Verhältnis √ a ist immer d 2. √ √ Und wir wissen nun bereits aus Satz 1.2.1, was 2 für eine Zahl ist. Wir wissen, dass ad = 2 irrational ist und dass gilt: √ 1 2≡1+ 1 2+ 1 2+ 2+... Bricht man diesen Kettenbruch (die Iteration bzw. Rekursion) an einer bestimmten Stelle k ∈ N0 √ ab, indem man willkürlich ak+1 = 0 setzt, so erhält man eine Näherung von 2 (der k-ten Ordnung): d z.B. k=0: =1 a d 1 3 k=1: =1+ = = 1, 5 a 2 2 d 1 7 k=2: =1+ 1 = 5 = 1, 4 a 2+ 2 d 1 17 k=3: =1+ 1 = 12 = 1, 416̄ a 2+ 1 2+ 2 6 2 Grundbegriffe 2.1 Logik Die Aussagenlogik untersucht die Struktur von Sätzen (Aussagen) A, B,... hinsichtlich ihres Wahrheitswerts. Sätze (Aussagen) können entweder wahr (w) oder falsch (f ) sein. Beispiel 2.1.1 (Wahrheitswert von Aussagen). A : 4 ist eine gerade Zahl (w) B : 15 ist durch 7 teilbar (f ) C : Seite und Diagonale des Quadrats sind inkommensurabel (w) Die Aussagenlogik arbeitet mit Junktoren (logischen Operatoren): ∧ : „und” ∨ : „oder” (Achtung: nicht „entweder... oder...”!) ¬ : „nicht” ⇒: „wenn..., dann...” bzw. „aus... folgt...” ⇔: „genau dann, wenn” Mit Hilfe von Junktoren erhalten wir zusammengesetzte Aussagen, die wiederum auf ihren Wahr- heitsgehalt untersucht werden können. Dies ist wichtig für die mathematische Beweisführung. Wir untersuchen den Wahrheitsgehalt mit Hilfe von Wahrheitstafeln. Beispiel 2.1.2 (Wahrheitstafel für A ∧ B und A ∨ B). A B A∧B A∨B w w w w w f f w f w f w f f f f Für die Junktoren gelten bestimmte Rechenregeln: Satz 2.1.1 (Rechenregeln). Für ∧ und ∨ gelten das Kommutativgesetz, das Assoziativgesetz und das Distributivgesetz, A∧B ⇔ B∧A (A ∧ B) ∧ C ⇔ A ∧ (B ∧ C) (A ∨ B) ∧ C ⇔ (A ∧ C) ∨ (B ∧ C) und analog für ∨ (bzw. ∨ und ∧ vertauscht im DG). Weiter gelten die De-Morgan-Regeln: ¬(A ∧ B) ⇔ ¬A ∨ ¬B ¬(A ∨ B) ⇔ ¬A ∧ ¬B 7 Zuletzt gilt für die doppelte Verneinung: ¬(¬A) ⇔ A Beweis. Mittels Wahrheitstafeln zeigt man jeweils die Äquivalenz der links und rechts von „⇔” stehenden Aussagen (Übung). Definition 2.1.1 (Äquivalenz). Zwei Aussagen A1 und A2 heißen (logisch) äquivalent, wenn sie dieselben Einträge in der Wahrheitstafel besitzen. Sind zwei Aussagen A1 und A2 äquivalent, dann ist die Aussage A1 ⇔ A2 eine Tautologie. Definition 2.1.2 (Tautologie, Paradoxon). Eine Aussage nennt man eine Tautologie oder allge- mein gültige Aussage, wenn alle ihre Einträge in der Wahrheitstafel wahr (w) sind. Eine Aussage nennt man ein (logisches) Paradoxon, wenn alle ihre Einträge in der Wahrheitstafel falsch (f ) sind. Beispiel 2.1.3 (Tautologie ¬A ∨ A und Paradoxon ¬A ∧ A). Sei A eine Aussage. A ¬A ¬A ∨ A ¬A ∧ A w f w f f w w f Satz 2.1.2. Seien A und B Aussagen. Die Aussagen (A ⇒ B) ∧ (B ⇒ A) und A ⇔ B sind äquivalent. Beweis. Wir beweisen dies mittels Wahrheitstafel: A B A⇒B B⇒A (A ⇒ B) ∧ (B ⇒ A) A⇔B ((A ⇒ B) ∧ (B ⇒ A)) ⇔ (A ⇔ B) w w w w w w w w f f w f f w f w w f f f w f f w w w w w Zum Erstellen dieser Wahrheitstafel ist es wichtig zu erkennen, dass die Implikation A ⇒ B nicht bedeutet, dass B wahr sein muss, sondern lediglich dass, wenn A wahr ist, dann B wahr ist. Darüber hinaus gilt die allgemeine Regel: aus Falschem kann alles folgen (ex falso quodlibet). Bemerkung 2.1.1. Die Äquivalenz von (A ⇒ B)∧(B ⇒ A) und A ⇔ B ist wichtig, um Beweise zu führen. Wir beweisen in der Regel, dass A ⇔ B, indem wir A ⇒ B und B ⇒ A zeigen. Satz 2.1.3 (Kontrapositionsgesetz). Seien A, B Aussagen. Dann ist allgemein gültig: (A ⇒ B) ⇔ (¬B ⇒ ¬A) 8 Beweis. Mittels Wahrheitstafel (Übung). Beispiel 2.1.4 (Ball, Scheibe). Wir nehmen zur Veranschaulichung ein Alltagsbeispiel, auch wenn Alltagsbeispiele nie ganz präzise sind. Seien A, B die folgenden Aussagen: A: „der Junge trifft mit dem Ball die Scheibe” B: „die Scheibe zerbricht”. Dann gilt: A ⇒ B. Dies impliziert aber auch ¬B ⇒ ¬A, denn „wenn die Scheibe nicht gebrochen ist, folgt daraus, dass der Junge mit dem Ball nicht die Scheibe getroffen hat” und andersherum. Bemerkung 2.1.2. Statt eine Aussage direkt zu beweisen, können wir sie also auch durch Kontraposition (¬B ⇒ ¬A) beweisen. Bemerkung 2.1.3 (Sprechweise). Statt A ⇔ B sagen wir auch „A ist hinreichend und notwendig für B” bzw. „B ist hinreichend und notwendig für A”. Statt A ⇒ B sagen wir auch „A ist hinreichend für B” oder äquivalent „B ist notwendig für A” (siehe Kontraposition). Achtung: Aus A ⇒ B folgt nicht die Aussage ¬A ⇒ ¬B! Satz 2.1.4. Seien A und B Aussagen. Es ist nicht allgemein gültig, dass (A ⇒ B) ⇔ (¬A ⇒ ¬B) Beweis. Beweis durch Gegenbeispiel. Sei k ∈ Z. Seien A und B die folgenden Aussagen: A: „k ist durch 9 teilbar” B: „k ist durch 3 teilbar” Dann gilt: A ⇒ B. Es gilt aber nicht: ¬A ⇒ ¬B, denn wenn eine Zahl k nicht durch 9 teilbar ist, folgt daraus nicht, dass sie nicht durch 3 teilbar ist. Betrachte z.B. k = 6. In diesem Beispiel haben wir die Wahrheit der Aussage A ⇒ B einfach akzeptiert. Was machen wir, wenn wir diese noch beweisen müssen? Bemerkung 2.1.4 (Widerspruchsbeweis). Die Aussage A ⇒ B beweisen wir in der Regel durch einen Widerspruch. Wir nehmen dazu an, dass A gilt, aber B nicht, formal A ∧ ¬B, und zeigen dann mittels korrekter Schlüsse, dass dies zu einem Widerspruch führt. Beispiel 2.1.5 (Widerspruchsbeweis). Sei A wieder die Aussage „eine ganze Zahl k ist durch 9 teilbar” und B die Aussage „eine ganze Zahl k ist durch 3 teilbar” (siehe oben). Zu zeigen: A ⇒ B Beweis. Wir nehmen an, dass es eine ganze Zahl k gibt, die durch 9 teilbar ist, aber nicht durch 3 (A ∧ ¬B). Wenn aber k durch 9 teilbar ist, dann ist k = m · 9 mit m ∈ Z. Dies gilt genau dann, wenn k = (3 · m) · 3. Daraus folgt, dass es ein p ∈ Z gibt (nämlich p = 3 · m) mit k = p · 3. Somit ist k durch 3 teilbar und dies ist im Widerspruch zur Annahme. Somit gilt: A ⇒ B. Weitere wichtige Schlussregeln für Beweise ergeben sich aus den folgenden Eigenschaften von „⇒” und „⇔” (auch Transitivität von „⇒” und „⇔” genannt). 9 Satz 2.1.5 (Transitivität von „⇒” und „⇔”). Seien A, B, C Aussagen. Dann ist allgemein gültig: (A ⇒ B) ∧ (B ⇒ C) ⇒ (A ⇒ C) (A ⇔ B) ∧ (B ⇔ C) ⇒ (A ⇔ C) Beweis. Mittels Wahrheitstafeln (Übung). Bemerkung 2.1.5. Dieser Satz kann (später) mittels vollständiger Induktion auf eine beliebige Anzahl an Aussagen A1 ,..., An , n ∈ N, erweitert werden. Bemerkung 2.1.6 (Prädikatenlogik). Zum Abschluss noch ein Exkurs zur Prädikatenlogik. In der Logik unterscheiden wir formal die Aussagenlogik von der Prädikatenlogik. Wechseln wir zur Prädikatenlogik kommen zusätzlich noch Variablen x, y,... und (zwei) Quantoren dazu: ∃ : „es existiert” ∀ : „für alle” Aussagen werden nun durch Prädikate P, Q,... ausgedrückt. Ist z.B. P das Prädikat „... ist grün” und Q das Prädikat „... ist stachlig”, dann entspricht der Term ∃x : P(x) ∧ Q(x) der Aussage „es existiert ein x, das grün und stachlig ist”. In der Prädikatenlogik gibt es allgemein gültige Regeln zur Verneinung der Quantoren: ¬(∀x : P(x)) ⇔ ∃x : ¬P(x) ¬(∃x : P(x)) ⇔ ∀x : ¬P(x) Wir sind nun bereits sehr nah an der Mengenlehre. In der Mengenlehre werden wir in der Regel nicht mehr (wie hier) mit universellen Quantoren arbeiten, sondern mit Quantoren über Mengen. Diese sind wie folgt definiert. Sei M eine Menge. ∀x ∈ M : P(x) ⇔ ∀x : (x ∈ M ⇒ P(x)) ∃x ∈ M : P(x) ⇔ ∃x : (x ∈ M ∧ P(x)) Wichtig: Die Reihenfolge von Quantoren darf nicht vertauscht werden! Beispiel 2.1.6 (Reihenfolge Quantoren). Die Aussage ∀k ∈ Z : ∃l ∈ Z : l ≤ k ist wahr, denn für jede ganze Zahl k ∈ Z gibt es eine Zahl l ∈ Z mit l ≤ k. Setze z.B. l := k oder l := k − 1. Anders herum ist die Aussage ∃l ∈ Z : ∀k ∈ Z : l ≤ k falsch, denn es existiert keine Zahl l ∈ Z, die kleiner oder gleich jeder ganzen Zahl k ∈ Z ist (Z hat kein kleinstes Element!). 10 2.2 Vollständige Induktion Ein sehr nützliches Beweisverfahren ist die vollständige Induktion. Wir benutzen sie, um zu zeigen, dass eine Aussage A(n) für alle n ∈ N (oder für alle n ∈ N0 ) gilt. Dabei ist A(n) in der Regel eine Gleichung, in der ein Parameter n ∈ N vorkommt. Für die Induktion müssen wir zwei Dinge zeigen: 1) A(1) ist wahr (Induktionsanfang) 2) A(n) ⇒ A(n + 1) ist wahr (Induktionsschritt) Daraus folgt: A(n) ist wahr ∀n ∈ N. Ausführlicher: Schritt 2) ist der Beweis dafür, dass, wenn A(n) wahr ist (Induktionsannahme), A(n + 1) wahr ist (Induktionsbehauptung). Bemerkung 2.2.1. Falls n ∈ N0 , dann beginnen wir beim Induktionsanfang mit n = 0, also zeigen in 1), dass A(0) wahr ist. Es ist wichtig, bei 1) mit dem ersten nicht-trivialen Fall der Aussage zu beginnen. Dann können wir von A(1) ausgehend mit Hilfe von 2) iterativ die Wahrheit der nachfolgenden Aussagen feststellen: A(1) wahr ⇒ A(2) wahr ⇒ A(3) wahr ⇒... So können wir letztlich darauf schließen, dass die Aussage A(n) für alle n ∈ N gilt. Bemerkung 2.2.2 (Wohlordnungsprinzip von N). Das Verfahren der vollständige Induktion basiert auf der Tatsache, dass wir die natürlichen Zahlen anordnen können (Wohlordnungsprinzip von N, äquivalent zum Auswahlaxiom auf N, siehe axiomatische Mengenlehre). Bemerkung 2.2.3 (Minimum, Maximum). Insbesondere gibt es wegen des Wohlordnungsprin- zips von N für jede nicht-leere endliche Teilmenge A von N ein kleinstes Element, d.h. ∃k ∈ A, sodass ∀n ∈ A : k ≤ n, und ein größtes Element ∃g ∈ A, sodass ∀n ∈ A : g ≥ n. Wir nennen k das Minimum von A und g das Maximum von A und schreiben: k =: min A und g =: max A. Achtung: Nicht jede Teilmenge von R enthält ein kleinstes und größtes Element! Bemerkung 2.2.4 (Supremum, Infimum). Man betrachte z.B. das offene Intervall ]0, 1[⊂ R. Es gilt: 0 ∈ / ]0, 1[ und 1 ∈ / ]0, 1[. In dem Fall besitzt die Menge, d.h. das Intervall ]0, 1[, kein Minimum und kein Maximum, aber es gibt zwei besondere Punkte außerhalb des Intervalls, denen sich alle aufsteigenden bzw. absteigenden Folgen, die in ]0, 1[ liegen, annähern: das Supremum, sup ]0, 1[= 1, und das Infimum, inf ]0, 1[= 0. Falls es ein Maximum bzw. Minimum gibt, gilt: „sup = max” bzw. „inf = min” (siehe Analysis). 11 Bemerkung 2.2.5. Seien a, b ∈ R. Mit [a, b] ⊂ R bezeichnet man das abgeschlossene Intervall. Es enthält seine Randpunkte a, b. Mit ]a, b[⊂ R bezeichnet man das offene Intervall. Es enthält seine Randpunkte a, b nicht (siehe Analysis). Wir betrachten im Folgenden ein paar Beispiele zur Induktion. Satz 2.2.1 (Geometrische Reihe). Sei |q| < 1, n ∈ N0. Dann gilt: n X 1 − q n+1 1) qk = 1−q k=0 und insbesondere ∞ X 1 2) qk =. 1−q k=0 Bemerkung 2.2.6 (Summenzeichen). Zunächst ein Hinweis zur Schreibweise. Σ ist das sog. „Summenzeichen”. Wir summieren damit über die verschiedenen Werte von k wie im Folgenden angegeben: n X q k = q 0 + q 1 + q 2 +... + q n−1 + q n. k=0 Beispiel 2.2.1 (Summenzeichen). Betrachte q = 12. Dann gilt: n n  k  n X k X 1 1 1 1 1 q = = 1 + + + +... + 2 2 4 8 2 k=0 k=0 Beweis (von Satz 2.2.1). Wir beweisen die erste Aussage (Gleichung 1) mittels vollständiger In- duktion. Die zweite Aussage (Gleichung 2) folgt daraus mit Hilfe der Regeln für die Grenzwert- bildung. Induktionsanfang (n = 0): 0 X 1−q 1 − q 0+1 qk = q0 = 1 = = 1−q 1−q k=0 Die Aussage ist also für n = 0 wahr. Wir können uns interessehalber noch n = 1 anschauen: 1 X (1 + q)(1 − q) 1 − q2 1 − q 1+1 qk = q0 + q1 = 1 + q = = = 1−q 1−q 1−q k=0 Die Aussage ist also auch für n = 1 wahr. Pn 1−q n+1 Induktionsannahme (IA): Wir nehmen an, die Aussage k=0 q k = 1−q gilt für festes n. Induktionsschritt (n ⇒ n + 1): n+1 n X X 1 − q n+1 1 − q n+1 + q n+1 (1 − q) 1 − q n+2 qk = q k + q n+1 = + q n+1 = = 1−q 1−q 1−q k=0 k=0 12 Hier haben wir im zweiten Schritt die Induktionsannahme verwendet. Die Induktionsbehauptung A(n + 1) ist also wahr, wenn die Induktionsannahme A(n) wahr ist. Daraus folgt: Die Aussage ist für alle n ∈ N0 wahr. Insbesondere gilt nun im Limes n → ∞ : ∞ n X X 1 − q n+1 1 − limn→∞ q n+1 1 q k = lim q k = lim = =. n→∞ n→∞ 1 − q 1−q 1−q k=0 k=0 Hier folgt die vorletzte Gleichung aus den Rechenregeln für Limiten (ohne Beweis verwenden wir, dass wir den Limes in den Quotienten und die Differenz „reinziehen” können). Die letzte Gleichung folgt daraus, dass |q| < 1, also limn→∞ q n+1 = limn→∞ q n = 0. Beispiel 2.2.2 (Geometrische Reihe). Betrachte q = 21. Dann gilt: ∞  k X 1 1 1 1 1 =1+ + + +... = 1 = 2. 2 2 4 8 1− 2 k=0 Satz 2.2.2 (Gaußsche Summenformel). Für die Summe der ersten n natürlichen Zahlen gilt die Gaußsche Summenformel: n X n(n + 1) k=. 2 k=1 Beweis. Mittels vollständiger Induktion (Übung). Bemerkung 2.2.7 (Historisch). Es heißt, Gauß (1777 – 1855) habe die Summenformel in der Grundschule entdeckt, nachdem er von seinem Lehrer aufgefordert wurde, die natürlichen Zahlen von 1 bis 100 zusammen zu zählen. Rechnung: (1 + 99) + (2 + 98) +... + (49 + 51) + 50 + 100 = 50 · 100 + 50 = 50 · (101) = 5050. Satz 2.2.3 (Binomischer Lehrsatz). Seien x, y ∈ R, n ∈ N0. Es gilt der Binomische Lehrsatz: n   n X n (x + y) = xn−k y k. k k=0 Dabei ist   n n! =. k (n − k)!k! Bemerkung 2.2.8. Man kennt den binomischen Lehrsatz aus der Wahrscheinlichkeitsrechnung. Dort ist x = p die Wahrscheinlichkeit, dass ein gewisses Ereignis eintritt und y = (1 − p) die Wahrscheinlichkeit, dass es nicht eintritt. Die Summe x + y = p + 1 − p = 1 ist die Gesamtwahr- scheinlichkeit. Beispiel (n-facher Münzwurf): Hier ist p = 1/2 die Wahrscheinlichkeit für „Zahl” und 1 − p = 1/2 die für „Kopf”. Der Binomialkoeffizient nk gibt die Zahl der Möglichkeiten an,
bei denen k aus n Münzen „Zahl” zeigen. Σ summiert über alle Möglichkeiten, wie oft „Zahl” unter n Würfen geworfen werden kann (von k = 0 bis k = n). 13 Beweis (von Satz 2.2.3). Wir führen die Induktion über n ∈ N0. Induktionsanfang (n = 0):   0   0 0 0 0 X 0 0−k k (x + y) = 1 = x y = x y 0 k k=0 Der Fall n = 0 ist also wahr. Wir können uns interessehalber noch n = 1 anschauen:     1   1 1 1 0 1 0 1 X 1 1−k k (x + y) = x + y = x y + x y = x y 0 1 k k=0 Der Fall n = 1 ist also auch wahr. Pn Induktionsannahme (IA): Wir nehmen nun an, die Aussage (x + y)n = n xn−k y k gilt.
k=0 k Induktionsschritt (n ⇒ n + 1): n   n+1 n X n n−k k (x + y) = (x + y) (x + y) = x y (x + y) k k=0 n   n   n   n   X n n−k k X n n−k k X n n+1−k k X n n−k k+1 = x y x+ x y y= x y + x y k k k k k=0 k=0 k=0 k=0 n   n+1   X n n+1−k k X n = x y + xn+1−l y l k l−1 k=0 l=1 Hier haben wir im zweiten Schritt die Induktionsannahme verwendet und im letzten Schritt die Substitution l := k + 1 (wobei wir nun, da wir richtig substituiert haben, das l auch wieder k nennen können). Nun nutzen wir, dass für jedes k ≥ 1 gilt:     n n n! n! n!(n + 1 − k) + n!k + = + = k k−1 (n − k)!k! (n − (k − 1))!(k − 1)! (n + 1 − k)!k!   (n + 1)! n+1 = =. ((n + 1) − k)!k! k Damit folgt: n   n+1 X  n+1 X n n+1−k k n (x + y) = x y + xn+1−k y k k k−1 k=0 k=1   n       n n+1 0 X n n n+1−k k n 0 n+1 = x y + + x y + x y 0 k k−1 n k=1   n     n + 1 n+1 0 X n + 1 n+1−k k n + 1 0 n+1 = x y + x y + x y 0 k n+1 k=1 n+1 X n + 1  = xn+1−k y k k k=0 14 Wir haben also gezeigt: Aus A(n) wahr, folgt, A(n + 1) wahr. Damit ist die Aussage für alle n ∈ N0 wahr. Bemerkung 2.2.9 (Vollständige Induktion). Statt des Induktionsschrittes n ⇒ n + 1, also statt zu zeigen, dass für gegebenes n die Implikation A(n) ⇒ A(n+1) wahr ist, kann man auch zeigen, dass die Implikation A(k) : k < n ⇒ A(n) wahr ist. Dies ist auch ein gültiger Induktionschritt. In Worten: Man zeigt, dass die Aussage, wenn sie für k < n gilt, auch für n gilt. 2.3 Mengenlehre Man kann die Mengenlehre als den Rahmen oder die Sprache betrachten, in der sich die (moderne) Mathematik begründen und betreiben lässt. Die Mengenlehre wurde durch Cantor eingeführt. Er gab 1895 die folgende Definition einer Menge: Definition 2.3.1 (Menge). Unter eine Menge verstehen wir jede Zusammenfassung M von bestimmten wohlunterschiedenen Objekten m unserer Anschauung oder unseres Denkens (welche die Elemente von M genannt werden) zu einem Ganzen. Bemerkung 2.3.1 (Extensionalitätsprinzip). Eine Menge ist durch ihre Elemente vollständig bestimmt. Bemerkung 2.3.2 (Schreibweise). Wir schreiben: x ∈ M : „x ist ein Element von M ” / M : „x ist kein Element von M ” x∈ Bemerkung 2.3.3 (Russel’sche Antinomie). Man kann zunächst versuchen, die Mengendefini- tion wie folgt zu verstehen (naive Mengenlehre). Sei G die Menge aller Objekte (unserer An- schauung oder unseres Denkens). Sei E(x) eine Eigenschaft von Objekten x aus G. Dann bildet M = {x ∈ G|E(x)} wieder eine Menge, nämlich die Menge aller Objekte x ∈ G mit der Eigenschaft E(x). Man beachte, dass auch M ∈ G, denn G ist ja die Menge aller Objekte. Eine solches Mengenverständnis führt zu Widersprüchen, wie Russel gezeigt hat. Er veröffent- lichte 1903 die sog. Russel’sche Antinomie, das ist „die Menge aller Mengen, die sich selbst nicht enthalten” Formal: R = {x|x ∈ / x} Wäre R ∈ R ⇒ R ∈ / R, was ein Widerspruch ist. Andersherum, falls R ∈ / R ⇒ R ∈ R, was auch ein Widerspruch ist. 15 Dieses Paradoxon zeigt, dass der naive Mengenbegriff nicht widerspruchsfrei ist. Problem ist, dass er von einer fertigen Gesamtheit von Mengen ausgeht. Tatsächlich brauchen wir einen sol- chen Mengenbegriff in der Mathematik nicht. Es reicht, Mengen aus Elementen zu bilden, die bereits gegeben sind. Dies kann man stufenweise tun, z.B. 1. Stufe: ∅, 2. Stufe: ∅, {∅}, 3. Stufe: ∅, {∅}, {{∅}}... (siehe axiomatische Mengenlehre). Beginnen wir mit gegebenen Objekten x, können wir eine Menge M durchaus über ihre Eigen- schaften E(x) definieren und erhalten damit einen direkt Zusammenhang zu den Aussagen. Beispiel 2.3.1. Sei A die Aussage „... ist eine Quadratzahl”, dann ist die zugehörige Menge A = {x ∈ N|A(x)} = {x ∈ N|x = k 2 , k ∈ N} = {1, 4, 9, 16,...} Bemerkung 2.3.4. Bei Mengen kommt es weder auf die Reihenfolge der Elemente an noch darauf, ob Elemente mehrfach aufgezählt werden. So sind die folgenden Mengen ein- und dieselbe: {1, 2, 3} = {3, 1, 2} = {1, 2, 2, 3}. Mengen können auch selbst wieder Mengen enthalten, wie z.B. die Menge M = {1, {1}, {2, 3}}. Dabei sind 1 und {1} verschieden. Beispiel 2.3.2. Bekannte Mengen sind: ∅ oder {}: die leere Menge (sie beinhaltet kein Element) N = {1, 2, 3,...}: die Menge der natürlichen Zahlen Z = {..., −2, −1, 0, 1, 2,...}: die Menge der ganzen Zahlen Q = pq p ∈ Z ∧ q ∈ Z \ {0} : die Menge der rationalen Zahlen  R : die Menge der reellen Zahlen C = {x + iy x ∈ R ∧ y ∈ R}: die Menge der komplexen Zahlen Definition 2.3.2 (Gleichheit von Mengen). Zwei Mengen A und B sind gleich, wenn sie dieselben Elemente enthalten: A=B ⇔ ∀x : x ∈ A ⇔ x ∈ B Definition 2.3.3 (Teilmenge). A ist eine Teilmenge von B, wenn alle Elemente, die in A ent- halten sind, auch in B enthalten sind: A⊆B ⇔ ∀x : x ∈ A ⇒ x ∈ B Wir nennen eine Menge A ⊂ B eine echte Teilmenge von B, wenn B Elemente enthält, die in A nicht vorkommen (A ̸= B). Wir schreiben dann A ⊂ B oder explizit A ⊊ B. Bemerkung 2.3.5. Insbesondere gilt für jede Menge B: ∅ ⊆ B, B ⊆ B. Satz 2.3.1. Für Mengen A, B, C gilt: a) A⊆B∧B ⊆A ⇔ A=B 16  b) A⊆B∧B ⊆C ⇒ A⊆C Beweis. Zu a): A ⊆ B ∧ B ⊆ A ⇔ (∀x : x ∈ A ⇒ x ∈ B) ∧ (∀x : x ∈ B ⇒ x ∈ A) ⇔ ∀x : (x ∈ A ⇒ x ∈ B) ∧ (x ∈ B ⇒ x ∈ A) ⇔ ∀x : (x ∈ A ⇔ x ∈ B) ⇔ A=B Zu b): Analog. Definition 2.3.4 (Potenzmenge). Als Potenzmenge P(A) bezeichnen wir die Menge aller Teil- mengen von A, P(A) = {M |M ⊆ A}. Beispiel 2.3.3. Sei A = {1, 2, 4}. P(A) = P({1, 2, 4}) = {∅, {1}, {2}, {4}, {1, 2}, {1, 4}, {2, 4}, {1, 2, 4}} Definition 2.3.5 (Differenz). Die Differenz B \ A der Mengen B und A ist die Menge aller Elemente, die in B, aber nicht in A liegen: B \ A = {x|x ∈ B ∧ x ∈ / A} = {x ∈ B|x ∈ / A}. Ist A eine Teilmenge von B, dann nennen wir B \ A das Komplement von A in B. Ist B eine nicht eigens zu spezifizierende Grundmenge (im Allgemeinen Ω genannt), dann schreiben wir für das Komplement Ac. Beispiel 2.3.4. Seien B = {1, 3, 5} und A = {1, 5}, dann ist B \ A = {3}. Definition 2.3.6 (Schnitt). Der Schnitt der Mengen A und B ist die Menge aller Elemente, die in A und B liegen: A ∩ B = {x|x ∈ A ∧ x ∈ B} = {x ∈ A|x ∈ B}. Ist A ∩ B = ∅, so nennen wir A und B disjunkt. Beispiel 2.3.5. Seien A = {1, 2}, B = {2, 7, 8} und C = {7, 8, 9}. Dann ist A ∩ B = {2}, B ∩ C = {7, 8} und A ∩ C = ∅, also A und C disjunkt. Definition 2.3.7 (Vereinigung). Die Vereinigung der Mengen A und B ist die Menge aller Elemente, die in A oder B liegen: A ∪ B = {x|x ∈ A ∨ x ∈ B}. 17 Satz 2.3.2 (Rechenregeln für ∩ und ∪). Seien A, B Mengen. Für ∩ und ∪ gelten Kommutativ-, Assoziativ- und Distributivgesetze sowie die De-Morgan-Regeln (A ∩ B)c = Ac ∪ B c und (A ∪ B)c = Ac ∩ B c. Beweis. Dies folgt aus den entsprechenden Rechenregeln für ∧ und ∨ (Übung). Bemerkung 2.3.6 (Notation). Wir können die Definitionen von ∩ und ∪ auf endliche und sogar abzählbar unendliche – mehr zu diesen Begriffen später – Mengen ausdehnen. Seien A1 , A2 ,..., An Mengen, n ∈ N. Dann ist: n \ \ ∞ \ n \ Ai = A1 ∩ A2 ∩... ∩ An und An = An = lim Ai n→∞ i=1 n∈N n=1 i=1 n [ [ ∞ [ n [ Ai = A1 ∪ A2 ∪... ∪ An und An = An = lim Ai n→∞ i=1 n∈N n=1 i=1 Beispiel 2.3.6. Betrachte reelle Intervalle An , Bn ⊆ R (auch Intervalle sind Mengen, nämlich Teilmengen von R). Seien a, b ∈ R, a < b, und n ∈ N. Sei An =]a − 1/n, b + 1/n[. Dann ist m   \ \ 1 1 An = lim a − ,b + = [a, b]. m→∞ n n n∈N n=1 Sei weiter Bn = [a + 1/n, b − 1/n]. Dann ist m   [ [ 1 1 Bn = lim a + ,b − =]a, b[. m→∞ n n n∈N n=1 Definition 2.3.8 (Kartesisches Produkt). Als kartesisches Produkt nicht-leerer Mengen A1 ,..., An bezeichnen wir die Menge aller Folgen der Länge n, sog. n-Tupel (a1 ,.., an ), mit a1 ∈ A1 , a2 ∈ A2 ,..., an ∈ An : A1 × A2 ×... × An = {(a1 , a2 ,..., an )|ai ∈ Ai ∀i = 1,.., n}. Ist Ai = A ∀i = 1,..., n so schreiben wir An := A × A ×.... × A (n-mal). Bemerkung 2.3.7. Bei n-Tupeln kommt es im Unterschied zu Mengen auf die Reihenfolge der Einträge an. So ist (1, 2, 3) ̸= (2, 1, 3) aber {1, 2, 3} = {2, 1, 3}. Bemerkung 2.3.8 (Reelle Folgen). Man kann die Definition des kart. Produkts auf abzählbar unendlich viele Mengen Ak , k ∈ N, ausdehnen. So ist z.B. RN die Menge aller reellen Folgen (a1 , a2 ,...) mit ak ∈ R für alle k ∈ N. Bemerkung 2.3.9 (Historisch). Wir nennen das kartesische Produkt „kartesisch” in Erinnerung an Descartes, der erkannt hat, dass man die Punkte der euklidischen Ebene durch Zahlenpaare 18 (2-Tupel) darstellen kann und die Ebene als kart. Produkt R2 = R × R = {(x, y)|x, y ∈ R}. Analog kann man die Punkte des 3-dim. euklidischen Raums als 3-Tupel darstellen und den 3-dim. Raum als kart. Produkt R3 = R × R × R = {(x, y, z)|x, y, z ∈ R}. Bemerkung 2.3.10 (Paar). Ein 2-Tupel (·, ·) nennt man auch ein Paar. Paare können auch direkt über (Mengen von) Mengen definiert werden. Seien A, B Mengen. Sei A × B = {(a, b) : a ∈ A, b ∈ B}. Dann definieren wir (a, b) := {{a}, {a, b}}. Damit ist (a, b) ⊂ P(A ∪ B) bzw. (a, b) ∈ P(P(A ∪ B)). Explizit: A × B := {x ∈ P(P(A ∪ B))|x = {{a}, {a, b}} mit a ∈ A, b ∈ B}. Achtung: Es gibt keine analoge Definition für n-Tupel mit n ≥ 3! Definition 2.3.9 (Endliche Menge). Eine Menge A heißt endlich, wenn sie nur endlich viele Elemente enthält. Wir bezeichnen die Anzahl der Elemente mit |A|. Beispiel 2.3.7. Sei A = {1, 2, 4, 7, 9}. Dann ist |A| = 5. Bemerkung 2.3.11 (Mächtigkeit). Später betrachten wir auch unendliche Mengen wie N, Q und R. Dann verallgemeinert sich der Ausdruck „Anzahl der Elemente” auf den Begriff der „Mächtigkeit”. Auch für ihn schreiben wir |A|. Satz 2.3.3. Seien A1 ,..., An endliche Mengen. Dann gilt: |A1 × A2... × An | = |A1 | · |A2 | ·... · |An |. Beweis. Wir suchen die Anzahl an n-Tupeln (a1 ,..., an ) mit ai ∈ Ai ∀i = 1,..., n. Dabei gibt es |A1 | Möglichkeiten a1 zu wählen. Für jede dieser |A1 | Möglichkeiten gibt es |A2 | Möglichkeiten a2 zu wählen, für jede dieser |A1 | · |A2 | Möglichkeiten gibt es |A3 | Möglichkeiten a3 zu wählen usw. Damit erhält man genau die oben stehende Produktregel. Satz 2.3.4. Seien A, B und C endliche Mengen. Dann gilt: a) |A ∪ B| = |A| + |B| − |A ∩ B|, b) |A ∪ B ∪ C| = |A| + |B| + |C| − |A ∩ B| − |A ∩ C| − |B ∩ C| + |A ∩ B ∩ C|. 19 Seien A1 ,..., An , n ∈ N, endliche Mengen. Dann gilt das sog. Inklusions-Exklusions-Prinzip: n [ X \ c) Ai = (−1)|I|−1 Ai. i=1 I: i∈I ∅̸=I⊆{1,...,n} Beispiel 2.3.8 (Zu c)). Sei n = 7. Dann sind mögliche Indexmengen die Mengen I1 , I2 , I3 ⊆ {1, 2, 3,..., 6, 7} mit I1 = {2, 5}, I2 = {1, 2, 4, 6, 7} und I3 = {3}. In diesem Fall ist |I1 | = 2, |I2 | = 5 sowie |I3 | = 1. Weiter ist Ai = A2 ∩ A5 und T i∈I1 i∈I2 Ai = A1 ∩ A2 ∩ A5 ∩ A6 ∩ A7 und i∈I3 Ai = A3. T T Beweis. Zu a) Anschaulich: Wenn wir alle Elemente aus A und aus B zusammenzählen, zählen wir genau die Elemente doppelt, die in A ∩ B enthalten sind. Die müssen wir wieder abziehen, wenn wir die Anzahl an Elementen bestimmen wollen, die in A ∪ B enthalten sind. Formal: Für zwei endliche Mengen A und B gilt: A ∪ B = (A \ B) ∪ (A ∩ B) ∪ (B \ A), wobei A \ B, A ∩ B und B \ A disjunkte Mengen sind. Das heißt: |A ∪ B| = |A \ B| + |A ∩ B| + |B \ A| Weiter sind A \ B und A ∩ B disjunkt und (A \ B) ∪ (A ∩ B) = A, d.h. |A \ B| + |A ∩ B| = |A| und analog für B, d.h. |B| = |B \ A| + |A ∩ B|. Es folgt: |A ∪ B| = |A| + |B| − |A ∩ B|. Falls A, B disjunkt, dann ist A ∩ B = ∅ und |∅| = 0. Folglich ist dann: |A ∪ B| = |A| + |B|. Zu b): Die Aussage b) folgt direkt aus a) und den Rechengesetzen: |A ∪ B ∪ C| = |A ∪ B| + |C| − |(A ∪ B) ∩ C| = |A| + |B| − |A ∩ B| + |C| − |(A ∩ C) ∪ (B ∩ C)| = |A| + |B| + |C| − |A ∩ B| − |A ∩ C| − |B ∩ C| + |A ∩ B ∩ C|. Zu c): Wir beweisen nun mittels vollständiger Induktion, dass sich die Relation auf beliebige, ja sogar abzählbar unendliche Vereinigungen von Mengen ausgeweitet werden kann. Wir führen die Induktion über n ∈ N und beginnen mit dem Induktionsanfang n = 1. Für n = 1 gilt: | i=1 Ai | = |A1 | = (−1)1−1 | i=1 Ai |. Das stimmt also. S T Wir betrachten nun den Induktionsschritt von n auf n + 1 unter der Induktionsannahme, dass die Relation für n stimmt. 20  [ [  [  Ai = Ai + |An+1 | − Ai ∩ An+1 i∈{1,...,n+1} i∈{1,...,n} i∈{1,...,n} [ [ = Ai + |An+1 | − (Ai ∩ An+1 ) i∈{1,...,n} i∈{1,...,n} X \ X \ = (−1)|I|−1 Ai + |An+1 | − (−1)|J|−1 (Aj ∩ An+1 ) I: i∈I J: j∈J ∅̸=I⊆{1,...,n} ∅̸=J⊆{1,...,n} X \ \ = (−1)|I|−1 Ai + (−1)|{n+1}|−1 Ai ∅̸=I⊆{1,...,n+1} i∈I i=n+1 n+1∈I/ X \ + (−1)|J∪{n+1}|−1 Aj J: j∈(J∪{n+1}) ∅̸=J⊆{1,...,n} X \ = (−1)|I|−1 Ai. I: i∈I ∅̸=I⊆{1,...,n+1} Hier haben wir im dritten Schritt die Induktionsannahme gleich doppelt verwendet. Im letzten Schritt haben wir erkannt, dass der erste der drei verbleibenden Terme über alle Indexmengen I summiert, die n + 1 nicht enthalten, der letzte über alle, die n + 1 und mindestens ein weiteres i ∈ I enthalten, während der mittlere Term genau den noch fehlenden Term darstellt, der nur über die einelementige Indexmenge I = {n + 1} „summiert”. 2.4 Relationen Definition 2.4.1 (Relation). Seien X, Y Mengen, R ⊆ X × Y. Das Tripel R := (X, Y, R) heißt (zweistellige) Relation zwischen (Elementen von) X und (Elementen von) Y. Formal: x∼y :⇔ (x, y) ∈ R. Statt (X, Y, R) schreiben wir auch (X, Y, ∼). Falls Y = X, spricht man von einer Relation auf X. In dem Fall schreibt man (X, ∼) statt (X, X, ∼). Beispiel 2.4.1. R1 = (R, ≤), R2 = (R, >) und R3 = (R, =) sind Relationen auf R. Die zugehörigen Mengen sind R1 = {(x, y) ∈ R2 |x ≤ y}, R2 = {(x, y) ∈ R × R|x > y} und R3 = {(x, y) ∈ R × R|x = y}. Eine wichtige Art von Relationen sind Äquivalenzrelationen. 21 Definition 2.4.2 (Äquivalenzrelation). Eine Relation (X, ∼) heißt Äquivalenzrelation, wenn gilt: 1) ∀x ∈ X : x ∼ x (reflexiv) 2) ∀x, y ∈ X : x ∼ y ⇔ y ∼ x (symmetrisch) 3) ∀x, y, z ∈ X : x∼y∧y ∼z ⇒x∼z (transitiv) Die Äquivalenzrelation ist eine Abschwächung der Gleichheitsrelation. Insbesondere ist die Gleich- heitsrelation selbst eine Äquivalenzrelation, wie der folgende Satz zeigt. Satz 2.4.1. (X, =) ist eine Äquivalenzrelation. Beweis. Alle drei Bedingungen sind erfüllt: 1) ∀x ∈ X : x = x (reflexiv) 2) ∀x, y ∈ X : x = y ⇔ y = x (symmetrisch) 3) ∀x, y, z ∈ X : x=y∧y =z ⇒x=z (transitiv) Wir betrachten ein weiteres wichtiges Beispiel. Satz 2.4.2. Seien x, y ∈ Z und m ∈ N. Die Relation (Z, ∼) mit x∼y ⇔ m|(x − y) ist eine Äquivalenzrelation. Hier steht m|(x − y) für „m teilt (x − y)”. Beweis. Wir prüfen die drei Bedingungen: 1) ∀x ∈ Z : m|(x − x) ⇔ m|0 und m|0 ist wahr (reflexiv) 2) ∀x, y ∈ Z : m|(x − y) ⇔ m|(−1)(x − y) ⇔ m|(y − x) (symmetrisch) 3) ∀x, y, z ∈ Z : m|(x − y) ∧ m|(y − z) ⇒ m|((x − y) + (y − z)) ⇔ m|(x − z) (transitiv) Begründung für „⇒” in 3): Weil m|(x − y), ∃k ∈ Z mit (x − y) = k · m und weil m|(y − z), ∃l ∈ Z mit (y − z) = l · m. Es folgt: (x − y) + (y − z) = k · m + l · m = (k + l) · m. Folglich ∃p ∈ Z, nämlich p := k + l, mit (x − y) + (y − z) = p · m und somit m|((x − y) + (y − z)). Die im letzten Satz gezeigte Relation ist bekannt als Kongruenz modulo. Definition 2.4.3 (Kongruenz modulo). Seien x, y ∈ Z und m ∈ N. Die Relation x ≡ y mod m :⇔ m|(x − y) heißt Kongruenz modulo. Wir sagen „x kongruent y modulo m”. Beispiel 2.4.2. Es ist 7 ≡ 2 mod 5 und 7 ≡ −2 mod 3. 22 Der Begriff der Äquivalenzrelation bringt mit sich den Begriff der Äquivalenzklasse. Definition 2.4.4 (Äquivalenzklasse). Sei (X, ∼) eine Äquivalenzrelation und a ∈ X. Die Menge [a] := {x ∈ X|x ∼ a} heißt Äquivalenzklasse von a. Bemerkung 2.4.1 (Repräsentant der Äquivalenzklasse). Es reicht also, für jede Menge zu- einander äquivalenter Elemente (i.e. für jede Äquivalenzklasse) einen einzigen Repräsentanten a anzugeben. (Hätte man etwa die Äquivalenzklassen „Hund” und „Katze”, so würde je ein einzelner Hund bzw. eine einzelne Katze reichen, um die entsprechende Klasse zu spezifizieren bzw. zu repräsentieren). Beispiel 2.4.3. Betrachte (X, =). Die Äquivalenzklasse von a ∈ X ist gegeben durch [a] = {a}. Beispiel 2.4.4. Seien a, b ∈ Z, m ∈ N. Betrachte (Z, ∼) mit a ∼ b ⇔ m|(a − b). In dem Fall ist die Äquivalenzklasse zu a gegeben durch [a] = {z ∈ Z| m|(z − a)} = {z ∈ Z|∃k ∈ Z : z − a = k · m} = {z ∈ Z|∃k ∈ Z : z = a + k · m} = {a + k · m|k ∈ Z} =: a + mZ Hier ist mZ := {k · m|k ∈ Z} = {..., −2m, −m, 0, m, 2m,...} die Menge aller ganzzahligen Vielfachen von m. Weil ∀k ∈ Z : [a] = [a + k · m] , gibt es nur m (paarweise) verschiedene Äquivalenzklassen: , , ,..., [m − 1]. Man bezeichnet diese Klassen auch als „Restklassen” (denn die Zahlen einer Klasse liefern bei Division durch m denselben Rest!) und schreibt für ihre Menge: Zm := {m , m , m ,..., [m − 1]m }. Hat man einmal festgelegt, dass man auf Zm rechnet, kann man die eckigen Klammern auch wieder weglassen und schreibt dann wieder 1 statt oder m. Bemerkung 2.4.2 (Quotientenraum). Zm definiert einen sog. Quotientenraum, Zm =: Z/mZ. Satz 2.4.3. Sei (X, ∼) eine Äquivalenzrelation und a, b ∈ X. Dann ist entweder [a] = [b] (falls a ∼ b) oder [a] ∩ [b] = ∅ (falls a ≁ b). 23 Beweis. Es gibt nur zwei mögliche Fälle, entweder a ∼ b oder a ≁ b. 1. Fall: Sei a ∼ b. Für jedes x ∈ [a] gilt: x ∼ a und a ∼ b, also x ∼ b wegen Transitivität. Damit ist x ∈ [b], also [a] ⊆ [b]. Analog folgt, mit a ∼ b ⇔ b ∼ a (Symmetrie), dass [b] ⊆ [a] und damit [a] = [b]. 2. Fall: Sei a ≁ b. Angenommen [a] ∩ [b] ̸= ∅. Dann ∃x ∈ X mit x ∈ [a] ∩ [b]. Also x ∼ a und x ∼ b. Wegen Symmetrie auch a ∼ x. Aus a ∼ x und x ∼ b folgt mit Transitivität: a ∼ b. Dies ist ein Widerspruch, folglich muss [a] ∩ [b] = ∅ gelten. Definition 2.4.5 (Umkehrrelation). Sei R = (X, Y, R) eine Relation. Das Tripel R−1 := (Y, X, R−1 ) mit R−1 = {(y, x) ∈ Y × X|(x, y) ∈ R} heißt Umkehrrelation. Bemerkung 2.4.3 (Existenz der Umkehrrelation). Die Umkehrrelation ist selbst wieder eine Relation. Im Unterschied zur Umkehrfunktion existiert die Umkehrrelation immer (R−1 beinhal- tet ja einfach die Paare mit „vertauschten” Einträgen.) Beispiel 2.4.5. Sei X = {1, 2, 3} und Y = {1, 2, 3, 4, 5} und R = (X, Y, R) mit R = {(1, 5), (2, 3), (2, 4), (2, 5)}. Dann ist die Umkehrrelation gegeben durch R−1 = (Y, X, R−1 ) mit R−1 = {(5, 1), (3, 2), (4, 2), (5, 2)}. Man kann sich bildlich z.B. vorstellen, X sei eine Menge von Personen und Y eine Menge von Eissorten und (x, y) ∈ R besagt „x mag Eissorte y”. Dann gibt es zwei Eissorten, die von nie- manden gemocht werden (1 und 2) und eine Person (3), die kein Eis mag. Dazu gibt es natürlich eine Umkehrrelation R−1 und (y, x) ∈ R−1 besagt, dass „y von x gemocht wird”. (Man beachte: Im Unterschied zu Funktionen beschreiben R und R−1 keine eindeutigen Abbildungen, z.B. wird 2 ∈ X von R auf 3, 4, 5 ∈ Y abgebildet und 5 ∈ Y von R−1 auf 1, 2 ∈ X.) 2.5 Abbildungen (Funktionen) Definition 2.5.1 (Abbildung/Funktion). Wir nennen eine Relation f = (X, Y, R) eine Abbildung oder Funktion genau dann, wenn gilt: ∀x ∈ X ∃! y ∈ Y : (x, y) ∈ R Hier bedeutet ∃!: „es existiert genau ein”. Wir nennen y den Funktionswert von f and der Stelle x und schreiben y = f (x). Statt f = (X, Y, R) schreiben wir f : X → Y. Wir nennen X den Definitionsbereich, Y den Wertebereich und R = Gf den Graph von f. 24 Definition 2.5.2 (Bild, Urbild). Sei f : X → Y eine Abbildung, A ⊆ X, B ⊆ Y. Die Menge f (A) := {f (x)|x ∈ A} = {y ∈ Y |∃x ∈ A : f (x) = y} heißt Bild von A unter f. Die Menge f −1 (B) := {x ∈ X|f (x) ∈ B} = {x ∈ X|∃y ∈ B : f (x) = y} heißt Urbild von B unter f. Bemerkung 2.5.1. Insbesondere ist demnach f (A) ⊆ Y unf f −1 (B) ⊆ X. Beispiel 2.5.1 (Bild, Urbild). Betrachte f : R → R, f (x) = x2. Seien A = [−1, 1] ⊆ R und B = [1, 4] ⊆ R. Dann ist f (A) = [0, 1] das Bild von A und f −1 (B) = [−2, −1] ∪ [1, 2] das Urbild von B unter f. Definition 2.5.3 (Verkettung). Seien f : X → Y und g : Y → Z Abbildungen. Dann heißt die Abbildung X → Z, x → g(f (x)) Verkettung von g und f. Wir schreiben dafür g ◦ f. Satz 2.5.1 (Assoziativgesetz). Seien f : W → X, g : X → Y, h : Y → Z Funktionen. Dann gilt: (h ◦ g) ◦ f = h ◦ (g ◦ f ) und dies ist eine Abbildung von W nach Z. Beweis. Wiederholte Anwendung der Definition (Übung). Beispiel 2.5.2 (Verkettung). Sei f : R → R, f (x) = x2 + 2 und g : R → R, g(x) = 3x − 5. Dann ist: g ◦ f : R → R, (g ◦ f )(x) = g(f (x)) = 3(x2 + 2) − 5 = 3x2 + 1 Weiter gilt: f ◦ g : R → R, (f ◦ g)(x) = f (g(x)) = (3x − 5)2 + 2 = 9x2 − 30x + 27 Achtung: Auch wenn X = Y = Z ist, so ist i. A. f ◦ g ̸= g ◦ f (also ◦ i. A. nicht kommutativ)! Definition 2.5.4 (Injektivität, Surjektivität, Bijektivität). Sei f : X → Y eine Abbildung. f heißt injektiv ⇔ ∀x, x′ ∈ X : x ̸= x′ ⇒ f (x) ̸= f (x′ ) (oder äquivalent als Kontraposition: f injektiv ⇔ f (x) = f (x′ ) ⇒ x = x′ ) surjektiv ⇔ ∀y ∈ Y : ∃x ∈ X mit y = f (x) (oder kurz: f (X) = Y ) bijektiv ⇔ f injektiv und surjektiv Bemerkung 2.5.2. Wir nennen eine bijektive Abbildung auch eine 1:1-Abbildung. 25 Beispiel 2.5.3 (Injektivität, Surjektivität, Bijektivität). Die Funktion f : R → R+ 0 , x 7→ x ist 2 nicht injektiv, denn f (1) = f (−1) (genauer: für x = 1, x′ = −1 gilt: x ̸= x′ , aber f (x) = f (x′ ), √ also f nicht injektiv), aber f surjektiv, denn ∀y ∈ R+0 : ∃x ∈ R mit x = y, nämlich x = 2 y (und die Wurzel ist wohldefiniert, weil y ∈ R+ 0 ). Wir führen noch drei spezielle Funktionen ein. Definition 2.5.5 (Identität, Einbettung, Einschränkung). Sei X eine Menge. Die Abbildung idX : X → X, x→x heißt Identität. Sei A ⊆ X. Die Abbildung iA : A → X, x→x heißt Einbettung (Inklusion) von A in X. Sei Y eine Menge, f : X → Y eine Funktion. Die Abbildung f |A : A → Y, x → f (x) heißt Einschränkung (Restriktion) von f auf A. Bemerkung 2.5.3. Insbesondere ist demnach iA = idX |A. Beispiel 2.5.4 (Einschränkung). Man betrachte wieder die Funktion f : R → R+ 0 , x 7→ x. Diese 2 0 → R0 , x 7→ x ist injektiv und Funktion ist nicht injektiv, aber die Einschränkung f |R+ : R+ + 2 0 surjekiv, also bijektiv. Satz 2.5.2. Seien f : X → Y und g : Y → Z Abbildungen. Dann gilt: 1) g ◦ f injektiv ⇒ f injektiv 2) g ◦ f surjektiv ⇒ g surjektiv Beweis. 1) g ◦ f injektiv. Aus f (x) = f (x′ ) folgt g(f (x)) = g(f (x′ )), weil g eine Funktion. Daraus folgt, weil g ◦ f injektiv, dass x = x′. Wir haben also gezeigt: f (x) = f (x′ ) ⇒ x = x′ , also f injektiv. 2) g ◦ f surjektiv. Es gilt g(Y ) ⊆ Z, weil g : Y → Z. Noch z. zg.: Z ⊆ g(Y ). Weil g ◦ f surjektiv, ist (g ◦ f )(X) = g(f (X)) = Z. Aber f (X) ⊆ Y und damit g(f (X)) ⊆ g(Y ), weil g Funktion, also Z ⊆ g(Y ). Aus g(Y ) ⊆ Z und Z ⊆ g(Y ) folgt Z = g(Y ), also g surjektiv. Definition 2.5.6 (Umkehrfunktion). Eine Abbildung g : Y → X heißt Umkehrabbildung oder Umkehrfunktion von f : X → Y genau dann, wenn gilt: 1) g ◦ f = idX , d.h. g(f (x)) = x ∀x ∈ X und 2) f ◦ g = idY , d.h. f (g(y)) = y ∀y ∈ Y 26 Wir schreiben dann: g =: f −1. Beispiel 2.5.5. Betrachte f : R → R, f (x) = 3x + 5. Für die Umkehrfunktion f −1 muss gelten f ◦ f −1 = idY , also: y−5 f (f −1 (y)) = y ⇒ 3f −1 (y) + 5 = y ⇒ f −1 (y) = 3 Wir überprüfen, ob f −1 das notwendige Kriterium f −1 ◦ f = idX erfüllt: f (x) − 5 3x + 5 − 5 f −1 (f (x)) = = = x, also f −1 ◦ f = idX 3 3 Satz 2.5.3 (Umkehrfunktion). Falls die Umkehrfunktion f −1 existiert, so ist sie eindeutig und bijektiv. Auch f ist in dem Fall bijektiv. Beweis. Bijektivität von f, f −1 : Weil idX bijektiv ⇒ f −1 ◦ f bijektiv ⇒ f injektiv, f −1 surjektiv. Weil idY bijektiv ⇒ f ◦ f −1 bijektiv ⇒ f −1 injektiv, f surjektiv. ⇒ f, f −1 bijektiv Eindeutigkeit von f −1 : Seien f1−1 : Y → X und f2−1 : Y → X zwei verschiedene Umkehrfunktionen zu f. Dann gilt für jedes x ∈ X: f1−1 (f (x)) = x ∧ f2−1 (f (x)) = x Weil f surjektiv, d.h. f (X) = Y , existiert für jedes y ∈ Y ein x ∈ X mit y = f (x). Also ist f1−1 (y) = f2−1 (y) für jedes y ∈ Y (wäre f nicht surjektiv, könnte es y ∈ Y geben, auf denen f1−1 und f2−1 nicht übereinstimmen). Folglich f1−1 = f2−1. Satz 2.5.4 (Eigenschaften von f −1 ). Seien f : X → Y und g : Y → Z Funktionen. Es gilt: 1) f bijektiv ⇔ f besitzt eine Umkehrfunktion 2) f bijektiv ⇒ f −1 bijektiv und (f −1 )−1 = f 3) f, g bijektiv ⇒ g ◦ f bijektiv und (g ◦ f )−1 = f −1 ◦ g −1 Beweis. 1) „⇐” wurde bereits gezeigt (siehe Satz 2.5.3). „⇒”: Weil f surjektiv ist, existiert ∀y ∈ Y ein x ∈ X mit f (x) = y, und weil f injektiv ist, ist dieses x sogar eindeutig (denn für x, x′ ∈ X mit f (x) = y und f (x′ ) = y folgt, wegen f (x) = f (x′ ), dass x = x′ ), also: ∀y ∈ Y ∃!x ∈ X : f (x) = y. Aber dies definiert genau eine Funktion f −1 : Y → X, f −1 (y) := x. Dies ist die Umkehrfunktion, denn sie erfüllt: f (f −1 (y)) = y für alle y ∈ Y und f −1 (f (x)) = x für alle x ∈ X. Anschaulich: Im Fall einer bijektiven Funktion f : X → Y , dargestellt durch Pfeile von X nach Y , endet bei jedem Element in Y genau ein Pfeil. Dreht man diesen Pfeil um, so 27 endet bei jedem Element in X genau ein Pfeil. Dies ist die (wieder bijektive) Umkehrabbildung (Umkehrfunktion). 2) Dass f −1 existiert, folgt aus 1). Daraus folgt, dass f −1 bijektiv ist (siehe Satz 2.5.3). Wir erhalten außerdem aus Satz 2.5.3, dass f −1 eindeutig ist. Daraus folgt, dass (f −1 )−1 = f (denn f ist ja nach Definition der Umkehrfunktion bereits Umkehrfunktion zu f −1 ). 3) Aus der Definition der Umkehrfunktion und der Assoziativität der Verkettung (siehe Satz 2.5.1) folgt: (f −1 ◦ g −1 ) ◦ (g ◦ f ) = f −1 ◦ (g −1 ◦ g) ◦ f = f −1 ◦ idY ◦ f = f −1 ◦ f = idX. Anders herum gilt: (g ◦ f ) ◦ (f −1 ◦ g −1 ) = g ◦ (f ◦ f −1 ) ◦ g −1 = g ◦ idY ◦ g −1 = g ◦ g −1 = idZ. f −1 ◦ g −1 ist also Umkehrfunktion von g ◦ f und weil sie existiert, ist sie auch eindeutig und bijektiv und g ◦ f ist auch bijektiv (siehe Satz 2.5.3). 2.6 Unendliche Mengen Definition 2.6.1 (Gleichmächtigkeit). Eine Menge M heißt gleichmächtig zu einer anderen Menge N genau dann, wenn eine bijektive Abbildung ϕ : M → N existiert. Wir schreiben dann: |M | = |N |. Wir können nun den Begriff der endlichen Menge präzisieren und den Begriff der unendlichen Menge einführen: Definition 2.6.2 (Endliche, abzählbar und überabzählbar unendliche Mengen). Sei M eine nicht-leere Menge und n ∈ N. Dann gilt: 1) |∅| = 0 2) M hat n Elemente (d.h. |M | = n) ⇔ ∃ϕ : {1,..., n} 7→ M bijektiv 3) M heißt endlich ⇔ ∃n ∈ N mit |M | = n (sonst heißt M unendlich) 4) M heißt abzählbar unendlich ⇔ M gleichmächtig zu N (d.h. |M | = |N|) 5) M heißt überabzählbar unendlich ⇔ M nicht endlich und M nicht abzählbar unendlich Bemerkung 2.6.1 (N bzw. N0 ). Sei M gleichmächtig zu N. Ist |M | = |N|, so ist |M | = |N0 |, denn weil ϕ : M → N bijektiv und ϕ′ : N → N0 , n → n − 1 bijektiv, so ist auch ϕ′ ◦ ϕ : M → N0 bijektiv. In dem Fall: |M | = |N| = |N0 |. Bemerkung 2.6.2. Für endliche Mengen gilt: Wenn M ⊆ N und |M | = |N |, dann folgt M = N. Achtung: Dies gilt nicht für (abzählbar oder überabzählbar) unendliche Mengen! 28 Beispiel 2.6.1. Betrachte N und 3N = {n ∈ N|n = 3k, k ∈ N} = {3, 6, 9, 12,..}. Dann gilt: 3N ⊂ N und |3N| = |N| (denn es existiert ϕ : N → 3N, n → 3n bijektiv), aber 3N ̸= N. Satz 2.6.1. N, Z und Q sind abzählbar unendlich. Beweis. N ist trivialer Weise abzählbar (unendlich), denn ϕ = idN : N → N, n → n ist bijektiv. Z ist abzählbar (unendlich), denn es existiert eine bijektive Abbildung 1 − (−1)n (2n + 1) ϕ′ : N0 → Z : n →. 4 Damit werden die ganzen Zahlen anschaulich wie folgt „abgezählt”: 0 1 2 3 4 5 6... 0 +1 –1 +2 –2 +3 –3... Dass Q abzählbar (unendlich) ist, folgt aus einer ähnlichen Überlegung wie im Fall von Z sowie einer besonderen „Abzählung”. Diese Abzählung ist bekannt als Cantors erstes Diagonalargument. Sie geht wie folgt:   1 1 1 1 → 2 3 → 4...     ↙ ↗ ↙   2 2 2... 1 2 3    ↓ ↗ ↙    3 3...... 1 2      ↙   4......... 1    ↓ ........  .... Zur Abzählung aller rationalen Zahlen Q werden die nicht vollständig gekürzten Brüche übersprungen, die 0 wird hinzugefügt und nach jeder positiven rationalen Zahl wird die entsprechend negative rationale Zahl eingefügt. Damit ergibt sich: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14... 0 +1 –1 + 12 – 12 +2 –2 +3 –3 + 1 3 – 31 + 1 4 – 14 + 2 3 – 23... Die Menge der Primzahlen P ist eine weitere bekannte Menge, die abzählbar unendlich ist. Definition 2.6.3 (Primzahl). p ist Primzahl :⇔ p ∈ N, p ≥ 2 und ∀a ∈ N : a|p ⇒ a = 1 ∨ a = p. 29 Satz 2.6.2. Die Menge der Primzahlen P ist abzählbar unendlich, d.h. |P| = |N|. Beweis. Einerseits gilt: P ⊂ N (echte Teilmenge), d.h. |P| ≤ |N|. Andererseits gilt: Es gibt unend- lich viele Primzahlen (Übung). Daraus folgt: |P| = |N|. Insbesondere können wir die Primzahlen P als Teilmenge von N der Größe nach anordnen (siehe Bem. 2.2.2 zum Wohlordnungsprinzip von N) mit p1 < p2 < p3 <.... Damit können wir die Primzahlen „abzählen”, d.h. ∃ ϕ bijektiv: N → P, i → pi. Tatsächlich gibt es aber auch Mengen, die überabzählbar unendlich sind. Welche Mengen sind überabzählbar unendlich? Wie kann man das zeigen? Satz 2.6.3. Die Menge der reellen Zahlen R ist überabzählbar unendlich, d.h. |R| > |N|. Beweis. Cantors zweites Diagonalargument (Übung). Bemerkung 2.6.3 (ℵ, Kontinuumshypothese). Cantor zeigt also: |R| > |N|. Wir bezeichen die Mächtigkeit von unendlichen Mengen mit dem hebräischen Buchstaben „Aleph”. Für die kleinste solche Menge schreiben wir: |N| = ℵ0. Wie groß ist |R|? Ist |R| = ℵ1 , also die nächstgrößere Menge? Diese These nennt man die Kontinuumshypothese. Sie stammt von Cantor selbst. Oder gibt es dazwischen noch etwas, also eine Menge M , deren Mächtigkeit zwischen der von N und R liegt: |N| < |M | < |R|? Gödel beweist 1938: Die Kontinuumshypothese lässt sich auf Basis der axiomatischen Mengen- lehre nicht widerlegen. Cohen zeigt 1960: Die Kontinuumshypothese lässt sich auf Basis der axio- matischen Mengenlehre nicht beweisen. Dies ist ein Beispiel für die Gültigkeit der Gödelschen Unvollständigkeitssätze. Satz 2.6.4. Die Mächtigkeit von R ist gleich der Mächtigkeit der Menge der 0-1-Folgen. Insbe- sondere ist die Menge der 0-1-Folgen also auch überabzählbar unendlich. Beweis. Man zeigt Gleichmächtigkeit, indem man zeigt, dass es eine 1:1-Abbildung zwischen beiden Mengen gibt. Dazu wechselt man von der Darstellung reller Zahlen im Dezimalsystem zur Darstellung reeller Zahlen im Binärsystem. Jedes r ∈ (0, 1) lässt sich im Binärsystem in der Form 0, d1 d2 d3.... mit dk ∈ {0, 1} für alle k ∈ N schreiben. Explizit: ∞ X 1 1 1 1 r= dk 2−k = d1 · + d2 · + d3 · + d4 · +... 2 4 8 16 k=1 Eine im Binärsystem dargestellte Zahl ist z. B. 0, 00101100001.... So kann man jede reelle Zahl r ∈ (0, 1) mit einer 0-1-Folge identifizieren (und dieses Argument erweitert sich auf ganz R, denn für r ∈ / (0, 1) kommen zu der unendlichen 0-1-Folge nur endlich viele Folgeglieder hinzu). Es gibt also eine 1:1-Abbildung zwischen R und der Menge der 0-1-Folgen. Bemerkung 2.6.4 (Exkurs zum Binärsystem). Betrachten wir zuerst N. Heutzutage werden natürliche Zahlen n ∈ N im Dezimalsystem dargestellt, d.h. in der Form cm...c3 c2 c1 c0 mit ci ∈ 30 {0,..., 9} für alle 0 ≤ i ≤ m (hier ist ci die Ziffer der Zahl an der i-ten Stelle). Der Wert der Zahl ist in dem Fall m X n= ci · 10i i=0 mit m ∈ N, ci ∈ {0,..., 9}. Dieselben Zahlen können im Binärsystem dargestellt werden in der Form dl...d3 d2 d1 d0 mit dk ∈ {0, 1} für alle 0 ≤ k ≤ l. Der Wert der Zahl ist in dem Fall l X n= dk · 2k k=0 mit l ∈ N, dk ∈ {0, 1}. Im Vergleich ergibt sich für die Zahlen: Dezimalsystem 0 1 2 3 4 5 6... Binärsystem 0 1 10 11 100 101 110... Im Unterschied zu natürlichen Zahlen gehen bei reellen Zahlen in der obigen Darstellung als Summe auch negativen Indizes ein, wobei die Summe bei rationalen Zahlen nach endlich vielen (negativen) Gliedern abbricht oder sich wiederholt (z. B. ist 1 5 im Binärsystem 0, 0011). Für 0: irrationale Zahlen bricht die Summe nie ab und wiederholt sich nie. D.h. allgemein für r ∈ R+ m X r= dk · 2k k=−n mit n ∈ N oder n → ∞. 31 3 Gruppen, Ringe, Körper 3.1 Gruppen Definition 3.1.1 (Verknüpfung). Sei M eine Menge. Eine Verknüpfung ◦ auf M ist eine Abbil- dung ◦ : M × M → M, (a, b) → a ◦ b. Bemerkung 3.1.1. Verknüpfungen sind etwa die Addition „+” und Multiplikation „·” auf N. Achtung: Die Subtraktion „–” und Division „:” sind keine Verknüpfungen auf N! Definition 3.1.2 (Gruppe). Eine Menge G mit einer Verknüpfung ◦ heißt Gruppe (G, ◦) genau dann, wenn gilt: 1) ∀a, b, c ∈ G : (a ◦ b) ◦ c = a ◦ (b ◦ c) („Assoziativgesetz”) 2) ∃e ∈ G, sodass ∀a ∈ G : a ◦ e = e ◦ a = a („Existenz eines neutralen Elements”) 3) ∀a ∈ G ∃a−1 ∈ G: a ◦ a−1 = a−1 ◦ a = e („Existenz eines inversen Elements zu a”) (G, ◦) heißt abelsche oder kommutative Gruppe, wenn zusätzlich gilt: 4) ∀a, b ∈ G : a ◦ b = b ◦ a („Kommutativgesetz”) Bemerkung 3.1.2. Tatsächlich genügt in dieser Definition die Existenz eines rechtsneutralen und rechtsinversen Elements (oder analog eines linksneutralen und linksinversen Elements): 2’) ∃e ∈ G, sodass ∀a ∈ G : a ◦ e = a („Existenz eines rechtsneutralen Elements”) 3’) ∀a ∈ G ∃a−1 ∈ G : a ◦ a−1 = e („Existenz eines rechtsinversen Elements”) Beispiel 3.1.1. (Z, +), (Q, +), (R, +) sind abelsche Gruppen. Neutrales Element ist jeweils e = 0 und inverses Element zu a ist −a. Dagegen ist (N, +) keine Gruppe (∄ inverses Element). (Q \ {0}, ·), (R \ {0}, ·) sind abelsche Gruppen. Neutrales Element ist jeweils e = 1 und inverses Element zu a ist a1. Dagegen ist (Z \ {0}, ·) keine Gruppe (∄ inverses Element). (Zn , +), (Qn , +), (Rn , +) mit der komponentenweise definierten Addition (a1 ,..., an ) + (b1 ,..., bn ) := (a1 + b1 ,..., an + bn ) sind abelsche Gruppen. Neutrales Element ist e = (0,..., 0) und inverses Element zu (a1 ,..., an ) ist (−a1 ,..., −an ). Satz 3.1.1 (Eindeutigkeit e und a−1 ). Das neutrale Element e einer Gruppe ist, sofern es existiert, eindeutig. Ebenso ist das inverse Element a−1 zu a, sofern es existiert, eindeutig. Beweis. Angenommen e und e′ sind neutrale Elemente. Dann gilt: e ◦ e′ = e′ ◦ e = e′ (weil e neutrales Element) und e′ ◦ e = e ◦ e′ = e (weil e′ neutrales Element). Folglich: e = e′. 32  Sei a−1 inverses Element zu a. Angenommen a′−1 ist weiteres inverses Element zu a. Dann gilt: a ◦ a′−1 = a′−1 ◦ a = e. Damit folgt (unter Verwendung der Gruppenaxiome): a−1 = a−1 ◦ e = a−1 ◦ (a ◦ a′−1 ) = (a−1 ◦ a) ◦ a′−1 = e ◦ a′−1 = a′−1. Definition 3.1.3 (Permutationsgruppe). Sei M = {1,..., n}. Man nennt die Menge der bijekti- ven Abbildungen auf M , i.e. Sn := {ϕ : M → M bijektiv}, zusammen mit der Funktionsverket- tung ◦ die Permutationsgruppe. Die bijektiven Abbildungen ϕ : {1,..., n} → {1,..., n}, i → ϕ(i) nennt man Permutationen. Bemerkung 3.1.3. Die Permutationsgruppe erfüllt die Gruppenaxiome (Übung). Satz 3.1.2. Für die Mächtigkeit von Sn gilt: |Sn | = n! Beweis. Es gibt insgesamt n Möglichkeiten, welchen Wert ϕ(1) annehmen kann, mal (n − 1) Möglichkeiten, welchen Wert ϕ(2) annehmen kann, usw. Bemerkung 3.1.4. Für eine gegebene Permutation π : {1,..., n} → {1,..., n}, i → π(i) schreiben wir:   1 2 3... n π(1) π(2) π(3)... π(n) Tatsächlich reicht es zur Spezifikation einer Permutation auch aus, nur die untere Reihe dieser Klammer in Form eines n-Tupels anzugeben, also (π(1), π(2),..., π(n)). Beispiel 3.1.2 (Nicht-kommutative Gruppe). Seien ρ : {1,..., 5} → {1,..., 5}, i → ρ(i) und σ : {1,..., 5} → {1,..., 5}, j → σ(j) Permutationen mit     1 2 3 4 5 1 2 3 4 5 ρ: , σ: 3 1 2 4 5 5 1 4 3 2 Dann sind ρ ◦ σ und σ ◦ ρ Permutationen mit     1 2 3 4 5 1 2 3 4 5 ρ◦σ : , σ◦ρ: 5 3 4 2 1 4 5 1 3 2 Insbesondere ist also ρ ◦ σ ̸= σ ◦ ρ, d.h. die Permutationsgruppe ist nicht kommutativ! Satz 3.1.3. 1) Sei m ∈ N. (Zm , +) mit der Verknüpfung [a]m + [b]m = [a + b]m ist eine kommutative Gruppe mit m Elementen. 2) Sei p Primzahl. (Zp \ {p }, ·) mit der Verknüpfung [a]p · [b]p = [a · b]p ist eine kommutative Gruppe mit p − 1 Elementen. 33 Beweis. Zu 1): Zm = {m , m ,..., [m − 1]m }, d.h. Zm hat m Elemente. Dabei ist [a]m = a + m · Z = {a + m · k|k ∈ Z}. Zuerst zeigen wir, dass [a]m + [b]m = [a + b]m tatsächlich wieder auf Zm abbildet, d. h. dass + : Zm × Zm → Zm. Dies sieht man wie folgt: [a]m = [a + km]m ∀k ∈ Z und [b]m = [b + lm]m ∀l ∈ Z. Um auf Zm abzubilden, muss gelten, dass [a + b]m = [a + km + b + lm]m ∀k, l ∈ Z. Dies ist tatsächlich der Fall, denn [a + b]m = [a + km + b + lm]m ⇔ m| (a + km + b + lm − (a + b)) ⇔ m (km + lm) und letztere ist eine wahre Aussage. Nachweis der Gruppeneigenschaften: Assoziativität: ([a]m + [b]m ) + [c]m = [a + b]m + [c]m = [(a + b) + c]m = [a + (b + c)]m = [a]m + [b + c]m = [a]m + ([b]m + [c]m ) Neutrales Element: m m + [a]m = [0 + a]m = [a]m = [a + 0]m = [a]m + m Inverses Element: [−a]m [−a]m + [a]m = [−a + a]m = m = [a + (−a)]m = [a]m + [−a]m Kommutativität: [a]m + [b]m = [a + b]m = [b + a]m = [b]m + [a]m Zu 2): Weitgehend analog. Man muss sich allerdings genau überlegen, wie das inverse Element aussieht (Übung). Definition 3.1.4 (Homomorphismus, Isomorphismus, Automorphismus). Seien (G, ◦) und (H, ⋆) Gruppen. Eine Abbildung ϕ : G → H heißt 1) Homomorphismus genau dann, wenn ∀a, b ∈ G : ϕ(a ◦ b) = ϕ(a) ⋆ ϕ(b), 2) Isomorphismus genau dann, wenn ϕ Homomorphismus und ϕ bijektiv ist. In dem Fall nennen wir (G, ◦) und (H, ⋆) isomorphe Gruppen. 3) Ist ϕ : G → G ein Isomorphismus einer Gruppe G auf sich selbst, dann nennen wir ϕ einen Automorphismus. Beispiel 3.1.3. (R, +) und (R+ , ·) sind isomorph, denn es existiert eine bijektive Abbildung ϕ : R → R+ , a → ea mit ϕ(a + b) = ea+b = ea · eb = ϕ(a) · ϕ(b) für alle a, b ∈ R. 34 Beispiel 3.1.4. (Z4 , +) und (Z5 \{0̄}, ·) sind isomorph, denn es existiert eine bijektive Abbildung ϕ : (Z4 , +) → (Z5 \ {0̄}, ·), [k]4 → [2k ]5 mit k ∈ {0, 1, 2, 3}, welche die Gleichung ϕ([k]4 + [l]4 ) = ϕ([k]4 ) · ϕ([l]4 ) für alle k, l ∈ {0, 1, 2, 3} erfüllt. Bemerkung 3.1.5 (Isomorphismus). Man bezeichnet zwei isomorphe Strukturen S und S ′ (Gruppen, später auch Körper, Vektorräume etc.) als „strukturgleich” und schreibt: S ∼ = S′. Bemerkung 3.1.6 (Automorphismus). Jede Struktur S hat einen trivialen Automorphismus, die Identität id : x → x. Vorwegnahme: Tatsächlich gibt es auf den Körpern Q und R nur den trivialen Automorphismus, erst auf C gibt es einen nichttrivialen Automorphismus, nämlich die komplexe Konjugation z = x + iy → z̄ = x − iy. 3.2 Ringe Definition 3.2.1 (Ring). Sei R eine Menge mit zwei Verknüpfungen: i) + : R × R → R, (a, b) → a + b („Addition”) ii) · : R × R → R, (a, b) → a · b („Multiplikation”) (R, +, ·) heißt Ring genau dann, wenn gilt: 1) (R, +) ist eine kommutative Gruppe 2) Die Multiplikation · ist assoziativ (oder äquivalent: (R, ·) ist „Halbgruppe”), d.h. es gilt ∀a, b, c ∈ R : (a · b) · c = a · (b · c) 3) Es gelten die Distributivgesetze, d.h. ∀a, b, c ∈ R : (a + b) · c = (a · c) + (b · c) und c · (a + b) = (c · a) + (c · b) (R, +, ·) heißt kommutativer Ring, wenn zusätzlich gilt: 4) ∀a, b ∈ R: a · b = b · a Bemerkung 3.2.1 (Nullelement, inverses Element). Das neutrale Element der Addition nennen wir Nullelement und schreiben 0. Für das inverse Element der Addition zu a schreiben wir −a. Damit können wir die Subtraktion definieren als a − b := a + (−b). Achtung: Die Division kommt erst später auf Körpern! Bemerkung 3.2.2. Statt (a · c) + (b · c) schreiben wir kurz a · c + b · c oder ac + bc. Dabei bedeutet unsere Schreibweise: „Punkt vor Strich” und „kein Zeichen gleich Punkt”. Definition 3.2.2 (Einselement). Sei (R, +, ·) ein Ring. Ein neutrales Element der Multiplikation e ∈ R heißt Einselement. Statt e schreiben wir in dem Fall 1 und dann gilt ∀a ∈ R: 1·a=a·1=a Bemerkung 3.2.3 (Eindeutigkeit). Falls ein Einselement existiert, so ist es eindeutig (Beweis dazu ist analog zum neutralen Element bei Gruppen, siehe Satz 3.1.1). 35 Definition 3.2.3 (Nullteilerfrei). Sei (R, +, ·) ein Ring. Wir nennen R nullteilerfrei genau dann, wenn ∀a, b ∈ R gilt: a·b=0⇒a=0∨b=0 Beispiel 3.2.1. (Z, +, ·) ist ein kommutativer, nullteilerfreier Ring mit Einselement. (mZ, +, ·) mit m ≥ 2, m ∈ N ist ein kommutativer, nullteilerfreier Ring ohne Einselement. (N, +, ·) ist kein Ring (Erinnerung: (N, +) ist ja bereits keine Gruppe mangels inversen Elements!) (Q, +, ·) und (R, +, ·) sind kommutative, nullteilerfreie Ringe mit Einselement und es sind sogar Körper (mehr dazu später)! Ein Beispiel für einen kommutativen Ring mit Einselement, der nicht nullteilerfrei ist, ist der Quotientenraum (Zm , +, ·) mit m ≥ 2 und m keine Primzahl Satz 3.2.1. (Zm , +, ·) mit m ≥ 2 ist ein kommutativer Ring mit Einselement. Er ist nullteilerfrei genau dann, wenn m eine Primzahl ist. Beweis. (Zm , +) ist kommutative Gruppe (siehe Satz 3.1.3). Das Nullelement ist m. (Zm , ·) ist Halbgruppe, d.h. die Multiplikation ist assoziativ. Sie ist auch kommutativ und die Distributivgesetze gelten (siehe Satz 3.1.3 bzw. Übung). Das Einselement ist m. 1. Fall: Angenommen m ist keine Primzahl. Dann ∃a, b ∈ Z, a, b ≥ 2 mit m = a · b. Daraus folgt: [a]m · [b]m = [a · b]m = [m]m = m. Wäre nun (Zm , +, ·) nullteilerfrei, dann müste aus dieser Bedingung folgen, dass [a]m = m oder [b]m = m. Dies ist aber nicht der Fall. Tatsächlich gilt: [a]m ̸= m , denn m teilt nicht a, und [b]m ̸= m , denn m teilt nicht b. (Zm , +, ·) ist also nicht nullteilerfrei. 2. Fall: Angenommen m ist eine Primzahl. Es gilt [a]m · [b]m = m genau dann, wenn [a · b]m = m und dies gilt genau dann, wenn m|(a · b). Daraus folgt, weil m Primzahl ist (siehe Übung): m|a ∨ m|b. Dies ist genau dann der Fall, wenn a oder b (oder beide) Vielfache von m sind, wenn also [a]m = m ∨ [b]m = m. (Zm , +, ·) ist also nullteilerfrei. Satz 3.2.2 (Rechenregeln). Sei (R, +, ·) ein Ring, a, b, c ∈ R, dann gelten folgende Rechenregeln: 1) 0·a=a·0=0 2) − (a · b) = (−a) · b = a · (−b) 3) (−a) · (−b) = a · b 4) Falls ein Einselement 1 ∈ R existiert: −a = (−1) · a = 1 · (−a) 36  5) Falls R nullteilerfrei ist: (c ̸= 0 ∧ a · c = b · c) ⇒ a = b und (c ̸= 0 ∧ c · a = c · b) ⇒ a = b Aus Rechenregel 5) folgt insbesondere, dass man wie gewohnt beidseitig kürzen kann. Beweis. Zu 1): Sei a ∈ R. Aus dem Distributivgesetz und der Tatsache, dass 0 das neutrale Element der Addition ist, folgt: 0 · a + 0 · a = (0 + 0) · a = 0 · a 0·a+0 = 0·a ⇒ 0 · a = 0 und analog a · 0 = 0. Zu 2): Seien a, b ∈ R. Aus dem Distributivgesetz und der Tatsache, dass −a das inverse Element der Addition zu a ist, folgt: a · b + (−a) · b = (a + (−a)) · b = 0 · b = 0 a · b + (−(a · b)) = 0 ⇒ −(a · b) = (−a) · b und für die zweite Gleichung analog. Zu 3) – 5): Übung. 3.3 Körper Definition 3.3.1 (Körper). (K, +, ·) heißt Körper genau dann, wenn gilt: 1) (K, +, ·) ist ein Ring 2) (K \ {0}, ·) ist eine kommutative Gruppe Für das neutrale Element der Multiplikation schreiben wie 1. Für das inverse Element der Multiplikation zu a schreiben wir 1 a oder a−1. Damit können wir die Division definieren als a b := a · 1 b = a · b−1. Beispiel 3.3.1. (Q, +, ·) ist ein Körper („der Körper der rationalen Zahlen”) (R, +, ·) ist ein Körper („der Körper der reellen Zahlen”) (Z, +, ·) ist kein Körper, denn (Z \ {0}, ·) ist keine Gruppe (∄ inverses Element) Bemerkung 3.3.1. In Körpern gelten die uns gewohnten Rechenregeln der Addition, Subtrak- tion, Multiplikation und Division! Insbesondere gelten demnach auf Körpern Sätze bzw. können Beweise geführt werden, wie wir sie etwa bereits im Kapitel zur vollständigen Induktion kennengelernt haben (z.B. Beweis der geometrische Reihe ∞ k=0 q = 1−q für |q| < 1, q ∈ R). k 1 P 37 Bemerkung 3.3.2 (Gauloisfeld). Jeder Körper hat mindestens 2 Elemente, das neutrale Ele- ment der Addition „0” und das neutrale Element der Multiplikation „1”. Wir bezeichnen den Körper, der aus genau diesen zwei Elementen besteht, als Gauloisfeld GF (2) = {0, 1}. Auch die komplexen Zahlen C bilden einen Körper. Bemerkung 3.3.3 (Komplexe Zahlen). Historisch sind die komplexen Zahlen entstanden als Antwort auf die Frage, wie man Gleichungen der Form x2 = −1 lösen soll. Dieses Problem wurde bereits im 8. Jhd. von Al-Chwarizmi benannt. Eingeführt wurden die komplexen Zah- len im 16. Jhd. von Cardano. Erstmals mit der imaginären Zahl i gerechnet hat Euler (1748). Cauchy entwickelte die komplexe Analysis (Integration und Differentiation im Komplexen), auch Funktionentheorie genannt (1814). Der Begriff „komplexe Zahl” stammt von Gauß (1831). Die komplexen Zahlen C bilden einen Körper, wenn man sie als R2 mit den entsprechenden Verknüpfungen der Addition und Multiplikation auffasst. Definition 3.3.2 (Körper der komplexen Zahlen). Eine komplexe Zahl z ist ein Paar z = (x, y) reeller Zahlen x, y ∈ R. Die Menge C = {(x, y)|x, y ∈ R} = R2 mit den Verknüpfungen + : R2 × R2 → R2 , (x1 , y1 ) + (x2 , y2 ) := (x1 + x2 , y1 + y2 ) 2 2 2 · :R ×R →R , (x1 , y1 ) · (x2 , y2 ) := (x1 · x2 − y1 · y2 , x1 · y2 + x2 · y1 ) wird als Körper der komplexen Zahlen bezeichnet. Bemerkung 3.3.4. (C, +, ·) erfüllt die Körperaxiome (Übung). Definition 3.3.3 (Imaginäre Einheit). Wir definieren die imaginäre Einheit i := (0, 1). Bemerkung 3.3.5. Seien x, y ∈ R. Mit Hilfe der imaginären Einheit und den oben definierten Vorschriften der Addition und Multiplikation können wir wie folgt rechnen: i · i = (0, 1) · (0, 1) = (−1, 0), (x, 0) + i(y, 0) = (x, 0) + (0, 1) · (y, 0) = (x, 0) + (0, y) = (x, y). Damit kommen wir zu der üblichen Schreibweise für die komplexen Zahlen: C = {x + iy|x, y ∈ R} Demnach ist z ∈ C genau dann, wenn z := x + iy mit x, y ∈ R. Dabei nennen wir x den Real- und y den Imaginärteil. Die reellen Zahlen sind demnach diejenigen komplexen Zahlen, deren Imaginärteil y = 0 ist. In dieser Schreibweise ist i · i = −1 und wenn wir dies berücksichtigen, können wir bei der Addition und Multiplikation jetzt wie folgt „rechnen”: z1 + z2 = (x1 + iy1 )