Grundlagen Der Analysis: Logik, Mengenlehre, Arithmetik

Transcript

Grundlagen der Analysis: Logik, Mengenlehre, Arithmetik Rainer Schimming, Greifswald Inhalt: Zusammenfassung 1. Logik 1.1. Aussagenlogik 1.2. Pr¨adikatenlogik 1.3. Aufbau einer mathematischen Theorie 2. Mengenlehre 2.1. Der Mengenbegriff 2.2. Rechnen mit Mengen 2.3. Produktmenge, Korrespondenz, Abbildung 2.4. Operationen und Relationen 2.5. “Gr¨oßenvergleich” von Mengen 3. Arithmetik ( = Zahlenlehre) 3.1. Nat¨ urliche Zahlen 3.2. Ganze und rationale Zahlen 3.3. Reelle Zahlen 3.4. Ungleichungen 3.5. Summen und Produkte 3.6. Wurzeln, Potenzen mit rationalem Exponenten Zusammenfassung Der vorliegende Preprint ist eine Skripte der Anfangs-Abschnitte 1. Logik, 2. Mengenlehre, 3. Arithmetik der Vorlesung “Analysis” des Verfassers. Es sollen die im Analysis–Kurs ben¨otigten elementaren Kenntnisse u ¨ber Aussagen, Mengen, Korrespondenzen, Abbildungen, Operationen, Relationen, die Zahlbereiche IN, ZZ, Q I , IR u. a. bereitgestellt werden. Die Skripte wird die ¨ Vorlesungen und Ubungen begleiten und unterst¨ utzen; sie kann auch im Selbststudium genutzt werden. Der Verfasser dankt Frau Dipl.-Math. Gesina Wandt f¨ ur die technische Herstellung der Skripte. Den Kollegen Peter Schreiber und Lutz Habermann sei f¨ ur Hinweise gedankt, die zu einer Verbesserung des Textes gef¨ uhrt haben. 1 1 1.1 Logik Aussagenlogik Definition 1. Die Logik betrachtet Regeln des Denkens, insbesondere des korrekten Folgerns oder Schließens. Definition 2. Eine Aussage ist ein sprachlicher Ausdruck, welcher entweder wahr oder falsch ist, d. h. einen Wahrheitswert wahr oder falsch besitzt. Beispiele. Aussage Berlin ist eine Stadt. 2·2=4 3 teilt 8 2H2 + O2 −→ 2H2 O Jede gerade Zahl ≥ 4 ist Summe zweier Primzahlen. Wahrheitswert wahr wahr falsch wahr Verwendete Sprache Umgangssprache Mathematische Formelsprache Kombination beider Chemische Formelsprache unbekannt Gegenbeispiele. Die folgenden sprachlichen Ausdr¨ ucke sind keine Aussagen: Gib her! Wie sp¨at ist es? 3 teilt x. Definition 3. Eine Aussageoperation bildet aus gegebenen Aussagen A, B, C, . . . eine neue Aussage X. Sie heißt extensional, falls der Wahrheitswert von X nur von den Wahrheitswerten von A, B, C, . . . (aber nicht von deren Inhalt!) abh¨angt, intensional sonst. Die Anzahl der Eing¨ ange A, B, C, . . . heißt Stellenzahl der Aussageoperation. Beispiele intensionaler Aussageoperationen: A weil B (Beziehung Ursache – Wirkung) A wichtiger als B (Wertung) Definition 4. Die Aussagenlogik betrachtet Aussagen hinsichtlich ihrer Wahrheitswerte, insbesondere extensionale Aussageoperationen. 2 Definition 5. Extensionale Aussageoperationen mit einem eigenen Symbol: Aussageoperation umgangssprachlich symbolisch Negation nicht A ¬A Konjunktion A und B (sowohl A als auch B) A∧B Disjunktion A oder B (oder beides) A∨B Subjunktion wenn A, so B A −→ B (A nur dann, wenn B; B immer dann, wenn A) Bisubjunktion A genau dann, wenn B A ←→ B Definition 6. Die Zuordung von Wahrheitswerten wahr oder falsch zu Aussagenvariablen A, B, C . . . heißt eine Belegung dieser Variablen. Die Wahrheitswerttabelle einer extensionalen Aussageoperation gibt f¨ ur alle Belegungen der Eing¨ ange A, B, C . . . die Belegung des Ausgangs X an. Es sei abgek¨ urzt falsch = 0, wahr = 1. Definition 7. Die Wahrheitswert–Tabellen zu ¬, ∧, ∨, −→, ←→ lauten per definitionem: A ¬A 0 1 1 0 A 0 0 1 1 B 0 1 0 1 A∧B 0 0 0 1 A∨B 0 1 1 1 A −→ B 1 1 0 1 A ←→ B 1 0 0 1 Satz 1. Alle einstelligen extensionalen Aussageoperationen sind beschrieben durch die folgenden Wahrheitswerttabellen: A Kontradiktion Identit¨at Negation Tautologie 0 0 0 1 1 1 0 1 0 1 Alle A 0 0 1 1 zweistelligen extensionalen Aussageoperationen sind beschrieben durch B Kontr. A ∧ B ¬(A −→ B) A ¬(B −→ A) B ¬(A ←→ B) A ∨ B 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 1 1 1 0 0 0 1 1 0 0 1 1 1 0 1 0 1 0 1 0 1 3 ¬(A ∨ B) A ←→ B 1 1 0 0 0 0 0 1 ¬B 1 0 1 0 B −→ A 1 0 1 1 ¬A 1 1 0 0 A −→ B 1 1 0 1 ¬(A ∧ B) Taut. 1 1 1 1 1 1 0 1 Definition 8. Die extensionale Aussageoperation (jeder Stellenzahl), deren Ausgang immer falsch ist, heißt Kontradiktion, . . . immer wahr ist, heißt Tautologie. Definition 9. Seien H, K aus Aussagenvariablen A, B, C . . . und aus ¬, ∧, ∨, −→, ←→ regelrecht aufgebaute Ausdr¨ ucke. Aus H folgt K, H =⇒ K, falls H −→ K f¨ ur alle Belegungen von A, B, C . . . wahr (d. h. eine Tautologie) ist. H ist (logisch) ¨aquivalent zu K, H ⇐⇒ K, falls H ←→ K f¨ ur alle Belegungen von A, B, C . . . wahr (d. h. eine Tautologie) ist. Bemerkungen. 1. Was hier “regelrecht” heißt, l¨aßt sich pr¨azisieren, indem man beschreibt, wie entsprechende Ausdr¨ ucke rekursiv (d. h. schrittweise) aufgebaut sind. 2. =⇒ und ⇐⇒ treffen die intuitiven Vorstellungen vom logischen Folgern bzw. von der logischen Gleichwertigkeit. 3. Beachte: −→ und ←→ sind Operationen mit Aussagen; =⇒ und ⇐⇒ sind dagegen Relationen zwischen Ausdr¨ ucken. Satz 2. Aussagenlogische Gesetze. ¨ Aquivalenzen: Kommutativgesetze A ∧ B ⇐⇒ B ∧ A A ∨ B ⇐⇒ B ∨ A A ←→ B ⇐⇒ B ←→ A Assoziativgesetze (A ∧ B) ∧ C ⇐⇒ A ∧ (B ∧ C) (A ∨ B) ∨ C ⇐⇒ A ∨ (B ∨ C) (A ←→ B) ←→ C ⇐⇒ A ←→ (B ←→ C) Distributivgesetze (A ∨ B) ∧ C ⇐⇒ (A ∧ C) ∨ (B ∧ C) (A ∧ B) ∨ C ⇐⇒ (A ∨ C) ∧ (B ∨ C) Verschmelzungsgesetze A ∧ (A ∨ B) ⇐⇒ A A ∨ (A ∧ B) ⇐⇒ A Doppel–Negations–Regel ¬¬A ⇐⇒ A De Morgansche Regeln ¬(A ∧ B) ⇐⇒ ¬A ∨ ¬B ¬(A ∨ B) ⇐⇒ ¬A ∧ ¬B Kontrapositionsregel A −→ B ⇐⇒ ¬B −→ ¬A 4 Darstellungen der Subjunktion Darstellung der Bisubjunktion Schlußregeln: Abtrennungsregel Kettenschlußregel Abschw¨ achungsregeln A −→ B ⇐⇒ ¬A ∨ B ⇐⇒ ¬(A ∧ ¬B) A ←→ B ⇐⇒ (A −→ B) ∧ (B −→ A) (A −→ B) ∧ A =⇒ B (A −→ B) ∧ (B −→ C) =⇒ (A −→ C) A =⇒ A ∨ B A =⇒ (B −→ A) A ∧ B =⇒ A Tautologien: Gesetz vom ausgeschlossenen Dritten A ∨ ¬A ist immer wahr Gesetz vom ausgeschlossenen Widerspruch ¬(A ∧ ¬A) ist immer wahr Beweis der Doppel–Negations–Regel: A ¬A ¬¬A ¬¬A ←→ A 0 1 0 1 1 0 1 1 . . . der Abtrennungsregel: A B A −→ B (A −→ B) ∧ A 0 0 1 0 0 1 1 0 1 0 0 0 1 1 1 1 ((A −→ B) ∧ A) −→ B 1 1 1 1 . . . des Gesetzes vom ausgeschlossenen Widerspruch: A ¬A A ∧ ¬A ¬(A ∧ ¬A) 0 1 0 1 1 0 0 1 Geschichte. “Rechnen mit Gedanken” ist eine alte Idee bzw. ein Programm, z. B. von den Philosophen R. Lullus (1480) und G. W. Leibniz (1666) formuliert. Logik im heutigen Sinne datiert seit 1847; in dem Jahr erschienen die beiden B¨ ucher G. Boole: The Mathematical Analysis of Logic. A. de Morgan: Formal Logic. 5 1.2 Pr¨ adikatenlogik Problem. Sprachliche Ausdr¨ ucke enthalten außer Konstanten typischerweise auch Variablen f¨ ur Objekte (z. B. Mengen, Zahlen, Funktionen, . . . ). Daf¨ ur ist eine Logik zu entwickeln! Definition 1. Eine Aussageform oder ein Pr¨ adikat ist ein sprachlicher Ausdruck A(x, y, . . . ), der endlich viele Variablen x, y, . . . enth¨alt und zu einer Aussage wird, wenn alle Variablen mit Werten belegt werden. Die Anzahl der Variablen heißt die Stellenzahl der Aussageform. Eine Aussage ist per definitionem eine 0–stellige Aussageform. Beispiele. Stellenzahl Variable(n) Aussageform 0 keine 2·2=4 1 x 3 teilt x. Wahr z. B. f¨ ur x = 9. Falsch z. B. f¨ ur x = 8. 2 x, y x teilt y. 3 x, y, z x+y =z Definition 2. Eine Quantifizierung von Variablen erzeugt aus einer Aussageform eine solche niedrigerer Stellenzahl. Definition 3. Quantifizierungen mit einem eigenen Symbol: Quantifizierung umgangssprachlich Generalisierung f¨ ur alle x (f¨ ur jedes x, f¨ ur beliebiges x) Partikularisierung symbolisch ∀xA(x, . . . ) oder V xA(x, . . . ) es gibt (mindestens) ein x ∃xA(x, . . . ) oder W (es existiert (mindestens) ein x) xA(x, . . . ) verst¨ arkte Partikularisierung es gibt genau ein x (es existiert genau ein x; es gibt ein und nur ein x) ∃!xA(x, . . . ) Beispiele. Quantifizierungen ohne eigenes Symbol: umgangssprachlich durch ∀, ∃ ausgedr¨ uckt es gibt h¨ochstens ein x mit A(x) ∀x1 ∀x2 (A(x1 ) ∧ A(x2 ) −→ x1 = x2 ) (es gibt kein x mit A(x) oder es gibt genau ein x mit A(x)) es gibt mehrere x mit A(x) ∃x1 ∃ x2 (A(x1 ) ∧ A(x2 ) ∧ x1 6= x2 ) (es gibt mehr als ein x mit A(x)) 6 Beispiele. Aussagen, die Quantifizierungen enthalten: 1. Gruppenaxiome: ∀x ∀y ∀z : (x · y) · z = x · (y · z) ∃e ∀x : e · x = x · e = x ∀x ∃y : x · y = y · x = e 2. Sprichw¨orter. umgangssprachlich Hunde, die bellen, beißen nicht Wenn zwei sich streiten, freut sich der Dritte symbolisch ∀x(A(x) ∧ B(x) −→ ¬C(x)), wobei A = ist ein Hund, B = bellt, C = beißt ∀x ∀y(A(x, y) −→ ∃zB(z)), wobei A = streiten sich, B = freut sich Genauer: ∀x ∀y(A(x, y) −→ ∃z : z 6= x ∧ z 6= y ∧ B(z)) Satz Pr¨adikatenlogische Gesetze. Kommutativgesetze ∀x∀yA(x, y, . . . ) ⇐⇒ ∀y∀xA(x, y, . . . ) ∃x∃yA(x, y, . . . ) ⇐⇒ ∃y∃xA(x, y, . . . ) ∀x(A(x, . . . ) ∧ B(x, . . . )) ⇐⇒ (∀xA(x, . . . )) ∧ (∀x(B(x, . . . )) ∃x(A(x, . . . ) ∨ B(x, . . . )) ⇐⇒ (∃xA(x, . . . )) ∨ (∃x(B(x, . . . )) De Morgansche Regeln ¬∀xA(x, . . . ) ⇐⇒ ∃x¬A(x, . . . ) ¬∃xA(x, . . . ) ⇐⇒ ∀x¬A(x, . . . ) Abschw¨ achungsregeln ∃x∀yA(x, y, . . . ) =⇒ ∀y∃xA(x, y, . . . ) ∃!xA(x, . . . ) =⇒ ∃xA(x, . . . ) Vereinbarung. Es sei erlaubt, ∀x ∀y . . . durch ∀x, y, . . . abzuk¨ urzen, ∃x ∃y . . . durch ∃x, y, . . . abzuk¨ urzen usw.. Der Doppelpunkt : diene als Trennzeichen anstelle von Klammern. Definition 4. Die Pr¨adikatenlogik 1. Stufe betrachtet Individuen x, y, z, . . . und Pr¨adikate A(x), A(x, y, . . . ), A(x, y, z, . . . ), . . . . Genau die Individuen k¨onnen dort quantifiziert werden. Die Pr¨ adikatenlogik 2. Stufe betrachtet Individuen, Pr¨adikate und zus¨atzlich Pr¨adikate von Pr¨adikaten. Genau die Individuen und die Pr¨adikate k¨onnen dort quantifiziert werden. Usw. Beispiele. Gesetze der Pr¨adikatenlogik 2. Stufe: Gesetz vom ausgeschlossenen Dritten: ∀A ∀x(A(x) ∨ ¬A(x)). Ersetzbarkeitseigenschaft der Gleichheitsrelation: ∀A ∀x, y(x = y −→ (A(x) ←→ A(y))). Geschichte. Die Klassenlogik von Aristoteles, eine der ersten wissenschaftlichen Theo7 rien (nach heutiger Auffassung) u ¨berhaupt, ist eine Aussagen– und Pr¨adikatenlogik in anderer Form als der heute u ¨blichen. G. Frege’s Begriffschrift (1859) ist ebenfalls eine alternative Aussagen– und Pr¨adikatenlogik, die sich nicht durchgesetzt hat, weil sie sehr unhandlich ist. Die Pr¨adikatenlogik in der heutigen Form geht auf C. S. Peirce und G. Peano (2. H¨alfte des 19. Jahrhunderts) zur¨ uck. 1.3 Aufbau einer mathematischen Theorie Die Fachsprache einer mathematischen Theorie setzt sich aus der Umgangssprache und einer speziellen Symbol– oder Formelsprache zusammen. Definition 1. Man unterscheidet zwei Arten sprachlicher Ausdr¨ ucke: Ein Term ist ein Ausdruck, der als ein mathematisches Objekt interpretiert werden kann. Eine Formel ist ein Ausdruck, der als eine Aussage oder Aussageform interpretiert werden kann. Im folgenden besprechen wir wichtige Arten von Bausteinen einer mathematischen Theorie: Axiom, Definition, Satz, Beweis. Vorl¨ aufige Definition. Ein Axiom ist eine als wahr angenommene Aussage. Ein Axiomensystem besteht aus endlich vielen Axiomen und wird an den Anfang einer Theorie gesetzt. Definition 2. Ein Axiomensystem ist eine implizite Definition der Grundbegriffe einer Theorie im folgenden Sinn: Es f¨ uhrt die Grundbegriffe ein und regelt deren Beziehungen untereinander. Beispiele. 1. Axiomensystem f¨ ur die Gleichheit = : x, y, z, . . . bezeichnen mathematische Objekte, A, B, C, . . . bezeichnen Aussageformen. x = y bedeutet: x ist gleich y. Reflexivit¨ at: ∀x : x = x Transitivit¨at: ∀x, y, z : x = y ∧ y = z −→ x = z Symmetrie: ∀x, y : x = y −→ y = x Leibnizsche Ersetzbarkeit: ∀A ∀x, y : x = y −→ (A(x) = A(y)) 2. Einige Axiome der ebenen Geometrie: Es gibt Punkte P , Q, R . . . und Geraden g, h, k . . . . P ∈ g bedeutet: Der Punkt P liegt auf der Geraden g. (Die Gerade g geht durch den Punkt P .) 1. ∀g ∃P, Q : P ∈ g ∧ Q ∈ g ∧ P 6= Q. 2. ∀P, Q mit P 6= Q ∃!g : P ∈ g ∧ Q ∈ g. 3. ∀g ∃P : P ∈ / g. 8 Definition 3. Eine Definition hat die Form Definiendum := Definiens. Dabei ist das Definiendum, d. h. das zu Definierende, ein abk¨ urzender neuer Name; das Definiens, d. h. das Definierende, ist ein durch bekannte sprachliche Mittel gegebener Ausdruck. Sind hier beide Seiten Formeln, so bevorzugt man die Symbolik Definiendum :⇐⇒ Definiens. Zus¨ atze. 1. Es ist auch erlaubt, die Reihenfolge zu vertauschen: Definiens =: Definiendum bzw. Definiens ⇐⇒: Definiendum. 2. Umgangssprachlich wird eine Definition ausgedr¨ uckt durch heißt, wird genannt, per definitionem ist . . . (oder auch im Konjunktiv: heiße, werde genannt, per definitionem sei . . . ). 3. Das genau dann, wenn in einer Definition ersetzen wir meist durch falls. 4. Das Definiendum wird u ¨blicherweise durch eine besondere Schriftart hervorgehoben. Beispiele. heißt Mittelwert der Zahlen a, b. A := a+b 2 Die kleinste positive Nullstelle der Sinusfunktion heißt Kreiszahl π. Zwei Vektoren a, b sind orthogonal, a ⊥ b, falls a · b = 0. Definition 4. Jedes Axiom ist auch ein Satz. Ein Beweis in einer Theorie ist eine endliche Folge von Formeln derart, daß sich jede Formel verm¨oge einer Schlußregel aus den vorhergehenden Formeln und aus schon bewiesenen S¨atzen ergibt. Die letzte Formel eines Beweises ist ein Satz der Theorie; dieser wird durch den zugeh¨origen Beweis bewiesen. Bemerkungen. 1. Demgem¨aß ist eine mathematische Theorie rekursiv (d. h. schrittweise) aufgebaut: Satz 0. Stufe := Axiom, Satz 1. Stufe := Aus Axiomen hergeleitet, Satz 2. Stufe := Aus Axiomen und S¨atzen 1. Stufe hergeleitet, usw. 2. Wiederholung: Wichtige Schlußregeln: Abtrennungsregel (A −→ B) ∧ A =⇒ B, Kettenschlußregel (A −→ B) ∧ (B −→ C) =⇒ (A −→ C), De Morgansche Regeln ¬(A ∧ B) ⇐⇒ ¬A ∨ ¬B, ¬(A ∨ B) ⇐⇒ ¬A ∧ ¬B, Pr¨ adikatenlogische Abschw¨achungsregel ∃x∀yA(x, y, . . . ) =⇒ ∀y∃xA(x, y, . . . ), Pr¨ adikatenlogische De Morgansche Regeln ¬∀xA(x, . . . ) ⇐⇒ ∃x¬A(x, . . . ), ¬∃xA(x, . . . ) ⇐⇒ ∀x¬A(x, . . . ). 9 3. Ein nur als Zwischenresultat angesehener Satz heißt auch Hilfssatz oder Lemma. Ein als besonders wichtig angesehener Satz heißt auch Hauptsatz oder Theorem. Ein zu einem Satz hinzugef¨ ugter Satz heißt auch Korollar. Definition 5. In einem Satz der Form A −→ B oder ∀x(A(x) −→ B(x)) heißt A bzw. A(x) Voraussetzung oder Pr¨amisse und heißt B bzw. B(x) Behauptung oder Konklusion. Geschichte. Die heutige Auffassung von einer mathematischen Theorie, insbesondere u ¨ber den axiomatischen Aufbau, geht auf D. Hilbert (1862–1843) zur¨ uck. Diese moderne Auffassung ist auch Vorbild f¨ ur Theorien in den Naturwissenschaften. 2 2.1 Mengenlehre Der Mengenbegriff Definition 1. Mengendefinition nach G. Cantor (1895): Eine Menge ist die Zusammenfassung unterscheidbarer einzelner Objekte, genannt Elemente, zu einem Ganzen. x ∈ M heißt: x ist Element der Menge M (M enth¨alt x). x ∈ / M heißt ¬x ∈ M . “Axiom.” Mengenbildungsprinzip. Zu einer “sinnvollen” einstelligen Aussageform A existiert M = {x|A(x)} := Menge aller x, f¨ ur die A(x) wahr ist. Beispiele. Einermenge {a} := {x|x = a}, Zweiermenge {a, b} := {x|x = a ∨ x = b}, Dreiermenge {a, b, c} := {x|x = a ∨ x = b ∨ x = c}, usw. Die leere Menge ∅ := {x|x 6= x} enth¨alt kein Element. F¨ ur die sogenannten Zahlbereiche sind besondere Symbole reserviert: IN = Menge der nat¨ urlichen Zahlen, ZZ = Menge der ganzen Zahlen, Q I = Menge der rationalen Zahlen, IR = Menge der reellen Zahlen. 10 Gegenbeispiel. Antinomie von B. Russel 1902: M := {x|x ∈ / x} definiert keine Menge M , d. h. die Aussageform A(x) := x ∈ / x ist nicht “sinnvoll”. ¨ Beweis. Ubung. Definition 2. Sei E eine Menge 6= ∅, genannt Grundbereich. A eine einstellige Aussageform. Man definiert ∀x ∈ E : A(x) :⇐⇒ ∀x : x ∈ E −→ A(x) ∃x ∈ E : A(x) :⇐⇒ ∃x : x ∈ E ∧ A(x) {x ∈ E|A(x)} :⇐⇒ {x|x ∈ E ∧ A(x)} ¨ Bemerkung. Der Ubergang von E und A zu M := {x ∈ E|A(x)} heißt auch klassisches Definitionsschema. Es wurde von Aristoteles eingef¨ uhrt. Dabei heißt E die Gattung, A das artbildende Merkmal, M die Art. Beispiele f¨ ur das klassische Definitionsschema: 1. M = {x ∈ IR|f (x) = 0} ist die L¨ osungsmenge der Bestimmungsgleichung f (x) = 0 im Bereich der reellen Zahlen. 2. Intervalle reeller Zahlen [a, b] := {x ∈ IR|a ≤ x ≤ b}, ]a, b[:= {x ∈ IR|a < x < b}, [a, b[:= {x ∈ IR|a ≤ x < b}, ]a, b] := {x ∈ IR|a < x ≤ b}. Definition 3. Veranschaulichung von Mengen nach L. Euler. Ein Mengendiagramm ordnet Mengen M , N, . . . Punktmengen in der Ebene zu mit gleichen Verh¨altnissen bez¨ uglich gemeinsamer / nicht gemeinsamer Elemente. Beispiele. M¨ogliche Diagramme f¨ ur zwei Mengen M , N : M=N M M N M M N 11 N N Geschichte. Georg Cantor (1845–1918) ist der Begr¨ under der Mengenlehre; ab 1874 publizierte er dar¨ uber. Seine Ideen waren damals revolution¨ar und setzten sich nur gegen Widerst¨ande durch. Die Antinomie von B. Russell (1901) sowie bald darauf entdeckte weitere Antinomien der “naiven Mengenlehre” machten einen axiomatischen Aufbau notwendig. Es gibt verschiedene Varianten der axiomatischen Mengenlehre; meist beruft man sich auf die von E. Zermelo und A. Fraenkel (1904–1908). 2.2 Rechnen mit Mengen Axiom. Extensionalit¨atsprinzip. Zwei Mengen sind gleich, falls sie dieselben Elemente haben. D. h. M = N , falls ∀x : x ∈ M ←→ x ∈ N . Definition 1. M ist Teilmenge (Untermenge) von N , M ⊆ N , falls jedes Element von M auch Element von N ist, d. h. ∀x : x ∈ M −→ x ∈ N . M ist echte Teilmenge von N , M ⊂ N , falls M ⊆ N und M 6= N . Die Relation ⊆ zwischen Mengen heißt Inklusion, ⊂ heißt echte Inklusion. Die Menge aller Teilmengen von M heißt Potenzmenge von M und wird mit 2M bezeichnet. Beispiele. 1. {a} ⊆ {a, b} ⊆ {a, b, c} ⊆ . . . . 2. Echte Inklusionen der Zahlbereiche: IN ⊂ ZZ ⊂ Q I ⊂ IR. 3. F¨ ur jede Menge M gilt ∅ ⊆ M . 4. F¨ ur eine Einermenge M = {a} ist 2M = {∅, {a}}. F¨ ur eine Zweiermenge M = {a, b} mit M a 6= b ist 2 = {∅, {a}, {b}, {a, b}}. Satz 1. Gesetze f¨ ur die Inklusion: Reflexivit¨at M ⊆M Transitivit¨at M ⊆ N und N ⊆ L −→ M ⊆ L Antisymmetrie M ⊆ N und N ⊆ M −→ M = N Gesetze f¨ ur die echte Inklusion: Irreflexivit¨at nicht M ⊂ M Transitivit¨at M ⊂ N und N ⊂ L −→ M ⊂ L Asymmetrie M ⊂ N −→ nicht N ⊂ M Beweis f¨ ur ⊆: Reflexivit¨at: ∀x (x ∈ M −→ x ∈ M ) =⇒ M ⊆ M . Transitivit¨at: M ⊆ N und N ⊆ L =⇒ ∀x : (x ∈ M −→ x ∈ N ) ∧ (x ∈ N −→ x ∈ L) =⇒ ∀x (x ∈ M −→ x ∈ L) =⇒ M ⊆ L. 12 Antisymmetrie: M ⊆ N und N ⊆ M =⇒ ∀x : (x ∈ M −→ x ∈ N ) ∧ (x ∈ N −→ x ∈ L) ⇐⇒ ∀x (x ∈ M ←→ x ∈ N ) ⇐⇒ M = N . Definition 2. Der Durchschnitt zweier Mengen M und N ist M ∩N := {x|x ∈ M und x ∈ N } Die Vereinigung von M und N ist M ∪ N := {x|x ∈ M oder x ∈ N } Die Differenz von M und N ist M \ N := {x|x ∈ M und x ∈ / N} Zwei Mengen M, N heißen elementfremd oder disjunkt, falls M ∩ N = ∅. Satz 2. Gesetze f¨ ur Durchschnitt und Vereinigung: Kommutativgesetze M ∩N =N ∩M M ∪N =N ∪M Assoziativgesetze (M ∩ N ) ∩ L = M ∩ (N ∩ L) (M ∪ N ) ∪ L = M ∪ (N ∪ L) Distributivgesetze (M ∪ N ) ∩ L = (M ∩ L) ∪ (N ∩ L) (M ∩ N ) ∪ L = (M ∪ L) ∩ (N ∪ L) Verschmelzungsgesetze M ∩ (M ∪ N ) = M M ∪ (M ∩ N ) = M 13 Beweis des 1. Distributivgesetzes: F¨ ur alle x ist x ∈ (M ∪ N ) ∩ L ⇐⇒ ⇐⇒ ⇐⇒ ⇐⇒ ⇐⇒ x∈M ∪N ∧x∈L (x ∈ M ∨ x ∈ N ) ∧ x ∈ L (x ∈ M ∧ x ∈ L) ∨ (x ∈ N ∧ x ∈ L) x∈M ∩L∨x∈N ∩L x ∈ (M ∩ L) ∪ (N ∪ L) Gem¨aß dem Extensionalit¨atsprinzip ist (M ∪ N ) ∩ L = (M ∩ L) ∪ (N ∩ L). Definition 3. Komplement. F¨ ur die Teilmenge M eines festen Grundbereiches E heißt M := E \ M auch E  M M  Satz 3. Gesetze f¨ ur das Komplement. M = M, ∅ = E, E = ∅, M ∪ M = E, M ∩ M = ∅, De Morgansche Regeln: M ∩ N = M ∪ N , M ∪ N = M ∩ N . Beweis der 1. De Morganschen Regel: F¨ ur alle x ist x ∈ M ∩ N ⇐⇒ ⇐⇒ ⇐⇒ ⇐⇒ ⇐⇒ ¬(x ∈ M ∩ N ) ¬(x ∈ M ∧ x ∈ N ) (¬x ∈ M ) ∨ (¬x ∈ N ) x∈M ∨x∈N x∈M ∪N Aus dem Extensionalit¨atsprinzip folgt die Behauptung M ∩ N = M ∪ N . 2.3 Produktmenge, Korrespondenz, Abbildung Idee. Zweiermenge {x, y} = ungeordnete Zusammenfassung von x, y. {x, y} = {y, x}. Geordnetes Paar (x, y) = geordnete Zusammenfassung von x, y. (x, y) 6= (y, x). n–tupel (x1 , x2 , . . . , xn ) = geordnete Zusammenfassung von x1 , x2 , . . . , xn . 14 Definition 1. Das geordnete Paar aus zwei Elementen x, y ist (x, y) := {{x, y}, {x}}. F¨ ur n ≥ 3 sind n–tupel rekursiv definiert durch (x1 , x2 , . . . , xn ) := ((x1 , x2 , . . . , xn−1 ), xn ). Spezialf¨ alle. n n–tupel 2 geordnetes Paar 3 Tripel 4 Quadrupel 5 Quintupel Satz 1. “Axiom” des geordneten Paares bzw. n–tupels. (x, y) = (x0 , y 0 ) ←→ x = x0 und y = y 0 . (x1 , x2 , . . . , xn ) = (x01 , x02 , . . . , x0n ) ←→ x1 = x01 und x2 = x02 . . . und xn = x0n . ¨ Beweis. Ubung. Definition 2. Das Produkt (Mengenprodukt, Produktmenge) zweier Mengen M und N sei M × N := {(x, y)|x ∈ M und y ∈ N }. Das Produkt (Mengenprodukt, Produktmenge) von Mengen M1 , M2 , . . . , Mn sei M1 × M2 × · · · × Mn := {(x1 , x2 , . . . , xn )|x1 ∈ M1 und x2 ∈ M2 . . . und xn ∈ Mn }. Die n–te Potenz von M sei M n := M × M × · · · × M (n–mal). Man setzt außerdem noch M 1 = M . Beispiele. 1. IRn ≡ IR×IR×· · ·×IR (n–mal) = {(x1 , x2 , . . . , xn )|x1 , x2 , . . . , xn ∈ IR} heißt n–dimensionaler reeller Zahlenraum. 2. [0, 1] := {x ∈ IR|0 ≤ x ≤ 1} heißt Einheitsintervall [0, 1] × [0, 1] heißt Einheitsquadrat. [0, 1]n = [0, 1] × [0, 1] × · · · × [0, 1] (n–mal) heißt n–dimensionaler Einheitsw¨ urfel. 15 Satz 2. Gesetze f¨ ur das Mengenprodukt: Distributivgesetze (M1 ∩ M2 ) × N = (M1 × N ) ∩ (M2 × N ) (M1 ∪ M2 ) × N = (M1 × N ) ∪ (M2 × N ) (M1 \ M2 ) × N = (M1 × N ) \ (M2 × N ) N × (M1 ∩ M2 ) = (N × M1 ) ∩ (N × M2 ) N × (M1 ∪ M2 ) = (N × M1 ) ∪ (N × M2 ) N × (M1 \ M2 ) = (N × M1 ) \ (N × M2 ) Monotoniegesetz M1 ⊆ M2 −→ M1 × N ⊆ M2 × N und N × M1 ⊆ N × M2 ¨ Beweis. Ubung. Definition 3. Eine Korrespondenz oder Zuordnung F aus einer Menge M 6= ∅ in eine Menge N 6= ∅ ist eine Teilmenge der Produktmenge: F ⊆ M × N . Der Definitionsbereich von F ist D(F ) := {x|∃y : (x, y) ∈ F }, der Wertebereich von F ist W(F ) := {y|∃x : (x, y) ∈ F }. Wenn (x, y) ∈ F , so heißt x hier ein Original oder Urbild, y ein Wert oder Bild. Bemerkung. F ⊆ M × N enth¨alt genau die (x, y), f¨ ur die y ∈ N dem x ∈ M zugeordnet wird. Ein endliches F = {(x1 , y1 ), (x2 , y2 ), . . . , (xn , yn )} ist gleichwertig zu einer Wertetabelle x x1 x2 .. . y y1 y2 xn yn Die obige Definition verallgemeinert die Vorstellung von F als einer Art von Wertetabelle. Mengendiagramme: M N x F M y 16 x1 x2 x3 F y1 y2 y3 N Beispiele. M = {x1 , . . . , x5 }, N = {y1 , . . . , y4 }, F = {(x1 , y2 ), (x2 , y1 ), (x3 , y3 ), (x4 , y3 )}. y1 x1 x2 x3 x4 x5 y2 y4 y3 Definition 4. Operationen mit Korrespondenzen: Die inverse Korrespondenz oder Umkehrkorrespondenz zu F ⊆ M × N ist F −1 := {(y, x)|(x, y) ∈ F }. Die Komposition oder Verkettung von F ⊆ M × N und G ⊆ N × P ist G ◦ F := {(x, z)|∃y : (x, y) ∈ F und (y, z) ∈ G}. Mengendiagramme: F N M x y F−1 G F N M x F P G y 17 z Obiges Beispiel. M = {x1 , . . . , x5 }, N = {y1 , . . . , y4 }, F = {(x1 , y2 ), (x2 , y1 ), (x3 , y3 ), (x4 , y3 )} =⇒ F −1 = {(y2 , x1 ), (y1 , x2 ), (y3 , x3 ), (y3 , x4 )}. Satz 3. Gesetze f¨ ur Inversion Rollentausch von D und W Doppelte Inversion Assoziativgesetz Inversionsgesetz und Komposition: D(F −1 ) = W(F ), W(F −1 ) = D(F ), (F −1 )−1 = F , (H ◦ G) ◦ F = H ◦ (G ◦ F ), (G ◦ F )−1 = F −1 ◦ G−1 . Beweis des Assoziativgesetzes: H G F N M x F H G z y (x, u) ∈ (H ◦ G) ◦ F ⇐⇒ ⇐⇒ ⇐⇒ ⇐⇒ ⇐⇒ ⇐⇒ Q P u ∃y : (x, y) ∈ F und (y, u) ∈ H ◦ G ∃y : (x, y) ∈ F und (∃z : (y, z) ∈ G und (z, u) ∈ H) ∃y∃z : (x, y) ∈ F und (y, z) ∈ G und (z, u) ∈ G ∃z : (∃y : (x, y) ∈ F und (y, z) ∈ G) und (z, u) ∈ H ∃z : (x, z) ∈ G ◦ F und (z, u) ∈ H (x, u) ∈ H ◦ (G ◦ F ) Gem¨aß der Definition der Mengengleichheit ist (H ◦ G) ◦ F = H ◦ (G ◦ F ). Definition 5. Erste Einteilung von Korrespondenzen: Eine Korrespondenz F ⊆ M × N heißt . . . falls . . . in N auf N aus M D(F ) ⊆ M , W(F ) ⊆ N D(F ) ⊆ M , W(F ) = N von M D(F ) = M , W(F ) ⊆ N D(F ) = M , W(F ) = N 18 Beispiele. in N und nicht auf N F = {(x1 , y1 ), (x2 , y2 )} auf N F = {(x1 , y1 ), (x2 , y2 ), (x2 , y3 )} F = {(x1 , y1 ), (x2 , y2 ), (x3 , y1 )} F = {(x1 , y1 ), (x2 , y2 ), (x3 , y3 )} aus M und nicht von M von M Definition 6. Zweite Einteilung von Korrespondenzen: F ⊆ M × N heißt eindeutig, falls (x, y1 ), (x, y2 ) ∈ F −→ y1 = y2 , . . . mehrdeutig sonst. F ⊆ M × N heißt eindeutig umkehrbar, falls (x1 , y), (x2 , y) ∈ F −→ x1 = x2 , . . . mehrdeutig umkehrbar sonst. F heißt eineindeutig, falls F eindeutig und eindeutig umkehrbar ist. Zus¨ atze. 1. F ist eindeutig genau dann, wenn ∀x ∈ D(F ) ∃! y ∈ W(F ) : (x, y) ∈ F , F ist eindeutig umkehrbar genau dann, wenn ∀y ∈ W(F ) ∃! x ∈ D(F ) : (x, y) ∈ F . 2. Ist F eindeutig, so schreibt man anstatt (x, y) ∈ F auch y = F (x). Sind F , G eindeutig, so ist in der neuen Schreibweise (G ◦ F )(x) = G(F (x)). 19 Beispiele. mehrdeutig umkehrbar eindeutig umkehrbar mehrdeutig eineindeutig eindeutig Definition 7. Eine Abbildung F : M −→ N , x 7→ y ist eine eindeutige Korrespondenz von M in N . Eine Abbildung heißt injektiv oder eine Injektion, falls sie eindeutig umkehrbar ist, . . . surjektiv oder eine Surjektion, falls sie auf N ist, . . . bijektiv oder eine Bijektion, falls sie sowohl injektiv als auch surjektiv ist. Bemerkungen. 1. Eine Injektion ist eindeutig (weil jede Abbildung eindeutig ist) und eindeutig umkehrbar, also sogar eineindeutig. 2. Man verwendet, nach Bourbaki, zwei verschiedene Abbildungspfeile: −→ f¨ ur Mengen und 7→ f¨ ur Elemente. Spezialf¨ alle. 1. F¨ ur M 6= ∅ heißt id = idM := {(x, x)|x ∈ M } die identische Abbildung von M auf sich. F = id gen¨ ugt x = F (x). 2. F¨ ur M, N 6= ∅ und festes c ∈ N heißt F = {(x, c)|x ∈ M } eine konstante Abbildung. Man schreibt dann F (x) = const = c. 3. Die sogenannten Projektionen von der Produktmenge M1 × M2 auf die Faktoren pr1 : M1 × M2 −→ M1 , (x1 , x2 ) 7→ x1 , pr2 : M1 × M2 −→ M2 , (x1 , x2 ) 7→ x2 sind Surjektionen. 4. Die sogenannten Einbettungen der Faktoren M1 , M2 in die Produktmenge M1 × M2 i1 : M1 −→ M1 × M2 , x1 7→ (x1 , c2 ) mit festem c2 ∈ M2 , i2 : M2 −→ M1 × M2 , x2 7→ (c1 , x2 ) mit festem c1 ∈ M1 sind Injektionen. 20   Abbildungen Abbildung       Injektionen Injektion Satz 4. Die Komposition von ist wieder eine . Surjektionen Surjektion       Bijektionen Bijektion Das Inverse einer Bijektion ist wieder eine Bijektion. ¨ Beweis. Ubung. Definition 8. Die Menge aller Abbildungen F : M −→ N wird mit N M bezeichnet. Beispiele. 1. Eine reelle Zahlenfolge ist eine Abbildung IN −→ IR, n 7→ an . Also ist IRIN = Menge aller reellen Zahlenfolgen. 2. Eine reelle Funktion f mit Definitionsbereich [a, b] ist eine Abbildung [a, b] −→ IR, x 7→ y = f (x). Also ist IR[a,b] = Menge aller reellen Funktionen mit Definitionsbereich [a, b]. Geschichte. Ein intuitives Verst¨andnis von Korrespondenzen und Abbildungen hat es schon sehr lange gegeben. Die obige Definition des geordneten Paares, welche die mengentheoretische pr¨azise Bestimmung von Korrespondenzen und Abbildungen erm¨oglicht, stammt von K. Kuratowski (1896–1980). “Abbildungen” hießen fr¨ uher auch “Funktionen”. Die moderne Terminologie wurde vor allem durch das Lehrbuch der Autorengruppe N. Bourbaki (ab 1939) eingef¨ uhrt bzw. befestigt. 2.4 Operationen und Relationen Vorl¨ aufige Definition. Eine (zweistellige) Operation O erzeugt aus zwei Elementen x, y ein Element z = xOy. Eine n–stellige Operation erzeugt aus n Elementen x1 , x2 , . . . , xn ein Element z. Eine (zweistellige) Relation R ist eine Beziehung zwischen zwei Elementen x, y; man schreibt xRy. Eine n–stellige Relation ist eine Beziehung zwischen n Elementen x1 , x2 , . . . , xn . Definition 1. Eine (zweistellige) Operation in einer Menge E 6= ∅ ist eine Abbildung O : E × E −→ E, (x, y) 7→ z = O(x, y) ≡ xOy. Eine n–stellige Operation in E 6= ∅ ist eine Abbildung O : E n −→ E, (x1 , x2 , . . . , xn ) 7→ z = O(x1 , x2 , . . . , xn ). Insbesondere ist eine einstellige Operation O eine Abbildung E −→ E, x 7→ z = O(x). Beispiele. 21 Menge E 6= ∅ Operation in E Menge der Terme der Aussagenlogik 2M f¨ ur eine beliebige Menge M IN, ZZ, Q I , IR ZZ, Q I , IR Q I \ {0}, IR \ {0} ¬, ∧, ∨, −→, ←→ ∩, ∪, \ +, · − : Definition 2. Eine (zweistellige) Relation in einer Menge E 6= ∅ ist eine Teilmenge R ⊆ E×E. F¨ ur (x, y) ∈ R schreibt man auch xRy. Eine n–stellige Relation in E 6= ∅ ist eine Teilmenge R ⊆ E n. Bemerkung. R ⊆ E ×E enth¨alt genau die (x, y), f¨ ur welche x, y anschaulich in der Beziehung R zueinander stehen. Beispiele. Menge E 6= ∅ Relation in E beliebig Gleichheit = Zahlbereiche IN, ZZ, Q I , IR nat¨ urliche Ordnungsrelationen ≤, <, ≥, > Definition 3. Eigenschaften einer Relation R ⊆ E × E R heißt . . . . . . falls ∀x, y, z ∈ E: reflexiv irreflexiv transitiv symmetrisch antisymmetrisch linear konnex xRx ¬xRx xRy und yRz −→ xRz xRy −→ yRx xRy und yRx −→ x = y xRy oder yRx xRy oder yRx oder x = y R heißt . . . . . . falls R . . . reflexive Halbordnung irreflexive Halbordnung reflexive Ordnung irreflexive Ordnung reflexiv, transitiv und antisymmetrisch ist. irreflexiv und transitiv ist. lineare reflexive Halbordnung ist. konnexe irreflexive Halbordnung ist. Beispiele. Menge E 6= ∅ 2M IN, ZZ, Q I , IR reflexiv irreflexiv Halbordnung Ordnung ⊆, ⊇ ≤, ≥ ⊂, ⊃ <, > Definition 4. Sei E 6= ∅, ≤ eine reflexive Halbordnung in E, M ⊆ E. 22 Besonderes Element von E Definierende Eigenschaft(en) s ist obere Schranke von M ∀x ∈ M : x ≤ s s ist untere Schranke von M ∀x ∈ M : x ≥ s g ≡ sup M ist obere Grenze oder Supremum 1. g ist obere Schranke von M und oder kleinste obere Schranke von M 2. g ≤ s f¨ ur jede obere Schranke s von M g ≡ inf M ist untere Grenze oder Infimum oder gr¨ oßte untere Schranke von M 1. g ist untere Schranke von M und 2. g ≥ s f¨ ur jede untere Schranke s von M m ≡ max M ist gr¨oßtes Element oder Maximum von M 1. m ist obere Schranke von M und 2. m ∈ M m ≡ min M ist kleinstes Element 1. m ist untere Schranke von M und oder Minimum von M 2. m ∈ M M heißt nach oben beschr¨ankt, falls M eine obere Schranke besitzt, . . . nach unten beschr¨ankt, falls M eine untere Schranke besitzt, . . . beschr¨ ankt, falls M sowohl nach oben als auch nach unten beschr¨ankt ist. Diskussion von g = sup M : 1. bedeutet ∀x ∈ M : x ≤ g 2. bedeutet ∀x ∈ M : x ≤ s −→ g ≤ s Kontraposition von 2. lautet: s < g −→ ∃x ∈ M : x > s. Diskussion von g = inf M : 1. bedeutet ∀x ∈ M : x ≥ g 2. bedeutet ∀x ∈ M : x ≥ s −→ g ≥ s Kontraposition von 2. lautet: s > g −→ ∃x ∈ M : x < s. Satz 1. 1. Es gibt jeweils h¨ochstens ein (d. h. ein oder kein) sup M , inf M , max M , min M . 2. Existiert max M , so existiert auch sup M und es ist dann max M = sup M ; existiert min M , so existiert auch inf M und es ist dann min M = inf M . 3. Es gilt sup M = min{s|s ist obere Schranke von M }, inf M = max{s|s ist untere Schranke von M }. ¨ Beweis. Ubung. Beispiele. Sei ≤ die nat¨ urliche reflexive Ordnung in IR, M eine Teilmenge von IR wie angegeben: 23 M sup M inf M max M min M {0} 0 0 0 {1, 2, . . . , n} n 1 n IN / 1 / [a, b] b a b ]a, b[ b a / IR+ := {x ∈ IR|x > 0} / 0 / IR / / / / bedeutet hier: Ein solches Element existiert nicht. 0 1 1 a / / / ¨ Definition 5. Eine Aquivalenzrelation ∼ in einer Menge E 6= ∅ ist eine reflexive, transitive und symmetrische Relation in E. D. h. ∀x, y, z ∈ E : x ∼ x, x ∼ y und y ∼ z −→ x ∼ z, x ∼ y −→ y ∼ x. Bemerkung. x ∼ y liest man: x ist ¨ aquivalent (zu) y. Oft sagt man auch anstelle von aquivalent: ¨ahnlich, gleichartig, vom gleichen Typ, . . . . ¨ Beispiele. Menge E 6= ∅ ¨ Aquivalenzrelation in E beliebig Gleichheit = ¨ Menge der Terme der Aussagenlogik logische Aquivalenz ⇐⇒ ∼ Menge der geometrischen Figuren Kongruenz = in der Geometrie (Zwei Figuren heißen kongruent, F1 ∼ = F2 , falls es eine Bewegung gibt, welche F1 in F2 transformiert.) ¨ Definition 6. Sei ∼ eine Aquivalenzrelation in E. Die Teilmenge von E [x] := {y ∈ E|x ∼ y} ¨ heißt die Aquivalenzklasse von x ∈ E. Satz 2. Es gilt [x] = [y] genau dann, wenn x ∼ y. Beweis. (−→) [x] = [y] =⇒ y ∈ [x] =⇒ x ∼ y. (←−) Sei x ∼ y. z ∈ [x] =⇒ z ∼ x ∼ y =⇒ z ∼ y =⇒ z ∈ [y]. Also [x] ⊆ [y]. Analog [y] ⊆ [x]. Zusammen [x] = [y]. 24 Definition 7. Eine Zerlegung oder Partition einer Menge E 6= ∅ ist eine Menge P von Teilmengen X, Y, · · · ⊆ E, genannt Klassen, so daß 1. ∅ ∈ / P. D. h. ∅ ist keine Klasse. 2. ∀X, Y ∈ P : X ∩ Y = ∅ oder X = Y . D. h. die Klassen sind paarweise disjunkt. S S 3. P = E, wobei P := Vereinigung aller Klassen X ∈ P. D. h. jedes x ∈ E ist in einer Klasse X enthalten. Ein x ∈ X heißt ein Repr¨asentant der Klasse X ∈ P. Mengendiagramm. E X Y x Bemerkungen. Logisch ¨aquivalent zu 2. ist X ∩ Y 6= ∅ −→ X = Y . F¨ ur 3. sagt man auch: Die Zerlegung P u ¨berdeckt E. Beispiele. Menge E Zerlegung P Menge aller Sch¨ uler x, y, . . . einer Schule Menge der Klassen X, Y, . . . im u ¨blichen Sinn IR Menge der Invervalle [n, n + 1[ mit n ∈ ZZ ZZ Menge der Restklassen [0], [1], . . . [n − 1] modulo einer festen Zahl n ∈ IN. Dabei ist [r] := {kn + r|k ∈ ZZ} f¨ ur r = 0, 1, . . . , n − 1 r heißt der Rest bei Division von m = kn + r durch n. ¨ ¨ Satz 3. Ist ∼ eine Aquivalenzrelation in E, so ist die Menge der Aquivalenzklassen, genannt Faktormenge, P = E/∼ := {[x]|x ∈ E} eine Zerlegung von E. Beweis. 1. Jede Klasse ist 6= ∅, denn x ∈ [x]. 2. [x] ∩ [y] 6= ∅ =⇒ ∃z ∈ [x] ∩ [y] =⇒ ∃z : z ∈ [x] ∧ z ∈ [y] =⇒ ∃z : x ∼ z ∧ z ∼ y =⇒ x ∼ y =⇒ [x] = [y] 25 3. Die Klassen u ¨berdecken E, denn jedes x ist in einer Klasse, n¨amlich [x], enthalten. Satz 4. Ist P eine Zerlegung von E, so ist die durch x ∼ y :⇐⇒ ∃X ∈ P : x, y ∈ X ¨ definierte Relation ∼, genannt Klassengleichheit, eine Aquivalenzrelation in E. Beweis. 1. Reflexivit¨at: x ∼ x, da x in der Klasse von x liegt. 2. Transitivit¨at: x ∼ y und y ∼ z bedeutet ∃X ∈ P : x, y ∈ X und ∃Y : P : y, z ∈ Y . Da y ∈ X ∩ Y 6= ∅ muß X = Y gelten. Aus x, z ∈ X folgt x ∼ z. 3. Symmetrie: x ∼ y =⇒ x liegt in der Klasse von y =⇒ y liegt in der Klasse von x =⇒ y ∼ x. ¨ Satz 5. Hauptsatz u ¨ber Aquivalenzrelationen: ¨ Aquivalenzrelationen ∼ in E und Zerlegungen P von E entsprechen einander eineindeutig verm¨ oge P := E/∼ :≡ {[x]|x ∈ E} mit [x] := {y ∈ E|x ∼ y} und x ∼ y :⇐⇒ ∃X ∈ P : x, y ∈ X. Zum Beweis w¨are noch zu zeigen: Die Zuordnungen ¨ Aquivalenzrelation ∼ 7→ Faktormenge P = E/∼ Zerlegung P 7→ Klassengleichheit ∼. sind Umkehrungen voneinander. Beispiel. E = Menge konkreter Dinge, ∼ = Gleichfarbigkeit. Dann ist [x] = Farbe von x ≡ {y ∈ E | y gleichfarbig zu x}, P = E/∼ = { Rot, Gr¨ un, Blau, . . . } = Menge der Farben. 2.5 “Gr¨ oßenvergleich” von Mengen Idee. Zwei Mengen X, Y sind gleichm¨ achtig, d. h. haben im anschaulichen Sinn gleichviele Elemente, falls man jedem x ∈ M bijektiv ein y ∈ N zuordnen kann. M ist m¨ achtiger als N , d. h. M hat im anschaulichen Sinn mehr Elemente als N , falls nicht M aber eine echte Teilmenge M1 von M gleichm¨achtig zu N ist. Definition 1. Eine Menge M ist gleichm¨ achtig zu einer Menge N , M ∼ N , falls es eine Bijektion F : M −→ N gibt. M ist m¨ achtiger als N , M > N , oder auch N < M , falls nicht M ∼ N , aber ein M1 ⊂ M mit M1 ∼ N existiert. 26 Beispiele. 1. ZZ ∼ IN verm¨oge der Bijektion ZZ = { 0, 1, –1, 2, –2, 3, ↓ ↓ ↓ ↓ ↓ ↓ IN = { 1 2 3 4 5 6 2. IR ∼] − 1, 1[ verm¨oge der Bijektion –3, . . . } ↓ 7 ...} x 7→ y = tanh x y 1 x −1 Satz 1. Eigenschaften der Gleichm¨achtigkeit: 1. Reflexivit¨at: M ∼ M , 2. Transitivit¨at: M ∼ N und N ∼ L −→ M ∼ L, 3. Symmetrie: M ∼ N −→ N ∼ M Folgerung. In jedem nichtleeren Mengensystem (d. h. Menge von Mengen) ist ∼ eine ¨ Aquivalenzrelation. Beweis. 1. Die identische Abbildung M −→ M , x 7→ x ist eine Bijektion also M ∼ M . 2. M ∼ N und N ∼ L =⇒ ∃ Bijektion F : M −→ N und ∃ Bijektion G : N −→ L =⇒ ∃F, G : G ◦ F ist Bijektion M −→ L =⇒ M ∼ L. 3. M ∼ N =⇒ ∃ Bijektion F : M −→ N =⇒ ∃F : F −1 ist Bijektion N −→ M =⇒ N ∼ M . Satz 2. Eigenschaften der Relation < zwischen Mengen: Irreflexivit¨at: nicht M < M , Transitivit¨at: M < N und N < L −→ M < L. Folgerung. In jedem nichtleeren Mengensystem ist < eine irreflexive Halbordnung. Satz 3. F¨ ur jede Menge M ist die Potenzmenge von M m¨ achiger als M selbst: M < 2M . Indirekter Beweis. Angenommen M ∼ 2M =⇒ ∃ Bijektion F : M −→ 2M , x 7→ F (x). Betrachten dann M0 := {x ∈ M |x ∈ / F (x)} und x0 := F −1 (M0 ). 27 Die Annahme x0 ∈ M0 f¨ uhrt auf x0 ∈ / F (x0 ) = M0 . Die entgegengesetzte Annahme x0 ∈ / M0 f¨ uhrt auf x0 ∈ F (x0 ) = M0 . Da sich in jedem Fall ein Widerspruch ergibt, gilt nicht M ∼ 2M . Es ist aber M ∼ P := {{x} | x ∈ M } ⊂ 2M . Folgerung. Zu jeder Menge M gibt es Mengen gr¨oßerer M¨achtigkeit. Definition 2. Eine Menge M heißt unendlich, falls sie zu einer ihrer echten Teilmengen M1 gleichm¨achtig ist, d. h. M1 ⊂ M und M1 ∼ M , endlich sonst. Beispiele. ∅, {a}, {a, b}, {a, b, c}, . . . sind endliche Mengen. Die Zahlbereiche IN, ZZ, Q I , IR sind unendliche Mengen. Beispielsweise ist IN ∼ {2n|n ∈ IN} verm¨oge n 7→ 2n, IR ∼ {x ∈ IR|x > 0} verm¨oge x 7→ ex . Geschichte. Die Begriffe “gleichm¨ achtig” und “m¨ achtiger als” waren zun¨achst die wichtigsten Innovationen in Cantor’s Mengenlehre (ab 1874). Er f¨ uhrte auch die “M¨ achtigkeit” als Verallgemeinerung der Elementeanzahl auf beliebig große Mengen ein. Die M¨achtigkeiten heißen auch Kardinalzahlen und man kann mit ihnen rechnen. Die obige Definition einer unendlichen bzw. endlichen Menge stammt von R. Dedekind (1887). 3 Arithmetik (= Zahlenlehre) 3.1 Idee. Nat¨ urliche Zahlen 1 = Klasse aller Einermengen {a}, 2 = Klasse aller echten Zweiermengen {a, b}, 3 = Klasse aller echten Dreiermengen {a, b, c} usw.. Definition 1. Konstruktive Definition von IN: ¨ Eine nat¨ urliche Zahl ist eine Aquivalenzklasse im System E der nichtleeren endlichen Mengen bez¨ uglich der Gleichm¨achtigkeit ∼, d. h. ein Element von IN := E/∼ . Man setzt ¨ |M | := Aquivalenzklasse von M ∈ E bez¨ uglich ∼. |M | heißt auch Elementeanzahl von M . Beispiele. 1 = |{a}|, 2 = |{a, b}| falls a 6= b, 3 = |{a, b, c}| falls a 6= b, a 6= c, b 6= c usw.. 28 Definition 2. Arithmetik zur konstruktiven Definition von IN: F¨ ur nichtleere endliche Mengen M , N setzt man |M | + |N | := |M ∪ N |, wenn M ∩ N = ∅, |M | · |N | := |M × N |, |M | < |N | :⇐⇒ M < N (d. h. N ist m¨achtiger als M ). Bemerkung. Zur Rechtfertigung dieser Definition ist zu zeigen, daß |M ∪ N |, |M × N | sowie die G¨ ultigkeit von M < N nur von |M |, |N | und nicht von der Wahl der Repr¨asentanten M, N abh¨angen. Definition 3. sonst. Eine unendliche Menge M heißt abz¨ ahlbar, falls M ∼ IN gilt, u ¨berabz¨ahlbar Folgerung. Klassifikation aller Mengen: endlich Menge   abz¨ahlbar HH H unendlich } h¨ochstens abz¨ahlbar   H HH u ¨berabz¨ahlbar Bemerkung. M ist genau dann abz¨ahlbar, falls sich alle Elemente von M als eine unendliche Folge x1 , x2 , x3 , . . . mit paarweise verschiedenen Gliedern, d. h. xn 6= xm f¨ ur n 6= m, anordnen lassen. Denn eine solche Folge ist eine Bijektion IN −→ M , n 7→ xn ; deren Existenz bedeutet IN ∼ M . Dann ist auch M ∼ IN. Definition 4. Axiomatische Definition von IN (nach G. Peano 1891): I. 1 ist eine nat¨ urliche Zahl. 1 ∈ IN. II. Jede nat¨ urliche Zahl n hat genau einen Nachfolger n0 . ∀n ∃!m : n0 = m. III. Jede nat¨ urliche Zahl hat h¨ochstens einen Vorg¨anger. ∀n, m : n0 = m0 −→ n = m. IV. 1 hat keinen Vorg¨anger. ¬∃n : n0 = 1. V. Induktionsaxiom: Enth¨alt M ⊆ IN die 1 und mit jeder nat¨ urlichen Zahl n auch den 0 Nachfolger n , so ist M = IN. ∀M (M ⊆ IN ∧ 1 ∈ M ∧ (n ∈ M −→ n0 ∈ M ) −→ M = IN). Satz 1. Prinzip des Beweisens durch vollst¨andige Induktion: Sei A ein Pr¨adikat nat¨ urlicher Zahlen. Aus A(1) und ∀n ∈ IN : A(n) −→ A(n0 ) folgt 29 ∀n ∈ IN : A(n). Beweis. M := {n ∈ IN|A(n)} erf¨ ullt nach Voraussetzung das Induktionsaxiom =⇒ M = IN =⇒ Behauptung ∀n ∈ IN : A(n). Bemerkung. In Satz 1 heißt A(1) Induktionsanfang, A(n) Induktionsvoraussetzung, A(n0 ) Induktionsbehauptung, der Beweis von A(n) −→ A(n0 ) Induktionsschritt. Satz 2. Prinzip der rekursiven Definition: Zu einer Menge M 6= ∅, einem Anfangselement a ∈ M und einer Abbildung F : M −→ M gibt es genau eine Abbildung IN −→ M , n 7→ xn mit x1 = a und xn0 = F (xn ). Anschaulicher Beweis. Definieren Pr¨adikat A durch A(n) :⇐⇒ xn ist eindeutig berechenbar. A(1) ist wahr, denn x1 = a. A(n) −→ A(n0 ) ist wahr, denn xn0 = F (xn ). Nach Satz 1 gilt ∀n ∈ IN : A(n). Bemerkung. In Satz 2 heißt x1 = a Rekursionsanfang, xn0 = F (xn ) Rekursionsschritt. Definition 5. Arithmetik zur axiomatischen Definition von IN. Addition +, Multiplikation · und Potenzieren werden wie folgt rekursiv definiert. Dabei sei m ∈ IN beliebig. Operation in IN Addition m + n Multiplikation m · n Potenzieren mn Rekursionsanfang Rekursionsschritt m + 1 := m0 m · 1 := m m1 := m m + n0 := (m + n)0 m · n0 := mn + m 0 mn := mn · m Die Kleiner–Relation < und die Teilbarkeit | werden mittels + bzw. · definiert. m ist kleiner als n, m < n, falls ∃l : m + l = n. m teilt n, m|n, falls ∃l : m · l = n. Geschichte. Schon das vorwissenschaftliche Denken geht mit nat¨ urlichen Zahlen um. Die F¨ahigkeit dazu ist dem Menschen angeboren. Die oben angegebenen u ¨blichen Axiome der nat¨ urlichen Zahlen stammen von Guiseppe Peano (1891), mit Richard Dedekind (1888) und Hermann Grassmann (1861) als Vorl¨aufer. Alle drei Autoren behandelten das Prinzip der vollst¨andigen Induktion. 3.2 Ganze und rationale Zahlen Idee. Ganze Zahl := Differenz m − n nat¨ urlicher Zahlen m, n 30 ¨ :≡ Aquivalenzklasse von Zahlenpaaren (m, n) bez¨ uglich der Differenzengleichheit ∼, definiert durch (m1 , n1 ) ∼ (m2 , n2 ) ⇐⇒ m1 − n1 = m2 − n2 :⇐⇒ m1 + n2 = m2 + n1 Definition 1. Konstruktive Definition von ZZ: ¨ Eine ganze Zahl ist eine Aquivalenzklasse in IN × IN bez¨ uglich der durch (m1 , n1 ) ∼ (m2 , n2 ) :⇐⇒ m1 + n2 = m2 + n1 ¨ ¨ definierten Aquivalenzrelation ∼; d. h. ein Element von ZZ := IN × IN/∼ . Die Aquivalenzklasse von (m, n) heißt auch Differenz m − n. Es sei n ∈ IN mit (n + 1) − 1 ∈ ZZ identifiziert und so eine Einbettung IN ⊂ ZZ definiert. Definition 2. Arithmetik zur konstruktiven Definition von ZZ: F¨ ur m, n, k, l ∈ IN setzt man (m − n) + (k − l) := (m + k) − (n + l), (m − n) · (k − l) := (mk + nl) − (ml + nk), m − n ≤ k − l :⇐⇒ m + l ≤ k + n. Bemerkung. Zur Rechtfertigung dieser Definition ist zu zeigen, daß die Ausdr¨ ucke nur von m − n, k − l und nicht von der Wahl der Repr¨asentanten (m, n), (k, l) abh¨angen. Definition 3. Axiomatische Definition von ZZ: I. (ZZ, +, ·) ist ein kommutativer Ring mit Einselement 1. D. h. es gelten Axiome der Addition: Kommutativgesetz: m + n = n + m, Assoziativgesetz: (m + n) + l = m + (n + l), Existenz der Null: ∃0 ∈ ZZ ∀n ∈ ZZ : n + 0 = 0 + n = n, Existenz der entgegengesetzten Zahl: ∀n ∈ ZZ ∃ − n ∈ ZZ : n + (−n) = (−n) + n = 0. Axiome der Multiplikation: Kommutativgesetz: m · n = n · m, Assoziativgesetz: (m · n) · l = m · (n · l), Distributivgesetz: m · (n + l) = m · n + m · l, Einselement: 1 · n = n · 1 = n, 1 6= 0. II. (ZZ, +, ·) ist der kleinste kommutative Ring mit Einselement 1, der (IN, +, ·) enth¨alt. D. h. jeder kommutative Ring mit 1, der (IN, +, ·) enth¨alt, enth¨alt auch (ZZ, +, ·). Definition 4. m − n := m + (−n), n < m :⇐⇒ m − n ∈ IN. Bemerkung. Oft k¨ urzt man ab mn := m · n. Idee. Rationale Zahl 31 := Quotient m ganzer Zahlen m, n mit n 6= 0 n ¨ :≡ Aquivalenzklasse von Zahlenpaaren (m, n) bez¨ uglich der Quotientengleichheit ∼, definiert durch 1 2 (m1 , n1 ) ∼ (m2 , n2 ) ⇐⇒ m =m :⇐⇒ m1 n2 = m2 n1 n1 n2 Definition 5. Konstruktive Definition von Q I: ¨ Eine rationale Zahl ist eine Aquivalenzklasse in ZZ × (ZZ \ {0}) bez¨ uglich der durch (m1 , n1 ) ∼ (m2 , n2 ) :⇐⇒ m1 n2 = m2 n1 ¨ ¨ definierten Aquivalenzrelation ∼, d. h. ein Element von Q I := ZZ × (ZZ \ {0})/∼ . Die Aquivalenzklasse von (m, n) heißt auch Quotient m . Es sei n ∈ Z mit n1 ∈ Q I identifiziert und so eine n Einbettung ZZ ⊂ Q I definiert. Definition 6. Arithmetik zur konstruktiven Definition von Q I: F¨ ur m, k ∈ ZZ und n, l ∈ IN setzt man m + n m · n m ≤ n k ml + kn := , l nl k mk := , l nl k :⇐⇒ ml ≤ kn. l Bemerkung. Auch diese Definition ist zu rechtfertigen. Definition 7. Axiomatische Definition von Q I: I. (Q I , +, ·, ≤) ist ein geordneter K¨ orper. D. h. es gelten Axiome der Addition: Kommutativgesetz: a + b = b + a, Assoziativgesetz: (a + b) + c = a + (b + c), Existenz der Null: ∃0 ∈ Q I ∀a ∈ Q I : a + 0 = 0 + a = a, Existenz der entgegengesetzten Zahl: ∀a ∈ Q I ∃−a∈Q I : a + (−a) = (−a) + a = 0. Axiome der Multiplikation: Kommutativgesetz: a · b = b · a, Assoziativgesetz: (a · b) · c = a · (b · c), Einselement: ∃1 ∈ Q I ∀a ∈ Q I : a · 1 = 1 · a = a, 1 6= 0, Existenz der reziproken Zahl: ∀a ∈ Q I mit a 6= 0 ∃ a1 ∈ Q I : a · a1 = a1 · a = 1, Distributivgesetz: a · (b + c) = a · b + a · c. 32 II. Axiome der Anordnung: Reflexivit¨at: a ≤ a, Transitivit¨at: a ≤ b und b ≤ c −→ a ≤ c, Antisymmetrie: a ≤ b und b ≤ a −→ a = b, Linearit¨at: a ≤ b oder b ≤ a, Monotonie von + : a ≤ b −→ a + c ≤ b + c, Monotonie von · : a ≤ b und 0 ≤ c −→ a · c ≤ b · c. (Q I , +, ·) ist der kleinste K¨orper, der (ZZ, +, ·) enth¨alt. D. h. jeder K¨orper, der (ZZ, +, ·) enth¨alt, enth¨alt auch (Q I , +, ·). a Definition 8. a − b := a + (−b), := a · 1b f¨ ur b 6= 0, b a < b :⇐⇒ a ≤ b und a 6= b, a ≥ b :⇐⇒ b ≤ a, a > b :⇐⇒ a ≥ b und a 6= b. Satz 1. ZZ und Q I sind abz¨ahlbar. Beweis. 1. Die Elemente von ZZ lassen sich zu einer unendlichen Folge anordnen: 0, 1, −1, 2, −2, 3, −3, . . . . 2. Alle positiven rationalen Zahlen, also alle Elemente von Q I + := {x ∈ Q I | x > 0} lassen sich folgendermaßen zu einer unendlichen Folge anordnen: • Man arrangiere die Br¨ uche wie eine unendliche Matrix: 1 , 1 1 , 2 1 , 3 ... 2 , 1 2 , 2 2 , 3 ... 3 , 1 3 , 2 3 , 3 ... • Man numeriere die Matrixelemente in der Reihenfolge 1 2 . 3 4 . 5 . 6 7 ... . 8 ... . 9 ... . 10 . . . • Man modifiziere die Numerierung, indem man nicht teilerfremde Br¨ uche 1 1 1 2 3 diese Weise wird Q I + als Folge angeordnet: 1, 2 , 2, 3 , 3, 4 , 3 , 2 , 4, . . . . m n u ¨berspringt. Auf Bemerkung. Die Numerierung im obigen Beweis heißt Abz¨ ahlung nach Diagonalen oder 1. Cantorsches Diagonalverfahren. 33 ¨ Geschichte. Schon die alten Babylonier, Agypter und Inder rechneten mit ganzen und rationalen Zahlen. H. Grassmann (1809–1877), R. Dedekind (1831–1916) und andere begr¨ undeten die moderne Arithmetik der ganzen und rationalen Zahlen. Die oben verwendeten Begriffe Ring, kommutativer Ring, K¨ orper, geordneter K¨ orper sind Grundbegriffe der Allgemeinen Algebra, welche sich parallel zur Arithmetik im 19. Jahrhundert herausbildete. 3.3 Reelle Zahlen Definition 1. Axiomatische Definition von IR: I. (IR, +, ·, ≤) ist ein geordneter K¨ orper. D. h. es gelten Axiome der Addition, Axiome der Multiplikation, Axiome der Anordnung w¨ortlich wie f¨ ur (Q I , +, ·, ≤). II. Vollst¨andigkeitsaxiom oder auch Axiom der oberen Grenze: Jede nach oben beschr¨ankte nichtleere Menge reeller Zahlen besitzt ein Supremum. ∅= 6 M ⊂ IR und ∃s ∈ IR ∀x ∈ M : x ≤ s −→ sup M existiert. III. (IR, +, ·, ≤) ist der kleinste vollst¨andige (d. h. dem Vollst¨andigkeitsaxiom gen¨ ugende) geordnete K¨orper, der (ZZ, +, ·, ≤) enth¨alt. D. h. jeder solche K¨orper enth¨alt auch (IR, +, ·, ≤). a Definition 2. a − b := a + (−b), := a · 1b f¨ ur b 6= 0, b a < b :⇐⇒ a ≤ b und a 6= b, a ≥ b :⇐⇒ b ≤ a, a > b :⇐⇒ a ≥ b und a 6= b. Satz 1. Archimedisches “Axiom”: (IR, +, ·, ≤) ist ein archimedischer K¨ orper, d. h. ∀a, b ∈ IR mit a > 0, b > 0 ∃n ∈ IN : na > b. Indirekter Beweis. Angenommen, die Behauptung gilt nicht, d. h. ∃a, b ∈ IR mit a > 0, b > 0, ∀n ∈ IN : na ≤ b. Dann ist das Vollst¨andigkeitsaxiom auf M := {na|n ∈ IN} anwendbar; sei g := sup M . Zum einen ist g eine obere Schranke von M , d. h. ∀n ∈ IN : na ≤ g. Zum anderen ist die kleinere Zahl g − a keine obere Schranke von M , d. h. ∃m ∈ IN : ma > g − a, ¨aquivalent (m + 1)a > g. Beide S¨atze zusammen ergeben einen Widerspruch, wenn man n = m + 1 setzt. Satz 2. Dichtheit von Q I in IR: Es gibt isomorphe (d. h. strukturerhaltende) Einbettungen IN ⊂ ZZ ⊂ Q I ⊂ IR. Dabei ist Q I dicht in IR, d. h. zwischen zwei verschiedenen reellen Zahlen a, b liegt stets eine rationale Zahl r: ∀a, b ∈ IR : a < b −→ ∃r ∈ Q I : a < r < b. ¨ Beweis Ubung. 34 Zusatz. Den Axiomen f¨ ur das Rechnen mit reellen Zahlen wird noch ein “Geometrie–Axiom” hinzugef¨ ugt, welches wir hier nur anschaulich beschreiben: Die reellen Zahlen lassen sich durch die Punkte einer beliebig fest gew¨ahlten Gerade g Anschauungsraum treu darstellen. D. h. es gibt eine Bijektion IR −→ g, welche “rechnerische” Sachverhalte in IR als geometrische Sachverhalte in g darstellt (und umgekehrt). Wenn a < b, so liegt der Punkt zu a links von dem Punkt zu b (und umgekehrt). Dann ist b − a gleich dem Abstand der beiden Punkte auf g. Geschichte. Die alten Griechen haben nur die rationalen Zahlen als “Zahlen” anerkannt. Sie wußten schon, daß jede “Zahl” als die L¨ange einer Strecke auftritt, aber nicht umgekehrt. Die Menge Q I der rationalen Zahlen ist im anschaulichen Sinn “l¨ uckenhaft”. Durch Ausf¨ ullen der L¨ ucken gelangt man auf konstruktive Weise zur Menge IR der reellen Zahlen. Diese “Vervollst¨ andigung” kann auf verschiedene Weise bewerkstelligt werden. Fr¨ uher benutzte man h¨aufig sogenannte Dedekindsche Schnitte (nach R. Dedekind, 1872); heute bevorzugt man das Axiom der oberen Grenze. Im Verlauf des Mathematikstudiums werden noch andere M¨oglichkeiten der Vervollst¨andigung behandelt. Definition 3. (Wiederholung.) Betrachten eine Teilmenge M ⊆ IR. Besondere Zahl Definierende Eigenschaft(en) s ist obere Schranke von M ∀x ∈ M : x ≤ s s ist untere Schranke von M ∀x ∈ M : x ≥ s g ≡ sup M ist obere Grenze oder Supremum 1. g ist obere Schranke von M und oder kleinste obere Schranke von M 2. ∀ε > 0 ∃x ∈ M : x > g − ε g ≡ inf M ist untere Grenze oder Infimum oder gr¨ oßte untere Schranke von M 1. g ist untere Schranke von M und 2. ∀ε > 0 ∃x ∈ M : x < g + ε m ≡ max M ist gr¨oßtes Element oder Maximum von M 1. m ist obere Schranke von M und 2. m ∈ M m ≡ min M ist kleinstes Element oder Minimum von M 1. m ist untere Schranke von M und 2. m ∈ M Beispiele. 1. M = { n1 |n ∈ IN} hat sup M = max M = 1; inf M = 0; min M existiert nicht. Beweis von inf M = 0. 1. 0 ist untere Schranke von M . 2. Jede gr¨oßere Zahl 0 + ε ist nicht mehr untere Schranke: N¨amlich ∃x ∈ M : x < 0 + ε ⇐⇒ ∃n ∈ IN : n1 < ε ⇐⇒ n > 1ε . Solche n existieren nach dem Archimedischen Axiom. 1 2. M = {1 − 2n+1 | n ∈ IN} hat sup M = 1; max M existiert nicht; inf M = min M = 23 . Beweis von sup M = 1. 35 1. ∀n ∈ IN : 1 − 1 2n+1 < 1 =⇒ 1 ist obere Schranke von M . 1 2. Jeder kleinere Zahl 1 − ε ist nicht mehr obere Schranke: N¨amlich 1 − 2n+1 > 1 − ε ⇐⇒ 1 1 1−ε < ε ⇐⇒ 2n + 1 > ⇐⇒ n > . Solche n existieren nach dem Archimedischen Axiom. 2n+1 ε 2ε Definition 4. “Uneigentlicher” Gebrauch von sup und inf: Ist M ⊆ IR nicht nach oben beschr¨ankt, so setzt man sup M = +∞. Ist M ⊆ IR nicht nach unten beschr¨ankt, so setzt man inf M = −∞. 3.4 Ungleichungen Satz 1. Elementare Ungleichungen: a+b a < b −→ a < < b, Es gilt f¨ ur a, b ∈ IR: 2 - a a+b 2 ab ≤  a+b 2 2 b ≤ a2 + b 2 , 2 wobei a2 := a · a, b2 := b · b usw. Beweis. a b a < b =⇒ < 2 2 ( + a2 + 2b =⇒ ( a< a+b 2 a+b 2 a}, ] − ∞, b] := {x ∈ IR|x ≤ b}, ] − ∞, b[:= {x ∈ IR|x < b}, ] − ∞, +∞[:= IR. Unbeschr¨ ankte Intervalle reeller Zahlen: Definition 2. Der (Absolut–)Betrag von x ist |x| := Das Vorzeichen oder Signum von x ist Satz 2. Eigenschaften Positive Definitheit: Dreiecksungleichung: Multiplikativit¨at:  x f¨ ur x ≥ 0 −x f¨ ur x < 0  ur x > 0  1 f¨ 0 f¨ ur x = 0 sgn x :=  −1 f¨ ur x < 0 von | | und sgn . |x| ≥ 0 und |x| = 0 gdw. x = 0, ||x| − |y|| ≤ |x + y| ≤ |x| + |y|, |x · y| = |x| · |y|, x = (sgn x) · |x|, |x| = (sgn x) · x Beweis der Dreiecksungleichung: x ≤ |x| −x ≤ |x| y ≤ |y| −y ≤ |y| addiert x + y ≤ |x| + |y| −(x + y) ≤ |x| + |y| Eine der beiden linken Seiten ist |x + y|. =⇒ |x + y| ≤ |x| + |y|. Weiter 37 x |x| ≡ |(x + y) − y| ≤ |x + y| + | − y| = |x + y| + |y| =⇒ |x| − |y| ≤ |x + y|. Analog |y| − |x| ≤ |x + y|. Eine der beiden linken Seiten ist ||x| − |y||. =⇒ ||x| − |y|| ≤ |x + y|. Definition 3. Uε (x0 ) :=]x0 − ε, x0 + ε[ mit ε > 0 heißt auch ε–Umgebung von x0 . - x0 − ε x0 x0 + ε x Satz 3. Die folgenden Aussagen sind ¨ aquivalent: x ∈ Uε (x0 ), x0 ∈ Uε (x), −ε < x − x0 < ε, −ε < x0 − x < ε, |x − x0 | < ε. Dann ist auch ||x| − |x0 || < ε. Beweis. x ∈ Uε (x0 )≡]x0 − ε, x0 + ε[ ⇐⇒ x0 − ε < x < x0 + ε ⇐⇒ −ε < x − x0 < ε ⇐⇒ x − x0 < ε und x0 − x < ε ⇐⇒ |x − x0 | < ε. In der letzten Bedingung k¨onnen x, x0 vertauscht werden. Beachte noch ||x| − |x0 || ≤ |x − x0 |. Definition 4. Grundbegriffe der Fehlerrechnung: Sei x0 ein (im allgemeinen unbekannter) exakter Wert, x ein (im allgemeinen bekannter) N¨ aherungswert einer Gr¨oße. Man schreibt dann auch x ≈ x0 . x − x0 heißt (absoluter) Fehler. x−x0 im Falle x0 6= 0 heißt relativer Fehler. x0 Wenn |x − x0 | ≤ ε ist, so heißt ε eine (absolute) Fehlerschranke. Man schreibt dann auch x0 = x ± ε. Bemerkungen. 1. Der relative Fehler ist dimensionslos (d. h. eine reine Zahl ohne Maßeinheit) und kann deshalb auch in 0/0 oder 0/00 angegeben werden. 2. Ist ε eine Fehlerschranke, so ist jede gr¨oßere Zahl ebenfalls eine Fehlerschranke. 38 Definition 5. Aufgabe der Fehlerabsch¨ atzung: Gegeben. N¨aherungswerte x, y, . . . Fehlerschranken ε, η, . . . , d. h. |x − x0 | ≤ ε, |y − y0 | ≤ η, . . . . Funktion f von x oder x, y oder . . . Gesucht. Brauchbare Fehlerschranken f¨ ur f (x) oder f (x, y) oder . . . . Dabei sei noch |x|, |x0 | > ε, |y|, |y0 | > η, . . . angenommen. Beispiele. 1. Betrachten f (x) = x2 . |x2 − x20 | = |(x − x0 )(x + x0 )| = |x − x0 | · |x + x0 | < ε(|x| + |x0 |) < ε(2|x| + ε) = 2ε|x| + ε2 Hierbei wurde verwendet |x − x0 | ≤ ε, |x + x0 | ≤ |x| + |x0 |, |x0 | ≤ |x| + ε. Der Summand ε2 kann praktisch vernachl¨assigt werden. 2. Betrachten f (x, y) = xy . x y − ≤ x0 y0 xy0 −x0 y xy0 −xy+xy−x0 y x(y0 −y)+(x−x0 )y = yy0 = = ≤ yy0 yy0 η|x|+ε|y| |y||y0 | ≤ |x||y0 −y|+|x−x0 ||y| |y||y0 | ≤ η|x|+ε|y| |y|(|y|−η) . Praktisch kann hier im Nenner |y| − η durch |y| ersetzt werden. 3.5 Summen und Produkte Definition 1. Eine (unendliche) Folge mit Werten in einer Menge E 6= ∅ ist eine Abbildung IN −→ E, n 7→ an . Eine endliche Folge mit Werten in E ist eine Abbildung {1, 2, . . . , n} −→ E, k 7→ ak . Definition 2. Rekursive Definitionen. Seien a, a1 , a2 , · · · ∈ IR. Die Summe n X ak ≡ a1 + a2 + · · · + an k=1 ist rekursiv definiert durch 1 X ak := a1 , k=1 Ferner sei n+1 X ak := k=1 n X ak := k=m+1 39 ak + an+1 . k=1 n−m X l=1 Das Produkt n X al+m . n Y ak ≡ a1 · a2 · · · · · an k=1 ist rekursiv definiert durch 1 Y ak := a1 , n+1 Y n Y ak := k=1 k=1 ak ! · an+1 . k=1 Ferner sei f¨ ur n, m ∈ IN, n > m an := n Y a, n Y a−n := (an )−1 , k=1 ak := k=m+1 n−m Y al+m . l=1 Zusatz zu Definition 1. Eine (unendliche) Doppelfolge mit Werten in E ist eine Abbildung IN × IN −→ E, (m, n) 7→ amn . Eine endliche Doppelfolge mit Werten in E ist eine Abbildung {1, 2, . . . , m} × {1, 2, . . . , n} −→ E, (k, l) 7→ akl . P Q Satz 1. Gesetze f¨ ur und : n m n P P P ak = ak + ak k=1 n P k=1 m P k=1 k=m+1 (ak + bk ) = k=1 n P ak + k=1  n P l=1 akl  n Q = n P l=1 n P n Q bk k=1  m P akl ak = k=1  m Q k=1 (ak · bk ) =   n  Q ak · ak k=m+1  k=1  m Q k=1 n Q   n  Q ak · bk n Q  k=1  k=1 n Q akl  l=1 = l=1 (ab)n = an bn an+m = an am (an )m = an·m Beweise durch vollst¨andige Induktion. Beispiele von Summenformeln: n n P P (2k − 1) = n2 , k = 12 n(n + 1), k=1 n P k=1 k=1 k 2 = 61 n(n + 1)(2n + 1), n P qk = k=0 1−q n+1 1−q Beweise durch vollst¨andige Induktion. 40 f¨ ur q 6= 1. k=1 m Q k=1 akl  Alternativ: Trick von C. F. Gauss (als Sch¨ uler!): n P F¨ ur gerades n: k =1 +2 +... + k=1 n 2 n 2 +
+1 +n + (n − 1) + . . . + = (n + 1) + (n + 1) + (n + 1) = n 2 +... n 2 (n + 1)
− mal F¨ ur ungerades n ist n X k=1 k= n−1 X k + n= k=1 n−1 n n + n = (n + 1). 2 2 Trick von Archimedes zur Berechnung von sn := n P q k f¨ ur q 6= 1: k=1 sn = 1 + q + q 2 + · · · + q n qsn = q + q 2 + · · · + q n + q n+1 Differenz sn − qsn ≡ (1 − q)sn = 1 − q n+1 1 − q n+1 =⇒ sn = 1−q Definition 3. Spezielle Produkte: n Fakult¨ at f¨ ur n ∈ IN ist die Zahl n! := n Y k ≡ 1 · 2 · · · n. k=1 Zus¨atzlich ist 0! := 1. Der Binomialkoeffizient n u ¨ber k f¨ ur n, k = 0, 1, 2, . . . ist   n n! . := k k!(n − k)! Der Binomialkoeffizient x u ¨ber k f¨ ur x ∈ IR, k ∈ IN ist   k x 1 Y x · (x − 1) · · · (x − k + 1) := (x − l + 1) ≡ . k k! l=1 1 · 2···k Zus¨atzlich ist x 0
:= 1 f¨ ur x ∈ IR. Bemerkung. Die Definitionen von n k
, x k
, x 0 41
sind miteinander vertr¨aglich. Beispiele.
5·4·3 5 = 1·2·3 = 10, 3 n n−k Satz 2. Es gilt
1 2 3 =
= n k
1 · 12 −1 2 ( )·( 12 −2) 1·2·3 und n−1 k−1
+ = n−1 k 1 . 16
n k
= f¨ ur n, k ∈ IN. ¨ Beweis. Ubung.
Bemerkung. Die Rekursionsgleichung von Satz 2 und die Anfangsbedingung n0 = 1 bestimmen zusammen die Binomialkoeffizienten eindeutig. Darauf beruht ein Schema der Binomialkoeffizienten, genannt Pascalsches Dreieck: 1 1 1 1 1 1 1 2 1 3 4 5 3 1 6 4 10 10 1 5 1 ... Satz 3. Binomischer Lehrsatz. F¨ ur a, b ∈ IR und n ∈ IN ist     n   X n n−k k n n−2 2 n 2 n−2 n n n−1 (a + b) = a b ≡ a + na b + a b + ··· + ab + nabn−1 + bn . k 2 2 k=0 Der Beweis benutzt Satz 2 und vollst¨andige Induktion bez¨ uglich n. Speziell f¨ ur n = 1, 2, 3 erh¨alt man (a + b)1 = a + b, (a + b)2 = a2 + 2ab + b2 , (a + b)3 = a3 + 3a2 b + 3ab2 + b3 . Satz 4. Lagrangesche Identit¨at. n X k,l=1  (ak bl − al bk )2 = 2  Beweis. Man wende n P n X a2k ! k=1 · n X l=1 b2l ! − n X k=1 ak b k !2  . auf (ak bl − al bk )2 = a2k b2l + a2l b2k − 2(ak bk )(al bl ) an. k,l=1 42 Satz 5. Wichtige Ungleichungen: 1. Verallgemeinerte Dreiecksungleichung: n n X X |ak |. ak ≤ k=1 k=1 2. Schwarzsche Ungleichung: n X ak b k k=1 !2 ≤ n X a2k ! n X · k=1 b2k ! . k=1 3. Bernoullische Ungleichung: (1 + a)n > 1 + na f¨ ur 1 + a > 0, n ∈ IN. Beweis. 1. Durch vollst¨andige Induktion. 2. Aus der Lagrangeschen Identit¨at folgt die zu 2. ¨aquivalente Absch¨atzung ! ! !2 n n n X X X 0≤ a2k · b2l − ak b k . k=1 l=1 k=1 3. Durch vollst¨andige Induktion: Induktionsanfang: (1 + a)1 = 1 + 1 · a richtig. Induktionsschritt: (1+a)n+1 = (1+a)(1+a)n ≥ (1+a)(1+na) = 1+na+a+na2 ≥ 1+(n+1)a Geschichte. Archimedes lebte 287–212 v.u.Z.. Carl Friedrich Gauss lebte 1777–1855. Das Pascalsche Dreieck ist nach Blaise Pascal (1623–1662) benannt, die Bernoullische Ungleichung nach Jakob I. Bernoulli (1654–1705), die Schwarzsche Ungleichung nach Hermann Amandus Schwarz (1843–1921). 3.6 Wurzeln, Potenzen mit rationalem Exponenten Definition 1. xn = a. Sei n ∈ IN. Die n–te Wurzel aus a > 0 ist die Zahl x =: √ n a mit x > 0 und Satz 1. Rechtfertigung von Definition 1: Existenz und Eindeutigkeit der n–ten Wurzel. ∀a ∈ IR mit a > 0 ∀n ∈ IN ∃! x ∈ IR : x > 0 und xn = a. Idee. x = sup M mit M := {z ∈ IR | z > 0 und z n ≤ a}. 43 Beweis. Fall a ≥ 1: 1 ≤ a =⇒ 1n ≤ a =⇒ 1 ∈ M =⇒ M 6= ∅. Wenden auf den Schluß z > a =⇒ z n > an ≥ a =⇒ z ∈ / M Kontraposition an und erhalten z ∈ M =⇒ z ≤ a. Das heißt, a ist obere Schranke von M . =⇒ x := sup M existiert. Angenommen xn > a. Dann gibt es ein ε > 0, so daß noch x − ε > 0 und (x − ε)n ≥ a.
n
≥ xn 1 − n xε ≡ xn − nεxn−1 ≥ a? Hierbei wurde die Probieren: (x − ε)n = xn 1 − xε xn −a Bernoullische Ungleichung benutzt. W¨ahlen also etwa ε < x und ε ≤ nx n−1 . Nach Definition n n von x = sup M ∃z ∈ M : z > x − ε > 0 =⇒ z > (x − ε) ≥ a. Widerspruch zur Definition von M . Angenommen xn < a ⇐⇒ x0 n > a0 mit x0 := x1 , a0 := a1 . Nach obiger Konstruktion gibt es ein ε0 mit x0 − ε0 > 0 und (x0 − ε0 )n ≥ a0 =⇒ x + ε := (x0 − ε0 )−1 definiert ein ε > 0 mit (x + ε)n = (x0 − ε0 )−n ≤ (a0 )−1 = a. =⇒ x + ε ∈ M =⇒ x ist nicht obere Schranke von M und damit nicht sup M . Widerspruch! Also ist xn = a. Der Fall 0 < a < 1 wird durch a0 := a1 , x0 := x1 , x0 n = a0 n auf den obigen Fall zur¨ uckgef¨ uhrt. n n Zeigen noch die Eindeutigkeit: Angenommen x1 = a, x2 = a und etwa 0 < x1 < x2 =⇒ 0 < a = xn1 < xn2 = a. Widerspruch! Also ist x1 = x2 . Spezialf¨ alle. √ n 0 := 0, √ 1 a := a, √ a := √ 2 a. Bemerkung. Die Gleichung xn = a hat folgende L¨osungsmenge in den angegebenen F¨allen: n gerade n ungerade √ n a>0 √ a, − n a √ n a Satz 2. Wurzelgesetze: F¨ ur 0 < a, b ∈ IR und n, m ∈ IN ist r √ n √ √ √ √ √
m a a n n n n a · b = a · b, = √ , n am = n a , n b b a<0 − q n ∅ p n √ m |a| a= q m √ n a= √ m·n a, √ n an = a. Definition 2. Potenz mit rationalem Exponenten: √ n r F¨ ur 0 < a ∈ IR, r = m ∈ Q I mit m ∈ Z Z und n ∈ IN sei a := am . n Rechtfertigung. Die Definition ist unabh¨angig von der Darstellung von r als Bruch. qp Wenn √ = kl mit m, k ∈ ZZ und n, l ∈ IN, so ist ml = kn =⇒ n am = n l (am )l = n¨amlich r = m n qp p p p √ √ √ √l n l n l l n ml kn kn a = a = a = l n (ak )n = ak . 44 Satz 3. Potenzgesetze f¨ ur rationale Exponenten: F¨ ur 0 < a, b ∈ IR und r, s ∈ Q I ist  a  r ar = r, ar+s = ar as , (ab)r = ar br , b b (ar )s = ar·s , a−r = 1 , ar < > 0 < a < b −→ ar = br je nachdem, ob r = 0, > < < > r < s −→ ar = as je nachdem, ob a = 1. > < Definition 3. Arithmetisches Mittel A, geometrisches Mittel G, harmonisches Mittel H von zwei Zahlen a, b > 0 sind A := a+b , 2 G := √ a · b, H := 1 a 2 . + 1b . . . von n Zahlen a1 , a2 , . . . , an > 0 sind A := a1 + a2 + · · · + an , n G := √ n a1 · a2 · · · an , H := 1 a1 + 1 a2 n + ··· + Satz 4. Jeder der Mittelwerte M = A, G, H gen¨ ugt min ak ≤ M ≤ max ak . 1≤k≤n 1≤k≤n Ferner gilt H ≤ G ≤ A. Beweis der letzten Formel f¨ ur n = 2: 2 √ a + b a+b Schon gezeigt ab ≤ =⇒ G = ab ≤ = A. 2 2 r 1 +1 1 1 1 1 Weiter = a b ≥ · = =⇒ H ≤ G. H 2 a b G Beispiel. Sei an = n. Dann ist v u n n √ uY 1X 1 1 n+1 n n k ≡ n! ≤ A = k = · · n(n + 1) = G= t n k=1 n 2 2 k=1 =⇒ Ungleichung n! ≤  45 n+1 2 n f¨ ur n ≥ 2. 1 an .