7 Abbildungen II: Injektivität, Surjektivität und Bijektivität 28
1
1 Grundlagen
1.1 Natürliche und ganze Zahlen
Wir beginnen mit einer kleinen Wiederholung über natürliche Zahlen1.Mit dem Symbol ℕ bezeichnen wir die Menge der natürlichen Zahlen, also
ℕ ∶= {1, 2, 3, 4, … }.
Der Doppelpunkt auf der linken Seite des obigen Gleichheitszeichen bedeutet, dass die linke Seite,also das Symbol ℕ, durch die rechte Seite definiert wird. Das setzt natürlich voraus, dass wir dierechte Seite, also die Menge {1, 2, … }, bereits kennen.Mit ℕ0 bezeichnen wir die Menge
ℕ0 ∶= {0, 1, 2, 3, …}.
Unter den ganzen Zahlen ℤ verstehen wir die Menge
ℤ ∶= {… , −2, −1, 0, 1, 2, … }.
Alle diese Definitionen sind mit Vorsicht zu genießen, weil nicht klar ist, was „…“ bedeuten soll.
Definition 1.1 Wir sagen, die ganze Zahl 𝑎 teilt die ganze Zahl 𝑏, falls es eine ganze Zahl 𝑘 gibt, so dass𝑎𝑘 = 𝑏. Wir sagen in diesem Fall auch, dass 𝑎 ein Teiler von 𝑏 sei und schreiben 𝑎 ∣ 𝑏.Andernfalls sagen wir, dass 𝑎 kein Teiler von 𝑏 sei und schreiben 𝑎 ∤ 𝑏.
Beispiel 1.2 Es gilt
(a) 2 ∤ 3,
(b) 2 ∣ 4,
(c) 0 ∣ 0,
(d) 0 ∤ 𝑧 für alle ganzen Zahlen 𝑧 ≠ 0 und
(e) 𝑧 ∣ 0 für alle ganzen Zahlen 𝑧. ♢
Definition 1.3 Ganze Zahlen, die von 2 geteilt werden, nennen wir gerade Zahlen. Alle anderen ganzenZahlen nennen wir ungerade Zahlen.
Definition 1.4 Eine natürliche Zahl 𝑛 heißt Primzahl, wenn sie ungleich 1 ist und nur durch ±1 und ±𝑛teilbar ist. Die Menge der Primzahlen bezeichnen wir mit ℙ.
Beispiel 1.5 Die Zahl 2 ist eine Primzahl. Da 2 ∤ 3, ist auch 3 eine Primzahl. 4 ist keine Primzahl, dennes gilt 4 = 2 ⋅ 2. ♢
In Ihrem Studium werden Sie an verschiedenen Stellen sehen, dass Primzahlen eine fundamentaleBedeutung in der Mathematik haben. Im Augenblick benötigen wir die Menge der Primzahlen abernur, um Beispiele zu den folgenden Abschnitten diskutieren zu können.
1Was natürliche Zahlen sind, scheint intuitiv klar und aus der Schule bekannt. Tatsächlich machen wir es uns hier einbisschen einfach. Im Studium der Mathematik wird man eine gewisse Zeit darauf verwenden, sauber zu definieren,was natürliche Zahlen sind. Das führt aber schon über den Vorkursstoff hinaus.
2
1.2 Ungleichungen und Abschätzungen
In der Schule wird vorwiegend der Umgang mit Gleichungen gelehrt. Im Studium jedoch müssen Siean vielen Stellen souverän mit Ungleichungen umgehen können. Wir wiederholen daher in diesemAbschnitt wichtige Rechenregeln für Ungleichungen sowie einige Techniken zur Abschätzung vonTermen. Die auftretenden Variablen sind alle als reelle Zahlen (allgemeiner: Elemente eines angeord-neten Körpers) aufzufassen.
Wir definieren die Zeichen ≤, <, ≥ und > nicht, sondern setzen deren Bedeutung als bekannt voraus.2
Definition 1.6 Unter einer Ungleichungskette versteht man eine Ungleichung der Form
𝑎1 < 𝑎2 < 𝑎3 < ⋯ < 𝑎𝑛.
Die Ungleichungskette ist erfüllt genau dann, wenn alle Ungleichungen
𝑎1 < 𝑎2 und 𝑎2 < 𝑎3 und ⋯ und 𝑎𝑛−1 < 𝑎𝑛
zugleich erfüllt sind.
Satz 1.7 • Die Ungleichungen𝑎 < 𝑏 und 𝑎 + 𝑐 < 𝑏 + 𝑐
sind äquivalent (d.h. gleichbedeutend; Genaueres hierzu im nächsten Abschnitt).
• Für positive 𝑐 sind𝑎 < 𝑏 und 𝑐𝑎 < 𝑐𝑏
äquivalent.
• Für negative 𝑐 sind𝑎 < 𝑏 und 𝑐𝑎 > 𝑐𝑏
äquivalent.Analoge Resultate gelten für schwache Ungleichungen (d.h. ≤ statt <).
Satz 1.8 Aus𝑎 < 𝑏 und 𝑐 < 𝑑
folgt𝑎 + 𝑐 < 𝑏 + 𝑑.
Sind beide Ungleichungen schwach, so ist auch die Ergebnis-Ungleichung schwach.Kurz: Gleichsinnige Ungleichungen dürfen addiert werden.
Satz 1.9 Genau dann gilt 𝑎𝑏 > 0, wenn 𝑎 und 𝑏 entweder beide positiv oder beide negativ sind.Genau dann gilt 𝑎𝑏 < 0, wenn eine der Variablen positiv, die andere negativ ist.
Korollar 1.10 3 Gilt 𝑎 ≠ 0, so ist 𝑎2 > 0. Insbesondere ist 1 > 0.
2Tatsächlich ist es nicht einfach, eine saubere mathematische Definition von < zu geben. Man kann zwar sagen, dass 𝑎 < 𝑏bedeuten soll, dass 𝑏 − 𝑎 positiv ist. Dies führt aber auf das Problem, den Begriff positiv zu definieren.
Eine Lösung dieses Problems wird in der Analysis gegeben – lassen Sie sich überraschen.3Ein Korollar (von lat. corollarium — Zugabe, Geschenk) ist eine (zumeist einfache) Folgerung aus einem mathematischen
Resultat.
3
Satz 1.11 Aus0 < 𝑎 < 𝑏 und 0 < 𝑐 < 𝑑
folgt0 < 𝑎𝑐 < 𝑏𝑑.
Analog für schwache Ungleichungen.Kurz: Gleichsinnige Ungleichungen dürfen miteinander multipliziert werden, wenn alle Glieder positiv sind.
Satz 1.12 Einen Bruch mit positivem Zähler und positivem Nenner kann man vergrößern, indem man
• den Zähler vergrößert oder
• den Nenner verkleinert und positiv hält.
Beispiel 1.13 (a) Die komplexen Zahlen ℂ entstehen, indem man zu den reellen Zahlen ein Ele-ment 𝑖 hinzufügt, das der Gleichung 𝑖2 = −1 genügt, und dann die Grundrechenarten auf diesesElement erweitert.In ℂ kann man Ungleichungen nicht sinnvoll definieren. Man sagt auch, dass ℂ nicht angeord-net sei.Denn wegen Korollar 1.10 wären −1 = 𝑖2 und 1 = 12 positiv, also
−1 > 0 und 1 > 0.
Wegen Satz 1.8 folgt dann aber 0 > 0 — Widerspruch.
(b) Sind 𝑏, 𝑑 > 0 und gilt 𝑎𝑏 < 𝑐
𝑑 , so gilt 𝑎𝑏 < 𝑎+𝑐
𝑏+𝑑 < 𝑐𝑑 .
Wir zeigen, dass das erste <-Zeichen stimmt: Das Element 𝑏(𝑏 + 𝑑) ist positiv. Daher sind dieUngleichungen
𝑎𝑏 < 𝑎 + 𝑐
𝑏 + 𝑑 und 𝑎(𝑏 + 𝑑) < (𝑎 + 𝑐)𝑏
äquivalent. Ausmultiplizieren liefert
𝑎𝑏 + 𝑎𝑑 < 𝑎𝑏 + 𝑏𝑐, also 𝑎𝑑 < 𝑏𝑐.
Multiplikation mit der positiven Zahl 1𝑏𝑑 liefert
𝑎𝑏 < 𝑐
𝑑 .
Die Gleichung 𝑎𝑏 < 𝑎+𝑐
𝑏+𝑑 ist daher äquivalent zur als wahr vorausgesetzten Ausgangsgleichung𝑎𝑏 < 𝑐
𝑑 und damit ebenfalls wahr.Der Beweis der zweiten Ungleichung funktioniert analog.
(c) Für alle natürlichen Zahlen 𝑛 gilt3𝑛 − 6
𝑛2 + 2𝑛 + 3≤ 3
𝑛.
Denn wir haben
3𝑛 − 6𝑛2 + 2𝑛 + 3
Zähler vergrößern≤ 3𝑛
𝑛2 + 2𝑛 + 3Nenner verkleinern
≤ 3𝑛𝑛2 = 3
𝑛. ♢
4
2 Aussagenlogik
Mit Hilfe der formalen Logik können mathematische Aussagen exakt formuliert und bewiese wer-den.
2.1 Aussagen
Unter einer mathematischen Aussage verstehen wir ein sprachliches Gebilde, bei dem es sinnvoll ist,zu fragen, ob es entweder wahr (abgekürzt: 𝑤) oder falsch (abgekürzt: 𝑓 ) ist (Prinzip der Zweiwer-tigkeit der mathematischen Logik4). Es ist nicht erforderlich, tatsächlich sagen zu können, welcherWahrheitswert der Aussage zukommt.
Beispiel 2.1 Welche der folgenden Sätze sind Aussagen in obigem Sinne?
(a) Wie ist das Wetter heute?
(b) Heute ist Montag.
(c) Heute ist Montag und morgen ist Mittwoch.
(d) Dieser Satz ist eine falsche Aussage. ♢
Aussagen werden oft mit Großbuchstaben 𝐴, 𝐵, 𝐶 … bezeichnet.
Beispiel 2.2 Ein paar Beispiele für Aussagen:
𝐴: 9 ist eine Primzahl.
𝐵: Jede Primzahl ist ungerade.
𝐶: Jede gerade Zahl größer oder gleich 4 ist das Produkt aus genau zwei Primzahlen.
𝐷: Jede gerade Zahl größer oder gleich 4 ist die Summe aus genau zwei Primzahlen.
zu 𝐴: Die Aussage ist falsch, denn 3 ⋅ 3 = 9.
zu 𝐵: 2 ist gerade und eine Primzahl, also ist die Aussage falsch.
zu 𝐶: Es ist 8 = 2⋅2⋅2 zwar das Produkt dreier Primzahlen, aber nicht das Produkt zweier Primzahlen.𝐶 ist also falsch.
zu 𝐷: Aussage 𝐷 ist die sogenannte Goldbachsche Vermutung, an der sich Mathematiker schon seit1742 die Zähne ausbeißen. Aufgrund der Formulierung ist 𝐷 jedoch eine mathematische Aussa-ge. ♢
2.2 Operationen mit Aussagen
Aus einfachen Aussagen gewinnt man durch logische Verknüpfungen kompliziertere Aussagen. DieWahrheitswerte der einfachen Aussagen legen dabei den Wahrheitswert der komplizierteren Aussageeindeutig fest. Die wichtigsten logischen Verknüpfungen sind:
(a) Konjunktion („und“), Schreibweise: 𝐴 ∧ 𝐵.Beispiel: Seien 𝐴 und 𝐵 die Aussagen aus Beispiel 2.2. Dann bedeutet die Aussage 𝐴 ∧ 𝐵 ∶
4Es gibt auch mehrwertige oder sogar unscharfe (Fuzzy-)Logik, die in der Anwendung eine gewisse Rolle spielt. Diese istaber zur Grundlegung der Mathematik eher ungeeignet.
5
9 ist eine Primzahl und jede Primzahl ist ungerade.
Das ist eine neue Aussage.Der Wahrheitswert der neuen Aussage 𝐴 ∧ 𝐵 ist durch folgende Tabelle (eine sogenannte Wahr-heitstafel) definiert:
𝐴 𝐵 𝐴 ∧ 𝐵𝑤 𝑤 𝑤𝑤 𝑓 𝑓𝑓 𝑤 𝑓𝑓 𝑓 𝑓
Sind also 𝐴 und 𝐵 falsch, so ist auch 𝐴 ∧ 𝐵 falsch (4. Zeile der Wahrheitstafel).
Durch die folgende Wahrheitstafel werden weitere logische Verknüpfungen definiert.
gegeben, so ist 𝐶1 ∨ 𝐶2 eine wahre Aussage, da mindestens eine der beiden Aussagen 𝐶1, 𝐶2wahr ist. Tatsächlich sind aber sowohl 𝐶1 als auch 𝐶2 wahr.
(c) Negation („nicht“), Schreibweise: ¬𝐴.Die Negation von „2 ist keine Primzahl“ ist „2 ist nicht keine Primzahl“, also „2 ist eine Prim-zahl“.
(d) Implikation („𝐴 impliziert 𝐵“, „aus 𝐴 folgt 𝐵“), Schreibweise: 𝐴 ⟹ 𝐵Achtung: Eine Implikation 𝐴 ⟹ 𝐵 ist stets wahr, wenn 𝐴 falsch ist! Aus einer falschen Aussagekann man alles folgern!So ist z. B. die Aussage
Ist 9 eine Primzahl, so gilt die Goldbachsche Vermutung.
wahr, weil 9 keine Primzahl ist.
(e) Äquivalenz („𝐴 ist äquivalent zu 𝐵“, „𝐴 genau dann, wenn 𝐵“), Schreibweise: 𝐴 ⟺ 𝐵Sei 𝑞 eine natürliche Zahl. Die Aussagen „𝑞 ist eine gerade Primzahl“ und „𝑞 ist 2“ sind äquiva-lent. Sie sind entweder beide wahr (nämlich wenn 𝑞 = 2 gilt) oder beide falsch (falls 𝑞 ≠ 2).
5Das logische „oder“, ∨, ist kein exklusives Oder. Hier unterscheidet sich die mathematische Logik von der Umgangs-sprache.
6
Beweisverfahren für Tautologien
Mit Hilfe von Wahrheitstafeln kann man Rechenregeln (sog. Tautologien) für logische Ausdrückebeweisen.Z. B. stellt man fest, dass die Aussage 𝐴∧𝐵 genau dann wahr ist, wenn 𝐵∧𝐴 wahr ist. Diese sogenannteKommutativität von ∧ zeigt man, indem man die Tabelle
𝐴 𝐵 𝐴 ∧ 𝐵 𝐵 ∧ 𝐴𝑤 𝑤 𝑤 𝑤𝑤 𝑓 𝑓 𝑓𝑓 𝑤 𝑓 𝑓𝑓 𝑓 𝑓 𝑓
ausfüllt und die Spalten 3 und 4 vergleicht. Man sieht, dass die Wahrheitsbelegungen in jedem mög-lichen Fall, also immer, übereinstimmen.
Alle folgenden Tautologien lassen sich auf ähnliche Weise zeigen.
Verwechseln Sie nicht die Kontraposition mit der Umkehrung des Folgepfeils!Die Aussagen 𝐴 ⟹ 𝐵 und (¬𝐵) ⟹ (¬𝐴) sind logisch äquivalent. Die Aussagen
𝐴 ⟹ 𝐵 und 𝐴 ⟸ 𝐵
haben jedoch i. A. nichts miteinander zu tun!
(g) Syllogismus:((𝐴 ⟹ 𝐵) ∧ (𝐵 ⟹ 𝐶)) ⟹ (𝐴 ⟹ 𝐶),
(𝐴 ∧ (𝐴 ⟹ 𝐵)) ⟹ 𝐵.
7
(h) Umformulierung der Implikation
(𝐴 ⟹ 𝐵) ⟺ (¬𝐴 ∨ 𝐵).
(i) Umformulierung der Äquivalenz
(𝐴 ⟺ 𝐵) ⟺ ((𝐴 ⟹ 𝐵) ∧ (𝐵 ⟹ 𝐴)).
2.3 Quantoren
Mathematische Aussagen hängen oft von Variablen ab. Zum Beispiel hängt die Aussage
𝑛 ist größer als 2𝑛
von der Variable 𝑛 ab. Oft schränkt man den Grundbereich, aus dem die Variablen stammen dürfen,ein. Man definiert sich hierzu eine Menge 𝑀 und fordert, dass die Variable 𝑛 in 𝑀 liegen muss. Manschreibt 𝑛 ∈ 𝑀 hierfür. Wir werden später auf diese Notation zurückkommen.
Definition 2.3 Sei 𝐴(𝑛) eine von der Variablen 𝑛 ∈ 𝑀 abhängige Aussage.
(a) Wir schreiben∀𝑛 ∈ 𝑀 ∶ 𝐴(𝑛)
für die AussageFür alle 𝑛 aus der Menge 𝑀 ist die Aussage 𝐴(𝑛) wahr.
Der Ausdruck „∀𝑛 ∈ 𝑀 ∶ 𝐴(𝑛)“ ist also genau dann wahr, wenn 𝐴(𝑛) für jede Belegung der Variablen 𝑛mit Werten aus 𝑀 wahr ist.Man nennt ∀ den Allquantor.
(b) Wir schreiben∃𝑛 ∈ 𝑀 ∶ 𝐴(𝑛)
für die AussageEs existiert ein 𝑛 ∈ 𝑀, so dass 𝐴(𝑛) wahr ist.
Der Ausdruck „∃𝑛 ∈ 𝑀 ∶ 𝐴(𝑛)“ ist also genau dann wahr, wenn mindestens ein 𝑛 ∈ 𝑀 existiert, sodass 𝐴(𝑛) wahr ist.Man nennt ∃ den Existenzquantor.
Beispiel 2.4 Die folgenden Aussagen seien für ganze Zahlen 𝑛 bzw. 𝑚 erklärt.
(a) Die Aussage𝐴(𝑛): 𝑛 ist größer als 2𝑛
ist für alle natürlichen Zahlen 𝑛 falsch. Aufgrund der Zweiwertigkeit der mathematischen Logikist dann ¬𝐴(𝑛) für alle natürlichen Zahlen wahr. Es gilt also
∀𝑛 ∈ ℕ ∶ ¬𝐴(𝑛).
(b) Die Aussage𝐵(𝑛): 𝑛2 > 𝑛
ist für gewisse 𝑛 wahr, etwa für 𝑛 = 3. Somit gilt
∃𝑛 ∈ ℕ ∶ 𝐵(𝑛). ♢
8
Bemerkung 2.5 Bei der Negation einer quantisierten Aussage vertauschen ∀ und ∃ ihre Rollen. Esgilt
¬ (∀𝑛 ∈ ℕ ∶ 𝐴(𝑛)) ⟺ ∃𝑛 ∈ ℕ ∶ ¬𝐴(𝑛).
Oder in Worten ausgedrückt: Ist 𝐴(𝑛) nicht für alle 𝑛 richtig, dann gibt es mindestens ein 𝑛, so dass¬𝐴(𝑛) wahr ist.Analog gilt
¬ (∃𝑛 ∈ ℕ ∶ 𝐴(𝑛)) ⟺ ∀𝑛 ∈ ℕ ∶ ¬𝐴(𝑛).
Oder in Worten: Gibt es kein 𝑛, so dass 𝐴(𝑛) gilt, so ist ¬𝐴(𝑛) für alle 𝑛 wahr. ⋆
Beispiel 2.6 Die Aussage
𝐴 ∶ Für jede natürliche Zahl 𝑚 gibt es eine natürliche Zahl 𝑛, so dass 𝑛 > 𝑚 ist.
kann man abkürzend schreiben
𝐴 ∶ ∀𝑚 ∈ ℕ ∶ ∃𝑛 ∈ ℕ ∶ 𝑛 > 𝑚.
𝐴 ist völlig verschieden von der Aussage
𝐵 ∶ ∃𝑛 ∈ ℕ ∶ ∀𝑚 ∈ ℕ ∶ 𝑛 > 𝑚.
𝐵 in Worten: Es gibt eine natürliche Zahl 𝑛, so dass für jede natürliche Zahl 𝑚 die Ungleichung 𝑛 > 𝑚gilt.Eine Aussage kann sich also ändern, wenn man die Reihenfolge von Quantoren vertauscht.Aussage 𝐴 ist wahr, Aussage 𝐵 ist falsch.
Die Negation von 𝐴 ist¬𝐴 ∶ ∃𝑚 ∈ ℕ ∶ ∀𝑛 ∈ ℕ ∶ ¬(𝑛 > 𝑚).
In Worten: Es existiert eine natürliche Zahl 𝑚, so dass für jede natürliche Zahl 𝑛 die Ungleichung𝑛 ≤ 𝑚 gilt. ♢
Achtung: Die Symbole ∧, ∨, ¬, ⟹, ⟺ , ∀ und ∃ sind oft sehr nützlich, etwa wenn man verschach-telte logische Ausdrücke negieren will.Keinesfalls sollten sie aber im Sinne stenographischer Abkürzungen in einem mathematischen Text(z. B. bei der Bearbeitung von Übungsblättern, Klausuraufgaben oder Bachelorarbeiten) verwendetwerden.Ein mathematischer Text sollte immer aus vollständigen Sätzen bestehen.
9
3 Beweistechniken
3.1 Beweis von Implikationen
Gegeben seien zwei Aussagen 𝐴 und 𝐵. Eine Grundaufgabe der Mathematik ist es, die Implikation
𝐴 ⟹ 𝐵
zu beweisen. Die wichtigsten Beweismethoden hierfür sind:
direkter Beweis Man nehme 𝐴 als wahr an (für falsches 𝐴 ist die Implikation sowieso wahr) undfolgere durch eine Kette logischer Schlüsse, dass auch 𝐵 wahr sein muss.
Kontraposition Man beweist die Aussage¬𝐵 ⟹ ¬𝐴.
Aufgrund der Kontrapositionsregel zeigt dies, dass auch 𝐴 ⟹ 𝐵 wahr ist.Man verneint also 𝐵 und zeigt, dass hieraus die Verneinung von 𝐴 folgt.
Widerspruchsbeweis Man benutzt hier die Äquivalenz von
¬(𝐴 ⟹ 𝐵) und 𝐴 ∧ (¬𝐵).
Um zu zeigen, dass 𝐴 ⟹ 𝐵 wahr ist, zeigt man, dass 𝐴 ∧ (¬𝐵) falsch ist.Man nimmt also an, dass 𝐴 und ¬𝐵 zugleich wahr sind. Nun führt man solange logische Schlüs-se durch, bis man auf einen Widerspruch stößt. Dies zeigt, dass 𝐴 ∧ (¬𝐵) falsch ist. 𝐴 ⟹ 𝐵 istalso wahr.
Die Beweistypen Kontraposition und Widerspruchsbeweis nennt man indirekte Beweise.
Beispiel 3.1 Sei 𝑞 eine natürliche Zahl. Ferner seien die Aussagen
𝐴 ∶ 𝑞 ist gerade und Primzahl
und𝐵 ∶ 𝑞 < 5
gegeben. Wir beweisen die Aussage 𝐴 ⟹ 𝐵 auf verschiedene Weisen:
per direktem Beweis Sei 𝑞 gerade und eine Primzahl. Dann lässt sich 𝑞 wegen Definition 1.3 schreibenin der Form 𝑞 = 2 ⋅ 𝑥 mit einer natürlichen Zahl 𝑥. Da 𝑞 zudem als Primzahl vorausgesetzt war,folgt 𝑥 = 1, also 𝑞 = 2. Also ist 2 = 𝑞 < 5.
per Kontraposition Die Verneinung von 𝐵 ist „𝑞 ≥ 5“, die von 𝐴 ist „𝑞 ist ungerade oder keine Prim-zahl“.Sei also 𝑞 ≥ 5. Ist 𝑞 ungerade, so ist ¬𝐴 wahr. Ist 𝑞 jedoch gerade, so ist 2 ∣ 𝑞. Dies zeigt, dass 𝑞keine Primzahl ist. Wieder ist ¬𝐴 wahr.In jedem Fall gilt also ¬𝐵 ⟹ ¬𝐴. Damit ist aber 𝐴 ⟹ 𝐵 gezeigt.
per Widerspruchsbeweis Sei 𝑞 gerade und eine Primzahl. Ferner sei 𝑞 ≥ 5. Dann ist 2 ∣ 𝑞. Wegen𝑞 ≥ 5 ist dies ein Widerspruch zur Tatsache, dass 𝑞 eine Primzahl ist.Daher ist 𝐴 ∧ (¬𝐵) falsch. Es muss daher ¬(𝐴 ∧ (¬𝐵)), also 𝐴 ⟹ 𝐵, wahr sein. ♢
10
3.2 Beweis von Äquivalenzen
Gegeben seien Aussagen 𝐴1, … , 𝐴𝑛. Zu zeigen ist, dass alle diese Aussagen untereinander äquivalentsind, d.h. es ist zu zeigen, dass
𝐴𝑖 ⟺ 𝐴𝑗 für alle Indizes 𝑖 ≠ 𝑗
gilt.
direkter Beweis Man folgere durch eine Kette von Äquivalenzen, dass für je zwei Aussagen 𝐴𝑖, 𝐴𝑗die Aussage 𝐴𝑖 ⟺ 𝐴𝑗 wahr ist.Diese Beweisstrategie kommt häufig beim Lösen von (Un-)Gleichungen vor.
Beispiel 3.2 Bestimmen Sie alle natürlichen Zahlen 𝑛, die der Ungleichung
−3𝑛 + 2 < −7
genügen!
Es ist−3𝑛 + 2 < −7 ⟺ −3𝑛 < −9 ⟺ 𝑛 > 3.
Die Ungleichung also von allen natürlichen Zahlen 𝑛 ≥ 4 gelöst. ♢
Reduktion auf Implikationen Statt der Äquivalenz 𝐴 ⟺ 𝐵 beweist man die beiden Implikationen
𝐴 ⟹ 𝐵 und 𝐵 ⟹ 𝐴.
Hierfür kann man Methoden aus dem vorherigen Abschnitt benutzen.
Nachteil: Zeigt man die Äquivalenz von 𝑛 Aussagen auf diese Weise, so muss man 𝑛(𝑛 − 1) = 𝑛2 − 𝑛Implikationen beweisen.
In der Praxis benutzt man daher oft das Ringschlussprinzip: Man zeigt die 𝑛 Implikationen
𝐴1 ⟹ 𝐴2, 𝐴2 ⟹ 𝐴3, 𝐴3 ⟹ 𝐴4, … , 𝐴𝑛 ⟹ 𝐴1.
Dies beweist dann die Äquivalenz aller Aussagen untereinander. (Man folge den Implikationspfeilenso lange, bis man von der Aussage 𝐴𝑖 zur Aussage 𝐴𝑗 gelangt.)
Beispiel 3.3 Zeige, dass für eine natürliche Zahl 𝑛 die folgenden Aussagen äquivalent sind:
(a) 𝑛 ist gerade.
(b) 𝑛2 ist durch 4 teilbar.
(c) 𝑛2 ist gerade.
Beweis per Ringschluss:„(𝑎) ⟹ (𝑏)“: Sei 𝑛 gerade. Dann ist 𝑛 = 2𝑥 mit einer natürlichen Zahl 𝑥. Also ist 𝑛2 = (2𝑥)2 = 4𝑥2.Somit ist 4 ∣ 𝑛2.
„(𝑏) ⟹ (𝑐)“: Sei 𝑛2 durch 4 teilbar. Dann existiert eine natürliche Zahl 𝑥 mit 𝑛2 = 4𝑥. Dann ist𝑛2 = 2 ⋅ (2𝑥). Also ist 𝑛2 gerade.
11
„(𝑐) ⟹ (𝑎)“; per Kontraposition: Sei 𝑛 ungerade. Dann lässt sich 𝑛 darstellen in der Form
Um eine Aussage zu widerlegen, müssen Sie sie als falsch nachweisen. Dies geschieht bei Aussagender Form Stets gilt… durch die Angabe eines Gegenbeispiels, das möglichst einfach und konkret seinsollte.
Beispiel 3.4 Widerlege die Aussage
Für jede natürliche Zahl 𝑚 gibt es eine natürliche Zahl 𝑛, so dass 𝑛 + 𝑚 = 𝑛𝑚.
Ein Gegenbeispiel zur Aussage ist 𝑚 = 1, denn hier ergibt sich die Gleichung
𝑛 + 1 = 𝑛,
die von keinem natürlichen 𝑛 gelöst wird. ♢
Bemerkung 3.5 Zum Widerlegen reicht ein einziges Gegenbeispiel aus. Ein Beispiel reicht allerdingsi. A. nicht als Beweis! ⋆
12
4 Rekursion und vollständige Induktion
Sowohl die vollständige Induktion als auch die Rekursion nutzen die Eigenschaft der natürlichenZahlen aus, zu jedem Element 𝑛 auch dessen eindeutigen Nachfolger 𝑛 + 1 zu enthalten.Diese Eigenschaft ist kennzeichnend für die natürlichen Zahlen: Man kann ℕ definieren als kleinsteMenge, die 1 enthält und obige Nachfolgereigenschaft besitzt. (Man muss dann allerdings wissen,was „1“ ist, was „kleinste“ bedeutet und was ein „Nachfolger“ ist.)Man sieht dann, dass jedes Element aus ℕ außer 1 auch einen eindeutigen Vorgänger hat und dasssich jedes 𝑛 ∈ ℕ schreiben lässt in der Form
𝑛 = 1 + 1 + ⋯ + 1⏟⏟⏟⏟⏟⏟⏟𝑛-mal
.
4.1 Rekursion
Das Verfahren der Rekursion benutzt man vorwiegend zur Definition von mathematischen Ausdrü-cken.
Definition 4.1 (Summenschreibweise) Seien 𝑥, 𝑦 ∈ ℤ und 𝑎𝑘 Zahlen. Man setzt
𝑦∑𝑘=𝑥
𝑎𝑘 ∶=⎧{{⎨{{⎩
0 falls 𝑦 < 𝑥,𝑎𝑥 falls 𝑥 = 𝑦,∑𝑦−1
𝑘=𝑥 𝑎𝑘 + 𝑎𝑦 sonst.
Hierdurch wird eine Kurzschreibweise für Summen definiert.
Die eigentliche Rekursion verbirgt sich in der letzten Zeile der geschweiften Klammer: Das Symbol∑𝑦
𝑘=𝑥 𝑎𝑘 wird hier durch das Symbol ∑𝑦−1𝑘=1 𝑎𝑘 definiert. Ist dieses Symbol ebenfalls unbekannt, so wird
es durch ∑𝑦−2𝑘=𝑥 𝑎𝑘 definiert. Setzt man diesen Schritt lange genug fort, so landet man bei dem Symbol
∑𝑥𝑘=𝑥 𝑎𝑘. Dieses ist aber konkret gegeben.
Beispiel 4.2 Seien 𝑎1, 𝑎2, 𝑎3 beliebige Zahlen. Dann ist3
∑𝑘=1
𝑎𝑘 =2
∑𝑘=1
𝑎𝑘 + 𝑎3 =1
∑𝑘=1
𝑎𝑘 + 𝑎2 + 𝑎3 = 𝑎1 + 𝑎2 + 𝑎3.♢
Analog definieren wir für Produkte
Definition 4.3 Seien 𝑥, 𝑦 ∈ ℤ und 𝑎𝑘 Zahlen. Man setzt
𝑦∏𝑘=𝑥
𝑎𝑘 ∶=⎧{{⎨{{⎩
1 falls 𝑦 < 𝑥,𝑎𝑥 falls 𝑥 = 𝑦,∏𝑦−1
𝑘=𝑥 𝑎𝑘 ⋅ 𝑎𝑦 sonst.
Rekursionen werden auch oft benutzt, um sog. Folgen (das sind geordnete Reihen von Zahlen) zudefinieren.
Beispiel 4.4 Sei 𝑎 eine positive Zahl. Wir setzen
𝑎1 ∶= 𝑎 und 𝑎𝑛+1 ∶= 12(𝑎𝑛 + 𝑎
𝑎𝑛) für 𝑛 ∈ ℕ.
Auf diese Weise wird eine Folge 𝑎1, 𝑎2, 𝑎3, … definiert. Man kann zeigen, dass 𝑎𝑛 für große 𝑛 dem Wert√𝑎 beliebig nahe kommt.Diese Folge lässt sich sehr einfach rekursiv definieren. Einen expliziten Term für 𝑎𝑛 anzugeben istjedoch äußerst schwierig.Setzen wir z. B. 𝑎 = 2, so ergibt sich
Definition 4.6 (Potenzen) Für eine Zahl 𝑎 und 𝑛 ∈ ℕ0 setzen wir
𝑎𝑛 ∶=𝑛
∏𝑘=1
𝑎.
Insbesondere gilt 𝑎0 = 1 für alle 𝑎.
4.2 Vollständige Induktion
Die vollständige Induktion ist eine Methode, die sich zum Beweis von Aussagen der Form
∀𝑛 ∈ ℕ ∶ 𝐴(𝑛)
eignet.
Beispiel 4.7 Betrachten Sie die Aussagen
𝐴 ∶ Für alle 𝑛 ∈ ℕ ist die Zahl 22𝑛 + 1 eine Primzahl.
und𝐵 ∶ Für alle 𝑛 ∈ ℕ ist die Zahl 22𝑛 − 1 durch 3 teilbar.
Sind diese Aussagen wahr?
Man könnte vermuten, dass 𝐴 wahr ist, denn man rechnet leicht nach, dass 22𝑛 + 1 für 𝑛 = 1, 2, 3, 4eine Primzahl ist. Es gilt aber 225 + 1 = 4294967297 = 641 ⋅ 6700417. Die Aussage 𝐴 ist hiermit alsowiderlegt.
Die Aussage 𝐵 ist allerdings wahr. Dies stellt uns vor ein Problem, denn egal, wie viele natürlicheZahlen 𝑛 wir testen, wir werden nie einen Widerspruch erzeugen können. Andererseits können wirdurch solche Tests die Aussage auch nicht beweisen, denn es gibt unendlich viele natürliche Zahlen,und wir können nicht alle überprüfen.
Wie beweist man also Aussagen dieses Typs? ♢
14
Prinzip der vollständigen Induktion
Für jede natürliche Zahl 𝑛 ∈ ℕ sei eine Aussage 𝐴(𝑛) gegeben. Ferner gelte:
(a) 𝐴(1) ist wahr.
(b) Die Aussage 𝐴(𝑛) ⟹ 𝐴(𝑛 + 1) ist für alle 𝑛 ∈ ℕ wahr, d.h. gilt die Aussage 𝐴(𝑛) für ein 𝑛 ∈ ℕ,so ist stets auch 𝐴(𝑛 + 1) wahr.
Dann stimmt die Aussage 𝐴(𝑛) für alle 𝑛 ∈ ℕ.
Man kann sich dieses Prinzip wie folgt klarmachen:Gilt die Aussage 𝐴(1), dann folgt nach (b), dass auch 𝐴(2) wahr ist. Wieder folgt mit (b), dass auch𝐴(3) gilt. Hieraus folgt die Gültigkeit von 𝐴(4), usw.Dass die Aussage 𝐴 nun für alle 𝑛 ∈ ℕ wahr ist, ergibt sich daraus, dass man jede natürliche Zahl alshinreichend hohen Nachfolger der 1 schreiben kann.
Die Forderung in (a) nennt man den Induktionsanfang.Der Beweis der Implikation in (b) kann im Prinzip mit allen Beweismethoden aus dem vorherigenAbschnitt geschehen. Oft benutzt man aber folgendes Vorgehen:Man nimmt an, dass 𝐵(𝑛) für ein festes, aber beliebiges 𝑛 ∈ ℕ wahr ist. Diese Annahme nennt manInduktionsannahme oder Induktionsvoraussetzung.Im nun folgenden Induktionsschluss zeigt man, dass aus der wahren Aussage 𝐵(𝑛) auch 𝐵(𝑛 + 1)folgt6.
Bitte gewöhnen Sie sich an, alle drei Schritte, also Induktionsanfang, Induktionsvoraussetzung undInduktionsschluss, in Ihren Lösungen kenntlich zu machen.
4.3 Beispiele
Wir stellen hier einige Induktionsbeweise vor.
Satz 4.8 (‚kleiner Gauß‘) Für alle natürlichen Zahlen 𝑛 ∈ ℕ gilt
𝑛∑𝑘=1
𝑘 = 𝑛(𝑛 + 1)2 .
Beweis 1. Wir beweisen die Aussage mit vollständigen Induktion.Die zu beweisende Aussage ist
𝐴(𝑛) ∶ Es gilt𝑛
∑𝑘=1
𝑘 = 𝑛(𝑛 + 1)2 .
Induktionsanfang 𝐴(1) ist wahr, denn1
∑𝑘=1
𝑘 = 1 = 1 ⋅ 22 .
Induktionsvoraussetzung Die Aussage 𝐴(𝑛) sei wahr für ein 𝑛 ∈ ℕ.
6Tipp: Wer beim Induktionsschluss die Induktionsannahme nicht benutzt hat, hat ziemlich sicher etwas falsch gemacht.
15
Induktionsschluss Dann ist auch 𝐴(𝑛 + 1) wahr, denn
Aufgrund der Induktionsvoraussetzung ist 3 ∣ 𝑧3 − 𝑧. Wegen 3𝑧2 + 3𝑧 = 3 ⋅ (𝑧2 + 𝑧) ist 3 auch einTeiler von 3𝑧2 + 3𝑧. Insgesamt folgt 3 ∣ (𝑧 + 1)3 − (𝑧 + 1).
Ind.schl. 2 Dann gilt die Aussage auch für −𝑧, denn
(−𝑧)3 − (−𝑧) = −(𝑧3 − 𝑧).
Da 𝑧3 − 𝑧 nach Induktionsvoraussetzung von 3 geteilt wird, wird auch −(𝑧3 − 𝑧) von 3 geteilt.Insgesamt folgt die Gültigkeit der Behauptung für alle ganzen Zahlen. ■
18
5 Mengen
Wir werden den Begriff der Menge nicht präzise definieren, sondern naiv mit ihm umgehen – mathe-matisch fundierte Mengenlehre wird schnell sehr abstrakt und beweislastig und liefert im Rahmendes Vorkurses keine neuen Erkenntnisse.
Für uns gilt daher:
Unter einer Menge verstehen wir jede Zusammenfassung 𝑀 von bestimmten wohlunterschiedenen Objekten 𝑚unserer Anschauung oder unseres Denkens (welche die Elemente von 𝑀 genannt werden) zu einem Ganzen.
Diese nette „Definition“ ist leider widersprüchlich: Sei z. B. 𝑀 die Menge aller Mengen, die nichtElement von sich selbst sind. Ist dann 𝑀 ein Element von sich selbst?
5.1 Notationen
Ist 𝑀 eine Menge und 𝑥 ein Element von 𝑀, so schreiben wir
𝑥 ∈ 𝑀.
Wir sagen auch: „𝑥 gehört zu 𝑀“ oder „𝑥 liegt in 𝑀“. Ist 𝑥 kein Element von 𝑀, so schreiben wir
𝑥 ∉ 𝑀.
Stets gilt entweder 𝑥 ∈ 𝑀 oder 𝑥 ∉ 𝑀.
Eine Menge kann durch Aufzählung ihrer Elemente erklärt werden, z. B. ist
𝑀 ∶= {𝑎, 𝑏, 𝑐, 𝑑}
die Menge, die genau die Elemente 𝑎, 𝑏, 𝑐 und 𝑑 enthält. Oft benutzt man den Platzhalter „ …“, umanzudeuten, dass eine Menge weitere Elemente enthält, die sich aus den bereits angegebenen Elemen-ten „ergeben“.
Meist werden Mengen aber durch Angabe einer Eigenschaft beschrieben. Schreibweise:
𝑀 = {𝑥 ∣ 𝑥 hat Eigenschaft 𝐸} oder 𝑀 = {𝑥 ∶ 𝑥 hat Eigenschaft 𝐸}.
Beispiel 5.1 (a) Die Menge der natürlichen Zahlen
ℕ ∶= {1, 2, 3, 4, 5, 6, …}.
(b) Die Menge der natürlichen Zahlen einschließlich 0
Mengen haben aber nicht unbedingt etwas mit Zahlen zu tun. Zum Beispiel wird in der Mathematikmit Mengen von Mengen, Mengen von Abbildungen usw. gearbeitet. ♢
19
Definition 5.2 Zwei Mengen 𝑀 und 𝑁 sind gleich, in Zeichen 𝑀 = 𝑁, wenn jedes Element von 𝑀 auch einElement von 𝑁 ist, und umgekehrt.Die Aussage 𝑀 = 𝑁 ist also definiert durch die Aussage 𝑥 ∈ 𝑀 ⟺ 𝑥 ∈ 𝑁.
Beispiel 5.3 Es gilt {1, 2, 3} = {1, 1, 1, 1, 1, 2, 3}. Zwar kommt das Element 1 in der rechten Menge„öfters“ vor, aber dies wird in der Definition der Mengengleichheit nicht überprüft. ♢
Definition 5.4 Eine Menge 𝑀 heißt Teilmenge einer Menge 𝑁, in Zeichen 𝑀 ⊂ 𝑁, falls jedes Element von𝑀 auch zu 𝑁 gehört.Insbesondere gilt 𝑀 ⊂ 𝑁, falls 𝑀 = 𝑁.7
Will man ausdrücken, dass 𝑀 eine echte Teilmenge von 𝑁 ist, d.h. dass 𝑀 ⊂ 𝑁 und 𝑀 ≠ 𝑁 gilt, soschreibt man 𝑀 ⊊ 𝑁.
(Hierbei steht „ ∶⟺ “ für „wird definiert durch“.)
Aus den Definitionen folgt sofort
Satz 5.5 (Gleichheitskriterium für Mengen) Seien 𝑀, 𝑁 Mengen. Genau dann gilt 𝑀 = 𝑁, wenn 𝑀 ⊂𝑁 und 𝑁 ⊂ 𝑀.
Definition 5.6 (leere Menge) Die Menge
∅ ∶= {} = {𝑥 ∈ 𝑀 ∣ 𝑥 ≠ 𝑥}
heißt leere Menge. Sie ist eindeutig bestimmt und hängt nicht von der Ausgangsmenge 𝑀 ab.Die leere Menge ist Teilmenge einer jeden Menge. ∅ enthält kein Element.
Definition 5.7 (Potenzmenge) Sei 𝑀 eine Menge. Unter der Potenzmenge 2𝑀 von 𝑀 verstehen wir dieMenge
2𝑀 ∶= {𝑁 ∣ 𝑁 ⊂ 𝑀} = {𝑁 ∣ 𝑁 ist Teilmenge von 𝑀}
aller Teilmengen von 𝑀. Daher ist 2𝑀 eine Menge von Mengen.
Statt 2𝑀 schreibt man für die Potenzmenge oft auch ℙ(𝑀), 𝒫(𝑀) oder 𝔓(𝑀).
7Dies wird leider nicht einheitlich gehandhabt. In manchen Büchern und Vorlesungen werden die Symbole ⊆ (statt ⊂)bzw. ⊂ (statt ⊊) benutzt.
20
5.2 Operationen mit Mengen
Im Folgenden stellen wir einige wichtige Operationen mit Mengen vor. Im Wesentlichen handelt essich hier um die Übertragung der logischen Operatoren in die Mengenlehre.
Die Vereinigung
Die Vereinigungsmenge𝑀 ∪ 𝑁 ∶= {𝑥 ∣ 𝑥 ∈ 𝑀 ∨ 𝑥 ∈ 𝑁}
zweier Mengen 𝑀, 𝑁 besteht genau aus den Elementen, die in 𝑀 oder 𝑁 liegen.
Beispiel 5.9
{1, 2} ∪ {2, 3} = {1, 2, 3}. ♢
Sei allgemeiner 𝒮 eine Menge, deren Elemente selbst Mengen sind. Die Vereinigung der Mengen aus𝒮 ist die Menge
⋃𝑀∈𝒮
𝑀 ∶= {𝑥 ∣ ∃𝑀 ∈ 𝒮 ∶ 𝑥 ∈ 𝑀}.
⋃𝑀∈𝒮 𝑀 ist also die Menge der Elemente, die mindestens einem 𝑀 ∈ 𝒮 angehören.
Oft wird das Mengensystem 𝒮 indiziert, d.h. jedem Element von 𝒮 wird ein eindeutiger Index 𝑖 auseiner Indexmenge 𝐼 zugeordnet, d.h.
𝒮 = {ℳ𝑖 ∣ 𝑖 ∈ ℐ}.Statt ⋃𝑀∈𝒮 𝑀 schreibt man dann ⋃𝑖∈𝐼 𝑀𝑖. Es gilt
⋃𝑖∈𝐼
𝑀𝑖 = {𝑥 ∣ ∃𝑖 ∈ 𝐼 ∶ 𝑥 ∈ 𝑀𝑖} .
Beispiel 5.10 Sei 𝐼 ∶= ℕ und 𝑀𝑖 ∶= {𝑖, 𝑖 + 1, … , 2𝑖} für 𝑖 ∈ 𝐼. Dann ist
⋃𝑖∈𝐼
𝑀𝑖 = ℕ.
Beweis:„⊂“ Da jede der Mengen 𝑀𝑖 Teilmenge von ℕ ist, gilt auch ⋃𝑖∈𝐼 𝑀𝑖 ⊂ ℕ.
„⊃“ Wir müssen also noch zeigen, dass auch ℕ ⊂ ⋃𝑖∈𝐼 𝑀𝑖 gilt.Sei also 𝑛 ein beliebiges Element aus ℕ. Dann ist 𝑛 ∈ 𝑀𝑛. Folglich ist
𝑛 ∈ ⋃𝑖∈𝐼
𝑀𝑖 = ⋃𝑛∈ℕ
𝑀𝑛.
Da 𝑛 beliebig war, gilt ℕ ⊂ ⋃𝑖∈𝐼 𝑀𝑖. ♢
Der Durchschnitt
Der Durchschnitt zweier Mengen 𝑀 und 𝑁
𝑀 ∩ 𝑁 ∶= {𝑥 ∣ 𝑥 ∈ 𝑀 ∧ 𝑥 ∈ 𝑁}
besteht genau aus denjenigen Elementen, die sowohl in 𝑀 als auch in 𝑁 liegen.
Beispiel 5.11
2ℕ ∩ ℙ = {2}. ♢
21
Allgemeiner ist⋂
𝑀∈𝒮𝑀 ∶= {𝑥 ∣ ∀𝑀 ∈ 𝒮 ∶ 𝑥 ∈ 𝑀}
der Durchschnitt einer nichtleeren Menge 𝒮 von Mengen. Er besteht genau aus den Elementen, diein allen 𝑀 ∈ 𝒮 liegen. In Indexschreibweise ergibt sich
⋂𝑖∈𝐼
𝑀𝑖 = {𝑥 ∣ ∀𝑖 ∈ 𝐼 ∶ 𝑥 ∈ 𝑀𝑖}.
Beispiel 5.12 Sei 𝐼 ∶= ℕ und 𝑀𝑖 ∶= {𝑛 ∈ ℕ| 𝑖 < 𝑛 < 4𝑖} für 𝑖 ∈ 𝐼. Dann ist
⋂𝑖∈𝐼
𝑀𝑖 = ∅.
Wie könnte man diese Behauptung beweisen? ♢
Das Komplement
Unter dem Komplement oder der Differenz einer Menge 𝑁 in 𝑀 versteht man die Menge
𝑀 ∖ 𝑁 ∶= {𝑥 ∣ 𝑥 ∈ 𝑀 ∧ 𝑥 ∉ 𝑁}.
Man liest 𝑀 ∖ 𝑁 auch als „𝑀 ohne 𝑁“.𝑀 ∖ 𝑁 besteht aus allen Elementen von 𝑀, die nicht zu 𝑁 gehören.
Beispiel 5.13 ℕ ∖ 2ℕ ist genau die Mengen der ungeraden natürlichen Zahlen. ♢
(3) Die de Morganschen Regeln gelten sogar allgemeiner für Mengensysteme:
𝑋 ∖ ⋂𝑀∈𝒮
𝑀 = ⋃𝑀∈𝒮
(𝑋 ∖ 𝑀)
𝑋 ∖ ⋃𝑀∈𝒮
𝑀 = ⋂𝑀∈𝒮
(𝑋 ∖ 𝑀)
Solche Regeln kann man – ähnlich wie in der Aussagenlogik – durch Wahrheitstafeln beweisen.Wir führen dies am Beispiel der zweiten de Morganschen Regel einmal vor:Beweis von 𝑋 ∖ (𝑀 ∪ 𝑁) = (𝑋 ∖ 𝑀) ∩ (𝑋 ∖ 𝑁)Auf der linken als auch rechten Seite des Gleichheitszeichens stehen Teilmengen von 𝑋. Sei also 𝑥 ∈ 𝑋.Dann gilt
Gilt 𝑀 = 𝑀1 = ⋯ = 𝑀𝑛, so schreibt man statt 𝑀1 × 𝑀2 × ⋯ × 𝑀𝑛 oft auch 𝑀𝑛.
23
Beispiel 5.17 Aus der Schule kennen Sie die Menge
ℝ3 = ℝ × ℝ × ℝ = {(𝑥, 𝑦, 𝑧) ∣ 𝑥, 𝑦, 𝑧 ∈ ℝ}.
Man kann diese Menge mit den Punkten des Raums identifizieren. ♢
Satz 5.18 Seien 𝑀1, 𝑀2, 𝑁 Mengen. Dann gelten die folgenden Aussagen:
(a) (𝑀1 ∩ 𝑀2) × 𝑁 = (𝑀1 × 𝑁) ∩ (𝑀2 × 𝑁).
(b) (𝑀1 ∪ 𝑀2) × 𝑁 = (𝑀1 × 𝑁) ∪ (𝑀2 × 𝑁).
Beweis 6. Übungsaufgabe. ■
24
6 Abbildungen I: Bild, Urbild und Graph
Eine Abbildung oder Funktion 𝑓 einer Menge 𝑀 in eine Menge 𝑁 ist eine Vorschrift, die jedem Ele-ment 𝑥 ∈ 𝑀 jeweils ein eindeutig bestimmtes Element 𝑦 ∈ 𝑁 zuordnet.Genauer definiert man
Definition 6.1 (Abbildung) Seien 𝑀, 𝑁 Mengen und 𝑅 ⊂ 𝑀 × 𝑁. Wir nennen das Tupel
𝑓 = (𝑀, 𝑁, 𝑅)
eine Abbildung oder eine Funktion von 𝑀 nach 𝑁, wenn es zu jedem 𝑥 ∈ 𝑀 genau ein 𝑦 ∈ 𝑁 mit (𝑥, 𝑦) ∈ 𝑅gibt.Man nennt 𝑀 den Definitionsbereich von 𝑓 und 𝑁 den Zielbereich von 𝑓 .Statt (𝑥, 𝑦) ∈ 𝑅 schreibt man auch
𝑦 = 𝑓 (𝑥)und nennt 𝑦 das Bild von 𝑥 unter 𝑓 .Statt 𝑓 = (𝑀, 𝑁, 𝑅) schreibt man auch
𝑓 ∶ 𝑀 → 𝑁, 𝑥 ↦ 𝑓 (𝑥).
Beispiel 6.2 Oft werden Abbildungen durch Terme definiert, z. B.
𝑓 ∶ ℕ → ℕ, 𝑧 ↦ 𝑧2.
Es gibt aber auch Funktionen, die sich nicht durch Terme beschreiben lassen:
𝑔 ∶ ℕ → ℕ, 𝑛 ↦ kleinste Primzahl, die größer als 𝑛 ist.
Im zweiten Beispiel ist nicht klar, ob 𝑔 überhaupt eine Funktion ist, d.h. ob jeder natürlichen Zahl auchein eindeutiger Wert aus der Zielmenge zugeordnet wird.Gibt es zu jedem 𝑛 ∈ ℕ immer eine eindeutige kleinste Primzahl die größer ist als 𝑛? Die Frage kannman bejahen, wenn man weiß, dass es unendlich viele Primzahlen gibt. ♢
Da zwei Tupel genau dann gleich sind, wenn sie in ihren Einträgen übereinstimmen, folgt
Definition 6.3 (Gleichheit von Abbildungen) Seien 𝑓1 = (𝑀1, 𝑁1, 𝑅1) und 𝑓2 = (𝑀2, 𝑁2, 𝑅2) Abbil-dungen. Dann gilt 𝑓1 = 𝑓2 genau dann, wenn
• 𝑀1 = 𝑀2 und
• 𝑁1 = 𝑁2 und
• 𝑅1 = 𝑅2 gilt.
Oder anders formuliert:Zwei Abbildungen 𝑓1 und 𝑓2 sind genau dann gleich, wenn ihre Definitions- und Zielbereiche übereinstimmenund für alle Elemente 𝑥 des Definitionsbereichs stets 𝑓1(𝑥) = 𝑓2(𝑥) gilt.
Bitte beachten Sie: Um eine Abbildung zu definieren werden drei Angaben benötigt: Definitionsbe-reich, Zielbereich und die Abbildungsvorschrift, die wie oben als Term oder Menge angegeben wer-den kann.
Beispiel 6.4 Betrachten Sie die Abbildungen
𝑓 ∶ ℕ → ℕ, 𝑧 ↦ 2𝑧 , 𝑔 ∶ ℕ → 2ℕ, 𝑧 ↦ 2𝑧
undℎ ∶ ℕ → ℕ, ℎ(𝑧) ∶= Anzahl der Elemente der Menge {𝑧 + 1, 𝑧 + 2, … , 3𝑧}.
Obwohl 𝑓 (𝑧) = 𝑔(𝑧) für alle 𝑧 ∈ ℕ gilt, ist 𝑓 ≠ 𝑔. Andererseits sind die Abbildungen 𝑓 und ℎ gleich.♢
25
6.1 Bild und Urbild
Wir führen eine Reihe wichtiger Bezeichnungen ein:
Definition 6.5 (a) Der Graph einer Abbildung 𝑓 ∶ 𝑀 → 𝑁 ist die Menge
Γ𝑓 ∶= {(𝑥, 𝑓 (𝑥)) ∣ 𝑥 ∈ 𝑀} ⊂ 𝑀 × 𝑁.
Der Graph von 𝑓 stimmt also genau mit der Menge 𝑅 aus der Funktionsdefinition überein.
(b) Das Bild einer Teilmenge 𝐴 ⊂ 𝑀 unter 𝑓 ∶ 𝑀 → 𝑁 ist die Menge
𝑓 (𝐴) ∶= {𝑓 (𝑥) ∣ 𝑥 ∈ 𝐴} ⊂ 𝑁.
𝑓 (𝑀) heißt Bildmenge oder Bild von 𝑓 .
(c) Das Urbild einer Menge 𝐵 ⊂ 𝑁 ist die Menge
𝑓 −1(𝐵) ∶= {𝑥 ∈ 𝑀 ∣ 𝑓 (𝑥) ∈ 𝐵} ⊂ 𝑀.
(d) Sei 𝐴 eine Teilmenge von 𝑀. Dann nennt man
𝑓 |𝐴 ∶ 𝐴 → 𝑁, 𝑥 ↦ 𝑓 (𝑥)
die Einschränkung von 𝑓 auf 𝐴.
Beispiel 6.6 Es sei
𝑓 ∶ ℕ → ℕ, 𝑛 ↦ { 1 falls 𝑛 ≥ 4,𝑛2 falls 𝑛 < 4.
(a) Das Bild von ℙ unter 𝑓 ist 𝑓 (ℙ) = {1, 4, 9}, denn 𝑓 (2) = 4, 𝑓 (3) = 9 und 𝑓 (𝑛) = 1 für alle 𝑛 ∈ ℙmit 𝑛 ≥ 4.
(b) Das Urbild von ℙ ⊂ ℕ unter 𝑓 ist 𝑓 −1(ℙ) = ∅, denn 𝑓 (𝑛) ist für kein 𝑛 ∈ ℕ eine Primzahl. ♢
Beispiel 6.7 Der Graph Γ einer Funktion ℝ → ℝ ist eine Teilmenge des ℝ2. Identifiziert man dieElemente von Γ mit Punkten des ℝ2, so kann man diese in ein Koordinatensystem einzeichnen underhält eine graphische Darstellung von 𝑓 . ♢
Es gelten die folgenden Regeln für Bild- und Urbildmengen.
Satz 7.2 Für eine Funktion 𝑓 ∶ 𝑋 → 𝑌 sind äquivalent:
(a) 𝑓 ist surjektiv.
(b) 𝑓 (𝑋) = 𝑌.
(c) Zielbereich und Bild der Funktion stimmen überein.
(d) Jedes Element des Zielbereichs hat mindestens ein Urbild.
Beispiel 7.3 Eine Funktion 𝑓 ∶ ℝ → ℝ ist surjektiv genau dann, wenn jede Parallele zur 𝑥-Achse denFunktionsgraphen in mindestens einem Punkt schneidet. ♢
Definition 7.4 (Injektivität) Eine Abbildung 𝑓 ∶ 𝑋 → 𝑌 heißt injektiv, wenn für alle 𝑥1, 𝑥2 ∈ 𝑀 gilt
𝑥1 ≠ 𝑥2 ⟹ 𝑓 (𝑥1) ≠ 𝑓 (𝑥2).
Satz 7.5 Für eine Funktion 𝑓 ∶ 𝑋 → 𝑌 sind äquivalent:
(a) 𝑓 ist injektiv.
(b) ∀𝑥1, 𝑥2 ∈ 𝑋 ∶ 𝑥1 ≠ 𝑥2 ⟹ 𝑓 (𝑥1) ≠ 𝑓 (𝑥2).
(c) ∀𝑥1, 𝑥2 ∈ 𝑋 ∶ 𝑓 (𝑥1) = 𝑓 (𝑥2) ⟹ 𝑥1 = 𝑥2.Mit anderen Worten: Hat ein Element 𝑦 ∈ 𝑌 ein Urbild, so ist dieses Urbild eindeutig.
(d) Jedes 𝑦 ∈ 𝑌 hat höchstens ein Urbild.
Beispiel 7.6 Eine Funktion 𝑓 ∶ ℝ → ℝ ist injektiv genau dann, wenn jede Parallele zur 𝑥-Achse denFunktionsgraphen in höchstens einem Punkt schneidet. ♢
Definition 7.7 (Bijektivität) Eine Funktion 𝑓 ∶ 𝑋 → 𝑌 heißt bijektiv, wenn sie surjektiv und injektiv ist.𝑓 ist also bijektiv genau dann, wenn jedes 𝑦 ∈ 𝑌 genau ein Urbild 𝑥 ∈ 𝑋 besitzt.
Da eine bijektive Funktion zu jedem Element des Zielbereichs genau ein Urbild besitzt, kann man eineneue Funktion definieren
Definition 7.8 (Umkehrfunktion) Sei 𝑓 ∶ 𝑋 → 𝑌 bijektiv. Dann ist auch
𝑔 ∶ 𝑌 → 𝑋, 𝑦 ↦ eindeutiges Urbild von 𝑦 unter 𝑓
eine Funktion. Man nennt sie die Umkehrfunktion oder Umkehrabbildung zu 𝑓 und schreibt 𝑓 −1 für sie.
Satz 7.9 Genau dann ist die Funktion 𝑓 bijektiv, wenn sie eine Umkehrfunktion besitzt. Diese Umkehrfunktionist durch 𝑓 eindeutig bestimmt.
bijektiv = es gibt eine Umkehrfunktion
28
Beispiel 7.10 (a) Betrachten Sie die Abbildungen
𝑓 ∶ ℤ → ℤ, 𝑧 ↦ 𝑧2 und 𝑔 ∶ ℕ → ℕ, 𝑧 ↦ 𝑧2.
𝑓 ist nicht surjektiv, denn es gibt Elemente im Zielbereich, die kein Urbild besitzen, z. B. −1. Esist
𝑓 (ℤ) ⊊ ℤ.𝑓 ist auch nicht injektiv, denn die beiden Elemente 1 und −1 aus dem Definitionsbereich habendasselbe Bild
𝑓 (1) = 1 = 𝑓 (−1).Auch 𝑔 ist nicht surjektiv, denn 2 ∈ ℕ hat kein Urbild unter 𝑔. Allerdings ist 𝑔 injektiv. Denn für𝑥1, 𝑥2 ∈ ℕ mit 𝑔(𝑥1) = 𝑔(𝑥2) folgt
𝑔(𝑥1) = 𝑔(𝑥2) ⟹ 𝑥21 = 𝑥2
2 ⟹ |𝑥1| = |𝑥2|𝑥𝑖 ist positiv
⟹ 𝑥1 = 𝑥2.
Ein Element aus dem Bild von 𝑔 hat also ein eindeutiges Urbild.
(b) Die Funktion𝑓 ∶ ℕ → 2ℕ, 𝑛 ↦ 2𝑛
ist bijektiv. Ihre Umkehrfunktion ist gegeben durch
𝑓 −1 ∶ 2ℕ → ℕ, 𝑛 ↦ 12𝑛. ♢
Definition 7.11 (Komposition) Es seien 𝑓 ∶ 𝑋 → 𝑌 und 𝑔 ∶ 𝑌 → 𝑍 Abbildungen. Die Abbildung 𝑔 ∘ 𝑓(gelesen: „𝑔 nach 𝑓 “) ist dann definiert durch
𝑔 ∘ 𝑓 ∶ 𝑋 → 𝑍, 𝑥 ↦ 𝑔(𝑓 (𝑥)).
Man nennt 𝑔 ∘ 𝑓 die Verknüpfung von 𝑓 mit 𝑔 oder die Komposition von 𝑓 mit 𝑔 oder die Hintereinander-ausführung von 𝑔 und 𝑓 .
Damit man die Komposition 𝑔 ∘ 𝑓 bilden kann, ist es notwendig, dass der Zielbereich von 𝑓 eine Teil-menge des Definitionsbereichs von 𝑔 ist.
Beispiel 7.12 (a) Betrachte
𝑓 ∶ ℕ → ℕ, 𝑛 ↦ 3𝑛 und 𝑔 ∶ ℕ → ℕ, 𝑛 ↦ 𝑛2.
Wir können beide Kompositionen 𝑓 ∘ 𝑔 und 𝑔 ∘ 𝑓 bilden.Es ist für 𝑛 ∈ ℕ
(b) Sei 𝑓 ∶ 𝑋 → 𝑌 bijektiv. Dann gilt für alle 𝑥 ∈ 𝑋
𝑓 −1(𝑓 (𝑥)) = 𝑥.
Ferner haben wir für alle 𝑦 ∈ 𝑌𝑓 (𝑓 −1(𝑦)) = 𝑦. ♢
29
Definition 7.13 Die Abbildungid𝑋 ∶ 𝑋 → 𝑋, 𝑥 ↦ 𝑥
heißt Identität auf 𝑋. Sie ist bijektiv mit id−1𝑋 = id𝑋.
Satz 7.14 Genau dann ist 𝑓 ∶ 𝑋 → 𝑌 bijektiv, wenn es eine Abbildung 𝑔 ∶ 𝑌 → 𝑋 gibt, so dass
𝑔 ∘ 𝑓 = id𝑋 und 𝑓 ∘ 𝑔 = id𝑌
gilt.
Beweis 8. Die Abbildung 𝑔 stellt gerade die Umkehrabbildung zu 𝑓 dar. ■
Achtung: Eine Umkehrfunktion 𝑓 −1 ist nur für bijektive Abbildungen definiert.Das Urbild 𝑓 −1(𝐴) existiert für jede Abbildung 𝑓 ∶ 𝑋 → 𝑌 und jede Teilmenge 𝐴 ⊂ 𝑋.Hier werden für zwei verschiedene Dinge ähnliche Notationen benutzt!
Der folgende Satz zeigt, unter welchen Umständen Abbildungseigenschaften von Funktionen unterder Verkettung erhalten bleiben.
Satz 7.15 Es seien 𝑓 ∶ 𝑋 → 𝑌 und 𝑔 ∶ 𝑌 → 𝑍 Abbildungen.
(a) Sind 𝑓 und 𝑔 beide injektiv, so ist 𝑔 ∘ 𝑓 injektiv.
(b) Sind 𝑓 und 𝑔 beide surjektiv, so ist 𝑔 ∘ 𝑓 surjektiv.
(c) Sind 𝑓 und 𝑔 beide bijektiv, so ist auch 𝑔 ∘ 𝑓 bijektiv. In diesem Fall gilt
(𝑔 ∘ 𝑓 )−1 = 𝑓 −1 ∘ 𝑔−1.
Beweis 9. Wir beweisen nur Aussage (a).
Seien 𝑓 und 𝑔 injektiv. Wir müssen zeigen: Sind 𝑥1, 𝑥2 ∈ 𝑋 und gilt (𝑔 ∘ 𝑓 )(𝑥1) = (𝑔 ∘ 𝑓 )(𝑥2), so folgt𝑥1 = 𝑥2.Gelte also (𝑔 ∘ 𝑓 )(𝑥1) = (𝑔 ∘ 𝑓 )(𝑥2). Dann ist
![Abschätzung der Dichte von Summenmengen (III. Mitteilung). · y ^a + i{;.-]M2-3a(l-a)}. Es erhebt sich die Frage, in welcher Beziehung dieses Ergebnis und sein Beweis zu den Abschätzungen](https://static.unterlagen.site/doc/80x56/5f07092a7e708231d41afa43/abschtzung-der-dichte-von-summenmengen-iii-mitteilung-y-a-i-m2-3al-a.jpg)
