Skript
Skript
i
.
ii
Inhaltsverzeichnis
1 Grundlagen 1
1.1 Mengen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Relationen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.2.1 Äquivalenzrelationen . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.2.2 Ordnungsrelationen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.2.3 Hüllen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.2.4 Anwendung: Relationales Datenmodell . . . . . . . . . . . . . . . . . . 15
1.3 Abbildungen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
1.4 Abzählbarkeit und Gleichmächtigkeit . . . . . . . . . . . . . . . . . . . . . . . 25
1.5 Aussagenlogik . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
1.5.1 Logische Äquivalenz und Tautologien . . . . . . . . . . . . . . . . . . . 30
1.5.2 Normalformen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
2 Reelle Zahlen 35
2.1 Quantoren . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
2.2 Die Körperaxiome der reellen Zahlen . . . . . . . . . . . . . . . . . . . . . . . 36
2.3 Die Anordnung der reellen Zahlen . . . . . . . . . . . . . . . . . . . . . . . . . 39
2.4 Der Absolutbetrag . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
2.5 Potenzen, Summen und Produkte . . . . . . . . . . . . . . . . . . . . . . . . . 41
2.6 Vollständige Induktion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
2.7 Reelle Funktionen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
2.7.1 Funktionsgraphen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
2.7.2 Beschränkte Mengen und Funktionen . . . . . . . . . . . . . . . . . . . 51
2.7.3 Monotone Funktionen . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
2.7.4 Trigonometrische Funktionen . . . . . . . . . . . . . . . . . . . . . . . 56
2.7.5 Polynome und Nullstellen . . . . . . . . . . . . . . . . . . . . . . . . . 58
iii
3 Der Euklidische Raum Rn 63
3.1 Der Rn . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
3.2 Das Skalarprodukt . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
3.3 Lineare Gleichungssysteme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
3.4 Lineare Abbildungen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
3.4.1 Matrix Algebra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
3.4.2 Lineare Abbildungen als Matrix . . . . . . . . . . . . . . . . . . . . . . 74
3.4.3 Anwendungen: Google Matrix und PageRank . . . . . . . . . . . . . . 76
3.4.4 Lineare Abbildungen in der Geometrie . . . . . . . . . . . . . . . . . . 78
3.4.5 Inverse einer Linearen Abbildung . . . . . . . . . . . . . . . . . . . . . 82
3.4.6 Anwendung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
3.5 Determinante . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
3.5.1 Motivation und Definition . . . . . . . . . . . . . . . . . . . . . . . . . 85
3.5.2 Eigenschaften der Determinante . . . . . . . . . . . . . . . . . . . . . . 88
3.5.3 Determinante einer Oberen Dreiecksmatrix . . . . . . . . . . . . . . . 92
3.5.4 Berechnung der Determinante mit dem Gaußalgorithmus . . . . . . . . 92
iv
Kapitel 1
Grundlagen
1.1 Mengen
Eine Menge ist eine Zusammenfassung von (mathematischen) Objekten. Die Objekte in einer
Menge werden als Elemente bezeichnet. Wir schreiben x ∈ X falls x ein Element der Menge
X ist und y 6∈ X falls y kein Element der Menge ist.
Hier sind einige Beispiele von Mengen, die Ihnen womöglich schon begegnet sind:
Beispiele 1.1.1.
(i) Die leere Menge ∅ ist die Menge die kein Element enthält.
Oft benutzen wir geschweifte Klammern für Mengen deren Elemente leicht aufzuschreiben
sind, zum Beispiel, die leere Menge ∅ := {} oder die Menge {2, 3, 5, 7} der Primzahlen kleiner
10. Ähnlich können auch Mengen, die eine unendliche Folge von Elemente enthält, dargestellt
werden:
Beispiele 1.1.2.
(i) N = {1, 2, 3, 4, . . . }
(ii) N0 = {0, 1, 2, 3, 4, . . . }
Anders verhält es sich mit der Menge der reellen Zahlen R. Diese Menge kann nicht in
dieser Weise beschrieben werden. Dies werden wir später in Satz 4.2.52 noch genauer sehen.
Wir beschreiben eine Menge auch als Zusammenfassung von Elementen, die eine gewisse
Eigenschaft besitzen. Damit wir über gewisse Eigenschaften reden können, wollen wir diese
erstmal einführen.
Definition 1.1.3.
1
(i) Eine ganze Zahl z ∈ Z ist durch n ∈ N teilbar, falls eine k ∈ Z gibt, sodass z = kn. Wir
schreiben auch n|z. Dann wird n auch als Teiler von z bezeichnet.
(iv) Eine natürlich Zahl p ∈ N ist prim oder heißt Primzahl, falls 1 und p die einzigen
Teiler von p sind.
Eine ganze Zahl z ∈ Z ist also gerade, falls k ∈ Z existiert, so dass z = 2k gilt und ungerade,
falls es ein k ∈ Z existiert, so dass z = 2k + 1 gilt.
Beispiele 1.1.4.
(i) Die Menge aller geraden Zahlen {z : z ist eine ganze Zahl und 2|z}.
(ii) Die Menge der Primzahlen {p : p ist eine natürlich Zahl und prim}.
Hier ließt man „ := “ als definiert als und „ : “ in der Mengenklammer als „sodass“ oder „für
die gilt“.
Definition 1.1.5. Seien X und Y Mengen. Wir nennen X eine Teilmenge von Y falls jedes
x ∈ X auch ein Element von Y ist. Wir schreiben X ⊂ Y um auszudrücken, dass X eine
Teilmenge von Y ist.
In der gleichen Weise, in der wir Mengen durch Elemente mit bestimmten Eigenschaften
beschreiben, können wir dies mit Teilmengen tun:
Beispiele 1.1.6.
Anders als in der Schulmathematik, in der meist gewissen Techniken wie Dreisatz, p-q-
Formel, Differenzieren oder Lösen von linearen Gleichungen erlernt und angewendet werden,
werden wir die meisten Aussagen nicht einfach hinnehmen sondern versuchen sie mit unserem
bisherigen Wissen zu beweisen. Das Erarbeiten und Schreiben eines Beweises ist ein langer
Lernprozess, benötigt Zeit und vor allem Hilfestellungen. Eine Metapher ist vielleicht das
schreiben eines Gedichtes. Es hilft erstmal einige Gedichte von Anderen gelesen zu haben, um
ein Gefühl zu bekommen, wie die Struktur aussehen kann, und sich inspirieren zu lassen. Des
weiteren gibt es gewisse Formate von Gedichten wie das Elfchen und Reime wie der Paar oder
Kreuzreim an denen man sich orientieren kann. Im Nu schafft man es ein simples Gedicht zu
schreiben:
2
Mathematik
Öffnet Welten
Undurchschaubar und mysteriös
Lernen bringt uns voran
Zuversicht
In dieser Weise wollen wir Ihnen Beweismethoden wie mathematische Induktion als Richtlinien
an die Hand geben und Sie langsam an diese große Herausforderung heranzuführen.
Hier sehen Sie zum Beispiel den Aufbau eines Beweis um zu zeigen dass eine Menge X
Teilmenge einer Menge Y ist:
Teilmenge:
• Gemäß der Definition, müssen wir zeigen, dass für jedes x ∈ X, auch x ∈ Y
1 gilt. 1
• Sei x ∈ X.
Die ersten Beweise werden wir noch in Spiegelstrichen unterteilen. Danach schreiben wir
sie im Fließtext, wie es sonst üblich ist.
• Nach der Definition von Teilmenge, müssen wir zeigen dass wenn x ∈ X, dann auch
x ∈ Z.
• Sei x ∈ X.
3
Liste: Hier ist eine Liste der Dinge, die wir während eines Beweises tun.
• Wir stellen die mathematischen Objekte vor, die wir während des Beweises
verwenden.
Definition 1.1.8. Angenommen, X und Y sind Mengen. Wir sagen, dass X gleich Y ist,
wenn X eine Teilmenge von Y ist und Y eine Teilmenge von X ist. Wir schreiben X = Y .
In der zweiten Beweisstrategie geht es darum zu zeigen dass zwei Mengen gleich sind:
4
Mengengleichheit:
Beispiel 1.1.9.
Bevor wir einen Beweis dafür sehen, dass zwei Mengen gleich sind, führen wir zunächst
folgende Definitionen ein:
{z : z ∈ X oder z ∈ Y }.
{z : z ∈ X und z ∈ Y }.
{z : z ∈ X und z 6∈ Y }.
Beispiel 1.1.11.
(ii) {n ∈ N : n ist durch 2 teilbar}∩{n ∈ N : n ist durch 3 teilbar} = {n ∈ N : n ist durch 6 teilbar}
5
(i) X ⊂ X ∪ Y und Y ⊂ X ∪ Y
(ii) X ∩ Y ⊂ X und X ∩ Y ⊂ Y
(iii) X \ Y ⊂ X
(iv) X ∪ Y = Y ∪ X und X ∩ Y = Y ∩ X
(v) (X ∪ Y ) ∪ Z = X ∪ (Y ∪ Z) und (X ∩ Y ) ∩ Z = X ∩ (Y ∩ Z)
(i) X \ (A ∩ B) = (X \ A) ∪ (X \ B),
(ii) X \ (A ∪ B) = (X \ A) ∩ (X \ B).
Beweis.
X \ (A ∩ B) = (X \ A) ∪ (X \ B).
6
In beiden Fällen haben wir gezeigt dass z ∈ X \ (A ∩ B).
• Wir haben gesehen dass
X \ (A ∩ B) ⊂ (X \ A) ∪ (X \ B) und (X \ A) ∪ (X \ B) ⊂ X \ (A ∩ B),
Den Beweis von (ii) schreiben wir nun in Fließtext und benutzen gewisse Abkürzungen. Hier
bedeutet „⊂“, dass wir nun beweisen dass die linke Menge in der rechten enthalten ist. Analog
interpretieren wir „⊃“.
X \ (A ∪ B) ⊂ (X \ A) ∩ (X \ B).
Gemäß der Definition müssen wir zeigen, dass für jedes x ∈ X \ (A ∪ B) auch
x ∈ (X \ A) ∩ (X \ B) gilt. Sei also x ∈ X \ (A ∪ B), d. h. x ∈ X aber x 6∈ A ∪ B.
Bemerkung 1.1.12 (vii) besagt, dass x 6∈ A und x 6∈ B. Da x ∈ X und x 6∈ A,
erhalten wir x ∈ X \ A. Des Weiteren, weil x ∈ X und x 6∈ B, haben wir zusätzlich
dass x ∈ X \ B. Gemäß der Definition von Durchschnitt erhalten wir dass x ∈
(X \ A) ∩ (X \ B).
X \ (A ∪ B) ⊃ (X \ A) ∩ (X \ B).
Gemäß der Definition müssen wir zeigen, dass für jedes x ∈ (X \ A) ∩ (X \ B) auch
x ∈ X \ (A ∪ B). Sei x ∈ (X \ A) ∩ (X \ B), d. h. x ∈ X \ A und x ∈ X \ B. Daraus
folgt, dass x ∈ X aber x 6∈ A und x 6∈ B. Mit Bemerkung 1.1.12 (vii) folgt, dass
x 6∈ A ∪ B. Unter der Benutzung der Definition von \ liefert dies x ∈ X \ (A ∪ B).
Im Beweis von (i) werden in (a) als auch (b) jeweils 2 Fälle betrachtet. Diese Fälle waren,
bis auf Vertauschung von A und B, identisch. Aufgrund der symmetrischen Situation, könnte
man erwarten, dass die Lesenden den Beweis des zweiten Falls selbstständig aus dem ersten
Fall herleiten. In solchen Fällen schreibt man: „Fall 2 ist ähnlich“ oder : „Ohne Beschränkung
der Allgemeinheit (o. B. d. A.) müssen wir nur den ersten Fall betrachten.“ Ich würde jedoch
aufpassen, gerade am Anfang, dies zu tun, ohne zu verifizieren, dass der Beweis wirklich iden-
tisch ist (d. h. ihn aufgeschrieben zu haben). Manchmal können die Situationen symmetrisch
erscheinen, aber nach sorgfältiger Überlegung stellt man fest, dass es nicht so einfach ist!
Definition 1.1.14. Seien X und Y Mengen. Dann ist
X × Y = {(x, y) : x ∈ X, y ∈ Y }
die Menge der geordneten Paare (x, y) mit erster Koordinate x in X und zweiter
Koordinate y in Y . Wir nennen X × Y das kartesische Produkt von X und Y .
Allgemeiner, sei n ∈ N und seien X1 , . . . , Xn Mengen. Dann ist
X1 × · · · × Xn = {(x1 , . . . , xn ) : xi ∈ Xi für i = 1, . . . , n}
die Menge der n-Tupel (x1 , . . . , xn ) mit i–ter Koordinate xi in Xi für i = 1, . . . , n. Wir
nennen X1 × · · · × Xn das kartesische Produkt von X1 , . . . , Xn .
7
Aufgepasst! Ein 1-Tupel ist (x1 ) mit x1 ∈ X1 . Ein 0-Tupel ist das leere Tupel ().
1 1
Beispiele 1.1.15.
(i) R × R = R2
(ii) R × · · · × R = Rn
| {z }
n−mal
(iii) {1, 2, 3} × {1, 8} = {(1, 1), (1, 8), (2, 1), (2, 8), (3, 1), (3, 8}
{(1, 1, 5), (1, 8, 5), (2, 1, 5), (2, 8, 5), (3, 1, 5), (3, 8, 5),
(iv) {1, 2, 3} × {1, 8} × {5, 11} =
(1, 1, 11), (1, 8, 11), (2, 1, 11), (2, 8, 11), (3, 1, 11), (3, 8, 11)}
Definition 1.1.16. Die Menge aller Teilmengen einer Menge X heißt Potenzmenge von X
und wird mit P(X) bezeichnet:
P(X) = {Y : Y ⊂ X}
P(X) = {∅, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}}
Beispiele 1.1.18.
√
(i) Sei P = {{1, 7}, {1, 3, π}, {−2341, 2}}. Dann ist
[ √
Y = {−2341, 1, 2, 3, π, 7}
Y ∈P
8
Definition 1.1.19. Sei X eine Menge. Eine Partition von X ist eine Teilmenge P ⊂ P(X) \
{∅} sodass
• Y ∈P Y = X.
S
Beispiele 1.1.20.
{{1, 4}, {2, 3}}, {{1, 2, 3, 4}}, und {{1, 2}, {3}, {4}}
Partitionen von X.
(ii) Sei
Tiere = {Fink, Rotkelchen, Amsel, Hai, Goldfisch, Zebra, Panda, Katze, Wal}
Dann ist
1.2 Relationen
Will man verschiedene Elemente in einer Menge oder verschiedener Mengen miteinander ver-
gleichen, braucht man eine Beziehung zwischen diesen. Eine einzelne Menge ist strukturlos.
Eine solche Beziehung nennen wir „Relation“. Die Untersuchung der Eigenschaften von Rela-
tionen ist eine wichtige Aufgabe in der Mathematik.
Definition 1.2.1. Eine (binäre) Relation zwischen zwei Mengen X und Y ist eine Teil-
menge
R ⊂X ×Y
Im Falle X = Y sprechen wir von einer Relation auf X.
Eine Relation R ⊂ X × Y beschreibt also ein Beziehung, die zwischen Elementen aus X
und Y besteht: x ∈ X steht in Relation zu y ∈ Y genau dann wenn (x, y) ∈ R . Wir schreiben
auch x R y oder x ∼ R y für (x, y) ∈ R und x 6 R y oder x 6∼ R y für (x, y) 6∈ R .
Beispiele 1.2.2. Sei X eine beliebige Menge und G die Menge aller Geraden in der Ebene
R2 (Geraden werden hier als Teilmengen des R2 auf gefasst).
R = := {(x, x) : x ∈ X}
Beispiel: Auf X = {−1, 0, 1} ist R= = {(0, 0), (1, 1), (−1, −1)}, da 0 = 0, 1 = 1,
−1 = −1 aber 0 6= 1, 0 6= −1 und 1 6= −1.
9
(ii) Die Anordnung a ≤ b auf N (oder Z, Q, R):
≤ := {(a, b) ∈ N × N : a ≤ b}
Beispiel: (1, 2), (3, 64), (5, 5) ∈ ≤, aber (2, 1), (295, 56) 6∈ ≤).
Beispiel: Auf X = {0, 1, 2, 3, 4, 5} sind (∅, {0, 1, 5}), ({0, 4}, {0, 1, 3, 4, 5}), ({5}, {5}) ∈
⊂ aber ({1, 3, 5}, ∅), ({1}, {2, 3, 4, 5}) 6∈ ⊂.
Beispiel: (1, 23), (2, 24), (5, 5) ∈ |, aber (2, 1), (3, 29) 6∈ |).
|| := {(g, h) ∈ G × G : g = h oder g ∩ h = ∅}
R := {(v, g) ∈ R2 × G : v ∈ g}
Beachte: v R g genau dann wenn der Punkt v auf der Geraden g liegt.
Man kann aus mehreren Relationen auch neue Relationen bilden. Da Relationen auch Men-
gen sind, kann man zum Beispiel die Vereinigung, den Durchschnitt oder das Komplement
nehmen.
Beispiele 1.2.3.
R −1 = {(y, x) ∈ Y × X : (x, y) ∈ R }.
10
Beispiele 1.2.5.
(ii) Die Verkettung von < und < auf N ist: {(x, y) ∈ N × N : x < y − 1}.
(iii) Wir betrachten die Menge X = {x, y, z} mit paarweise verschiedenen Elementen x, y, z,
d. h. es gilt x 6= y 6= z 6= x und die Relationen
Es gilt
R −1
1 = {(z, x), (y, x), (z, y)},
R 1 ◦ R 2 = {(x, z), (x, y), (z, z), (y, z), (y, y), (z, y)},
R 2 ◦ R 1 = {(x, y), (x, z), (x, x), (y, y), (y, z), (y, x))},
R −1
1 ◦ R 1 = {(x, x), (x, y), (y, x), (y, y)}.
Beispiel 1.2.7. Wir betrachten wieder die Menge X = {x, y, z} mit paarweise verschiedenen
Elementen x, y, z, d. h. es gilt x 6= y 6= z 6= x und die Relationen
R 1 ist
• transitiv, da mit (x, y), (y, z) ∈ R 1 auch (x, z) ∈ R 1 gilt. Andere entsprechende Fälle
treten nicht auf.
R 2 ist
11
• symmetrisch, da mit (a, b) ∈ R 2 auch (b, a) ∈ R 2 für alle a, b ∈ X gilt,
• transitiv, da mit (a, b) ∈ R 2 und (b, c) ∈ R 2 auch (a, c) ∈ R 2 folgt für alle a, b, c ∈ X.
Bemerkung 1.2.8. Sei R eine Relation in der Menge X und IX = {(x, x) : x ∈ X} die
Gleichheitsrelation in X.
(i) Der Unterschied zwischen antisymmetrischen und asymmetrischen Relationen ist, dass
in antisymmetrischen Relationen auch x R x gelten kann, während diese Eigenschaft in
asymmetrischen Relationen verboten ist.
1.2.1 Äquivalenzrelationen
In diesem Abschnitt wollen wir Relationen betrachten, die die charakteristischen Eigenschaften
der Gleichheitsrelation besitzen.
Definition 1.2.9. Sei X eine nicht leere Menge. Eine Relation R auf X die reflexiv, sym-
metrisch und transitiv ist, heißt Äquivalenzrelation. Für x ∈ X nennt man die Menge
[x]∼ R = {y ∈ X : x R y}
die Äquivalenzklasse von x. Man nennt x und jedes andere Element aus [x]∼R einen Ver-
treter oder Repräsentanten dieser Äquivalenzklasse.
Beispiele 1.2.10. (i) Die Gleichheitsrelation x = y auf X.
(ii) Die Relation „parallel“ || auf der Menge G aller Geraden in der Ebene R2 (siehe oben).
Die Äquivalenzklasse von g ∈ G ist der Menge aller zu g parallelen Geraden.
(iii) Sei Mensch die Menge aller Menschen (die in einem Land geboren wurden). Dann ist
„im gleichen Land geboren zu sein“ eine Äquivalenzrelation. Die Äquivalenzklassen sind
dann die Mengen aller Menschen, die im gleichen Land geboren wurden.
(iv) Auf der Menge {1, 2, 3} ist R = {(1, 1), (1, 2), (2, 1), (2, 2), (3, 3)} eine Äquivalenzrelati-
on, da sie reflexiv, symmetrisch und transitiv ist.
Bemerkung 1.2.11. Die Äquivalenzklassen einer Äquivalenzrelation auf der Menge X bilden
eine Partition von X.
Umgekehrt definiert jede Partition P = {Yi : i ∈ I} eine eindeutig bestimmte Äquivalenzrela-
tion ∼P mit Äquivalenzklassen Yi :
12
Definition 1.2.12. Sei X eine Menge und ∼ eine Äquivalenzrelation auf X. Ein Vertreter-
system ist eine Teilmenge von X, die für jede Äquivalenzklasse genau ein Element enthält.
Beispiele 1.2.13.
(i) Für die Gleichheitsrelation ist die gesamte Menge eine Vertretersystem.
(ii) Die Relation „parallel“ || auf der Menge G aller Geraden in der Ebene R2 sind die
Geraden durch (0, 0) ein Vertretersystem.
(iii) Für die Relation „im gleichen Land geboren zu sein“ ist eine Menge, die für jedes Land
genau einen Menschen enthält der in diesem Land geboren wurde, ein Vertretersystem.
(iv) Für die Äquivalenzrelation R = {(1, 1), (1, 2), (2, 1), (2, 2), (3, 3)} auf {1, 2, 3} aus Bei-
spiel 1.2.10 gibt es zwei Äquivalenzklassen
1.2.2 Ordnungsrelationen
In diesem Abschnitt wollen wir Relationen betrachten, die sich wie ⊂ auf einer Menge X
verhalten oder wie ≤ auf R.
Definition 1.2.14. Sei X eine Menge. Eine Ordnung auf X ist eine reflexive, antisym-
metrische und transitive Relation. Eine strike Ordnung auf X ist eine asymetrische und
transitive Relation. Wir nennen eine (strikte) Ordnung total, wenn je zwei Elemente ver-
gleichbar sind:
für alle x 6= y in X gilt x y oder y x
Ansonsten nennen wir sie partiell.
Beispiele 1.2.15.
(iv) Sei J = {1, 2, 3, 4, 5} die Menge aller Teilschritte (Jobs) eines Ablaufes. Die Reihenfolge
der Jobs kann durch die Relation „a muss vor b erledigt werden“ festgelegt werden.
Wenn zum Beispiel Job 1 vor Job 2 als auch vor Job 3, Job 2 vor Job 4 und Job 3 vor
Job 5 erledigt werden muss, so kann dies durch die strikte Ordnungsrelation
R = {(1, 2), (1, 3), (1, 4), (1, 5), (2, 4), (3, 5)}
beschrieben werden. Dies ist eine partielle strikte Ordnung, da zum Beispiel zwischen
Job 2 und Job 3 oder Job 4 und Job 5 keine Relation besteht (d. h. die Reihenfolgen, in
der diese Jobs ausgeführt werden, ist egal)
13
1.2.3 Hüllen
Am letzten Beispiel sehen wir, dass R eindeutig durch die Forderungen „ R entält R 0 =
{(1, 2), (1, 3), (2, 4), (3, 5)}“ und „ R ist transitiv“, bestimmt ist. Wenn R transitiv ist, folgt
nämlich aus (1, 3), (3, 5) ∈ R dass (1, 5) ∈ R und aus (1, 2), (2, 4) ∈ R dass (1, 4) ∈ R .
Formal erhalten wir, dass R aus R 0 entsteht, indem wir sukzessiv die Komposition R 0 ◦ R 0 ,
( R 0 ◦ R 0 ) ◦ R 0 , . . . hinzufügen (in diesem Beispiel ist R = R 0 ∪ ( R 0 ◦ R 0 )). Man sagt,
dass R die transitive Hülle von R 0 ist. Im Allgemeinen versteht man unter der Hülle einer
Relation R 0 die kleinste Relation die R 0 enthält und eine bestimmte Eigenschaft besitzt.
Definition 1.2.16. Sei R eine Relation auf der Menge X. Wir definieren:
(i) Für n ∈ N0 (
IX n=0
Rn =
R ◦ R n−1 n≥1
R refl = R ∪ IX
R sym = R ∪ R −1
Aufgepasst! Die Hüllen ergeben nur Sinn wenn es sich um eine Relation auf einer
1 1
Menge handelt, nicht für Relationen zwischen verschiedenen Mengen.
Aufgepasst! R 0 wird zwar definiert, taucht aber in der Definition von transitiver
1 1
Hülle nicht auf. Insbesondere ist R 0 im allgemeinen keine Teilmenge von R trans .
Bemerkung 1.2.17. Die transitive (symmetrische, reflexive) Hülle ist transitiv (symme-
trisch, reflexiv).
Beispiel 1.2.18. Gegeben sei die Relation R = {(1, 2), (2, 3), (3, 4), (4, 5)} auf X = {1, 2, 3, 4, 5}.
Dann ist
R refl = R ∪ IX = {(1, 2), (2, 3), (3, 4), (4, 5), (1, 1), (2, 2), (3, 3), (4, 4), (5, 5)}
und
R sym = R ∪ R −1 = {(1, 2), (2, 3), (3, 4), (4, 5), (2, 1), (3, 2), (4, 3), (5, 4)}.
14
Weiter gilt
Bisher haben wir nur binäre Relationen, d. h. Relationen zwischen zwei Mengen, betrachtet.
Allgemeiner kann man auch Relationen zwischen mehr als zwei Mengen untersuchen:
Definition 1.2.19. Für n ∈ N ist eine n-stellige Relation zwischen den Mengen X1 , . . . ,
Xn eine Teilmenge
R ⊂ X1 × · · · × Xn
Beispiel 1.2.20. Sei Frau die Menge aller Frauen, Mann die Menge aller Männer und
Mensch die Menge aller Menschen. Wir definieren die Relation R ⊂ Frau × Mann × Mensch
„biologische Eltern von...“ als (F, M, P ) ∈ R genau dann wenn
Relationen bilden die Grundlage des relationalen Datenmodells, das in modernen Daten-
banken verwendet wird. In Datenbanken stellt man Relationen in Form von Tabellen dar. Die
einzelnen n-Tupel der Relation sind dabei die Zeilen der Tabelle.
Beispiel 1.2.21. Die Produkte eines Computerhändlers können übersichtlich in Tabellenform
aufgelistet werden:
15
Die Zeilen der Tabelle sind Elemente von N × CHAR(30) × CHAR(20) × N × N und somit stellt
die Tabelle eine Relation R P ⊂ N × CHAR(30) × CHAR(20) × N × N dar (wobei CHAR(n) die
Menge aller Strings mit maximal n Einträgen ist). Die einzelnen Spalten der Tabelle gehören
dabei zu gewissen Attributen wie [Link], Produktname, etc.
Analog kann die Relation R H ⊂ N × CHAR(20) × CHAR(20), die nähere Informationen zu den
Herstellern enthält, folgendermaßen dargestellt werden:
Die beiden Relationen R P und R H bilden kleine Datenbanken. Damit wir diese in der Praxis
sinnvoll nutzen können, sollten Abfragen durchführbar sein, wie zum Beispiel: „Welche Tablets
verkauft der Händler zu welchem Preis?“ oder „Welche Produkttypen von HP hat der Händler
in seinem Sortiment?“
Nun ist es möglich, alle Abfragen, die man benötigt, einzeln zu implementieren. Steigen aber
die Anzahl der Daten und somit die Anzahl der benötigten Abfragen, so wird das irgendwann
zu aufwändig. Deshalb versucht man alle möglichen Abfragen auf einige wenige zu reduzieren,
und alle anderen auf diese zurückzuführen. Das führt direkt zur so genannten relationalen
Algebra, die in den meisten Datenbanken als „Structured Query Language“ (SQL) implemen-
tiert ist. Hier eine Auswahl der wichtigsten Operationen:
σBedingung : (SELECT) Diese Operation wählt die Zeilen aus, für die die Bedingung erfüllt ist.
Beispiel: Wir wählen aus R P alle Zeilen aus, deren Attribut Produkttyp den Wert
„Notebook“ hat.:
πName,Headquarters ( R H ) = {(Apple, Cupertino CA), (Dell, Round Rock TX), (HP, Palo Alto CA)}
16
bzw. in Tabellenform dargestellt:
Name Headquarters
Apple Cupertino CA
Dell Round Rock TX
HP Palo Alto CA
R 1 [j1 , j2 ] R 2 : (JOIN) „verkettet“ die Relationen R 1 und R 2 bezüglich der gemeinsamen At-
tribute j1 (von R 1 ) und j2 (von R 2 ). Die Zeilen der neuen Relation entstehen durch
Aneinanderfügung von je einer Zeile der ersten und der zweiten Relation, deren Attri-
butwerte von j1 und j2 übereinstimmen.
Beispiel: Die Relationen R P und R H können bezüglich [Link]. verkettet werden. In
Tabellenform wird ( R P [H.N r., H.N r.] R H ) wie folgt dargestellt:
Die Anfrage „Name und Preisliste aller Tablets“ könnte damit wie folgt formuliert werden
πProduktname,Preis (σProdukttyp=Tablet ( R P ))
17
Produktname Preis
Elite x2 G8 Tablet 2768
iPad Pro 12.9” 1199
iPad 379
iPad Mini 549
iPad Air 649
Die Anfrage „Liste der Produkttypen von HP“ könnte damit wie folgt formuliert werden
Schritt 1: Wir nehmen ( R P [H.N r., H.N r.] R H ): (siehe Tabelle oben)
Produkttyp
Notebook
Tablet
Drucker
Notebook
Drucker
1.3 Abbildungen
Wir beginnen diesen Abschnitt mit einigen Beispielen, von denen Ihnen sicher schon manche
begegnet sind.
Beispiele 1.3.1.
• f : R → R, f (x) = sin(x2 ).
18
Nun wollen wir formal definieren, was genau eine Abbildung ist.
• einer Vorschrift, die jedem x ∈ X eindeutig ein y ∈ Y zuordnet. Wir schreiben f (x) für
das Element in Y das x zugeordnet wird.
Beispiele 1.3.3.
• f : R → R, x 7→ sin(x2 ).
• Eine wichtige Abbildung ist die identische Abbildung auf einer beliebigen Menge X:
IdX : X → X, x 7→ x
Aufgepasst! Man muss bei der Wahl des Definitionsbereich als auch Wertebereich
immer aufpassen. Es kann zum Beispiel Vorschriften geben die für gewisse Elemente
1 1
nicht definiert sind, oder die definierten Bilder liegen in einer größeren Menge als
der Wertebereich. Hier sind zwei Beispiele die dies verdeutlichen:
19
√
Beispiele 1.3.5. Betrachte die Vorschrift x 7→ x.
(i) Diese Abbildung ist für R → R nicht definiert, da die Wurzel einer negativen Zahl nicht
in R liegt. Wenn wir uns bei dem Definitionsbereich jedoch auf R+ beschränken, erhalten
√
wir mit f1 : R+ → R, x 7→ x eine wohldefinierte Abbildung.
(ii) Sei Q+ := {x ∈ Q √ : x ≥ 0}. Dies obige Abbildung ist für Q → Q nicht definiert,
+
da beispielsweise 2 nicht rational ist. Wenn man allerdings den Wertebereich auf R
√
vergrößert und die Abbildung f2 : Q+ → R, x → x betrachtet ist dies wieder „wohl-
definiert“.
Die obige Abbildung f2 kann auch als Einschränkung von f1 auf den Definitionsbereich Q+
gesehen werden. Dies ist ein allgemeines Konzept:
f (x) = y.
Dann ist
f −1 (Y0 ) := {x ∈ X : f (x) ∈ Y0 } ⊂ X
Aufgepasst! Das Bild von x und der Menge {x} ist formal etwas anderes. Das Bild
1 von x ist ein Element aus Y und das Bild von {x} ist die Teilmenge {f (x)} von Y .1
Dies gilt analog für Urbilder von y und {y}.
Aufgepasst! Man kann jede Abbildung auf eine beliebige Teilmenge des Defini-
1 tionsbereich beschränken. Dies gilt nicht für den Wertebereich. Hier kann nur auf1
Teilmengen einschränken, die das Bild des Definitionsbereich enthalten.
Beispiel 1.3.7. Betrachte die Abbildung R → R, x 7→ x2 . Dann ist 4 das Bild von 2, 3 und
−3 sind Urbilder von 9. Das Bild von R ist R+ und das Urbild von [0, 4] ist [−2, 2].
Definition 1.3.8. Seien X und Y Mengen und f : X → Y eine Abbildung.
20
(i) Wir nennen f injektiv falls aus x1 , x2 ∈ X mit f (x1 ) = f (x2 ) stets x1 = x2 folgt.
(ii) Wir nennen f surjektiv falls es für jedes y ∈ Y , ein x ∈ X existiert so dass f (x) = y.
Beispiele 1.3.9.
Beispiele 1.3.11.
Wie schreibt man einen Beweis, dass eine Abbildung injektiv, surjektiv oder bijektiv ist?
Seien X und Y Mengen und f : X → Y eine Abbildung.
injektiv:
• Gemäß der Definition, müssen wir zeigen, dass für x1 , x2 ∈ X mit f (x1 ) =
f (x2 ) stets x1 = x2 gilt.
1 1
• Seien x1 , x2 ∈ X sodass f (x1 ) = f (x2 ).
• Wir folgern dass x1 = x2 , und haben somit gezeigt dass f injektiv ist.
21
surjektiv:
• Gemäß der Definition, müssen wir zeigen, dass für jedes y ∈ Y , ein x ∈ X
existiert sodass f (x) = y.
• Sei y ∈ Y .
1 1
• [Finde mit Hilfe mathematischer Argumente ein x ∈ X sodass f (x) = y.]
Zwei Dinge müssen gemacht werden:
bijektiv:
• Gemäß der Definition, müssen wir zeigen, dass f injektiv und surjektiv ist.
1 1
• [Füge einen Beweis dass f injektiv ist ein]
• Die Abbildung f ist somit injektiv und surjektiv und daher bijektiv.
(vi) Wenn f injektiv ist, ist ff (X) : X → f (X), x 7→ f (x) bijektiv.
Beweis. (i) Wir wollen zeigen dass f injektiv ist. Gemäß der Definition, müssen wir zeigen,
dass für x1 , x2 ∈ X mit f (x1 ) = f (x2 ) stets x1 = x2 gilt. Seien x1 , x2 ∈ X sodass
f (x1 ) = f (x2 ). Dann gilt
Da g ◦ f injektiv ist, können wir folgern dass x1 = x2 und haben somit gezeigt dass f
injektiv ist.
22
(ii) Wir wollen zeigen, dass g surjektiv ist. Gemäß der Definition, müssen wir zeigen, dass
für jedes z ∈ Z, ein y ∈ Y existiert sodass g(y) = z. Sei z ∈ Z. Da g ◦ f surjektiv ist,
gibt es x ∈ X so dass (g ◦ f )(x) = z. Sei y = f (x). Dann gilt
(iii) Wir wollen zeigen dass g ◦ f injektiv ist. Gemäß der Definition, müssen wir zeigen, dass
für x1 , x2 ∈ X mit g ◦ f (x1 ) = g ◦ f (x2 ) stets x1 = x2 gilt. Seien x1 , x2 ∈ X sodass
g ◦ f (x1 ) = g ◦ f (x2 ). Mit anderen Worten, g(f (x1 )) = g(f (x2 )). Da g injektiv ist, folgt
f (x1 ) = f (x2 ). Des Weiteren, weil f auch injektiv ist, erhalten wir, dass x1 = x2 . Somit
haben wir gezeigt das g ◦ f injektiv ist.
(iv) Wir wollen zeigen dass g ◦ f surjektiv ist. Gemäß der Definition, müssen wir zeigen, dass
wir für jedes z ∈ Z, ein x ∈ X finden können so dass g ◦ f (x) = z. Da g surjektiv ist,
existiert y ∈ Y so dass g(y) = z. Da außerdem f surjektiv ist, gibt es x ∈ X so dass
f (x) = y. Dann ist
g ◦ f (x) = g(f (x)) = g(y) = z,
und wir haben gezeigt dass, g ◦ f surjektiv ist.
(v) Wir wollen zeigen dass f bijektiv ist. Gemäß der Definition, müssen wir zeigen, dass
f injektiv und surjektiv ist. Aus (iii) folgt dass f injektiv und aus (iv) folgt dass f
surjektiv ist. Wir folgern dass f bijektiv ist.
(vi) Übungsaufgabe
Lemma 1.3.13. Seien X und Y Mengen und f : X → Y eine bijektive Abbildung. Dann gibt
es eine inverse Abbildung (oder Umkehrabbildung) f −1 : Y → X so dass
(i) Können wir überhaupt für jedes y ∈ Y , ein x ∈ X finden so dass f (x) = y?
Ja, weil f surjektiv ist.
(ii) Wenn es x1 6= x2 gibt so dass f (x1 ) = f (x2 ) = y, was ist dann f −1 (y)? Solche x1 und
x2 gibt es nicht, da f injektiv ist.
Aber wie zeigt man eigenltich genau dass zwei Abbildungen gleich sind?
23
Gleichheit von Abbildungen: Seien f : X → Y und g : X → Y zwei Abbildun-
gen mit gleichem Defintions- und Wertebereich.
und
f ◦ f −1 (y) = f (f −1 (y)) = y für alle y ∈ Y
Es folgt
f −1 ◦ f = IdX und f ◦ f −1 = IdY
(ii) (f −1 )−1 = f .
f (x) = y, (1.1)
(i) f injektiv ⇐⇒ für alle y ∈ Y existiert höchstens eine Lösung von (2.10) (Eindeutigkeit).
(ii) f surjektiv ⇐⇒ für alle y ∈ Y existiert mindestens eine Lösung von (2.10) (Existenz).
(iii) f bijektiv ⇐⇒ Existenz & Eindeutigkeit von Lösungen von (2.10) für beliebige y ∈ Y .
Sei f bijektiv, y ∈ Y und x ∈ X die eindeutige Lösung von (2.10). Dann definiert
f −1 (y) := x. (1.2)
24
1.4 Abzählbarkeit und Gleichmächtigkeit
(i) M ∼ M (Reflexivität)
(ii) M ∼ N =⇒ N ∼ M (Symmetrie)
Beweis. Übungsaufgabe
Mit dem Begriff der Gleichmächtigkeit wollen wir die „Größe“ zweier Mengen vergleichen
bzw. entscheiden, ob zwei Mengen in gewisser Art und Weise „gleich viele“ Elemente enthalten.
Definition 1.4.3. Für p ∈ N sei Np := {1, . . . , p} die Menge der ersten p natürlichen Zahlen.
Eine Menge M heißt endlich, wenn es ein p ∈ N gibt, so dass M ∼ Np gilt. In diesem Fall
schreiben wir |M | = p.
Für p > q gibt es keine surjektive Abbildung von Nq auf Np und keine injektive Abbildung
von Np nach Nq . Daraus folgt, dass die Zahl p aus Definition 1.4.3 eindeutig bestimmt ist.
Diese Zahl p heißt Kardinalität von M , wird mit |M | bezeichnet und gibt also an, wie viele
Elemente die Menge M enthält.
Für endliche Mengen ist die Situation also einfach, denn jede endliche Menge ist gleich-
mächtig zu einer Art Referenz-Teilmenge von N, und M und Np enthalten dann tatsächlich
auch gleich viele Elemente, nämlich p. Schwieriger, aber auch interessanter, ist die Situation
bei Mengen mit unendlich vielen enthaltenen Elementen.
Definition 1.4.4. Eine Menge M heißt
Wir unterscheiden also endliche Mengen, abzählbar unendliche Mengen, d. h. Mengen, die
so groß sind wie N, und überabzählbare Mengen, d. h. Mengen, die (grob gesprochen) größer
als N sind.
Satz 1.4.5. Jede Teilmenge M ⊂ N ist abzählbar.
25
Beweis. (i) f (M ) ist eine Teilmenge von N und somit gemäß Satz 1.4.5 f (M ) abzählbar. Sei
nun f0 : M → f (M ), x 7→ f (x). Da f injektiv ist, ist f0 bijektiv. Daher ist M ∼ f (M )
und folglich abzählbar.
x = g(h(x)) = g(h(x0 )) = x0
Beh.
(i) M1 × M2 .
∞
S
(ii) M := Mn .
n=1
abzählbar.
Damit sind abzählbare Vereinigungen von abzählbaren Mengen wieder abzählbar, insbe-
sondere sind endliche Vereinigungen von abzählbaren Mengen abzählbar.
Beweis. Es gilt −N ∼ N und Z = −N ∪ {0} ∪ N. Daher ist Z abzählbar nach Satz 1.4.7 (ii).
Definiere die surjektive Abbildung f : Z × N → Q, (p, q) 7→ pq . Da Z × N nach Satz 1.4.7
(i) abzählbar (und offentsichtlich unendlich) ist, ist Z × N ∼ N. Daher existiert eine bijektive
Abbildung g : N → Z × N.
1.3.12(iv) 1.4.6(ii)
=⇒ f ◦ g : N → Q surjektiv =⇒ Q abzählbar
26
1 2 3 4
1 1 1 1
1 2 3 4
2 2 2 2
1 2 3 4
3 3 3 3
1 2 3 4
4 4 4 4
1.5 Aussagenlogik
In diesem Abschnitt werden wir die Grundlagen der aristotelischen Aussagenlogik einführen.
Eine Aussage in dieser Logik ist ein sprachliches Gebilde, dass entweder wahr oder falsch
ist (das sogenannte Zweiwertigkeitsprinzip). Es folgt, dass wir das Prinzip des ausgeschlos-
senen Dritten anwenden können und Widerspruchsbeweise gültig sind (im Gegensatz zum
mathematischen Konstruktivismus bzw. Intuitionismus).
Neben Mengen bilden das Argumentieren mit und das Beweisen von Aussagen das zweite
Fundament der Mathematik.
Wir haben Beweise bisher mit den Mitteln der Umgangssprache geführt. Jedoch werden,
wie wir anhand unserer Beweisstrategien sehen, dass bei Beweisen oft gewisse Konstruktionen,
Redewendungen und Formulierungen immer wieder verwendet. Wir versuchen dies nun zu
formalisieren, welches das Fundament der Logik bildet.
Wir sehen uns erstmal Beispiele von Aussagen an, die uns schon begegnet sind. Eine wichtige
Eigenschaft ist, dass ein sprachliches Gebilde eine Aussage ist, ganz gleich ob sie wahr oder
falsch ist.
Beispiele 1.5.1.
√
(i) 2 ist eine rationale Zahl.
27
(i) P gilt nicht, bzw. P ist falsch. (Negation von P )
Beispiel: Sei P die Aussage „5 ist kleiner als 2“. Dann ist „5 ist nicht kleiner als 2“
auch eine Aussage.
(iv) Aus P folgt Q, bzw. wenn P gilt, dann gilt auch Q, bzw. P impliziert Q. (Implikation
von Q aus P )
Beispiel: Sei P die Aussage „x ist eine reelle Zahl“ und Q die Aussage „x ist eine ganze
Zahl“. Dann ist „Wenn x eine reelle Zahl ist, dann ist x auch eine ganze Zahl“ auch eine
Aussage.
(v) P und Q sind äquivalent, bzw. P gilt genau dann wenn Q gilt. (Äquivalenz von P und
Q)
Beispiel: Sei P die Aussage „x ist eine gerade Zahl die prim ist“ und Q die Aussage
„x = 2“. Dann ist „x ist eine gerade Zahl die prim ist genau dann wenn x = 2 ist“ auch
eine Aussage.
Die obigen umgangssprachlich formulierten Aussagen werden formal in der Logik wie folgen-
dermaßen formuliert:
(i) ¬P
(ii) (P ∨ Q)
(iii) (P ∧ Q)
(iv) (P → Q)
(v) (P ↔ Q)
Wir wollen nun aussagenlogische Formeln formal definieren. Die Grundbausteine hierfür
sind Aussagenvariablen oder atomare Aussagen. Es gibt unendlich viele Aussagenvariablen
und wir bezeichen diese oft mit A, B, C, . . . wenn wir nur mit endlich vielen arbeiten oder
mit A1 , A2 , . . . wenn beliebig viele benötigt werden. Aussagenlogische Formel sind zunächsten
Zeichenketten:
Definition 1.5.3. Sei X eine nichtleere Menge von Aussagenvariablen. Eine Folge x1 x2 . . . xn
mit xi ∈ X ∪ {¬, ∨, ∧, →, ↔, (, )} heißt Zeichenkette.
28
(ii) Wenn P und Q Zeichenketten sind, dann sind auch
Zeichenketten
Definition 1.5.5. Sei X eine nichtleere Menge von Aussagenvariablen. Die Klasse aller aus-
sagenlogischen Formeln ist die kleinste Kollektion F aller Zeichenketten die X enthält und
wenn P und Q in F liegen, so auch
Sei X wieder eine nicht leere Menge von Aussagenvariablen. Wir erinnern uns: Aussagen
sind nach Aristoteles sprachliche Gebilde die entweder wahr oder falsch sind. Um dies zu
formalisieren sei eine beliebige Abbildung mit Definionsbereich X und Zielbereich {0, 1} ge-
geben. Hierbei kann 0 als falsch und 1 als wahr interpretiert werden. Diese Abbildung kann
im Anschluss nach einem Schema induktiv auf die Menge aller Aussagenlogischen Formeln
fortgesetzt werden. Nun folgt die formale Definition.
Definition 1.5.7. Sei X eine nicht leere Menge von Aussagenvariablen. Eine Belegung β
ist eine Abbildung
β : X → {0, 1}.
Diese lässt sich eindeutig mit Hilfe der folgenden Wahrheitstafel auf die Menge aller aussa-
genlogischen Formeln P und Q fortsetzen:
β(P ) β(Q) β(¬P ) β((P ∨ Q)) β((P ∧ Q)) β((P → Q)) β((P ↔ Q))
1 1 0 1 1 1 1
1 0 0 1 0 0 0
0 1 1 1 0 1 0
0 0 1 0 0 1 1
Die Belegung ist also so gewählt, dass ∨ das „einschließende oder“ nicht etwa „entweder
. . . oder“ bedeutet. Des Weiteren kann man aus etwas falschem immer alles schließen.
Bemerkung 1.5.8. Wenn zwei Belegungen β1 und β2 auf der endlichen Menge der Aussa-
genvariablen, welche in der aussagenlogischen Formel P vorkommen, übereinstimmen, so gilt
β1 (P ) = β2 (P ).
29
1.5.1 Logische Äquivalenz und Tautologien
Definition 1.5.9. Eine aussagenlogische Formel P ist eine Tautologie, falls β(P ) = 1 für alle
Belegungen β. Zwei aussagenlogische Formeln P und Q sind logisch äquivalent, bezeichnet
als P ∼ Q, falls (P ↔ Q) eine Tautologie ist.
Beispiel 1.5.10. Für jede Aussagenvariablen A ist A ∨ ¬A eine Tautologie.
Bemerkung 1.5.11. Die aussagenlogischen Formeln P und Q sind genau dann logisch äqui-
valent, wenn β(P ) = β(Q) für alle Belegungen β.
Aufgepasst! Dass P und Q logisch äquivalent sind bedeutet nicht, dass P und Q
1 1
als Ausdrücke gleich sind!!
• Für ∧, →, ↔ können wir logisch äquivalente Formeln finden, die nur ¬, ∨ benutzen:
– (P ∧ Q) ∼ ¬(¬P ∨ ¬Q)
– (P → Q) ∼ (¬P ∨ Q)
– (P ↔ Q) ∼ (P → Q) ∧ (Q → P )
• Negationsregeln
– ¬¬P ∼ P .
– (P ∨ ¬P ) ∼ > (Prinzip des ausgeschlossenen Dritten).
– (P ∧ ¬P ) ∼ ⊥ (Prinzip des ausgeschlossenen Widerspruchs).
• Distributivgesetze:
– (P ∨ Q) ∧ R ∼ (P ∧ R) ∨ (Q ∧ R) .
– (P ∧ Q) ∨ R ∼ (P ∨ R) ∧ (Q ∨ R) .
• Kontraposition:
– (P → Q) ∼ (¬Q → ¬P ).
30
– P ∧ (P → Q) → Q ∼ >.
– (P ∧ Q) ∼ (Q ∧ P ).
– (P ∨ Q) ∼ (Q ∨ P ).
– ((P ∧ Q) ∧ R) ∼ (P ∧ (Q ∧ R)).
– ((P ∨ Q) ∨ R) ∼ (P ∨ (Q ∨ R)).
Tableaumethode
Idee: Wir nehmen an, dass die aussagenlogische Formel P keine Tautologie ist, d. h. den
Wahrheitswert 0 hat. Wir versuchen dann Schritt für Schritt herauszufinden, welche
Implikationen dies für die Belegungen der Aussagenvariablen hat. Dies führt zu einem
Schema, dass einem Baum mit Verzweigungen ähnelt. Am Ende schließen dann ent-
weder alle Pfade (d. h. es gibt keine Belegung für die der Wahrheitswert 0 ist und die
aussagenlogische Formel ist eine Tautologie), oder wir finden eine Belegung für die die
Aussage den Wahrheitswert 0 annimmt.
Bemerkung 1.5.15. Hier ist die Liste der Regeln, wie man Stück für Stück eine gegebe-
ne aussagenlogische Formeln auflösen kann. Die Regeln kann man sich auch direkt aus der
Wahrheitstafel herleiten. P und Q seien aussagenlogische Formeln.
¬P :
¬P 7→ 0 ¬P 7→ 1
P 7→ 1 P 7→ 0
P ∨ Q:
P ∨ Q 7→ 0 P ∨ Q 7→ 1
P 7→ 0, Q 7→ 0 P 7→ 1 Q 7→ 1
P ∧ Q:
31
P ∧ Q 7→ 1 P ∧ Q 7→ 0
P 7→ 1, Q 7→ 1 P 7→ 0 Q 7→ 0
P → Q:
P → Q 7→ 0 P → Q 7→ 1
P 7→ 1, Q 7→ 0 P 7→ 0 Q 7→ 1
P ↔ Q:
P ↔ Q 7→ 0 P ↔ Q 7→ 1
P 7→ 0, Q 7→ 1 P 7→ 1, Q 7→ 0 P 7→ 0, Q 7→ 0 P 7→ 1, Q 7→ 1
Am besten versteht man die Methode an einem Beispiel (siehe Vorlesung für zusätzliche
Erklärung).
Beispiel 1.5.16.
((P → (Q → R)) 7→ 1, (P ∧ Q) 7→ 1
R 7→ 0
((P → (Q → R)) 7→ 1
P 7→ 1, Q 7→ 1
P 7→ 0 (Q → R) 7→ 1
schließt Q 7→ 0 R 7→ 1
schließt schließt
Da alle Pfade schließen, ist ((P → (Q → R)) → ((P ∧ Q) → R)) eine Tautologie.
32
((P → (Q → R)) → ((P ∨ Q) → R)) 7→ 0
((P → (Q → R)) 7→ 1, (P ∨ Q) 7→ 1
R 7→ 0
(Q → R) 7→ 1 P 7→ 0 P 7→ 0 (Q → R) 7→ 1
P 7→ 0
R 7→ 1 Q 7→ 0 schließt Q 7→ 1 Q 7→ 0 R 7→ 1
R 7→ 0
P 7→ 1
schließt Q 7→ 0 schließt schließt
R 7→ 0
1.5.2 Normalformen
n
• (P1 ∧ P2 ∧ . . . ∧ Pn ) oder ( Pi ) für die Formel ((. . . (P1 ∧ P2 ) ∧ . . .) ∧ Pn ).
V
i=1
n
• (P1 ∨ P2 ∨ . . . ∨ Pn ) oder ( Pi ) für die Formel ((. . . (P1 ∨ P2 ) ∨ . . .) ∨ Pn ).
W
i=1
Definition 1.5.17. Eine aussagenlogische Formel ist ein Literal, falls sie eine Aussagenva-
riable oder die Negation davon ist.
Beispiele 1.5.18. Seien A und B Aussagenvariablen. Dann sind A, ¬A, B und ¬B Literale
aber A ∨ B, A ∧ B, A → B und A ↔ B sind keine Literale.
33
!
n
• disjunktiver Normalform (DNF), falls sie eine endliche Disjunktion von
W
Pi
i=1
endlichen Konjunktionen
Pi = (Li1 ∧ . . . ∧ Lini )
von Literalen Lij ist.
Beispiele 1.5.20. Sei X = {Ai : i ∈ N} eine Menge von Aussagenvariablen. Dann ist
(A1 ∨ A2 ) ∨ A3 ∧ (A4 ∨ A5 ) ∧ A6
in KNF,
A1 ∨ (A2 ∧ A3 ) ∨ (A4 ∨ (A5 ∧ A6 ))
in DNF und
(A1 ∨ A2 ) ∧ A3 ∨ A4
Bemerkung 1.5.21. Jede aussagenlogische Formel ist logisch äquivalent zu einer aussagen-
logischen Formel in KNF und auch logisch äquivalent zu einer aussagenlogischen Formel in
DNF.
Zusatzinfo. Wenn wir noch verlangen, dass jedes Literal Lij in jeder endlichen Konjunktion
genau einmal vorkommt, bekommen wir eine kanonische DNF, welche bis auf Permutation der
Pi und innerhalb der Pi bis auf Permutation der Literale eindeutig ist, denn (Lij ∧ ¬Lij ) ∼ ⊥.
34
Kapitel 2
Reelle Zahlen
2.1 Quantoren
Bevor wir uns näher mit den reellen Zahlen beschäftigen, führen wir mit den sog. „Quantoren“
eine nützliche Notation ein. Bisher wurden bereits immer wieder Formulierungen wie „zu jedem
x gibt es ein y mit“ verwendet. Da diese in der Mathematik wiederholt auftauchen, benutzt
man dafür häufig abkürzende Schreibweisen.
Beispiel 2.1.1. In Definition 1.3.8 haben wir die Surjektivität einer Abbildung f : X → Y
kennen gelernt:
f heißt surjektiv, falls es zu jedem y ∈ Y ein x ∈ X gibt so dass f (x) = y gilt. (2.1)
Notation: (Quantoren) Sei x ein Objekt, für das eine Aussage P (x) formuliert wird. Dann
wird für „für alle x gilt P (x)“ die abkürzende Notation
∀x : P (x)
verwendet, d. h. der Quantor („Allquantor“) ∀ bedeutet „für alle“. Weiter führt man für „es
existiert ein x, so dass P (x) gilt“ die Schreibweise
∃x : P (x)
ein, d. h. der Quantor („Existenzquantor“) ∃ bedeutet „es existiert ein“.
Aufgepasst! „Es existiert ein(e)“ bedeutet, dass mindestens ein Objekt existiert.
1 1
Es können auch mehrere existieren.
Bemerkung 2.1.2. In Beispiel 2.1.1 lautet die Formulierung von (2.1) mit Hilfe von Quan-
toren
∀y ∈ Y ∃x ∈ X : f (x) = y. (2.2)
35
Beispiel 2.1.3. Wir werden sehen, dass es zu jeder reellen Zahl x ≥ 0 eine reelle Zahl y ∈ R
√
gibt, so dass y 2 = x gilt. Wir bezeichnen dann y = x. Diese Aussage lautet mit Quantoren
formuliert
∀x ≥ 0 ∃y ∈ R : y 2 = x.
Vertauscht man hier die Reihenfolge
∃y ∈ R ∀x ≥ 0 : y 2 = x,
Bemerkung 2.1.4. Es gilt folgende Faustregel für die Negation von Aussagen: Man erhält
die Negation einer Aussage, indem man die Quantoren ∀ und ∃ vertauscht und den Rest
verneint.
∀x ∈ R ∃y ∈ R : y 2 = x ist ∃x ∈ R ∀y ∈ R : y 2 6= x
Unter einem Axiom verstehen wir eine mathematische Aussage, deren Gültigkeit ohne Be-
weis angenommen wird. Die Konstruktion der reellen Zahlen beruht auf einigen Axiomen,
aus denen wir die zentralen Eigenschaften der reellen Zahlen und der damit verbundenen
Begrifflichkeiten herleiten.
Bemerkung 2.2.1. Wir nehmen nun eine gewisse Vertrautheit mit der Menge R der reellen
Zahlen an und beschreiben Addition und Multiplikation von reellen Zahlen durch die folgenden
Körperaxiome:
K+: Je zwei Elementen a, b ∈ R ist eindeutig ein Element a + b ∈ R zugeordnet, die Summe
von a und b.
36
K4: ∀a, b ∈ R : a + b = b + a (Kommutativgesetz)
K·: Je zwei Elementen a, b ∈ R ist eindeutig ein Element a · b ∈ R zugeordnet, das Produkt
von a und b, Notation: a · b =: ab
Proposition 2.2.3.
(i) Die Axiome (K2), (K3), (K6), (K7) und (K9) gelten auch „von links“ (mit den gleichen
Elementen). Man kann die Axiome (K2) , (K3), (K6), (K7) und (K9) dann auch wie
folgt formulieren:
K2’ ∃b ∈ R ∀a ∈ R : a + b = b + a = a
K3’ ∀a ∈ R ∃x ∈ R : a + x = x + a = 0
K6’ ∃b ∈ R ∀a ∈ R : a · b = b · a = a
K7’ ∀a ∈ R ∃x ∈ R : a · x = x · a = 1
K9’ ∀a, b, c ∈ R : ((a + b)c = ac + bc) ∧ (c(a + b) = ca + cb)
(ii) Die neutralen Elemente der Addition (K2) und der Multiplikation (K6) sind eindeutig
bestimmt.
(iii) Die inversen Elemente der Addition (K3) und der Multiplikation (K7) sind eindeutig
bestimmt.
Notation: Für a ∈ R bezeichnen wir mit −a das additive Inverse, d. h. das Element
aus R so dass a + (−a) = 0, und, falls a 6= 0, mit a−1 oder a1 das multiplikative Inverse,
d. h. das Element aus R so dass a · a−1 = 1.
Beweis.
(ii) Sei 00 ∈ R ein Element, das (K2’) erfüllt und 10 ∈ R ein Element, dass (K6’) erfüllt.
Dann ist
K2 K20
00 = 00 + 0 = 0
K6 K60
10 = 10 · 1 = 1
37
(iii) Seien a, b, c, d, e ∈ R, so dass b und c (K3’) für a erfüllen, d. h.
a+b=b+a=a+c=c+a=0
ad = da = ae = ea = 1.
Dann ist
K2 (K30 ) für c K1 (K30 ) für b K20
b = b+0 = b + (a + c) = (b + a) + c = 0+c = c
Bemerkung 2.2.4. Die Eindeutigkeit der Inversen kann wie folgt genutzt werden. Für a, b ∈
R gilt
a+b=0 =⇒ b = −a (2.3)
−1
a·b=1 =⇒ b=a (2.4)
(i) b + a = c + a ⇐⇒ b = c,
(iii) 0 · a = 0,
(v) −(−a) = a,
b=c
Beweis. (i) „ ⇐= “: b + a = c + a.
„ =⇒ “:
K2 K3 K1 b+a=c+a
b = b + 0 = b + (a + (−a)) = (b + a) + (−a) = (c + a) + (−a)
K1 K3 K2
= c + (a + (−a)) = c + 0 = c
(ii) Übungsaufgabe.
K2 K2 K9 (i)
(iii) 0 + 0 · a = 0 · a = (0 + 0) · a = 0 · a + 0 · a =⇒ 0=0·a
38
K9 K3 (iii) (2.3)
(iv) ab + (−a)b = (a + (−a)) · b = 0 · b = 0 =⇒ (−a) · b = −(ab)
Analog kann man zeigen, dass a · (−b) = −(ab) (Übungsaufgabe).
K3 K4 (2.3)
(v) 0 = a + (−a) = (−a) + a =⇒ a = −(−a)
(vi) Übungsaufgabe.
In Beispiel 1.2.15 haben wir „≤“ als Ordnungsrelation bereits kennen gelernt. Wir verzichten
im Folgenden auf die axiomatische Einführung von „<“ (und „≤“), d. h. von a < b („a kleiner
b“) für reelle Zahlen a, b und setzen auch hier eine gewisse Vertrautheit aus. Darauf aufbauend
definiert man
(i) a ≤ b genau dann wenn a < b oder a = b („a kleiner (oder) gleich b“).
Aufgepasst! Bei der Multiplikation mit negativen Zahlen und bei der Kehrwertbil-
1 1
dung drehen sich die Ungleichheitszeichen um.
39
(i) a heißt Maximum von M (max M ), falls x ≤ a für alle x ∈ M .
Bemerkung 2.3.4. (i) Maxima und Minima sind eindeutig bestimmt, denn:
(ii) Definitionsgemäß ist das Maximum das größte und das Minimum das kleinste Element
einer Menge.
Aufgepasst! Nicht jede Menge hat ein Maximum (oder ein Minimum), wie das
1 1
zweite der folgenden beiden Beispiele erläutert.
Beispiel 2.3.5.
0+1 1+1
=⇒ 0< <x< =1
2 2
=⇒ x∈I
Definition 2.4.1. Sei a ∈ R. Dann definieren wir den Absolutbetrag |a| von a durch
(
a falls a ≥ 0
|a| :=
−a falls a < 0.
Interpretation: |a| misst den Abstand von a zur 0 (auf der Zahlengerade).
(i) |a| ≥ 0,
40
(iii) −|a| ≤ a ≤ |a|,
Auch die folgenden elementaren Eigenschaften des Betrags sind leicht zu beweisen.
Beweis. Es gilt
Aus (i) und (ii) folgt mit Bemerkung 2.4.2(iv): |a| − |b| ≤ |a − b|.
Bemerkung 2.4.5. |b − a| gibt den Abstand zwischen a und b auf der Zahlengerade an.
q k := q · q · . . . · q von q
| {z }
k Faktoren
k
(ii) Weiter: q 0 := 1 und q −k := 1
qk
= 1
q für q 6= 0, k ∈ N
Proposition 2.5.2. Seien k, l ∈ Z und q, r ∈ R sowie q, r 6= 0, falls k < 0 oder l < 0. Dann
gelten die Potenzgesetze
Beweis. Auf die (leichten) Beweise verzichten wir hier. Ein Beweis für allgemeine Potenzen
folgt in Abschnitt ??.
41
Satz 2.5.3 (geometrische Summenformel). Für q ∈ R und n ∈ N gilt
1 − q n+1
q 0 +q 1 + q 2 + . . . + q n = (2.6)
|{z} 1−q
=1
Beweis. Betrachte
(1 − q)(q 0 + q 1 + . . . + q n ) = 1 + q + q 2 + . . . + q n − q − q 2 − . . . − q n+1
Teleskop-
= 1 − q n+1
summe
1 − q n+1
=⇒ q0 + q1 + q2 + . . . + qn =
1−q
n
(iii) ak := 0 für m > n (leere Summe)
P
k=m
n
(iv) ak := 1 für m > n (leeres Produkt)
Q
k=m
42
Bemerkung 2.5.5. Man wendet häufig Indextransformationen/Indexshifts an, um Summen
umzuformen. Hier einige Beispiele dazu:
4 3 3 n n+1
X j=k−1 X X X X
ak = aj+1 = ak+1 = a1 + a2 + a3 + a4 , ak = ak−1
k=1 j=0 k=0 k=0 k=1
Bemerkung 2.5.6. Die geometrische Summenformel in Satz 2.5.3 formulieren wir mit Sum-
menzeichen als
n
X 1 − q n+1
qk = .
1−q
k=0
Notation: N0 := N ∪ {0}
Wir diskutieren in diesem Abschnitt das Prinzip der vollständigen Induktion, ein
Beweisprinzip/Beweisverfahren, mit dem man Aussagen A(n) beweisen kann, die von n ∈ N0
abhängen.
Beispiel 2.6.1 (Gauß). Als Beispiel einer solchen Aussage A(n) betrachten wir die Aufgabe,
die Summe der ersten n natürlichen Zahlen zu bestimmen, d. h.
n
X
k = 1 + 2 + 3 + . . . + n =?
k=1
1 + 100 = 101
2 + 99 = 101
3 + 98 = 101
4 + 97 = 101
.. .. ..
. . .
49 + 52 = 101
50 + 51 = 101
erhält man 50 = n
2 Paare mit jeweiliger Summe 101 = n + 1, und als Ergebnis ergibt sich
100
X
k = 50 · 101 = 5050.
k=1
43
Für ungerade n argumentiert leicht modifizert (Bsp.: n = 101):
1 + 101 = 102
2 + 100 = 102
3 + 99 = 102
4 + 98 = 102
.. .. ..
. . .
49 + 53 = 102
50 + 52 = 102,
101
X
k = 51 + 50 · 102 = 51 + 5100 = 5151.
k=1
und man bekommt wieder das Ergebnis (2.7). Wir haben also die starke Vermutung, dass (2.7)
für n ∈ N gilt. Eine solche Aussage lässt sich häufig mit dem Beweisprinzip der vollständigen
Induktion beweisen.
Bemerkung 2.6.2 (Idee der vollständigen Induktion). Wir erläutern nun die grundsätzliche
Idee, die dem besagten Beweisprinzip zugrunde liegt. Zu zeigen sei die Aussage A(n) für
alle n ∈ N0 mit n ≥ n0 für ein n0 ∈ N. Angenommen, man kann zeigen, dass A(n0 ) gilt,
und weiter kann man beweisen, dass A(n + 1) gilt, wenn man voraussetzt, dass A(n) gilt,
d. h. die Implikation A(n) =⇒ A(n + 1) ist für alle n ∈ N, n ≥ n0 gültig. Dann gilt A(n) für
alle n ∈ N mit n ≥ n0 . Diese Schlussweise ist wenigstens plausibel, denn so erhält man die
Implikationskette
Satz 2.6.3 (Induktionsprinzip). Sei n0 ∈ Z. Sei A(n) für n ∈ Z, n ≥ n0 , eine Aussage, und
es gelte:
Beweis. Wir geben uns mit der Plausibilität zufrieden und verzichten auf einen Beweis.
44
Beweis durch vollständige Induktion: Aus Satz 2.6.3 ergibt sich die folgende
Beweisstruktur, die grundsätzlich beachtet werden muss.
1.) Induktionsanfang (IA): Es gibt ein n0 ∈ N0 so, dass A(n0 ) wahr ist.
1 1
2.) Induktionsvoraussetzung (IV): Annahme: A(n) ist wahr (für ein n ≥ n0 ).
Beh.
Bemerkung 2.6.5. Wir wollen den Sinn eines Induktionsbeweis durch ein einigermaßen
überraschendes Beispiel unterstreichen. Dazu betrachten wir den Ausdruck n2 +n+41 (n ∈ N0 )
und notieren die Ergebnisse für n = 0, . . . , 35:
n 0 1 2 3 4 5 6 7 29 ... 31 ... 35
n2 + n + 41 41 43 47 53 61 71 83 97 911 ... 1033 ... 1301
Das Ergebnis ist stets eine Primzahl. Das legt die Vermutung nahe, dass der Ausdruck für
alle n ∈ N0 eine Primzahl ergibt. Daher formulieren wir die Aussage:
Vermutung: [Was nicht stimmt] Für n ∈ N0 ist n2 + n + 41 eine Primzahl.
Tatsächlich ist n2 + n + 41 nur für n = 0, . . . , 39 eine Primzahl. Für n = 40 ist
45
keine Primzahl. Für n = 41 ist die Teilbarkeit durch 41 trivial. Es reicht nicht endlich viele
Beispiele zu untersuchen, um eine Aussage A(n) für alle n ∈ N0 zu beweisen und einen
Induktionsbeweis zu ersetzen.
Bemerkung 2.6.6. Der Beweis des Induktionsanfangs ist in vielen Fällen mehr oder weni-
ger trivial. Möglicherweise fällt es daher schwer, überhaupt eine Begründung zu formulieren,
weil die Behauptung so klar scheint. Der Hauptteil der Beweisarbeit liegt in der Regel im In-
duktionsschritt. Die Induktionsvoraussetzung wird einfach nur formuliert, hier gehen keinerlei
mathematische Argumente ein.
Aufgepasst! Auch wenn der Induktionsanfang häufig trivial ist, darf er nie weg
1 gelassen werden. Sonst kann man problemlos falsche Aussagen „beweisen“, wie das1
folgende Beispiel zeigt.
Beispiel 2.6.7.
IV:
n
X
k 2k = (n − 1) 2n+1 .
k=1
IS:
n+1 n
IV
X X
k
k2 = k 2k + (n + 1) 2n+1 = (n − 1) 2n+1 + (n + 1)2n+1 = (2n) 2n+1
k=1 k=1
n+2
= n2 = ((n + 1) − 1) 2(n+1)+1
Beweis. Den Beweis führt man durch eine einfache Induktion über n. (Übungsaufgabe)
Definition 2.6.9. Für n ∈ N definieren wir die Fakultät von n („n Fakultät“)
n
Y
n! := 1 · 2 · 3 · . . . · n = k
k=1
und weiter 0! := 1.
Kombinatorische Interpretation:
Satz 2.6.10. Für n ∈ N ist n! die Anzahl der möglichen Anordnungen (Permutationen)
einer n-elementigen Menge M .
46
Beweis. durch Induktion:
IS: Für eine Anordnung ai1 , ai2 , . . . , ain von {a1 , . . . , an } erhält man (n + 1) Anordnungen
einer (n + 1)-elementigen Menge:
Beispiel 2.6.11 (Interpretation von Satz 2.6.10). Frage: Wie viele Möglichkeiten gibt es, 10
Bücher auf einem Regal anzuordnen?
Antwort: Für das erste Buch gibt es 10 Möglichkeiten. Für jede dieser Positionen des 1.
Buches gibt es 9 freie Positionen für das 2. Buch, insgesamt also 10 · 9 = 90 Möglichkeiten,
die beiden Bücher zu positionieren, usw. Insgesamt erhält man für alle 10 Bücher
Folgende Eigenschaften folgen direkt aus der Definition, und es ist nützlich diese stets im
Hinterkopf zu haben.
47
Kombinatorische Interpretation:
Satz 2.6.14. Seien n ∈ N0 und k ∈ {0, . . . , n}. Die Anzahl Ckn der k-elementigen Teilmengen
n
einer n-elementigen Menge {A1 , . . . , An } ist gleich k .
Beweis. Den Beweis kann man durch Induktion über n führen und dabei den folgenden Hilfs-
satz verwenden. Hier verzichten wir aber darauf.
Bemerkung 2.6.16.
n=0 1
n=1 1 1
n=2 1 2 1
n=3 1 3 3 1
n=4 1 4 6 4 1
n=5 1 5 10 10 5 1
n=6 1 6 15 20 15 6 1
(ii) In Anwendungsbeispielen ist nk die Antwort auf die Frage, wie viele Möglichkeiten es
n · (n − 1) · (n − 2) · . . . · (n − k + 1) n · (n − 1) · (n − 2) · . . . · (n − k + 1) (n − k)!
= ·
k! k! (n − k)!
n! n
= = .
(n − k)! · k! k
Zurück zum Bücherregal, diesmal mit 50 Büchern: Wie viele Möglichkeiten hat man 5
Bücher auszuwählen, wobei es nicht auf die Reihenfolge ankommt?
Antwort: 50
5 .
48
(iii) Satz 2.6.14 liefert für Lotto 6 aus 49:
−1
49 49
= 13983816 Möglichkeiten und eine Wahrscheinlichkeit für 6 Richtige von
6 6
Satz 2.6.17 (Binomischer Lehrsatz). Für n ∈ N, x, y ∈ R gilt
n
X n k n−k
n
(x + y) = x y . (2.9)
k
k=0
IA (n = 1):
1
X 1 k 1−k 1 0 1 1 1 0
x y = x y + x y = y + x = (x + y)1 3
k 0 1
k=0
IS: Es folgt
n n n
n+1
X n k n−k X n k+1 n−k X n k n+1−k
(x + y) = (x + y) x y = x y + x y
k k k
k=0 k=0 k=0
n+1
X n n
X n k n+1−k
= xk y n−(k−1) + x y
k−1 k
k=1 k=0
n+1
X n n+1
X n
= xk y n+1−k + xk y n+1−k
k−1 k
k=0 k=0
n+1
L.2.6.15
X n + 1 k n+1−k
= x y .
k
k=0
(ii) n = 3:
3
X 3 3 0 3 3 1 2 3 2 1 3 3 0
(x + y)3 = xk y 3−k = x y + x y + x y + x y
k 0 1 2 3
k=0
= x + 3x2 y + 3xy 2 + y 3 .
3
49
2.7 Reelle Funktionen
Sei M eine Menge. Eine Abbildung f : M → R heißt Funktion. Häufig betrachten wir
Funktionen mit Definitionsbereich M ⊂ R.
2.7.1 Funktionsgraphen
Definitionsbereiche von reellen Funktionen sind oft Intervalle, daher die folgende Definition.
mit [a, b] = [a, a] = {a} für a = b und (a, b) = [a, b) = (a, b] = ∅ für a = b.
[a, ∞) := {x ∈ R : a ≤ x} „abgeschlossen“
(−∞, a] := {x ∈ R : x ≤ a} „abgeschlossen“
(a, ∞) := {x ∈ R : a < x} „offen“
(−∞, a) := {x ∈ R : x < a} „offen“
Wir untersuchen hier Funktionen mit Werten in den reellen Zahlen. Eine gute Möglichkeit
zur Veranschauung bietet der Graph einer Funktion.
Definition 2.7.2. Seien M eine Menge und f : M → R eine Funktion. Dann definieren wir
den Graph von f als
Γ(f ) := {(x, f (x)) : x ∈ M } ⊂ M × R.
Bemerkung 2.7.4. Man kann nicht für jede Funktion R → R den Graphen einfach zeichnen.
Betrachte dazu zum Beispiel die besonders „wilde“ Dirichlet-Funktion
(
1, falls x rational ist,
D(x) :=
0, falls x irrational ist.
50
2
Γ(h)
−2 2
Γ(f )
Γ(g)
−2
„punktweise“. Entsprechend
(iv) |f |(x) := |f (x)|, max{f, g}(x) := max{f (x), g(x)}, min{f, g}(x) := min{f (x), g(x)}
für x ∈ M,
(v) f ≤ g genau dann wenn f (x) ≤ g(x) für alle x ∈ M .
−C ≤ −|x| ≤ x ≤ |x| ≤ C
51
„ =⇒ “: Es gibt c, C ∈ R sodass c ≤ x ≤ C. Dann ist |x| ≤ max{C, −c}
Bemerkung 2.7.9.
Beispiele 2.7.10.
Daraus folgt 0 ≤ x ≤ 1
1−q für alle x ∈ M .
Beh.
(i) f heißt nach oben beschränkt genau dann wenn f (M ) nach oben beschränkt.
(ii) f heißt nach unten beschränkt genau dann wenn f (M ) nach unten beschränkt.
(iii) f besitzt ein Maximum auf M genau dann wenn f (M ) besitzt ein Maximum.
(iv) f besitzt ein Minimum auf M genau dann wenn f (M ) besitzt ein Minimum.
(vi) Ein Punkt x0 ∈ M heißt Extremalstelle von f , wenn x0 eine Maximal- oder Minimal-
stelle ist.
Beispiele 2.7.12.
52
Da f (x) > 0 für alle x ∈ (0, ∞) ist f nach unten durch 0 beschränkt,
Beh.
Dabei
1 1 2 1
x − x2 = ⇐⇒ x− =0 ⇐⇒ x= ,
4 2 2
d. h. x = 1
ist einzige Maximalstelle, f 2 = 4 ist das Maximum von f auf R.
1
1
2
Beh.
Eine interessante Eigenschaft, die Funktionen haben können, ist die Monotonie.
Bemerkung 2.7.14. Sei f streng monoton wachsend. Dann bedeutet das anschaulich für
den Graphen von f , dass es immer „bergauf“ geht, wenn man den Graphen von links nach
rechts durchläuft.
Beispiele 2.7.15.
53
(i) f : R → R, f (x) := x ist streng monoton wachsend.
Sei
f (x) = y, (2.10)
Sei x ∈ X die eindeutige Lösung von (2.10) für f bijektiv und y ∈ Y . Dann definiert
f −1 (y) := x. (2.11)
Beweis.
54
In jedem Fall ist f (x) 6= f (x0 ). Bijektivität folgt unter Benutzung von Satz 1.3.12
(vi). (i)
f −1 (y) ≥ f −1 (y 0 )
| {z } | {z }
=:x =:x0
Dann ist x ≥ x0 und f (x) = y < y 0 = f (x0 ). zu f streng monoton wachsend. (ii)
Bemerkung 2.7.19. Für streng monoton fallende Funktionen gelten zu 2.7.18 analoge Aus-
Γ(f )
sagen.
Aufgepasst! Die Umkehrung von Satz 2.7.18 (i) ist im Allgemeinen falsch, d. h. aus
1 1
der Injektivität folgt nicht die Monotonie von f , wie das folgende Beispiel zeigt.
2
Betrachte nun konkret z. B. a = 2, b = 1. Γ(f ) Γ(Id)
Dann ist
−2 2
f (x) = 2x + 1 Γ(f −1 )
x−1
f −1 (x) = −2
2
Man erhält den Graphen Γ(f −1 ) der Umkehrfunktion aus dem Graphen Γ(f ) durch Spiegelung
an der Winkelhalbierenden, d. h. am Graphen der identischen Funktion IdR .
55
2.7.4 Trigonometrische Funktionen
Wir führen nun trigonometrische Funktionen auf elementar geometrischem Weg ein. Formal
etwas präziser wäre eine Definition durch Reihen oder über Umkehrfunktionen und Integrale,
worauf wir hier verzichten. Diese Charakterisierungen werden wir aber nichtsdestotrotz später
an den entsprechenden Stellen kennenlernen.
Bemerkung 2.7.22.
Betrachte einen Winkel α mit Schenkeln der Län-
ge 1 und Spitze im Ursprung 0 = (0, 0) ∈ R2 . Da- .....
..... .....
bei nehmen wir an, dass α ein orientierter Win- .
...
..... ........
.....
..... ...
...
. ...
.....
kel ist, d. h. α > 0 bedeutet, dass die Strecke ...
.
.
.....
..... ...
...
...
...
. ...
zwischen (0, 0) und (1, 0) gegen den Uhrzeiger-
...
..
.. .
...
.
.1
...
. ...
...
... x = x(α)
..
..... ...
sinn (im „positiven Sinn“) gedreht wird, α < 0 . .
.. ....
..
.
.
...
.
....
. ...
...
...
...
...
entspricht der Drehung im Uhrzeigersinn. Dann ..
.. ...
.........
. ...
..
.... ....
. ...
..... ... ...
.
gilt für die Länge x = x(α) des Kreisbogens die
. .
..
.
....
.
..
....
α ...
...
................................................................................................................................................
.
...
..
Verhältnisgleichung 0
1
x α α · 2π
= ⇐⇒ x = x(α) = ,
2π 360◦ 360◦
wobei 2π der Umfang eines Kreises mit Radius 1
ist und x das gleiche Vorzeichen wie α hat.
Definition 2.7.23 (Bogenmaß). Unter den Voraussetzungen von Bem. 2.7.22 heißt x Bo-
genmaß des Winkels α.
Definition 2.7.24 (Sinus und Cosinus).
Betrachte nun den Vektor (u(x), v(x)) auf dem v ..............
...
Einheitskreis um 0, der mit der positiven x- ...
...............
... ................
..........
Achse den Winkel x = x(α) bildet. Dann de- ...
...
...
........
.......
......
......
... .....
finieren wir die Cosinus-Funktion •(u(x), v(x))
...
....... .... .... .... .... .... .... .... .... .................
sin x ...
...
......... ...
...... . ....
... ........ ... .....
.
..... ...
... .... .. ...
... ..... ...
cos x := u(x) für x ∈ R
...
... ..... ...
... ...
...... .
.
.
...
...
...
...
... ...
. ..
.. .
.....
. .
.
.
.
.
x = x(α)
...
...
... ..
. . ...
... .
....... .
. ...
und die Sinus-Funktion
.
.. . . ...
... ......... ..... .. ...
α ... ...... ... . .
.............................................................................................................................................
0 cos x 1 u
sin x := v(x) für x ∈ R.
Sinus und Cosinus gehören zur Familie der trigonometrischen Funktionen.
Aus Def. 2.7.24 folgen wesentliche Eigenschaften von Sinus und Cosinus:
Proposition 2.7.25. (i) Cosinus- und Sinusfunktion sind 2π-periodisch, d. h. für alle
x ∈ R und k ∈ Z gilt
56
(iv) cos2 x + sin2 x = 1.
(vi) Es gilt:
n o n o
(a) cos x = 0 ⇐⇒ x ∈ ± π2 , ± 3π
2 , ± 5π
2 , . . . = (k + 1
2 ) π, k ∈ Z ,
(b) sin x = 0 ⇐⇒ x ∈ {0, ±π, ±2π, ±3π, . . .} = {k π, k ∈ Z}.
Spezielle Werte von Sinus und Cosinus als Merkregel (man beachte die Regelmäßigkeit,
die zeilenweise auftritt) formuliert (ergeben sich aus Beziehungen in gleichseitigen oder
-schenkligen Dreiecken):
x 0 π
6 ˆ 30◦
= π
4 =ˆ 45◦ π
3 ˆ 60◦
= π
2 ˆ 90◦
=
1
√ 1
√ 1
√ 1
√ √
cos x 2 4=1 2 3 2 2 2 1 = 21 1
2 0=0
1
√ 1
√ √ √ √
sin x 2 0=0 2 1 = 12 1
2 2 1
2 3 1
2 4=1
Diese Eigenschaften spiegeln sich in den Graphen von Sinus und Cosinus wider.
Γ(sin)
−2π 2π
Γ(cos)
−1
Bemerkung 2.7.27. Als unmittelbare Konsequenz von Satz 2.7.26 notieren wir die Spezial-
fälle π π π
sin x + = sin x cos + cos x sin = cos x,
2 | {z 2 } | {z2 }
=0 =1
π π π
cos x − = cos x cos + sin x sin = sin x.
2 | {z 2 } | {z2 }
=0 =1
Anschaulich bedeutet das, dass man den Graphen der Cosinus-Funktion durch Verschiebung
um π2 nach links aus dem Graphen der Sinus-Funktion erhält. Entsprechend ergibt ein Rechts-
shift des Cosinusgraphen um π2 den Graphen der Sinus-Funktion.
57
Definition 2.7.28. Wir definieren die Tangens-Funktion
sin x n 1 o
tan x := für x ∈ D := R \ k + π : k∈Z .
cos x 2
Wir notieren einige nützliche Eigenschaften des Tangens, die leicht aus der Definition folgen.
Bemerkung 2.7.29.
sin(−x) − sin x
tan(−x) = = = − tan x.
cos(−x) cos x
Γ(tan)
x
− 3π −π − π2 0 π π 3π
2 2 2
Definition 2.7.30. Sei t eine Variable oder Unbestimmte. Ein Polynom mit Koeffizienten
in R oder ein Polynom über R ist ein formaler Ausdruck der Gestalt
m
X
P (t) := ak tk = am tm + am−1 tm−1 + . . . + a1 t + a0 (2.14)
k=0
mit a0 , . . . , am ∈ R. Meist schreiben wir statt P (t) einfach nur P . Wir bezeichnen die Menge
aller Polynome über R mit R[t]. Falls am 6= 0 (Leitkoeffizient) in (2.14) gilt, dann heißt m
der Grad von P .
58
Notation:
(ii) Für das Nullpolynom N , bei dem alle ai Null sind, ist deg N := −∞.
Bemerkung 2.7.31. Man kann Polynome auch addieren und multiplizieren. Wir betrachten
hierzu ein Beispiel: Sei P (t) = 3t4 − t2 und Q(t) = t2 + 2. Dann ist
(P · Q)(t) = (3 · 1)t6 + (3 · 2 + (−1) · 1)t4 + ((−1) · 2)t2 = 3t6 + 5t4 − 2t2 ∈ R[t]
(ii) Für S(t) := −3t4 + 5 ist (P + S)(t) = −t2 + 5 und somit deg(P + S) = 2.
Satz 2.7.32 (Euklidischer Algorithmus, Division mit Rest). Seien P, Q ∈ R[t], wobei Q nicht
das Nullpolynom sei. Dann existieren eindeutig bestimmte Polynome T, R ∈ R[t] mit
Statt eines Beweises diskutieren wir ein Beispiel, das das Vorgehen beim Euklidischen Al-
gorithmus verdeutlicht. Das Verfahren ähnelt der schriftlichen Division.
Beispiel 2.7.33. Betrachte P (t) := 4t4 + 3t3 − t − 1, Q(t) := 2t2 + 2.
4t4 + 3t3 − t − 1 = 2t2 + 2 2t2 + 32 t − 2 − 4t + 3
− 4t4 − 4t2
3t3 − 4t2 − t
− 3t3 − 3t
− 4t2 − 4t − 1
4t2 +4
− 4t + 3
3
=⇒ P (t) = 2t2 + t − 2 (2t2 + 2) + (−4t + 3)
2
59
Definition 2.7.34. Eine Polynomfunktion ist eine Funktion der Form R → R, x 7→ P (x)
für ein Polynom P ∈ R[t].
Notation: P (x) bedeutet dass man die reelle Zahl x für die Variable t einsetzet. Somit erhält
man eine reelle Zahl am xm +am−1 xm−1 +. . .+a1 x+a0 ∈ R und die Funktion ist wohldefiniert.
Bemerkung 2.7.35. Wir können Polynomfunktionen addieren und multiplizieren (siehe De-
finition 2.7.6). Wir erhalten, dass die Summe bzw. das Produkt zweier Polynomfunktionen,
durch die Summe bzw. das Produkt der Polynome gegeben ist.
Aufgepasst! Wir werden nicht immer zwischen dem Polynom P und der Funktion
R → R, x 7→ P (x) unterscheiden. Formal sind dies aber unterschiedliche Objekte
1 und es gibt Situationen in denen zwei unterschiedliche Polynome die selbe Funktion1
liefern. In diesen Fällen ist die Unterscheidung wichtig.
Falls P ∈ R[t], schreiben wir auch P für die Funktion R → R, x 7→ P (x).
(i) Betrachte ein lineares Polynom, P1 (x) = ax + b mit a, b ∈ R, a 6= 0. Dann hat P1 genau
eine Nullstelle x = − ab .
(ii) Sei P2 das quadratische Polynom P2 (x) := ax2 + bx + c, a 6= 0. Bestimmung der
Nullstellen durch quaddratische Ergänzung (p := ab , q := ac ):
2 !
p2
2 b c 2 p
P2 (x) = a x + x + = a(x + px + q) = a x+ − +q
a a 2 4
P2 (x) = 0
p 2 p2
⇐⇒ x+ − +q =0
2 4
r
p p2
⇐⇒ x+ =± −q
2 r4
p p2 p 1p 2
⇐⇒ x=− ± −q =− ± p − 4q pq-Formel
2 4 2 2
Die beiden Nullstellen sind zunächst nur definiert, falls p2 − 4q ≥ 0 gilt. Für p2 − 4q = 0
gibt es eine Nullstelle.
Satz 2.7.38. Sei P ∈ R[x], P 6= 0, mit P (x0 ) = 0 für ein x0 ∈ R. Dann existiert ein T ∈ R[x]
mit deg T = deg P − 1 und
P (x) = (x − x0 ) T (x).
| {z }
„Linearfaktor“
60
Wenn man also Nullstellen eines Polynoms kennt, kann man entsprechende Linearfaktoren
ausklammern. Konkret kann man dann den Euklidischen Algorithmus anwenden, um den Li-
nearfaktor auszuklammern, wobei der Rest dann wie im Beweis von Satz 2.7.38 verschwindet.
Beispiel 2.7.39. Ist eine Nullstelle eines Polynoms P bekannt, kann man mittels Polynom-
divison die Berechnung einer weiteren Nullstelle beschränken auf ein Polynom, dessen Grad
um 1 geringer ist als der von P .
Wir betrachten dazu das Polynom
Die Nullstelle x1 = 1 erraten wir. Dann führen wir eine Polynomdivision durch:
− 2x3 + 2x2
− 2x2 − 2x
2x2 − 2x
− 4x + 4
4x − 4
0
2x2 − 2x − 4 = 0 ⇐⇒ x2 − x − 2 = 0
61
Definition 2.7.42 (Ordnung von Nullstellen). Sei x0 ∈ R Nullstelle des Polynoms P ∈ Rm [x].
Dann existiert nach sukzessiver Anwendung von Satz 2.7.38 eine natürliche Zahle r ∈ N so
dass
P (x) = (x − x0 )r · T (x) (2.16)
gilt, wobei T ∈ Rm−r [x] ist mit T (x0 ) 6= 0.
In (2.16) ist r ∈ N0 eindeutig bestimmt und heißt Ordnung von x0 .
Notation: ν(P, x0 ) := r.
Die Nullstelle x0 heißt einfach, falls ν(P, x0 ) = 1 gilt.
Bemerkung 2.7.43. Es gilt ν(P, x0 ) = 0 genau dann wenn P (x0 ) 6= 0.
62
Kapitel 3
3.1 Der Rn
Rn = R × · · · × R = (ξ1 , . . . , ξn ) ξ1 , . . . , ξn ∈ R .
| {z }
n times
Hierbei wird R0 als der Nullraum vereinbart, R1 sind die reellen Zahlen selbst und R2 ist
die euklidische Ebene. Je nach Zusammenhang heißen die Elemente des Rn Punkte oder
Vektoren.
Vektoren können addiert und mit reellen Zahlen (Skalaren) multipliziert werden: Seien
a = (ξ1 , . . . , ξn ) und b = (η1 , . . . , ηn ) Vektoren und λ ∈ R:
a + b = (ξ1 + η1 , . . . , ξn + ηn )
λa = (λξ1 , . . . , λξn ).
y a+b y
b 2a
a
a
x x
63
(iv) Zu jedem a ∈ Rn gibt es ein b ∈ Rn mit a + b = 0. (inverses Element)
Definition 3.2.1. Das Skalarprodukt zweier Vektoren a = (ξi ) und b = (ηi ) im Rn ist
definiert als
a · b = ξ1 η1 + · · · + ξn ηn ∈ R.
Durch einfache Rechnungen erhält man die folgenden Eigenschaften für das Skalarprodukt:
Lemma 3.2.2. Für a, b, c ∈ Rn und t ∈ R gilt:
(bilinear) (a + b) · c = a · c + b · c und a · (b + c) = a · b + a · c
(symmetrisch) a·b=b·a
Die Positivdefinitheit ergibt sich daraus, dass eine Quadratsumme ξ12 + · · · + ξn2 niemals
negativ ist, und nur gleich Null, wenn alle ξi Null sind. Wenn keine Missverständnisse entstehen
können, schreiben wir auch a2 für a · a.
Nach dem Satz von Pythagoras der euklidischen Geometrie1 ist die Länge der Diagonale
eines Quaders die Wurzel aus der Quadratsumme der Seiten. Wir definieren demgemäß:
Definition 3.2.3. Die Norm oder Länge von a ∈ Rn ist
√
kak = a2 .
In der euklischen Geometrie ist (a+b)2 = a2 +b2 , wenn a und b einen rechten Winkel bilden.
Weil (a + b)2 = a2 + 2a · b + b2 , nennen wir daher zwei Vektoren a und b im Rn orthogonal,
wenn ihr Skalarprodukt a · b gleich Null ist.
Zusatzinfo. Allgemeiner definiert man den Winkel α zwischen zwei nicht–trivialen Vektoren
durch 0 ≤ α ≤ π und
a·b
cos(α) = . (3.1)
kakkbk
Dies ist wohldefiniert, da aus dem nächsten Lemma folgt, dass
a·b
−1 ≤ ≤ 1.
kakkbk
1
Das ist die Schulgeometrie des R2 und des R3 .
64
Die Cosinus und Sinusfunktion wurden in Abschnitt 2.7.4 behandelt.
Lemma 3.2.4. Seien λ ∈ R und a ∈ Rn . Dann gilt
kλ · ak = |λ| ·kak .
Weiter gilt
kak = 0 ⇐⇒ a = 0.
Beweis. p p √ √
kλak = (λa) · (λa) = λ2 (a · a) = λ2 a2 = |λ| ·kak .
Daraus folgt (mit λ = 0) insbesondere k0k = 0. Aus kak = 0 und a = (ξ1 , . . . , ξn ) folgt
umgekehrt
Xn
kak2 = ξi2 = 0
i=1
und daher a = (0, . . . , 0), denn existierte ein i ∈ {1, . . . , n} mit ξi 6= 0, so würde ξi2 > 0 und
daher kak2 > 0 folgen.
Beweis.
b
ka + bk ≤ kak +kbk .
a
a+b
65
Beweis. Aus der Cauchy–Schwarzschen Ungleichung folgt
2
ka + bk2 = (a + b)2 = a2 + 2(a · b) + b2 ≤ kak2 + 2kakkbk +kbk2 = kak +kbk .
d : Rn × Rn → R, (x, y) 7→ kx − yk
(i) d(x, y) ≥ 0
Definition 3.3.1. Eine lineare Gleichung (über R) ist ein Ausdruck der Form
α1 x1 + · · · + αn xn = β,
für die Unbekannten x1 , . . . , xn und reelle Zahlen αi , die Koeffizienten, und β. Eine Lösung
ist ein n-Tupel (ξ1 , . . . , ξn ) ∈ Rn das die Gleichung erfüllt.
Beispiel 3.3.2.
3x1 + (−2)x2 + 1x3 = 5
ist eine lineare Gleichung. Lösungen sind beispielsweise (1, 0, 2), (0, −1, 3), (1, − 12 , 1).
Aufgepasst! Jeder Summand einer linearen Gleichung ist das Produkt einer reellen
1 Zahl mit einer Variablen. Es kommen also weder Potenzen einer Variablen noch1
Produkte zweier oder mehrerer Variablen vor.
Beispiel 3.3.3.
x21 − 2x1 = 1 und 2x1 x2 + x3 = 5
sind keine linearen Gleichungen.
66
Definition 3.3.4. Ein lineares Gleichungssystem G (in n Variablen) ist ein System
α11 x1 + α12 x2 +··· + α1n xn = β1
α21 x1 + α22 x2 +··· + α2n xn = β2
..
.
αm1 x1 + αm2 x2 + · · · + αmn xn = βm
von m linearen Gleichungen. Ein lineares Gleichungssystem heißt homogen wenn βi = 0 für
alle i = 1, . . . , m.
Beispiel 3.3.5.
2x1 + 3x2 − x3 = 5
x1 − 2x2 + 3x3 = 6
−3x1 + x2 − 4x3 = −7
Die eigentliche Information des linearen Gleichungssystem liegt in den Koeffizienten und
den Konstanten auf der rechten Seite der Gleichung. Daher kodieren wir ein Gleichungssystem
in einem rechteckiges Zahlenschema.
Beispiel 3.3.5 (Fortführung)
2 3 −1 5
1 −2 3 6
−3 1 −4 −7
67
Definition 3.3.6. Eine Matrix A = (αi,j ) heißt
• quadratisch wenn m = n.
des obigen Gleichungssystems besteht aus den n-Tupeln, den Lösungen, die alle Gleichungen
von G erfüllen. (Beispiele folgen später)
Gegeben ein lineares Gleichungssystem G, stellt sich nun die Frage, ob G eine Lösung
besitzt. Und wenn ja, wie viele und wie wir diese finden können. Betrachte hierzu die folgenden
Beispiele:
Beispiele 3.3.8.
x1 = 5 1 0 0 0 5
x2 = 8 0 1 0 0 8
x3 = −2 0 0 1 0 −2
x4 = −3 0 0 0 1 −3
x1 + x2 + x3 + x4 = 5 1 1 1 1 5
x3 − 3x4 = 8 0 0 1 −3 8
x4 = −2 0 0 0 1 −2
Wir erhalten
x4 = −2
x3 = 8 + 3x4 = 8 + 3(−2) = 2
x1 = 5 − x4 − x3 − x2 = 5 + 2 − 2 − x2 = 5 − x2
Dann ist
n o
L(G2 ) = (ξ1 , ξ2 , ξ3 , ξ4 ) ∈ R4 : ξ1 = 5 − ξ2 , ξ3 = 2, ξ4 = −2
n o
= (5 − ξ2 , ξ2 , 2, −2) : ξ2 ∈ R
und es gibt unendlich viele Lösungen (für jede Wahl von ξ2 ∈ R eine).
68
(iii) Gegeben sei das lineare Gleichungssystem G3
x1 + x3 + x4 = −3 1 0 1 1 −3
x2 + 3x3 − 3x4 = 11 0 1 3 −3 11
0 = −7 0 0 0 0 −7
Hier erhalten wir einen Widerspruch, da 0 6= −7. Somit hat G3 keine Lösung.
Alle augmentierten Matrizen in den obigen Beispielen haben eine bestimmte Form
WICHTIG!: a1 , . . . , ar 6= 0
a1 ∗ ... ∗ β1
..
0 ... 0 a2 ∗ ... ∗ .
.. .. ..
. . 0 ... 0 a3 ∗ ... ∗ .
.. .. .. .. .. ..
. . . . 0 ... 0 . .
.. .. .. .. .. ..
. . . . . . 0 ar ∗ ... ∗ βr
.. .. .. .. .. .. ..
. . . . . . . 0 ... ... 0 βr+1
.. .. .. .. .. .. .. .. .. ..
. . . . . . . . . .
0 ... 0 0 ... 0 0 ... 0 0 0 ... ... 0 βm
(iii) G hat unendlich viele Lösungen wenn r < n und βr+1 = βr+2 = · · · = βm = 0.
69
x2 x2 x2
(i) (ii) (iii)
x1 x1 x1
Zλii0 : Addition des λ-fachen der i–ten Zeile zur i0 –ten Zeile für i 6= i0 .
Beispiel 3.3.10.
2 −4 6 14 1 1 −2 3 7 1 −2 3 7
Z12 Z−1
12
1 −1 2 6 −→ 1 −1 2 6 −→ 0 1 −1 −1
Z313
−3 7 −10 −22 −3 7 −10 −22 0 1 −1 −1
1 −2 3 7 1 0 1 5
Z−1
23 Z221
−→ 0 1 −1 −1 −→ 0 1 −1 −1
0 0 0 0 0 0 0 0
Die zwei letzten Matrizen repräsentieren zwei verschiedene lineare Gleichungssysteme in Zei-
lenstufenform mit den gleichen Lösungen wie das ursprüngliche System. Dies verdeutlicht,
dass man einem Gleichungssystem keine kanonische Zeilenstufenform zuordnen kann. Eine
wichtige Gemeinsamkeit der Zeilenstufenformen ist der Rang.
Lemma 3.3.11. Ein Gleichungssystem, das aus G durch Zeilenoperationen hervorgeht, hat
die gleichen Lösungen wie G.
Beweis. Es ist klar, dass sich bei Vertauschen von Zeilen die Lösungen nicht ändern. Für die
anderen Operationen reicht es zu zeigen, dass, wenn G0 bzw. G00 durch Zλi bzw. Zλi0 ,i aus G
entstanden ist, jede Lösung von G auch eine Lösung der i-ten Zeile von G0 bzw. der i0 -ten
Zeile von G00 ist.
Sei also (ξ1 , . . . , ξn ) eine Lösung von G und
70
die i–te und i0 –te Zeile des Gleichungssystem. Dann ist
Daraus folgt
(λαi1 )ξ1 + · · · + (λαin )ξn = λ(αi1 ξ1 + · · · + αin ξn ) = λbi ,
und somit ist (ξ1 , . . . , ξn ) eine Lösung der i–ten Zeile von G0 .
Des weiteren ist
und (ξ1 , . . . , ξn ) daher eine Lösung der i0 –ten Zeile von G00 .
(i) G lässt sich durch Zeilenoperationen in (normierte) Zeilenstufenform bringen. Wir be-
zeichnen diese als zugehörige (normierte) Zeilenstufenform.
(ii) Zwei zugehörige (normierte) Zeilenstufenformen von G besitzen den gleichen Rang.
Eine solche quadratische n × n–Matrix heißt regulär. Ansonsten, also wenn r < n, heißt
eine quadratische n × n–Matrix singulär.
1 ∗ ... ∗ β1
..
0 ... 0 1 ∗ ... ∗ .
.. .. ..
. . 0 ... 0 1 ∗ ... ∗ .
.. .. .. .. .. ..
. . . . 0 ... 0 . .
.. .. .. .. .. ..
. . . . . . 0 1 ∗ ... ∗ βr
.. .. .. .. .. .. ..
. . . . . . . 0 ... ... 0 βr+1
.. .. .. .. .. .. .. .. .. ..
. . . . . . . . . .
0 ... 0 0 ... 0 0 ... 0 0 0 ... ... 0 βm
Nach Bemerkung 3.3.9 hat es solches Gleichungssystem genau dann genau eine Lösung wenn
r = n und βr+1 = βr+2 = · · · = βm = 0. Wenn zusätzlich r = m ist die zweite Aussage leer
und man erhält für jede Wahl der βi genau eine Lösung. Falls r < m, wähle βr+1 6= 0. Somit
erhält man ein Gleichungssystem G mit Koeffizientenmatrix A, dass keine Lösung besitzt.
71
3.4 Lineare Abbildungen
Oft sagen wir einfach „T ist linear.“ Wir bezeichnen die Menge der linearen Abbildungen
von Rn nach Rm mit L(Rn , Rm ).
Lineare Abbildungen Rn → Rm können in m × n–Matrizen kodiert werden. Dies erleichtert
die Analyse und das Berechnen der Bilder einzelner Vektoren als auch der Komposition zweier
linearer Abbildungen.
(αij ) i=1...m .
j=1...n
ist.2 Die i sind die Zeilenindices, die j die Spaltenindices. Eine 1 × n–Matrix heißt Zeilen-
vektor, und eine m × 1–Martix Spaltenvektor. Die Menge aller m × n–Matrizen bezeichnen
wir mit Mm×n (R). Weiter schreiben wir Mn (R) für Mn×n (R), die Menge der quadratischen
n × n–Matrizen.
Mit 0mn bezeichnen wir die m × n–Matrix, deren Elemente Nullen sind:
0 ... 0
. .
.. . . ... (nur quadratisch wenn m = n).
0mn =
0 ... 0
| {z }
∈ Mm×n (R)
0 ... 0 1
| {z }
∈ Mn (R)
Wenn es keine Verwechslungsgefahr gibt, schreiben wir gelegentlich auch einfach 0 oder I.
2
Kürzere, weniger präzise, Schreibweisen sind (αij )i,j und (αij )
72
Definition 3.4.2. Seien A = (αij ) und B = (βij ) zwei m × n–Martizen und λ ∈ R.
Aufgepasst! Die Summe von zwei Matrizen kann nur gebildet werden, wenn die
1 1
beiden Matrizen jeweils die gleichen Anzahlen von Zeilen und Spalten haben.
Beispiele 3.4.3.
! ! !
1 2 −5 −3 −3 7 −2 −1 2
(i) + =
3 −2 4 0 1 4 3 −1 8
1 −2 −2 4
(ii) (−2) · −3 4 = 6 −8
0 5 0 −10
Definition 3.4.4. Das Produkt einer l × m–Martix A = (αP hi ) und einer m × n–Matrix
B = (βij ) ist die l × n–Matrix C = (γhj ), definiert durch γhj = m i=1 αhi βij .
Man beachte, dass AB nur definiert ist, wenn A soviel Spalten hat wie B Zeilen. Dann sind
die Zeilen von A so lang wie die Spalten von B und γhj ist das Produkt der h-ten Zeile von
A mit der j-ten Spalte von B.
Slogan: “Zeile mal Spalte”
Beispiel 3.4.5.
! −2 0 3 · ( − 2) + 2 · 3 + 0 · 5 3 · 0 + 2 · −2 + 0 · 0
3 2 0
· 3 −2 =
−1 0 5
5 0 (−1) · ( − 2) + 0 · 3 + 5 · 5 (−1) · 0 + 0 · −2 + 5 · 0
!
0 −4
=
27 0
73
Bemerkung 3.4.6. Seien a1 , . . . , al die Zeilen von A und b1 , . . . , bn die Spalten von B. Dann
sind a1 B, . . . , al B die Zeilen und Ab1 , . . . , Abn die Spalten von AB:
a1 a1 B
a2 a2 B
AB = .. B = ..
. .
al al B
Außerdem ist
a1 · b1 . . . a1 · bn
. ..
AB = .. . = (ah · bj ) j=1...n
h=1...l
al · b1 . . . al · bn
Bemerkung 3.4.7. Für Matrizen A, A0 ∈ Ml×m (R), B, B 0 ∈ Mm×n (R), C ∈ Mn×p (R) und
γ ∈ R gilt
Beispiel 3.4.8. ! ! !
1 2 0 −2 −4 4
=
3 4 −2 3 −8 6
! ! !
0 −2 1 2 −6 −8
=
−2 3 3 4 7 8
Multipliziert man eine m × n–Matrix mit einem n × 1–Spaltenvektor mit erhält man einen
m × 1–Spaltenvektor. Wenn wir nun die Elemente des Rn und des Rm als Spaltenvektoren
auffassen, wird dadurch eine Abbildung Rn → Rm , a 7→ A · a definiert.
74
T0 ist die Nullabbildung, TI die identische Abbildung.
Die Matrix Algebra garantiert, dass diese Abbildungen linear sind: Für x, y ∈ Rn , λ ∈ R ist
TA (x+y) = A(x+y) = Ax+Ay = TA (x)+TA (y) und TA (λx) = A(λx) = λ(Ax) = λTA (x)
Aufgepasst! Wie oben werden wir Tupel des Rn auch als Spaltenvektoren oder auch
Zeilenvektoren auffassen oder umgekehrt. Falls diesbezüglich Verwirrung entsteht,
bitte nachfragen!!! Wenn es nicht ausdrücklich von Nutzen ist Spaltenvektoren zu
1 1
verwenden, werden wir Elemente des Rn immer als Tupel schreiben. Dies wird im
zweiten Semester besonders wichtig sein, wenn wir Spaltenvektoren für etwas anderes
verwenden.
Beachte, dass die Notation mehrdeutig ist, da wir e1 für (1, 0) ∈ R2 und (1, 0, 0) ∈ R3
schreiben. Normalerweise ist es aus dem Kontext ersichtlich, in welchem Rn der Vektor ei
„lebt“.
Bemerkung 3.4.10. Für (ξ1 , ξ2 , . . . , ξn ) ∈ Rn gilt
(ξ1 , ξ2 , . . . , ξn ) = ξ1 e1 + ξ2 e2 + · · · + ξn en .
Das Bild von ei ist also die i-te Spalte von A und
Aus
ξ
.1 X n
(αi1 · · · αin ) .. =
αij ξj
ξn j=1
ergibt sich, dass die i–te Zeile von A die i–te Komponente von TA definiert. Sei e∗i der i-te
Einheitsvektor als Spalte geschrieben. Dann ist ei · A die i–te Zeile von A. Daraus ergibt sich
leicht, dass ei · A · e∗j = αij . Daraus folgt, dass
ei · TA (ej ) = αij .
75
Bemerkung 3.4.11. Die Abbildung Mm×n (R) → L(Rn , Rm ), A 7→ TA ist eine Bijektion.
Insbesondere kann jede lineare Abbildung als Multiplikation mit einer Matrix beschrieben
werden und je zwei gleiche Abbildungen werden durch die selbe Matrix beschrieben.
Wir definieren nun Summen und skalare Vielfache von linearen Abbildungen.
Definition 3.4.12. Für λ ∈ R und S, T ∈ L(Rn , Rm ) definieren wir S + T : Rn → Rm sowie
λT durch
(S + T )(a) := S(a) + T (a), (λT )(a) := λ · T (a)
für a ∈ Rn .
Wir zeigen nun, dass die Addition und Skalarmultiplikation von Matrizen den gleichen
Operationen auf linearen Abbildungen entsprechen. Des Weiteren kann die Verknüpfung von
Abbildungen durch Matrixmultiplikation ausgedrückt werden.
Lemma 3.4.13. Seien A, A0 ∈ Mm×n (R), B ∈ Mn×l (R) und λ ∈ R. Dann gilt
(iii) TA ◦ TB = TAB .
Beweis. (i) TA+A0 (a) = (A + A0 ) a = A a + A0 a = TA (a) + TA0 (a) = (TA + TA0 )(a)
Das bedeutet insbesondere, dass Summen und skalare Vielfache von linearen Abbildungen
wieder lineare Abbildungen sind.
PageRank ist ein Algorithmus der allen Webseiten einen Wert, basierend auf der Anzahl der
Links zu dieser Webseite, zuordnet. Er wurde von Serge Brin und Larry Page, zwei Doktoran-
den der Informatik der Stanford University und Gründer der Firma Google, 1996 entwickelt
und mit großem Erfolg 1998 veröffentlicht. Der PageRank-Algorithmus war (und ist) die
Grundlage der Google-Suchmaschine.
Das Grundprinzip von RankPage besteht darin, jeder Seite eine Punktzahl zuzuweisen, die
proportional dazu ist, wie oft ein Benutzer diese Seite durchsucht, indem er nach dem Zufalls-
prinzip auf die auf jeder Seite enthaltenen Links klickt. So hat eine Seite einen PageRank, der
umso höher ist, je größer die Summe der PageRanks der darauf verlinkenden Seiten ist:
Eine Seite ist wichtig, wenn andere wichtige Seiten darauf verweisen.
76
• die Anzahl der Links auf einer Seite die einen Link zu P haben,
Ihr Ansatz entspricht dem eines Random Walks auf dem Graphen des Webs, dem ge-
richteten Graphen, dessen Knoten die Webseiten und die Kanten die Hyperlinks des Webs
darstellen. Mit anderen Worten, der Random Surfer wählt im nächsten Schritt zufällig einen
der Links auf der Website auf der er sich gerade befindet.
Um den Page Rank wirklich auszurechen benötigen wir Werkzeuge, die wir erst im 2.
Semester kennenlernen werden. Wir wollen uns hier nun das Prinzip des Random Walk auf dem
Graphen des Webs anhand von linearen Abbildungen an einem Mini-Netzwerk klarmachen.
Beispiel 3.4.14. Gegeben sei das folgende Mini-Netzwerk.
1 5 6
2 3 4 7
Nehmen wir an, dass 720 Personen in unserem Netzwerk surfen, sich am Anfang alle auf
Seite 1 befinden und dass ein Surfer im Schnitt alle 30 Sekunden die Seite wechselt. Dies
wird modelliert durch das iterierte Anwenden der linearen Abbildung TA auf den Vektor
(720, 0, 0, 0, 0, 0, 0) für alle 30 Sekunden die vergehen. Dann sieht erwartungsgemäß unsere
77
Verteilung nach 3 Minuten folgendermaßen aus:
720
0
0
TA ◦ · · · ◦ TA (720, 0, 0, 0, 0, 0, 0) = A6 0
| {z }
0
6 mal
0
0
1 1
0 2 3 0 0 0 0 0 21 1
3 0 0 0 0
1
720 1
0
1 0 0 0 0 0 0 1 0 0 0 0 0 720
3 3
0 1 0 1
2 0 0 0 0 0 0
2 0 0 0 0 0 0
1 1 1 1
= A5 0 0 0 0 0 · 0 = A4 0 0 0 0 0 · 0
3 3 3 3
1 1 0 1 1 0
0 0 0 2 0 1 0 0 0
3 2 0 1 3
1 0 1 0
0 0 0 0 0 0 0 0 0 0 0 0
3 3
0 0
1 1
0 0 0 2 1 0 0 0 0 0 2 1 0 0
1 1
0 2 3 0 0 0 0 0 21 1
3 0 0 0 0
1
360 1
120
1 0 0 0 0 0 0 1 0 0 0 0 0 480
3 3
0 1 0 1
2 0 0 0 0 0 360
2 0 0 0 0 0
0
1 1 1
= A3 0 0 0 0 0 · 0 = A2 0 0 0 0 0 31 · 120
3 3 3
1 1 0 1 0
1 31
0 0 0 2 0 1 0 0 0
3 2 0
1 0 0
0 0 0 0 0 0 3
0 0 0 0 0 0 13
0 0
1 1
0 0 0 2 1 0 0 0 0 0 2 1 0 0
1 1
0 2 3 0 0 0 0 0 12 31 0 0 0 0
1
240 140 180
1 0 0 0 0 0 120 1 0 13 0 0 0 0 320 160
3
0 1 0 1 0
2 0 0 0 0 0 240
2 0 0 0 0 60 160
1 1
= A 0 0 0 0 0 · 0 = 0 0 31 0 0 0 1
· 100 = 40
3 3 3
1 1 60 1 1 20 90
0 0 0 2 0 1 0 0 0
3 2 0 1 3
1 0 1 20 20
0 0 0 0 0 0 0 0 0 0 0 0
3 3
60 60 70
1 1
0 0 0 2 1 0 0 0 0 0 2 1 0 0
Das heißt, nach 3 Minuten befinden sich erwartungsgemäß 180 Personen auf Seite 1, 160
Personen auf Seite 2, 160 Personen auf Seite 3, 40 Personen auf Seite 4, 90 Personen auf Seite
5, 20 Personen auf Seite 6, 70 Personen auf Seite 7.
Dies kodiert somit eine Streckung (λ > 1) oder Stauchung (0 < λ ≤ 1) um den Faktor λ.
78
Aufgepasst! Für λ < 0 erhält man einen Punktreflektion + Streckung/Stauchung
1 1
und für λ = 0 die Nullabildung.
Drehungen: Man mache sich zunächst klar, dass Drehungen im R2 linear sind.
Wir wollen den R2 um einen beliebigen Winkel θ gegen den Uhrzeigersinn drehen. Beschrie-
ben wird das durch die lineare Abbildung Rθ : R2 → R2 . Sei a = (x, y) ein beliebiger Vektor
in R2 und b = (−y, x). Betrachte das folgende Diagramm:
b = (−y, x) Rθ
sin(θ)
· a = (x, y)
θ
· cos(θ)
x
Dann ist
für λ = cos(θ) und µ = sin(θ). Es gilt 1 = cos2 (θ) + sin2 (θ) = λ2 + µ2 = 1. Somit ist jede
Drehung eine Matrix der Form
!
λ −µ
mit λ2 + µ2 = 1
µ λ
Orthogonale Projektion: Wir wollen auf eine Ursprungsgerade G erzeugt durch einen Vek-
tor b projizieren und bezeichnen diese Abbildung mit projG : R2 → R2 .
Als Bild:
79
y
a
G
b
· projG (a)
projG (a0 )
·
a0
Idee:
a
G
a⊥ b
· · projG (a)
·
x
80
Für allgemeines b = (x, y) erhält man
!
a·b 1 1 x2 xy
projG (a) = b= 2 (a · b) b = 2 a.
b·b x +y 2 x + y2 xy y 2
Reflektionen: Wir wollen an einer Gerade G die durch den Einheitsvektor b = (x, y) gegeben
ist reflektieren und bezeichnen diese Abbildung mit ref G : R2 → R2 .
a
G
a⊥
⊥
a
· · projG (a)
· −a⊥
x
ref G (a)
Somit ist
!
2 x2 xy
ref G (a) = 2 projG (a) − a = 2 a − I2 a
x + y 2 xy y 2
! !
1 2x2 2xy 1 x2 + y 2 0
= 2 a− 2 a
x + y 2 2xy 2y 2 x + y2 0 x2 + y 2
!
1 2x2 − (x2 + y 2 ) 2xy
= 2 a
x + y2 2xy 2y 2 − (x2 + y 2 )
!
1 x2 − y 2 2xy
= 2 a
x + y2 2xy y 2 − x2
81
3.4.5 Inverse einer Linearen Abbildung
Ax = y
genau eine Lösung besitzt. Nach Korollar 3.3.14 ist dies genau dann der Fall, wenn A regulär
ist, d. h. n = m = Rang(A). Eine bijektive lineare Abbildung nennen wir Isomorphismus.
Bemerkung 3.4.18. Die Inverse Abbildung einer bijektiven linearen Abbildung T : Rn →
Rn , x 7→ Ax ist wieder eine lineare Abbildung T −1 : Rn → Rn , x 7→ Bx. Gemäß der Definition
der inversen Abbildung gilt
T ◦ T −1 = T −1 ◦ T = IdRn : Rn → Rn , x 7→ In x = x
T ◦ T −1 : Rn → Rn , x 7→ AB x und T −1 ◦ T : Rn → Rn , x 7→ BA x.
82
Berechnung der Inversen Matrix
Notation: Seien A = (αij ) und B = (βij ) n × n–Matrizen. Wir schreiben wir A|B für die
n × (2n)–Matrix
α11 . . . α1n β11 . . . β1n
α21 . . . α2n β21 . . . β2n
. .. .. ..
.
. . . .
αn1 . . . αnn βn1 . . . βnn
Wenn eine n×n–Matrix A invertierbar ist, dann kann man wie folgt dass Inverse berechnen:
Man wendet Zeilenoperation auf die Matrix A|In an um sie in eine Matrix der Form In |B zu
verwandeln (wenn A invertierbar ist und somit Rang n hat, ist dies immer möglich). Dann
ist B = A−1 .
Beispiel 3.4.21. Wir wollen das Inverse der Matrix
1 1 1
A = 2 3 2
3 8 2
berechnen.
1 1 1 1 0 0 1 1 1 1 0 0
Z−2
12
2 3 2 0 1 0 −→ 0 1 0 −2 1 0
Z−3
3 8 2 0 0 1 13 0 5 −1 −3 0 1
1 0 1 3 −1 0 1 0 0 10 −6 1
Z−1
21 Z1
31
−→ 0 1 0 −2 1 0 −→ 0 1 0 −2 1 0
Z−5 Z−1
23 0 0 −1 7 −5 1 3 0 0 1 −7 5 −1
Dann ist
10 −6 1
A−1 = −2 1 0
−7 5 −1
3.4.6 Anwendung
Stellen Sie sich vor, Sie sind Besatzungsmitglied auf einem Schiff der französischen Küstenwa-
che. Ihr Schiff sendet regelmäßig seine Position an die Zentrale nach Marseille. Sie erwarten,
dass die Kommunikation abgefangen wird. Um also Ihre Position vor dritten geheim zuhalten,
müssen Sie Ihre tatsächliche Position
!
x1 ← östlicher Langengrad
x2 ← nördlicher Breitengrad
!
y1
in eine kodierte Position umwandeln.
y2
Beispiel 3.4.22. Wir nehmen an, dass wir den folgenden Kode benutzen:
y1 = x1 + 3x2
y2 = 2x1 + 5x2 .
83
Die Position des Schiffes sei 5◦ Ost und 42◦ Nord, d. h.
! !
x1 5
= .
x2 42
d. h. ! !
y1 131
=
y2 220
Dies kann mithilfe einer linearen Abbildung dargestellt werden:
! ! ! !
y1 1 x1 + 3 x2 1 3 x1
= =
y2 2 x1 + 5 x2 2 5 x2
| {z }
=A
Das Kodieren kann also dem Anwenden einer linearen Abbildung gleichgesetzt werden.
Da man bei jedem Eintreffen neuer Koordinaten abermals ein Gleichungssystem mit der selben
Koeffizientenmatrix lösen muss, stellt sich die Frage, ob man diese Aufgabe strukturierter
angehen kann. Genauer gesagt wollen wir für beliebige y1 , y2 die folgende Gleichung lösen:
! !
x1 y1
A =
x2 y2
Damit wir eine eindeutige Lösung erhalten und der Kode sinnvoll ist, sollte die obige Gleichung
genau eine Lösung besitzen. Dies ist genau dann der Fall, wenn A invertierbar ist. Dann ist
! ! ! !
x1 x1 −1 x1 −1 y1
= I2 =A A =A
x2 x2 x2 y2
Somit kann durch Berechnung der Inversen Matrix der Kode enschlüsselt werden. In unserem
Beispiel ist !
−1 −5 3
A =
2 −1
Prinzip::
84
Position Kode
!
x1
A·
x2
! !
x1 y1
x2 y2
!
y1
A−1 ·
y2
3.5 Determinante
Man kann jeder Matrix über R eine reelle Zahl zuweisen, die sogenannte Determinante der
Matrix, in einer Weise, dass eine Matrix genau dann invertierbar ist, wenn die Determinante
ungleich 0 ist. Des Weiteren können Determinanten benutzt werden, um das Inverse einer
Matrix zu berechnen als auch um die sogenannten Eigenwerte einer Matrix zu bestimmen (2.
Semester). Dies spielt eine wichtige Rolle bei Anwendungen in der Informatik (z. B. in der
Google Matrix) als auch in anderen Gebieten.
d 1 −c 1
x1 = ad−bc = det(A) ·d x3 = ad−bc = det(A) · (−c)
−b 1 a 1
·a
x2 = ad−bc = det(A) · (−b) x4 = ad−bc = det(A)
85
Das heißt !
−1 1 d −b
A = · .
det(A) −c a
Wir wollen nun dieses Konzept der Determinante auf n × n–Matrizen verallgemeinern. Die
beiden Summanden in der Determinante einer 2 × 2–Matrix sind jeweils ± das Produkt von
2 Einträgen der Matrix, wobei man aus jeder Spalte und jeder Zeile genau einen Eintrag
auswählt: !
a b
det ad − |{z}
= |{z} bc
c d
a b a b
c d c d
und somit
MA = {a · e · i, a · f · h, b · d · i, b · f · g, c · d · h, c · e · g}.
Es gibt 3 · 2 · 1 = 6 Muster in A. Im Allgemeinen gibt es n! viele Muster in einer n × n–Matrix.
Wir wollen nun für eine n × n–Matrix A die Determinante definieren als:
X
det(A) = ± P.
|{z}
P ∈MA ?
ad
|{z} − |{z}
bc .
a b a b
+ −
c d c d
86
Definition 3.5.4. Sei A = (aij ) eine quadratische Matrix. Ein Missstand in einem Muster
M in A ist ein Paar von Elementen akl , ast ∈ M so dass k < s und l > t:
.. ..
. .
. . . . . . a kl . . .
.. ..
. .
. . . ast . . . . . .
.. ..
. .
Beispiel 3.5.5.
(i) Sei !
a b
A= .
c d
! !
a b a b
Dann ist kein Missstand aber ist ein Missstand.
c d c d
(ii) Sei
a b c
A = d e f .
g h i
Dann sind
a b c a b c a b c a b c
d e f , d e f , d e f , d e f
g h i g h i g h i g h i
a b c a b c a b c a b c a b c
d e f , d e f , d e f , d e f , d e f
g h i g h i g h i g h i g h i
Missstände, aber
a b c a b c a b c a b c
d e f , d e f , d e f , d e f
g h i g h i g h i g h i
a b c a b c a b c a b c a b c
d e f , d e f , d e f , d e f , d e f
g h i g h i g h i g h i g h i
keine Missstände.
Definition 3.5.6. Sei A eine quadratische Matrix. Dann definieren wir die Determinante
det(A) durch X
det(A) = (−1)# der Missstände in P · P
P ∈MA
87
Bemerkung 3.5.7. Wenn A eine quadratische n × n–Matrix ist mit vi = (vi1 , . . . , vin ) als
i-te Zeile, dann ist
X
det(A) = (−1)|{(s,t) : 1≤s<t≤n, js >jt }| v1j1 · · · · · vnjn
{j1 ,...,jn }={1,...,n}
Beispiel 3.5.8.
1 2 3
det 4 5 6 = (−1)0 (1 · 5 · 9) + (−1)1 (1 · 6 · 8) + (−1)1 (2 · 4 · 9)
7 8 9
| {z } | {z } | {z }
1 2 3 1 2 3 1 2 3
4 5 6 4 5 6 4 5 6
7 8 9 7 8 9 7 8 9
= 45 − 48 − 72 + 84 + 96 − 105
=0
Proposition 3.5.9.
(i) Die Abbildung det : Mn×n (R) → R, A 7→ det(A) ist „linear in jeder Zeile“, d. h. für eine
Matrix mit Zeilen vi = (vi1 , . . . , vin ) ∈ Rn für i = 1, . . . , n und w = (w1 , . . . , wn ) ∈ Rn
(hier werden v1 , . . . , vn , w als Zeilenvektoren aufgefasst), λ ∈ R gilt:
.. ..
. .
(a) det λvi = λ · det vi
.. ..
. .
.. .. ..
. . .
(b) det vi + w = det vi + det w
.. .. ..
. . .
(ii) Für eine Matrix A ∈ Mn (R) mit zwei gleichen Zeilen ist det(A) = 0.
(iii) Wenn man B ∈ Mn (R) aus A ∈ Mn (R) erhält durch
(a) Multiplikation einer Zeile mit λ ∈ R \ {0}, ist
1
det(A) = det(B)
λ
(b) Addition eines Vielfachen einer Zeile zu einer anderen, ist
det(A) = det(B)
88
(c) Vertauschen von zwei Zeilen, ist
det(A) = − det(B)
Beweis. Um die Notation schlanker zu gestalten und die Formel etwas lesbarer zu machen,
definieren wir für eine Matrix mit Zeilen (vi = (vi1 , . . . , vin ) ∈ Rn )i=1,...,n , die Anzahl der
Missständen eines Muster v1j1 , . . . , vnjn durch #(j1 ,...,jn ) , d. h.
(i) Es ist
(a)
..
. X
det λvi = (−1)#(j1 ,...,jn ) v1j1 · · · · · (λviji ) · · · · · vnjn
..
{j1 ,...,jn }={1,...,n}
.
X
=λ· (−1)#(j1 ,...,jn ) v1,j1 · · · · · viji · · · · · vnjn
{j1 ,...,jn }={1,...,n}
..
.
= λ · det vi
..
.
(b)
..
. X
det vi + w = (−1)#(j1 ,...,jn ) v1j1 · · · · · (viji + wji ) · · · · · vnjn
..
{j1 ,...,jn }={1,...,n}
.
X
= (−1)#(j1 ,...,jn ) v1,j1 · · · · · viji · · · · · vnjn
{j1 ,...,jn }={1,...,n}
X
+ (−1)#(j1 ,...,jn ) v1,j1 · · · · · wji · · · · · vnjn
{j1 ,...,jn }={1,...,n}
.. ..
. .
= det vi + det w
.. ..
. .
(ii) Sei v = (v1 , . . . , vn ) die Zeile die zweimal vorkommt. Dann kommt für feste Wahl von
Einträgen aus den anderen Zeilen, jedes Paar vi , vj mit 1 ≤ i < j ≤ n in zwei Mustern
vor und zwar einmal als Missstand und einmal nicht als Missstand. Das heißt die Vor-
zeichen sind verschieden und somit kürzen sich diese Terme weg. Da dies für alle Muster
gilt ist die Summe am Ende 0 und det(A) = 0.
89
(iii) (a) Wir nehmen an, dass B aus A entstanden ist, indem die i-te Zeile vi mit λ multi-
pliziert haben. Dann gilt
.. .. ..
. . (i)(a) 1 . 1
det(A) = det vi = det λ1 λ vi = ·det λvi = det(B).
.. .. λ .. λ
. . .
(b)
.. .. .. ..
. . . .
vi vi vi vi
.. (i)(a)+(b) .. .. ..
det . = det . . .
+λ det = det
vj + λvi vj vi vj
.. .. .. ..
. . . .
| {z }
=0 nach (ii)
(c) Mithilfe von (iii) (a) und (b) kann erhält man
.. .. ..
. . .
vi −1 vi vj
1
.
..
Zij .
..
Zji ..
det = det = det .
vj vj − vi vj − vi
.. .. ..
. . .
.. ..
. .
v vj
−1
j 1
Zj .
..
Zij ..
= (−1) det = − det .
vi − vj vi
.. ..
. .
(a) det(A) 6= 0
(b) A ist invertierbar.
(c) Rang(A) = n
90
Definition 3.5.11. Für eine m × n–Matrix
a11 a12 ... a1n
a21 a22 ... a2n
..
A = (aij ) = .. .. ..
. . . .
am1 am2 . . . amn
Die transponierte Matrix AT ergibt sich also dadurch, dass die Rollen von Zeilen und
Spalten der Ausgangsmatrix A vertauscht werden. Anschaulich entsteht die transponierte
Matrix durch Spiegelung der Ausgangsmatrix an ihrer Hauptdiagonale a11 , a22 , . . . , akk mit
k = min{n, m}. Wir interessieren uns hauptsächlich für die transponierte Matrix einer qua-
dratischen Matrizen A in Mn (R).
Beispiel 3.5.12. Die transponiert Matrix von
2 −1 5 7
0 −2 3 8
−4 1 6 −3
ist
2 0 −4
−1 −2 1
5 3 6
7 8 −3
Die folgenden Eigenschaften der transponierten Matrix werden wir nicht beweisen:
Bemerkung 3.5.13. Für m × n–Matrizen A und B gilt:
(i) (A + B)T = AT + B T .
(iii) (AB)T = B T AT .
91
3.5.3 Determinante einer Oberen Dreiecksmatrix
Sei
a11 a12 a13 . . . a1n
0 a22 a23 . . . a2n
0 0 a33 . . . a3n
. ..
. .. .. ..
. . . . .
0 ... 0 0 ann
Dann kommt in jedem Muster mit Ausnahme von {a11 , a22 , a33 , . . . ann } eine 0 vor. Diese
Muster hat 0 Missstände. Somit ist
a11 a12 a13 . . . a1n
0 a22 a23 . . . a2n
Yn
0 0 a . . . a
det
33 3n = a11 · a22 · a33 · . . . · ann = aii
.. ..
.
..
.
..
.
..
. . i=1
0 ... 0 0 ann
Beispiel 3.5.14.
1 2 −1 5 1 2 −1 5 1 2 −1 5
1 2 0 4 Z−1 , Z −1
0 0 1 −1 V23 0 2 2 −8
12
det = 13 det = − det
1 4 1 −3 0 2 2 −8 0 0 1 −1
−1
Z14
1 3 2 2 0 1 3 −3 0 1 3 −3
1
1 2 −1 5 1 2 −1 5
Z−1
2
Z2 0 1 1 −4 24 0 1 1 −4
= −2 det = −2 det
0 0 1 −1 0 0 1 −1
0 1 3 −3 0 0 2 1
1 2 −1 5 1 2 −1 5
Z−2
Z 13
0 1 1 −4 4 0 1 1 −4
34
= −2 det = −2 · 3 det
0 0 1 −1 0 0 1 −1
0 0 0 3 0 0 0 1
| {z }
=1
= −6
Im Allgemeinen erhalten wir das folgende: Sei A eine quadratische Matrix. Nehmen wir an,
wir tauschen s mal zwei Zeilen, multiplizieren verschiedene Zeilen mit dem Skalaren λ1 , . . . , λm
und addieren vielfache von Zeilen zu anderen hinzu um A in eine obere Dreiecksmatrix B zu
verwandeln. Dann ist
(−1)s
det(A) = det(B)
λ1 · · · · · λm
92
Kapitel 4
4.1 Folgen
In diesem Abschnitt führen wir den Grenzwert (einer Folge) und damit den zentralen Begriff
der Analysis ein.
Motivation. Wir betrachten in diesem Abschnitt Folgen von reellen Zahlen z. B. die Folge der
Quadratzahlen 1, 4, 9, 16, 25, 36, . . . oder die Folge 11 , 12 , 13 , 14 , 15 , 16 , . . .. Anders als bei Mengen
von Zahlen kommt es bei Folgen (wie der Name schon suggeriert) auf die Reihenfolge an.
Anwendungen in der Informatik:
(i) In 4.1.1 ist statt N auch N0 oder Z≥l := {k ∈ Z : k ≥ l} für l ∈ Z als Definitionsbereich
möglich.
1 1 1
(an )n∈N = (1, , , , . . .)
2 3 4
Beispiele 4.1.3.
(i) Sei a ∈ R. Dann ist durch an = a für n ∈ N eine konstante Folge definiert.
93
(iii) Die gleiche Folge kann man auch z. B. durch ( n−1
n )n∈Z≥2 = ( n )n≥2 oder ( n−1 )n∈Z≥3 =
n−1 n−2
Bemerkung 4.1.4. Begriffe wie Monotonie und Beschränktheit (vgl. Definition 2.7.11, De-
finition 2.7.13) behalten für Folgen ihre Gültigkeit, d. h.
Beispiele 4.1.5.
(i) Sei an = 1
n für n ∈ N. Dann ist (an )n∈N nach unten und oben beschränkt:
∀n ∈ N : 0 ≤ an ≤ 1
(ii) Sei an = (−1)n , also (an )n∈N = (−1, 1, −1, 1, . . .). Dann ist (an )n∈N nicht monoton aber
beschränkt:
|(−1)n | = 1
(iii) Sei q ∈ [0, 1) und an = q n für n ∈ N0 . Dann ist (an )n∈N beschränkt und monoton
fallend:
∀n ∈ N0 : |q n | ≤ 1 ∧ ∀m ≤ n : q m > q n
f0 := 0, f1 := 1,
fn := fn−1 + fn−2 für n ≥ 2,
Dann ist
(fn )n∈N = (0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, . . .)
monoton wachsend und heißt Fibonacci-Folge. Hintergrund ist die Frage eines Kanin-
chenzüchters: Wie viele Paare entstehen aus einem einzigen Paar innerhalb eines Jahres,
wenn jedes Paar nach zwei Lebensmonaten genau ein weiteres Paar pro Monat zur Welt
bringt?
94
Zentraler Begriff der Analysis: der Grenzwert. Betrachte z. B. an = n1 , n ∈ N.
Vermutung: für sehr große n ∈ N wird an sehr klein (und bleibt dabei positiv). Für n0 ∈ N
gilt
1
0 ≤ an ≤ ∀n ≥ n0 ⇐⇒ an ∈ [0, 1/n0 ] ∀n ≥ n0 ,
n0
wobei die Länge des Intervalls 1
n0 ist. Diese Intervalllänge wird sehr klein für n0 groß.
0 1 1 1 1
n0 4 2
Formalisierung:
Definition 4.1.6. Eine Folge (an )n∈N reeller Zahlen heißt konvergent mit Grenzwert a ∈
R, falls gilt:
∀ε > 0 ∃n0 ∈ N ∀n ≥ n0 : |an − a| < ε. (4.1)
n→∞
Notation: a = lim an , an −→ a Eine Folge heißt divergent, falls sie nicht konvergiert.
n→∞
Falls eine konvergente Folge a = 0 als Grenzwert hat, so heißt sie Nullfolge.
Bemerkung 4.1.7.
(i) anschauliche Interpretation einer konvergenten Folge (an )n∈N an der Zahlengerade:
an , n ≥ n0 (ε)
a−ε a a+ε
Sei ε > 0 beliebig. Dann liegen alle Folgenglieder an ab einem Index n0 = n0 (ε) im
Intervall (a − ε, a + ε) der Länge 2ε.
(iii) Definition 4.1.6 liefert den Einstieg in die Welt der ε-Kriterien, die für die Analysis eine
große Bedeutung haben.
ε-Umgebung
a−ε a a+ε
(v) In Definition 4.1.6 ist es nicht nötig, das kleinstmögliche n0 zu bestimmen. Es genügt,
irgendeinen Index n0 anzugeben, ab dem alle Folgenglieder in U (a) liegen. Anders aus-
gedrückt, auf die ersten endlich vielen Folgenglieder kommt es beim Konvergenzbegriff
nicht an.
95
(vi) Aus Definition 4.1.6 folgt sofort
n→∞ n→∞ n→∞
an −→ a ⇐⇒ an − a −→ 0 ⇐⇒ |an − a| −→ 0.
Diese (trivialen) Äquivalenzen erweisen sich im Folgenden hin und wieder als nützlich.
(vii) Wenn man die Divergenz einer Folge beweisen möchte, kann es hilfreich sein die Vernei-
nung von (4.1)
∃ε > 0 ∀n0 ∈ N ∃n ≥ n0 : |an − a| ≥ ε (4.2)
zu bilden. Sehr häufig beweist man aber die Divergenz einer Folge durch Kontraposition
bzw. man führt einen Widerspruchsbeweis, indem man die Konvergenz annimmt und
daraus einen Widerspruch folgert.
Beispiel 4.1.8. Betrachte an := (−1)n .
Beh.
Wir kommen zurück zu dem Beispiel, das uns als Motivation für Definition 4.1.6 diente,
d. h. an = n1 , n ∈ N. Es liegt nahe:
n→∞
Vermutung: an −→ 0
Um das zu beweisen, benötigen wir ein weiteres Axiom:
Axiom A (Archimedes). N ist unbeschränkt.
Bemerkung 4.1.9. Auch wenn wir Axiom A als gegeben annehmen und nicht beweisen, so
es ist doch wenigstens plausibel:
Sei x obere Schranke mit Dezimaldarstellung x = x0 , x1 x2 x3 . . . mit x0 ∈ N und xi ∈
{0, 1, . . . , 9}, i ∈ N. Dann wähle x0 + 1 ∈ N .
| {z }
>x
Beispiele 4.1.10.
96
Die folgende Aussage erscheint auf den ersten Blick selbstverständlich (und ohne diese
Aussage wäre der Grenzwertbegriff ziemlich sinnlos), trotzdem muss sie bewiesen werden.
Proposition 4.1.11. Der Grenzwert a einer konvergenten Folge (an )n∈N ist eindeutig be-
stimmt.
|b−a|
Beweis. Angenommen b sei ein weiterer Grenzwert von (an )n∈N und a 6= b. Wähle ε := 2 >
0.
an , n ≥ n0 (ε)
a a+b b
2
ε ε
Dann existieren n1 und n2 ∈ N so dass |an − a| < ε für n ≥ n1 und |an − b| < ε für n ≥ n2
gelten. Sei n0 := max{n1 , n2 }. Dann gilt für n ≥ n0
Sei n ≥ n0
=⇒ |b − a| ≤ |b − an | + |an − a| < 2ε = |b − a|
Nächstes Ziel: Herleitung einiger Kriterien, mit deren Hilfe man die Konvergenz von Folgen
gut untersuchen kann, ohne die ε-Definition verwenden zu müssen. Dazu erinnern wir uns
zunächst an Beispiele 4.1.10: Mit bn = n1 , cn = n12 sowie an = 0 folgt
0 = an ≤ cn ≤ bn ∀n ∈ N.
Die Folge cn ist also „eingesperrt“ zwischen den Nullfolgen (an )n∈N und (bn )n∈N und ist daher
ebenfalls eine Nullfolge. Diese Schlussweise halten wir als Sandwichkriterium fest.
Proposition 4.1.12 (Sandwichkriterium). Betrachte Folgen (an )n∈N , (bn )n∈N , (cn )n∈N mit
lim an = lim bn = c. Weiter gelte:
n→∞ n→∞
∃N ∈ N ∀n ≥ N : an ≤ cn ≤ bn .
97
Seien n0 := max{N, n1 , n2 } und n ≥ n0 .
=⇒ c − ε < an ≤ cn ≤ bn < c + ε
=⇒ −ε < cn − c < ε =⇒ |cn − c| < ε
Beweis. Sei (an )n∈N mit lim an = a und ε = 1. Dann existiert ein n0 ∈ N so dass |an −a| < 1
n→∞
für alle n ≥ n0 gilt.
Definiere C := max{|a1 |, |a2 |, . . . , |an0 −1 |, |a| + 1}. Dann gilt |an | ≤ C für n ∈ N und
(an )n∈N ist beschränkt.
Bemerkung 4.1.14. Die Umkehrung von Proposition 4.1.13 ist falsch: Die Folge (an )n∈N
mit an = (−1)n ist beschränkt und divergent.
(1 + x)n ≥ 1 + nx ∀n ∈ N0 . (4.3)
IA (n = 0): 3
IS:
IV
nx2 ≥ 1 + (n + 1)x
(1 + x)n+1 = (1 + x)n (1 + x) ≥ (1 + nx)(1 + x) = 1 + (n + 1)x + |{z}
| {z }
≥0 ≥0
∀K > 0 ∃n ∈ N : q n > K
Beweis. Sei x := q − 1 > 0. Laut Bernoulli ist q n = (1 + x)n ≥ 1 + nx. Nach Archimedes gibt
es n ∈ N sodass n > K−1
x . Zusammen erhalten wir
K −1
qn > 1 + ·x=K
x
∀ε > 0 ∃n ∈ N : q n < ε
98
Beweis. Es gilt 1
q > 1. Sei ε > 0 beliebig.
n
Kor. 4.1.17 1 1
=⇒ ∃n ∈ N : > =⇒ ∃n ∈ N : q n < ε
q ε
Korollar 4.1.18. Für q ∈ (−1, 1) ist die Folge (nq n )n∈N beschränkt.
Beweis.
1. Fall: q = 0 Dann ist (nq n )n∈N = (0)n∈N die konstante Nullfolge und somit beschränkt.
2. Fall: q 6= 0 Setze
1
x := −1
|q|
Beachte, dass x = |q|
1
− 1 > 1 − 1 = 0. Somit können wir Bernoullis Ungleichung für x
anwenden. Dann gilt
n
1 Bernoulli Kehrwert 1 ·n>0 1
= (x+1)n ≥ 1+nx ≥ |{z} nx =⇒ |q|n ≤ =⇒ |nq n | = n|q|n ≤
|q| nx x
>0
Beispiele 4.1.19.
1 n→∞
(i) Sei k ∈ N. Da 0 ≤ 1
nk
≤ n −→ 0 ist nach Proposition 4.1.12 lim 1
k = 0.
n→∞ n
4. Fall: |q| > 1 Nach Korolar 4.1.16 ist (an )n∈N unbeschränkt und somit divergent
(Propostion 4.1.13).
Satz 4.1.20 (Rechenregeln für konv. Folgen). Es seien (an )n∈N und (bn )n∈N Folgen mit
lim an = a und lim bn = b. Dann gilt
n→∞ n→∞
99
(iii) Falls b 6= 0, gibt es N ∈ N sodass bn 6= 0 für alle n ≥ N , und es gilt
an a
lim = .
n→∞ bn b
Bemerkung 4.1.21. Für λ ∈ R folgt aus Satz 4.1.20 (ii) mit der konstanten Folge bn = λ
für n ∈ N, dass
lim (λ · an ) = λ · a
n→∞
3 + n − 4n2 n2 ( n32 + n1 − 4) 3
n2
+ 1
n −4 n→∞ −4
= = −→ = −2
6 + 2n2 n2 ( n62 + 2) 6
n2
+2 2
Hier haben wir letztlich alle drei Rechenregeln aus Satz 4.1.20 angewandt.
n
(ii) Betrachte sn := q k für |q| < 1. Dann liefert die geometrische Summenformel Satz
P
k=0
2.5.3
1 − q n+1 n→∞ 1
sn = −→ .
1−q 1−q
Dieses Beispiel wird uns später in Beispiel 4.3.6 im Zusammenhang mit der sog. geome-
trischen Reihe wieder begegnen.
Als nächstes formulieren wir nach Proposition 4.1.12 und Satz 4.1.20 weitere nützliche
Aussagen, auf deren Beweis wir hier verzichten.
Proposition 4.1.23. (i) Sei (bn )n∈N eine Nullfolge und |an − a| ≤ bn für alle n ∈ N. Dann
gilt lim an = a.
n→∞
(iii) Angenommen für Folgen (an )n∈N , (bn )n∈N mit lim an = a, lim bn = b existiert N ∈ N
n→∞ n→∞
so dass für n ≥ N
an ≤ bn .
Dann ist a ≤ b.
(iv) Sei (an )n∈N beschränkte Folge und (bn )n∈N Nullfolge. Dann ist (an ·bn )n∈N eine Nullfolge.
100
Beweis: Wir verzichten auf einen Beweis.
Aufgepasst! In Proposition 4.1.23 (ii) ist die Umkehrung falsch, wie das Beispiel
1 1
an = (−1)n zeigt.
Definition 4.1.24. Betrachte eine Folge (an )n∈N . Wir sagen (an )n∈N strebe gegen ∞ (oder
+∞), falls gilt:
∀K > 0 ∃N ∈ N ∀n ≥ N : K < an
n→∞ n→∞
Notation: lim an = ∞, an −→ ∞ Wir sagen (an )n∈N strebe gegen −∞, falls −an −→ ∞
n→∞
n→∞
gilt. Notation: lim an = −∞, an −→ −∞
n→∞
Beispiele 4.1.25.
(i) Die Folge (nk )n∈N strebt für jedes k ∈ N gegen unendlich.
2
(ii) Die Folge an = n n−1 ist divergent und strebt gegen ∞: Sei K ∈ N. Wir wollen ein N ∈ N
2
finden, so dass für alle n ≥ N die Ungleichung n n−1 > K gilt. Dazu bemerken wir
n2 − 1 1
an = =n− ≥ n − 1.
n n
|{z}
≤1
Wählen wir also zu gegebenem K > 0 eine natürliche Zahl N mit N > K + 1, so folgt
für n ≥ N , dass
1
an = n − ≥n−1≥N −1>K +1−1=K
n
gilt.
Satz 4.1.20 gibt eine Antwort für die Konvergenz und den Grenzwert eines Produktes von
zwei konvergenten Folgen. In der folgenden Proposition haben wir es mit einem Produkt von
zwei Folgen zu tun, wobei der eine Faktor (q n )n∈N eine Nullfolge ist und der andere Faktor
(nk )n∈N gegen unendlich strebt. Hier stellt sich die Frage „Wer gewinnt?“.
Proposition 4.1.27. Für k ∈ N0 , q ∈ (−1, 1) ist limn→∞ nk q n = 0
101
IV: Wir nehmen an, es gilt limn→∞ nk q n = 0 für ein k ∈ N und jedes −1 < q < 1.
IS: Wir müssen nun zeigen, dass für jedes −1 < q < 1, limn→∞ nk+1 q n = 0.
Sei also −1 < q < 1 beliebig. Setze r := |q|+1
2 . Daraus folgt, dass 0 ≤ |q| < r < 1
|q|
und 0 ≤ r < 1 (Die zweite Ungleichung erhalten wir durch Division der ersten durch
r > 0). Zusätzlich ist
n
Somit ist (nr ) · n |q|
n k
r als Produkt einer Nullfolge und einer beschränkten
n∈N
Folge nach Proposition 4.1.23 (iv) eine Nullfolge. Aus
n
|q|n
k+1 n k+1 n k+1 |q|
|n q − 0| = n |q| = n · r · n = (nrn ) · nk
n
r r
folgt dann schlussendlich mit Propostion 4.1.23 (i), dass limn→∞ nk+1 q n = 0.
Notation: Die Länge eines Intervalls I mit Grenzen a, b ∈ R, b ≥ a, bezeichnen wir mit
|I| := b − a.
−1 0 1
I1 [ ]
I2 [ ]
I3 [ ]
..
.
I10 [ ]
Beide Intervallgrenzen sind Nullfolgen. Daher ist es plausibel, dass es genau eine Zahl gibt
(und zwar 0), die in allen Intervallen In , n ∈ N, liegt. Typisch ist in diesem Beispiel, dass
• In+1 ⊂ In für n ∈ N ((an )n∈N ist monoton wachsend, (bn )n∈N ist monoton fallend)
n→∞
• bn − an −→ 0
gelten.
102
Definition 4.2.2. Unter einer Intervallschachtelung verstehen wir eine Folge (In )n∈N von
abgeschlossenen Intervallen In = [an , bn ], an ≤ bn , n ∈ N, mit folgenden Eigenschaften
(i) I1 ⊃ I2 ⊃ I3 ⊃ . . .
n→∞
(ii) |In | −→ 0.
lim an = c = lim bn .
n→∞ n→∞
∀n ∈ N : 0 ≤ |an − c| = c − an ≤ bn − an = |In |
∀n ∈ N : 0 ≤ |bn − c| = bn − c ≤ bn − an = |In |
Da |In | nach Annahme eine Nullfolge ist, erhalten wir gemäß Proposition 4.1.23 (i), dass
c = limn→∞ an = limn→∞ bn .
Bemerkung 4.2.4. Axiom I bringt uns einen ganz wesentlichen Schritt weiter, denn bisher
(siehe z. B. das ε-Kriterium Definition 4.1) mussten wir (im Wesentlichen) von vornherein
den Grenzwert einer Folge kennen, um auf Konvergenz schließen zu können. Axiom I (mit
Proposition 4.2.3) versetzt uns jetzt aber in die Lage, die Konvergenz einer Folge zu beweisen,
ohne den Grenzwert vorher schon zu kennen. Das ist ein ganz wichtiger Fortschritt, und wir
werden das auch noch im Zusammenhang mit einigen folgenden zentralen Konvergenzkriterien
genauer sehen.
Beweis.
103
(i) Zum Nachweis der Monotonie betrachten wir en
en−1 für n ≥ 2. Zu zeigen ist also
en
> 1 für n ≥ 2.
en−1
Es gilt
1 n+1 1 n
1+ = für n ∈ N bzw. 1+ = für n ≥ 2. (4.4)
n n n−1 n−1
Daraus folgt für n ≥ 2
n n−1 n−1 !n−1
n2 − 1
en n+1 n−1 n+1 n+1 n−1 n+1
= = · =
en−1 n n n n n n n2
1 n−1 n + 1 n2 − n + 1
n+1 Bernoulli n+1 1
= 1− 2 ≥ 1 − (n − 1) 2 = ·
n n 4.1.15 n n n n2
n3 + 1 1
= 3
= 1+ 3 >1
n n
(ii) Wir beweisen nun, dass (En )n∈N streng monoton fällt. Sei dazu wieder n ≥ 2.
n n+1 !n !n
n2 n2 − 1 + 1
En−1 (4.4) n n n n
= = =
En n−1 n+1 n + 1 n2 − 1 n+1 n2 − 1
!n n
n2 − 1
n 1 n 1
= + = 1+ 2
n+1 n2 − 1 n2 − 1 n+1 n −1
Bernoulli n n n 1 n n+1
≥ 1+ 2 > 1+ = = 1
4.1.15 n+1 n −1 n+1 n n+1 n
| {z }
n 1
> =n
n2
Korollar 4.2.6. (In )n∈N ist eine Intervallschachtelung, und damit sind (en )n∈N und (En )n∈N
konvergent mit
lim en = lim En .
n→∞ n→∞
Beweis. Wir zeigen also dass In = [en , En ] für n ∈ N die Bedingungen aus Definition 4.2.2
erfüllt.
e1 ≤ e2 ≤ . . . ≤ en < . . . < En ≤ . . . ≤ E2 ≤ E1
=⇒ [en , En ] ⊃ [en+1 , En+1 ] ∀n ∈ N
1 n+1 1 n 1 n 1 1 n
1
|In | = En −en = 1 + − 1+ = 1+ · 1+ −1 = 1 + ·
n n n n n n
|{z}
Nullfolge
104
Es gilt
1 n 1 n
1+ = 1+ = en < E1 .
n n
n
Somit ist 1 + n1 eine beschränkte Folge. Aus Proposition 4.1.23 (iv) folgt, dass
limn→∞ |In | = 0 und somit aus Axiom I und Bemerkung 4.2.3 die Behauptung.
Aus e1 ≤ e ≤ E1 folgt sofort, dass e ∈ [2, 4] gelten muss. Wir wollen aber noch mehr Eigen-
schaften und (bessere) Approximationen von e kennenlernen. Wir starten mit der Herleitung
einer alternativen Darstellung von e mit
n
X 1 1
an := , n ∈ N0 und bn := an + , n ∈ N.
k! n · n!
k=0
Wir wollen vorgehen wie zuvor und zeigen, dass [an , bn ] eine Intervallschachtelung liefert. An-
schließend beweisen wir, dass der zugehörige Grenzwert mit e übereinstimmt. Die wesentliche
Idee bei der Wahl der Folge (bn )n∈N ist es, die Folgenglieder an durch Addition von geeig-
neten monoton fallenden Termen so zu modifizieren, dass bn monoton fällt und gleichzeitig
n→∞
an − bn −→ 0 gilt.
Proposition 4.2.8. (i) Die Folge (an )n∈N ist streng monoton wachsend.
Korollar 4.2.9. Sei Jn := [an , bn ] für n ∈ N. Dann ist (Jn )n∈N eine Intervallschachtelung.
Insbesondere gilt also lim an = lim bn .
n→∞ n→∞
Beweis. Wir zeigen also dass Jn für n ∈ N die Bedingungen aus Definition 4.2.2 erfüllt.
105
(i) wie in Kor. 4.2.6.
1 n→∞
(ii) |Jn | = bn − an = n·n! −→ 0
Beh.
Behauptung: e ≥ a.
Beweis: Sei m ∈ N fest und n ≥ m.
n n
1 n
X n 1 X n n−1 n−k+1 1
=⇒ en = 1 + = k
= 1 + · · ... · ·
n k n n n n k!
k=0 k=1
m
X n n−1 n−k+1 1
≥ 1+ · · ... · ·
n n n k!
k=1
Beh.
106
Dann ergibt sich für n ∈ N
1 al − 1
=⇒ ≤ rn,l ≤
(n + 1)! (n + 1)!
lim
l→∞ 1 e−1
=⇒ ≤ e − an ≤ (4.7)
(n + 1)! (n + 1)!
1 e−1
=⇒ an + ≤ e ≤ an +
(n + 1)! (n + 1)!
1 (n + 1)!an − 1
an + ≤ e ≤ (4.8)
(n + 1)! (n + 1)! − 1
n = 1: Es ist
1
X 1 1 1
a1 = = + =2 und (1 + 1)! = 2.
k! 0! 1!
k=0
n = 2: Es ist
2
X 1 1 1 1 5
a2 = = + + = = 2.5 und (2 + 1)! = 3! = 6.
k! 0! 1! 2! 2
k=0
16 15 1 5 1 6 · 52 − 1 15 − 1 14
2.66 < = + = + ≤e≤ = = = 2.8.
6 6 6 2 6 6−1 5 5
e = 2.718281828459 . . .
107
An (4.7) kann man gut ablesen, dass die Folge an sehr schnell gegen e konvergiert, da (n+1)!
1
sehr schnell gegen Null konvergiert. Diese Approximation eignet sich daher sehr gut zur nä-
herungsweisen Bestimmung von e in Rechnern. Die Approximation durch die Folge en ist
deutlich schlechter/langsamer.
Eine weitere Eigenschaft der Eulerschen Zahl, die wir leicht beweisen können, ist die Tat-
sache, dass e irrational ist.
Satz 4.2.12 (Lambert 1767). Es gilt e ∈
/ Q.
1 p e−1
≤ − aq ≤ · q!
(q + 1)! q (q + 1)!
1 e−1 2
=⇒ 0< ≤ p · (q − 1)! − q!aq ≤ < ≤1
q+1 q+1 q+1
=⇒ 0 <p · (q − 1)! − q!aq < 1.
Wir werden nun zwei neue Begriffe kennenlernen, die einerseits sehr intuitiv sind, aber
andererseits häufig Schwierigkeiten machen. Um diese vorab zu erläutern, betrachten wir das
folgende Beispiel.
Beispiel 4.2.13. Sei an := (−1)n + n1 , n ∈ N, das heißt
3 2 5 4 7 6
(an )n∈N = 0, , − , , − , , − , . . . .
2 3 4 5 6 7
Dann ist (an )n∈N sicher divergent. Wenn wir aber nur die Folgenglieder mit geraden Indizes
n = 2k mit k ∈ N betrachten, dann ist die entsprechende Folge (a2k )k∈N konvergent, und zwar
mit Grenzwert 1. Wenn wir die Folge der Folgenglieder mit ungeraden Indizes n = 2k − 1,
k ∈ N, betrachten, so stellen wir fest, dass die entsprechende Folge (a2k−1 )k∈N ebenfalls
konvergiert, und zwar gegen −1. Man sagt, dass die Folge (an )n∈N die konvergenten Teilfolgen
(a2k )k∈N und (a2k−1 )k∈N besitzt. Weiterhin nennt man 1 und −1 Häufungspunkte der Folge
(an )n∈N .
Definition 4.2.14. Sei (an )n∈N eine Folge reeller Zahlen. Eine Zahl a ∈ R heißt Häu-
fungspunkt (HP) von (an )n∈N wenn es für jedes ε > 0 unendlich viele Glieder an gibt mit
|a − an | < ε
Bemerkung 4.2.15. Sei (an )n∈N eine Folge in R.
(i) a ist HP von (an )n∈N ⇐⇒ in jeder ε-Umgebung von a liegen unendlich viele Folgen-
glieder an
(ii) Aus lim an = a folgt, dass a der einzige HP von (an )n∈N ist, denn in diesem Fall liegen
n→∞
für beliebiges ε > 0 alle bis auf endlich viele Folgenglieder in der ε-Umgebung von a:
Beispiele 4.2.16. (i) an = (−1)n =⇒ (an )n∈N hat HPe 1 und −1.
108
n→∞
(ii) bn = n+1
n =⇒ bn −→ 1 =⇒ 1 ist einziger HP von (bn )n∈N .
Eine wichtige Konsequenz von Axiom I ist der folgende zentrale Satz der Analysis, dessen
Beweis auch einen gewissen „algorithmischen“ Charakter hat („Intervallhalbierungsverfah-
ren“).
Satz 4.2.17 (Satz von Bolzano-Weiertraß). Jede bechränkte Folge reeller Zahlen besitzt einen
(d. h. mindestens einen) HP.
=⇒ ∃k > 0 ∀n ∈ N : an ∈ [−k, k]
Halbiere [−k, k] =⇒ Eine der beiden Hälf-
ten [−k, 0] und [0, k] enthält unendlich viele −k k
Folgenglieder, bezeichne diese mit I1 (es gilt
|I1 | = k). Halbiere I1 und erhalte ein abge- I1 [ ] |I1 | = k
schlossenes Intervall I2 , in dem unendlich viele k
I2 [ ] |I2 | =
Folgenglieder liegen, wobei |I2 | = k2 gilt. Durch 2
Der zweite neue, angekündigte Begriff ist die Teilfolge. Die Teilfolge einer Folge ist das Ge-
genstück zur Teilmenge einer Menge. Da es aber bei einer Folge auf die Reihenfolge ankommt,
ist die Definition technisch ein wenig komplizierter, aber die Intuition sollte leicht zugänglich
sein: Man erhält aus einer gegebenen Folge eine Teilfolge durch Weglassen von (endlich oder
unendlich vielen) Folgengliedern. Es sollten aber schon unendlich viele Folgenglieder übrig
bleiben, damit das Ergebnis immer noch eine Folge ist.
Definition 4.2.18. Sei (an )n∈N eine Folge in R. Eine Folge (a0k )k∈N heißt Teilfolge (TF) von
(an )n∈N , falls es eine Folge (nk )k∈N von natürlichen Zahlen mit n1 < n2 < n3 < . . . gibt, so
dass
a0k = ank ∀k ∈ N gilt.
Beispiel 4.2.19. (i) Betrachte an = (−1)n . Dann sind (1, 1, 1, 1, . . . ) und (−1, −1, −1, −1, . . . )
TFen von (an )n∈N .
109
(ii) bn = 1
n =⇒ (bn )n∈N hat Teilfolgen (2−n )n∈N , (10−n )n∈N , ( n!
1
)n∈N .
k→∞
Proposition 4.2.20. Sei (an )n∈N konvergente Folge mit lim an = a. Dann gilt a0k −→ a
n→∞
für jede TF (a0k )k∈N von (an )n∈N .
Wie in Beispiel 4.2.13 angedeutet besteht ein enger Zusammenhang zwischen der Existenz
einer konvergenten Teilfolge und der Existenz eines Häufungspunktes:
Proposition 4.2.21. Ein a ∈ R ist HP der Folge (an )n∈N genau dann wenn eine TF (a0k )k∈N
von (an )n∈N existiert, die gegen a konvergiert: lim a0k = a.
k→∞
Beweis. „ =⇒ “: Wie konstruieren rekursiv eine Teilfolge (a0k )k∈N die gegen a konvergiert. Sei
a00 = a0 .
Angenommen a0k = ank ist gewählt. Da unendlich viele Glieder der Folge (an )n∈N in jeder
ε-Umgebung um a liegen, finden wir m > nk sodass |a − am | < k+1 1
. Setze a0k+1 = am .
Nach Konstruktion ist (ak )k∈N eine Teilfolge von (an )n∈N die gegen a konvergiert.
0
„ ⇐= “: Für ε > 0 liegen ab einem gewissen n0 ∈ N alle Folgeglieder der Teilfolge in der
ε-Umgebung um a und somit unendlich viele Glieder der ürsprünglichen Folge (an )n∈N .
Daher ist a ein HP der Folge.
Damit sind wir in der Lage den Satzes von Bolzano–Weierstraß umzuformulieren, indem
wir den Begriff des Häufungspunktes durch den der konvergenten Teilfolge ersetzen.
Satz 4.2.22 (Bolzano–Weierstraß). Aus jeder beschränkten Folge von reellen Zahlen kann
man eine konvergente Teilfolge auswählen.
Bemerkung 4.2.23. Der Satz von Bolzano–Weierstraß ist ein zentraler Satz der Analysis,
der vor allem für die weitere Entwicklung der Theorie wichtig ist. Für konkrete Anwendun-
gen ist er nicht so hilfreich, weil er nur die Existenz von Häufungspunkte bzw. konvergenten
Teilfolgen garantiert. Wollte man konkret solche bestimmen, könnte man das Intervallhal-
bierungsverfahren aus dem (konstruktiven) Beweis anwenden. Im Folgenden diskutieren wir
aber wichtige Konsequenzen, in deren Beweisen der Satz von Bolzano–Weierstraß eine wichtige
Rolle spielt.
Als nächstes diskutieren wir dabei Konvergenzkriterien für Folgen, bei denen man den
Grenzwert vorher nicht kennen muss.
Definition 4.2.24. Eine Folge (an )n∈N von rellen Zahlen heißt Cauchy–Folge (CF), falls
gilt
∀ε > 0 ∃n0 ∈ N ∀m, n ≥ n0 : |an − am | < ε.
Bemerkung 4.2.25.
110
(i) Grob gesprochen beschreibt diese sog. Cauchy-Folgen-Eigenschaft eine Eigenschaft, die
man als Verdichtung der Folge bezeichnen kann: Eine Folge ist eine Cauchy-Folge, wenn
die Folgenglieder untereinander beliebig wenig abweichen, falls nur die Indizes genügend
groß sind.
(ii) Dass die Indizes m und n einer Cauchy-Folge nach Überschreiten des Indexes n0 beliebig
weit auseinander liegen können, ist sehr wichtig: Es genügt keinesfalls, das Kleinwerden
des Abstandes nur für benachbarte Folgenglieder zu fordern, d. h. zu jedem ε > 0 gibt
es einen Index n0 ∈ N mit |an+1 − an | < ε für alle n ≥ n0 .
√
Dies zeigt das Gegenbeispiel an = n. Es gilt (3. binomische Formel):
√ √ √ √
√ √ ( n + 1 − n)( n + 1 + n)
an+1 − an = n + 1 − n = √ √
n+1+ n
n+1−n 1 n→∞
=√ √ ≤ √ −→ 0,
n+1+ n n
aber (an )n∈N ist unbeschränkt und damit divergent. Wir bemerken dabei, dass wir die
Wurzelfunktion erst in Kürze formal einführen, hoffen aber, dass das Beispiel auf der
Basis von Schulwissen verständlich ist.
(iii) Das Cauchy-Kriterium findet insbesondere bei der Untersuchung von Reihen häufig
Anwendung. Reihen sind Folgen von endlichen sogenannten „Partialsummen“
n
X
sn := ak , n∈N
k=1
Wir sehen nun, dass die Cauchy-Folgen genau die konvergenten Folgen in R sind.
Satz 4.2.26 (Cauchys Konvergenzkriterium). Eine Folge (an )n∈N konvergent genau dann
wenn sie eine CF ist.
Beweis.
„ =⇒ “: Sei ε > 0. Da (an )n∈N konvergent ist, gibt es n0 ∈ N, so dass für alle n > n0 :
ε
|an − a| <
2
Dann ist für alle n, m > n0
ε ε
|an − am | = |an − a + a − am | ≤ |an − a| + |a − am | = + =ε
2 2
„ ⇐= “: Sei (an )n∈N eine Cauchy-Folge. Wir zeigen zunächst, dass Cauchy-Folgen beschränkt
sind: Sei ε = 1 und n0 ∈ N, sodass für alle n, m > n0 ,
|an − am | < ε = 1
Dann sehen wir wie in Proposition 4.1.13, dass (|an |)n∈N durch
111
beschränkt ist.
Mit Bolzano-Weierstraß finden wir eine konvergente Teilfolge (ani )i∈N mit Grenzwert a.
Wir zeigen nun das (an )n∈N konvergent mit Grenzwert a ist. Sei dazu ε > 0. Da (ani )i∈N
konvergent mit Grenzwert a ist, gibt es i0 ∈ N so dass für alle i > i0 , |ani − a| < 2ε .
Nach der Cauchy-Bedingung für (an )n∈N , gibt es ein N ∈ N, sodass für alle m, n > N ,
|an − am | < 2ε . Sei i > i0 , sodass ni > N . Dann gilt für n > N :
ε ε
|an − a| = |an − ani + ani − a| ≤ |an − ani | + |ani − a| < + =ε
2 2
Als Konsequenz und Anwendung wollen wir nun Dezimalbrüche und deren Konvergenz
untersuchen.
Satz 4.2.27 (Konvergenz von Dezimalbrüchen). Seien k0 ∈ Z und kj ∈ {0, 1, . . . , 9} für
n
kj · 10−j gegen eine reelle Zahl.
P
j ∈ N. Dann konvergiert der Dezimalbruch an :=
j=0
m−n−1
X j+n+1 m−n−1 j n+1
Indexshift 1 X 1 1
= 9 = 9 ·
10 10 10
j=0 j=0
n+1 n
1 10 1
= 9 · = = 10−n
10 9 10
Bemerkung 4.2.28. Jede relle Zahl lässt sich durch eine Folge von Dezimalbrüchen wie in
4.2.27 darstellen. Üblicherweise schreibt man dann eine reelle Zahl a mit Folge von Dezinmal-
brüchen wie in Satz 4.2.27 in der Dezimalschreibweise
a = k0 , k1 k2 k3 k4 . . . bzw.
a = k0 .k1 k2 k3 k4 . . .
112
Beispiel 4.2.29. Wir untersuchen die Dezimalschreibweise von 13 und vermuten, dass 1
3 =
0.333333 . . . gilt. Und tatsächlich folgt
Xn n
X
0.333333 . . . = lim 3 · 10−j = 3 lim 10−j − 1
n→∞ n→∞
j=1 j=0
!
1 − 10−(n+1)
1
= 3 lim −1 = 3 −1
n→∞ 1 − 10−1 1 − 10−1
10 10 − 9 1 1
=3 −1 = 3· = 3· = .
9 9 9 3
Auch der nächste Satz liefert die Konvergenz einer Folge, ohne dass man vorher den Grenz-
wert kennen müsste. Daher handelt es sich um ein äußerst nützliches hinreichendes Kriterium
für die Konvergenz einer Folge. Wenn man weiß, dass eine Folge konvergiert, kann man dann
häufig „nachträglich“ den Grenzwert bestimmen, wie wir später sehen werden.
Satz 4.2.30. Jede monoton wachsende, nach oben beschränkte Folge konvergiert.
Beweis. Sei (an )n∈N eine monoton wachsende Folge die durch C ∈ R beschränkt ist. Wir
zeigen, dass die Cauchy-Bedingung für (an )n∈N erfüllt ist.
Angenommen nicht: Dann gibt es ε > 0, so dass für jedes n0 ∈ N, n, m ∈ N mit n0 < n, m
existieren, sodass |an − am | > ε. Wir wählen nun rekursiv für i ∈ N Glieder ani aus der Folge
(an )n∈N folgendermaßen aus: Sei an1 = a1 . Wenn ni für i ∈ N gegeben ist, wähle m1 , m2 ∈ N,
so dass ni < m1 ≤ m2 und |am2 − am1 | > ε. Beachten Sie, dass für m > n, am − an ≥ 0, da
die Folge monoton wachsend ist. Daher ist
Setze ni+1 = m2 . Es gilt also |ani+1 − ani | > ε für alle i ∈ N. Wähle eine natürliche Zahl
K > C−aε
1
+ 1, welche gemäß Archimedes existiert. Dann ist
Korollar 4.2.31. Jede monoton fallende, nach unten beschränkte Folge konvergiert.
Beweis. Sei (an )n∈N monoton fallend mit an ≥ K für n ∈ N. Sei bn := −an , n ∈ N. Dann ist
(bn )n∈N monoton wachsend mit bn = −an ≤ −K für n ∈ N
S.4.2.30 n→∞ n→∞
=⇒ ∃b ∈ R : bn −→ b =⇒ an = −bn −→ −b
Wir können als erstes Anwendungsbeispiel für Satz 4.2.30 nun zur Existenz von Quadrat-
wurzeln, d. h. zur Lösbarkeit von Gleichungen x2 = a, a ≥ 0, für die Unbekannte x, übergehen.
113
Satz 4.2.32. Sei a ≥ 0. Dann existiert genau ein x ≥ 0 mit x2 = a.
Beweis.
1. Fall: x + y = 0 Da x, y ≥ 0 folgt x = y = 0.
2. Fall: x − y = 0 Dann ist x = y.
Behauptung: (i) xn > 0 ∀n ∈ N. Insbesondere ist (xn )n∈N nach unten beschränkt.
(ii) (xn )n∈N ist monoton fallend (und damit konvergent nach Kor. 4.2.31),
(iii) für x := lim xn gilt x2 = a.
n→∞
Beweis:
(i) Wir zeigen dies per Induktion:
IA (n = 0): x0 > 0
IV: xn > 0 für ein n ∈ N
IS: xn+1 = 21 xn + xan ≥ 21 xn > 0
(ii) Für c, d ∈ R gilt
a 1 a 2
a = xn · ≤ xn + = (xn+1 )2 für n ∈ N0 . (4.11)
xn 2 xn
1 2 a 2 1 x4
x2n+1 = xn + 2a + ≤ x2n + 2x2n + n2 = x2n
4 xn 4 xn
xn , xn+1 >0
=⇒ xn+1 ≤ xn .
n→∞
(iii) Wir wollen in (4.9) auf beiden Seiten der Gleichung den Grenzwert für −→
bilden. Da wir leider durch xn auf der rechte Seite teilen, müssen wir eine
Fallunterscheidung machen.
1. Fall: a = 0 In diesem Fall gilt
n+1
1 1 1
xn+1 = xn = xn−1 = . . . = · x0
2 4 2
n→∞
=⇒ xn −→ 0 =⇒ x=0 =⇒ x2 = 0.
114
2. Fall: a>0 Aus Gleichung (4.11) erhalten wir x2 = lim x2n ≥ a > 0 und
n→∞
aus (i) folgt x ≥ 0. Somit ist auch x > 0 (denn für x = 0 ist x2 = 0.)
In diesem Fall können wir in (4.9) auf beiden Seiten der Gleichung den
n→∞
Grenzwert für −→ bilden und erhalten:
1 a 1 a
x = lim xn+1 = lim xn + = x+
n→∞ n→∞ 2 xn 2 x
a a
=⇒ 2x = x + =⇒ x= =⇒ x2 = a.
x x
Beh.
Bemerkung 4.2.33. Die Iteration (4.9) ist von praktischem Nutzen, denn man kann sie zur
Approximation von Wurzeln im Rechner benutzen. Für eine kurze Rechenzeit ist es dabei
wichtig, dass das Verfahren möglichst schnell konvergiert. Das wollen wir jetzt näher unter-
suchen. Für a = 2 und Startwert x0 = 2 ergeben sich beispielsweise die Iterationswerte
n xn
0 2
1 1.5
2 1.41667
3 1.414215686
4 1.4142135623746899
5 1.4142135623730950488016896
6 1.414213562373095048801688724209698078570
Man erhält mit jedem Iterationsschritt etwa doppel so viele richtige Stellen wie zuvor. In der
√
Praxis betrachtet man häufig den Fehler dn := xn − a
n gültige Stellen dn
1 1 ≤ 1 = 100
2 3 ≤ 0.01 = 10−2
3 6 ≤ 0.00001 = 10−5
4 12 ≤ 0.00000000001 = 10−11
5 24 ≤ 0.00000000000000000000001 = 10−23
Es liegt nahe, dass der Fehler quadratisch in n abnimmt. Das können wir auch beweisen:
√ √ √
1 a 1 2 1
dn+1 = xn+1 − a = xn + − a= xn + a − 2xn a = (xn − a)2
2 xn 2xn 2xn
1 1
≤ √ (xn − a)2 = √ d2n .
2 a 2 a
115
q Für den Fall a < 1 kann man bei der praktischen Berechnung einfach zur Berechnung von
a übergehen (und die quadratische Konvergenz ausnutzen) und anschließend den Kehrwert
1
nehmen.
Definition 4.2.34. Sei a ≥ 0. Die eindeutige Lösung x ≥ 0 von x2 = a aus 4.2.32 heißt
Quadratwurzel von a.
√ 1
Notation: x = a = a 2 .
Bemerkung 4.2.35. Die Potenzfunktion
Beweis.
1. Fall: a = 0 Sei ε > 0 beliebig. Wähle n0 ∈ N mit an < ε2 für alle n ≥ n0 . Dann ist
√
an < ε für alle n ≥ n0
Beispiele 4.2.37.
1 n→∞ n→∞
(i) n −→ 0 =⇒ √1 −→
n
0
√ n→∞
(ii) Es gilt zwar n −→ ∞, aber (vgl. Bem. 4.2.25)
√ √ n+1−n 1 1 n→∞
0≤ n+1− n= √ √ =√ √ ≤ √ −→ 0.
n+1+ n n+1+ n n
√
Lemma 4.2.38. Es gilt 2 ∈ R \ Q.
p2
2= =⇒ 2q 2 = p2 =⇒ p2 ist gerade =⇒ p ist gerade
q2
116
(Da p2 ungerade wenn p ungerade ist). Schreibe p = 2n mit n ∈ N.
Das Vorgehen bzgl. der Einführung der Quadrat-Wurzel kann verallgemeinert werden:
Bemerkung 4.2.39. Ähnlich wie in Satz 4.2.32 zeigt man, dass für a ∈ R, a > 0 und
k ∈ N, k ≥ 2 die rekursiv definierte Folge
1 a
xn+1 := (k − 1)xn + k−1 , n ∈ N0 (4.12)
k xn
für jeden Startwert x0 > 0 konvergiert, da sie monoton fällt und nach unten beschränkt ist.
Der Grenzwert x = lim xn ist die eindeutige positive Lösung der Gleichung xk = a.
n→∞
√ 1
Notation: x = k
a = a k heißt k-te Wurzel von a.
Weiter definieren wir die Potenzfunktion
Diese ist eine surjektiv und streng monoton wachsend. Sie hat daher nach Satz 2.7.18 eine
streng monoton wachsende Umkehrfunktion p−1 : [0, ∞) → [0, ∞). (streng monoton wach-
k √
send) mit Definitionsbereich [0, ∞) (surjekiv). Es gilt p−1
k (x) =
k
x für x ≥ 0.
Mit Hilfe des ε-Kriterium zeigt man leicht die folgenden interessanten Grenzwerte von
Folgen, die mit n-ten Wurzeln definiert sind.
√
Beispiele 4.2.40. (i) Für a > 0 gilt lim n a = 1.
n→∞
√
(ii) Weiter gilt sogar lim n
n = 1.
n→∞
Wir sind nun in der Lage, rationale Potenzen positiver reeller Zahlen zu definieren.
p
Definition 4.2.41 (Rationale Potenzen). Sei a > 0 und sei r = q ∈ Q mit p ∈ Z und q ∈ N.
Dann definieren wir p √
ar := a q := ( q ap ). (4.13)
Weiter definieren wir 0r := 0 für r > 0 sowie die rationale Potenzfunktion
Proposition 4.2.42.
(i) Zunächst bemerken wir, dass die rationale Potenz in Definition wohldefiniert ist, d. h. wenn
wir den Bruch f = pq erweitern oder kürzen, ändert sich der Wert von r nicht, und damit
darf sich der Wert von ar nicht ändern.
117
(iii) Weiter gilt das Rechengesetz („Funktionalgleichung“)
Beweis.
p kp
(i) Sei r = q = kq mit k ∈ N. Dann gilt
√
kq
√
kq
(( akp )q )k = ( akp )kq = akp = (|{z}
ap )k
| {z }
≥0 ≥0
√
kq
√
kq √
=⇒ ( akp )q = ap =⇒ ( akp ) = q
ap = ar
In beiden Implikationen benutzen wir, dass die Wurzelfunktionen bijektive Abbildung
von [0, ∞) → [0, ∞) ist. In der zweiten Implikation benutzen wir außerdem, dass die
q-te Wurzelfunktion die Umkehrfunktion der q-ten Potenzfunktion ist.
p
(iii) Zum Beweis von (4.16) seien r = q und s = u
v mit p, u ∈ Z und q, v ∈ N. Dann gilt
r + s = pv+qu
qv und somit
pv+qu √ √ √
ar+s = a qv = ( qv a)pv+qu = ( qv a)pv · ( qv a)qu = ar · as .
Die Beweise von (4.17) verschieben wir auf Abschnitt ??, wo wir eine Darstellung der
allgemeinen Potenzen mit Logarithmus und Exponentialfunktion behandeln werden.
Wir haben nun also die Quadratwurzel, allgemeine Wurzeln und rationale Potenzen ken-
nen gelernt. Als nächstes definieren wir allgemeine Potenzen, also auch irrationale Potenzen.
Dabei benutzen wir die Tatsache, dass jede reelle Zahl durch eine Folge von rationalen Zahlen
approximiert werden kann. Einen besonders eleganten und nützlichen Zugang zur allgemeinen
Potenzen werden wir später mit Hilfe der Exponentialfunktion diskutieren.
n→∞
Proposition 4.2.43. Sei a > 0, und sei x ∈ R. Weiter seien rn ∈ Q, n ∈ N mit rn −→ x.
Dann existiert der Grenzwert
z := lim arn , (4.18)
n→∞
und dieser Grenzwert ist unabhängig von der Wahl der Folge (rn )n∈N in Q. Falls x ∈ Q ist,
gilt
lim arn = ax . (4.19)
n→∞
118
Beweis: Wir verzichten auf einen Beweis.
Definition 4.2.44 (allgemeine Potenzen). Seien a ≥ 0 und x ∈ R. Wir definieren die allge-
meine Potenz ax durch
ax := lim arn , (4.20)
n→∞
n→∞
wobei (rn )n∈N eine beliebige Folge in Q ist mit rn −→ x.
Bemerkung 4.2.45. (i) Gleichung (4.19) garantiert, dass Definition 4.2.44 kompatibel
mit der Definition für rationale Potenzen ist.
(ii) Die Rechenregel (4.16) bleibt auch für allgemeine relle Potenzen gültig.
Zum Abschluss dieses Abschnittes wollen wir noch einige Eigenschaften von R und Q be-
sprechen. Insbesondere werden wir die Tatsache diskutieren, dass man jede reelle Zahl sowohl
durch rationale Zahlen als auch durch irrationale Zahlen annähern kann. Zunächst werden wir
aber einige Bezeichnungen kennenlernen, die in vielen Programmiersprachen verbreitet sind.
Proposition 4.2.46. Zu x ∈ R existiert genau ein m ∈ Z mit m ≤ x < m + 1.
Bemerkung 4.2.47. (i) Die Gaußklammer einer reellen Zahl x ist also die größte ganze
Zahl, die kleiner oder gleich x ist. Man nennt die Gauß-Klammer daher auch Abrun-
dungsfunktion. Sie wird alternativ auch mit bxc := [x] bezeichnet. Man nennt die
Gaußklammer insbesondere in Programmiersprachen „floor“ („Boden“).
Der folgende Satz besagt, dass zu zwei beliebigen reellen Zahlen a und b eine rationale Zahl
existiert, die zwischen a und b liegt. Man sagt, dass die Menge der rationalen Zahlen dicht
in der Menge der reellen Zahlen ist.
Satz 4.2.49. Q ist dicht in R, d. h. ∀a, b ∈ R mit a < b ∃q ∈ Q : a < q < b.
Die Beweisidee liegt darin, dass man das Intervall (a, b) durch Skalierung mit einem hin-
reichend großen Faktor n ∈ N so sehr in die Länge streckt, dass es eine ganze Zahl m im
gestreckten Intervall (na, nb) gibt. Dann sollte der Quotient m
n in (a, b) liegen.
Beweis. Es gilt b − a > 0 gilt. Dann wählen wir nach Archimedes ein n ∈ N mit
1
n> =⇒ nb − na > 1 =⇒ nb > na + 1
b−a
Nach Proposition 4.2.46 gibt es m0 = [na] ∈ Z sodass m0 ≤ na < m0 + 1. Wähle m = m0 + 1.
Dann ist na < m ≤ na + 1 < nb und somit a < m n < b mit n ∈ Q.
m
119
Satz 4.2.50. R \ Q ist dicht in R, d. h. zu a, b ∈ R mit a < b existiert ξ ∈ R \ Q mit a < ξ < b.
Beweis. Wähle mit Satz 4.2.49 q1 , q2 ∈ √ Q mit a < q1 < b und q1 < q2 < b. Definiere
ξ := q1 + q2√−q
2
1
. Dann ist q 1 < ξ < q 2 , da 2>1
a q1 ξ q2 b
√ q2 −q1
Weiter gilt ξ ∈
/ Q, denn sonst wäre 2= ξ−q1 ∈Q zu Lemma 4.2.38
Korollar 4.2.51. Für alle x ∈ R existieren Folgen (rn )n∈N in Q und (sn )n∈N in R \ Q mit
n→∞ n→∞
rn −→ x und sn −→ x.
Korollar 4.2.51 liefert also die angekündigte Aussage, dass man jede reelle Zahl sowohl
durch rationale als auch durch irrationale beliebig approximieren kann. Eine weitere zentrale
Eigenschaft der reellen Zahlen ist Inhalt des folgenden Satzes.
Satz 4.2.52. Die Menge R der reellen Zahlen ist überabzählbar.
Beweis. Wir zeigen, dass I := (0, 1) überabzählbar ist. Es reicht dabei die folgende Behaup-
tung zu beweisen:
Behauptung: Zu jeder Folge (xn )n∈N mit xn ∈ I für alle n ∈ N existiert z ∈ I mit z 6= xn für
alle n ∈ N.
Beh.
120
Korollar 4.2.53. Die Menge der irrationalen Zahlen R \ Q ist überabzählbar.
Beweis. Wir nehmen an R \ Q sei abzählbar. Da Q abzählbar ist, folgt mit Satz 1.4.7(ii) dass
Q ∪ R \ Q abzählbar wäre. zu Satz 4.2.52
Unendliche Reihen sind uns bereits im Zusammenhang mit der Dezimaldarstellung einer reel-
len Zahl begegnet (siehe z. B. Satz 4.2.27). Dabei haben wir eine reelle Zahl x ∈ R dargestellt
als
n
X
x = x0 .x1 x2 x3 . . . = x0 + x1 · 10−1 + x2 · 10−2 + x3 · 10−3 + . . . = lim xk · 10−k
n→∞
k=0
∞
Bemerkung 4.3.2. Der Ausdruck ak hat eine dopplete Bedeutung:
P
k=1
• Einerseits ist damit die Folge (sn )n∈N der Partialsummen gemeint. Insbesondere kann
∞
ak konvergieren oder divergieren.
P
k=1
∞
• Andererseits ist mit ak auch der Wert bzw. die Summe der Reihe im Falle der
P
k=1
Konvergenz gemeint, also der Grenzwert der Folge der Partialsummen.
Bemerkung 4.3.3. Häufig starten Reihen nicht unbedingt mit dem Index 1 sondern ab
∞
einem k0 ∈ Z. Dann lauten Definitionen und Sätze völlig analog für Reihen der Form
P
ak
k=k0
für Folgen (ak )k≥k0 . Die Begründung dafür liegt darin, dass für l > k0 die drei Reihen
∞
X ∞
X ∞
X
ak , ak0 +j−1 und ak
k=k0 j=1 k=l
121
entweder alle konvergieren oder alle divergieren, also alle dasselbe „Konvergenzverhalten“
aufweisen. Im Fall der Konvergenz gilt
∞
X ∞
X ∞
X
ak0 +j−1 = ak = ak0 + . . . + al−1 + ak .
j=1 k=k0 k=l
Für konvergente Reihen können also insbesondere endliche viele Summanden aus der Reihe
„abgespalten“ werden.
∞
Bemerkung 4.3.4 (Notwendiges Kriterium). Für die Konvergenz einer Reihe ak gilt das
P
k=1
folgende notwendige Kriterium
∞
X (4.21)
ak konvergent =⇒ lim ak = 0
k→∞
k=1
Weiter: Sei
∞
X ∞
X n
X
rn := ak = ak − ak = s − sn
k=n+1 k=1 k=1
| {z }
=:s
=⇒ r := lim rn = 0
n→∞
Die notwendige Bedingung aus Bem. 4.3.4 ist nicht hinreichend wie das folgende Beispiel
zeigt:
Beispiel 4.3.5. Wir betrachten die harmonische Reihe k . Es gilt lim k = 0.
P 1 1
k≥1 k→∞
1 1 1 1 1 1 1
s = 1+ + + + + + + + ...
2 3 4 5 6 7 8
1 1 1 1 1 1 1 1
> + + + + + + + +...
|2 {z 2} |4 {z 4} |6 {z 6} |8 {z 8}
=1 = 12 = 13 = 14
1 1 1
= 1+ + + + ... = s
2 3 4
Beh.
122
∞
Die Konvergenz der Reihe ak impliziert also die Bedingung
P
Aufgepasst!
k=1
lim ak = 0. Umgekehrt gibt es Nullfolgen (bk )k∈N , sodass die zugehörige Reihe
k→∞
∞
1 k=1 bk nicht konvergiert. Wir sagen, die Bedingung (das Kriterium) k→∞
P
lim ak = 01
∞
ist notwendig aber nicht hinreichend für die Konvergenz der Reihe ak . Auch
P
k=1
wenn die aufsummierten Folgenglieder immer kleiner werden und gegen 0 konvergie-
ren, muss die Summe nicht konvergieren.
∞
xk heißt geometrische Reihe.
P
k=0
∞
X 1
=⇒ xk = für |x| < 1. (4.22)
1−x
k=0
∞
„ =⇒ “: Durch Kontraposition: Für |x| ≥ 1 ist xk keine Nullfolge und xk somit divergent.
P
k=0
Bemerkung 4.3.7 (Reihen mit positiven Summanden). Sei ak ≥ 0 für alle k ∈ N und
n
ak . Dann gilt:
P
sn :=
k=1
∞
X
ak konvergent ⇐⇒ (sn )n∈N beschränkt
k=1
Beweis. „ ⇐= “: Wegen ak ≥ 0 für alle k ∈ N ist (sn )n∈N monoton wachsend. Da (sn )n∈N
∞
nach Annahme beschränkt ist, ist ak konvergent nach Satz 4.2.30.
P
k=1
123
∞
ak < ∞ (für ak ≥ 0).
P
Notation:
k=1
∞
Wir betrachten weiter Reihen ak mit positiven Summanden. Wenn die einzelnen Folgen-
P
k=1
glieder nach oben durch Folgenglieder einer konvergenten Reihe abgeschätzt werden können,
∞
dann wird dadurch auch die Konvergenz der Reihe ak erzwungen:
P
k=1
Dann gilt:
∞
P ∞
P
(i) bk konvergent =⇒ ak konvergent
k=1 k=1
∞
P ∞
P
(ii) ak divergent =⇒ bk divergent
k=1 k=1
Bemerkung 4.3.9.
∞ ∞ ∞
(i) In der Situation von (4.23) heißt bk Majorante von ak und ak heißt Mino-
P P P
k=1 k=1 k=1
∞
rante von bk .
P
k=1
(ii) Satz 4.3.8 erlaubt es, auf die Konvergenz/Divergenz einer Reihe zu schließen ohne die
Definition anzuwenden und die Folge der Partialsummen zu untersuchen.
∞
Somit ist (sn )n∈N beschränkt und folglich konvergent, d. h. ak ist konvergent.
P
k=1
Es folgen zwei weitere Kriterien, die es möglich machen auf Konvergenz/Divergenz zu schlie-
ßen, ohne dass man die Definition bemühen muss. Das erste Kriterium folgt aus Satz 4.3.8
durch einen passenden Vergleich mit der geometrsichen Reihe.
√
Satz 4.3.10 (Wurzelkriterium). Es sei ak ≥ 0 für alle k ∈ N, und es existiere w := lim k ak .
k→∞
Dann gilt:
124
∞
P
(i) w < 1 =⇒ ak konvergent.
k=1
∞
P
(ii) w > 1 =⇒ ak divergent.
k=1
Beweis.
∞ q
k3 k3
Beispiel 4.3.11. Die Reihe ist konvergent, denn w := lim k 1
P
3k 3k
= 3 < 1.
k=1 k→∞
Aufgepasst! Es genügt nicht, |ak | < 1 für (fast) alle k nachzuweisen, wie das
p
k
1 1
folgende Beispiel zeigt.
r
1 k 1
<1 ⇐⇒ <1
k k
ist erfüllt für alle k ≥ 2, dennoch divergiert die Reihe. Das Wurzelkriterium liefert für die
harmonische Reihe r
k 1
w := lim =1
k→∞ k
und erlaubt daher keine Aussage über Konvergenz bzw. Divergenz.
Satz 4.3.13 (Quotientenkriterium). Es sei ak > 0 für alle k ∈ N, und es existiere v :=
a
lim k+1
ak . Dann gilt
k→∞
∞
P
(i) v < 1 =⇒ ak konvergent
k=1
∞
P
(ii) v > 1 =⇒ ak divergent
k=1
125
Beweis.
(i) Vergleich mit geometrischer Reihe: Wegen v < 1 existieren ein q ∈ [v, 1) und ein k0 ∈ N
so dass für alle k ≥ k0
ak+1
≤q
ak
gilt. Dann folgt für k ≥ k0 (mit k1 = k − k0 ∈ N)
ak0 k0 +k1 ak
ak = ak0 +k1 ≤ ak0 +k1 −1 q ≤ ak0 +k1 −2 q 2 ≤ . . . ≤ ak0 q k1 = q = k00 q k ,
q k0 q
∞ ∞
und damit ist q k konvergente Majorante für ak .
P P
k=1 k=1
(ii) Wegen v > 1 existieren ein r > 1 und ein k1 ∈ N so dass für alle k ≥ k1
ak+1
≥r
ak
gilt. Dann folgt für k ∈ N
ak+1
1 Aufgepasst! Es genügt nicht, ak < 1 für (fast) alle k nachzuweisen. 1
Beispiel 4.3.14. Wir betrachten wieder die harmonische Reihe, und es gilt
ak+1 k
= < 1 für k ∈ N.
ak k+1
Trotzdem divergiert die harmonische Reihe. Weiterhin gilt
ak+1
v = lim = 1.
k→∞ ak
Das Quotientenkriterium liefert also keine Aussage über Konvergenz/Divergenz der harmoni-
schen Reihe.
Bemerkung 4.3.15. Satz 4.3.13 ist auch für Reihen ak mit ak ≥ 0 für k ∈ N anwendbar:
P
Man lässt die Summanden mit ak = 0 einfach weg, jedenfalls wenn nicht nur endlich viele
der ak von Null verschieden sind, aber in diesem Fall wäre die Reihe tatsächlich eine endliche
Summe und damit konvergent.
Beispiele 4.3.16.
126
P xk
(i) Sei x ∈ R+ . Dann betrachten wir die Reihe k! . Dann gilt für x > 0
k
√ 1 1 1 k→∞
lim k
ak = lim √ = lim α = 1 da k k −→ 1
k→∞ k→∞ k k α k→∞ k k
ak+1 kα
Ebenso lim = lim =1
k→∞ ak k→∞ (k + 1)α
Wurzel- und Quotientenkriterium können nicht angewendet werden. Für solche Fälle
lernen wir später das Integralkriterium kennen.
127
Das folgende Kriterium betrifft alternierende Reihen, das sind Reihen bei denen aufein-
ander folgende Summanden unterschiedliche Vorzeichen haben, d. h. mit ak ≥ 0, k ∈ N ist
∞
(−1)k+1 ak eine alternierende Reihe. Typisches Beispiel ist die alternierende harmoni-
P
k=1
∞
(−1)k+1 k1 = 1 − 1 1 1
+ . . .. Das wesentliche hinreichende Kriterium für
P
sche Reihe 2 + 3 − 4
k=1
die Konvergenz einer alternierenden Reihe ist das sog. Leibniz-Kriterium.
Satz 4.3.17 (Leibniz-Kriterium). Sei (ak )k∈N monoton fallende Nullfolge mit ak ≥ 0 für alle
∞
(−1)k+1 ak konvergent („alternierende Reihe“).
P
k ∈ N. Dann ist
k=1
n
Beweis. Sei sn := (−1)k+1 ak . Ziel ist es, Intervallschachtelungen aus den sn basteln. Für
P
k=1
j ∈ N gilt
konvergiert
Wir haben jetzt eine Reihe von Kriterien bzgl. der Kovergenz/Divergenz von Reihen ken-
nengelernt. Wenn man nun eine gegebene Reihe auf Konvergenz untersuchen möchte, stellt
sich die Frage, wie man vorgeht, welches Kriterium man wählt oder ob man etwa mit der
Definition argumentiert. Es folgt eine grobe Hilfe aber kein Kochrezept.
128
Konvergenz bei Reihen: Wenn man eine Reihe ak auf Konvergenz untersu-
P
chen will, geht man am besten so vor:
• Überprüfe, ob die Folge (ak )k∈N überhaupt eine Nullfolge ist. Ist das nicht der
Fall, ist die Reihe divergent.
• Liegt eine alternierende Reihe vor, so kann das Leibniz-Kriterium eine Antwort
geben.
1 1
• Tauchen in den ak Fakultäten auf, bietet sich häufig das Quotientenkriterium
an.
• Tauchen in den ak Potenzen (also Terme der Form (·)k ) auf, dann hilft oft das
Wurzelkriterium weiter.
Letztlich muss man häufig etwas herumprobieren, welches Kriterium weiterhilft oder
ob man ggf. die Definition verwendet.
Aufgepasst! Bei konvergenten Reihen darf man Klammern beliebig setzen, aber
1 1
man darf Klammern im Allgemeinen nicht weglassen.
129
Reihe
1 1 1 1 1 1 1 1 1
− + − − + −
1− − + − ...
2 4 3 6 8 5 10 12 7
1 1 1 1 1 1 1 1 1 1
= 1− − + − − + − − + − − ...
2 4 3 6 8 5 10 12 7 14
1 1 1 1 1 1 1
= − + − + − + ∓ ...
2 4 6 8 10 12 14
∞
1 X (−1)k+1 1
= = log 2
2 k 2
k=1
In obigem Beispiel haben wir die Reihenfolge der Summanden derart geändert, dass die
negativen Summanden „schneller“ aufsummiert werden als die positiven. Diese Umordnung
hat dann den Reihenwert entsprechend verkleinert.
Wir werden aber sehen, dass Umordnungen unter geeigneten Voraussetzungen erlaubt sind.
Dazu benötigen wir einen neuen Begriff.
∞ ∞
Definition 4.4.3. Eine Reihe ak heißt absolut konvergent, falls |ak | konvergiert.
P P
k=1 k=1
∞
(−1)k+1
Zurück zu obigem Beispiel: konvergiert, aber nicht absolut.
P
k
k=1
∞
P ∞
P
Proposition 4.4.4. ak absolut konvergent =⇒ ak konvergent
k=1 k=1
m
Beweis. Seien ε > 0 und n0 ∈ N, so dass |ak | < ε für m, n ≥ n0 , m > n
P
k=n+1
m m n n
! ! !
X X X X
=⇒ ak ≤ |ak | < ε d. h. |ak | CF =⇒ ak CF
k=n+1 k=n+1 k=1 n∈N k=1 n∈N
| {z }
=sm −sn
Bemerkung 4.4.5. Man kann zeigen, dass es, wenn eine Reihe konvergiert aber nicht ab-
solut konvergiert (man nennt die Reihe dann auch bedingt konvergent), eine Umordnung
der Reihe gibt, soPdass die umgeordnete Reihe divergiert. Man nennt dabei eine Reihe eine
Umordnung von ak , wenn es eine Bijektion ϕ : N → N gibt, sodass sie geschrieben werden
k
kann als aϕ(k) .
P
k
∞
P
Satz 4.4.6. Eine Reihe ak ist genau dann absolut konvergent, falls für jede Bijektion
k=1
∞
P
ϕ : N → N die Reihe aϕ(k) konvergiert.
k=1
130
∞
P ∞
P
In diesem Fall gilt aϕ(k) = ak für jede Bijektion ϕ : N → N, d. h. bei absolut konver-
k=1 k=1
genten Reihen darf man umsortieren.
Wir wollen nun Rechenregeln für konvergente Reihen diskutieren. Einfach sind dabei die
Addition von konvergenten Reihen und die Multiplikation einer Konvergenten Reihe mit einer
reellen Zahl.
∞
P ∞
P ∞
P
Proposition 4.4.7. Seien ak und bk konvergent. Für c ∈ R konvergieren auch (ak +
k=1 k=1 k=1
∞
P
bk ) und cak , und es gilt:
k=1
∞
X ∞
X ∞
X ∞
X ∞
X
(ak + bk ) = ak + bk und c · ak = c ak
k=1 k=1 k=1 k=1 k=1
Beweis. Seien
n
X n
X
sn = ak und tn = bk
k=1 k=1
∞ ∞
sodass lim sn = ak und lim tn = bk . Dann ist
P P
n→∞ k=1 n→∞ k=1
n n n ∞ ∞
S. 4.1.20
X X X X X
lim (ak + bk ) = lim ak + bk = lim (sn + tn ) = ak + bk
n→∞ n→∞ n→∞
k=1 k=1 k=1 k=1 k=1
und
n n n ∞
S. 4.1.20
X X X X
lim c · ak = lim c ak = c lim ak = c lim sn = c · ak
n→∞ n→∞ n→∞ n→∞
k=1 k=1 k=1 k=1
∞ ∞
(i) Es seien ak und bk konvergent mit
P P
k=1 k=1
m
X ∞
X m
X ∞
X
sm := ak , a := ak , tm := bk , b := bk (4.24)
k=0 k=0 k=0 k=0
Dann ist
a · b = lim sm · lim tm = lim sm · tm .
m→∞ m→∞ m→∞
131
Dabei ist
s0 t0 = a0 b0
s1 t1 = a0 b0 + a0 b1 + a1 b0 + a1 b1
s2 t2 = a0 b0 + a0 b1 + a1 b0 + a1 b1
+ a0 b2 + a1 b2 + a2 b2 + a2 b0 + a2 b1
..
.
und allgemein
m
X m
X m
X m
X
sm · tm = ak bk = ak bl =: dn
k=0 k=0 k,l=0 n=0 n=0n=1n=2n=3
∞
mit dn := ak bl , n ∈ N0 , also a · b = dn .
P P
max{k,l}=n n=0
∆n : = {(k, l) ∈ N0 × N0 : k + l = n}
= {(j, n − j) ∈ N0 × N0 : 0 ≤ j ≤ n}
definiere
X n
X
cn := ak bl = aj bn−j , n ∈ N0 (4.25)
k+l=n j=0 n=0n=1n=2n=3
Dann gilt
∞
m→∞
X
cn = a · b ⇐⇒ rm −→ 0, . (4.27)
n=0
∞ ∞
Aufgepasst! In den beiden Reihen cn und dn werden die gleichen Produkte
P P
n=0 n=0
der Folgenglieder von (an )n∈N und aufsummiert, allerdings in unterschiedli-
(bn )n∈N
1 1
cher Reihenfolge. Wie wir gesehen haben müssen die Werte der Reihen daher nicht
übereinstimmen. Unter geeigneten Voraussetzungen (absolute Konvergenz) tun sie
das aber, wie der folgende Satz garantiert.
132
∞ ∞ ∞
bk absolut konvergent. Sei cn wie in (4.25). Dann ist
P P P
Satz 4.4.8. Seien ak und cn
k=1 k=1 n=0
absolut konvergent, und es gilt
∞
X ∞
X ∞
X
cn = ak bk
n=0 k=0 k=0
X 2m
X 2m
X
|rm | = ak bl = cn ≤ |cn |
0≤k,l≤m n=m+1 n=m+1
k+l>m
2m ∞ ∞
m→∞
X X X
|rm | ≤ |cn | −→ 0 (Cauchy-Kriterium) =⇒ cn = a · b = dn
n=m+1 n=0 n=0
Beispiele 4.4.9.
∞
(i) Wir untersuchen die Reihe (n + 1)xn für |x| < 1:
P
n=0
∞
Es gilt xk = 1
(absolute Konvergenz) und daher
P
1−x
k=0
∞ ∞ ∞
! !
1 X X Satz 4.4.8
X
= xk xk = cn
(1 − x)2
k=0 k=0 n=0
mit
n
X n
X
cn = xj xn−j = xn = (n + 1)xn
j=0 j=0
∞
(n + 1)xn = 1
für |x| < 1.
P
=⇒ (1−x)2
n=0
133
(ii) Reihenentwicklung von e2 :
∞ ∞ ∞ X
n
2
X 1 X 1 X 1 1
e = · = ·
n! n! k! (n − k)!
n=0 n=0 n=0 k=0 | {z }
1 n!
= n! 1
· k! · (n−k)! 1
= n! ·(n
k)
∞ n ∞
X 1 X n k n−k X 2n
= 1 1 = .
n! k n!
n=0 k=0 n=0
| {z }
=(1+1)n
∞ ∞
(−1)k
(iii) Sei ak = bk = . Dann konvergieren ak und bk aber nicht absolut. Weiter
P P
√
k+1
k=0 k=0
gilt
n n
X (−1)j (−1)n−j X 1
cn = p = (−1)n p ,
j=0
(j + 1)(n − j + 1) j=0
(j + 1)(n − j + 1)
wobei man n 2 n 2
(j + 1)(n − j + 1) = +1 − −j
2 2
erhält, wenn beide Seiten der Gleichung ausmultipliziert. Daher folgt
n 2
(j + 1)(n − j + 1) ≤ +1
2
n n
X1 X 2 n+1
=⇒ |cn | ≥ n = =2·
+1 n+2 n+2
j=0 2 j=0
X
=⇒ cn keine NF =⇒ cn divergent
Wir haben in Beispiel 4.3.16 (i) bereits eine sehr bedeutende Reihe kennen gelernt, die wir
jetzt hier etwas genauer studieren.
Definition 4.5.1 (Exponentialreihe und Exponentialfunktion). Für x ∈ R definieren wir die
Exponentialreihe
∞
X xk
exp(x) := . (4.28)
k!
k=0
Eine wesentliche Eigenschaft der Exponentialfunktion ist Inhalt des folgenden Satz.
134
Satz 4.5.3 (Additionstheorem der Exponentialfunktion). Für x, y ∈ R gilt die/das Funktio-
nalgleichung/Additionstheorem
und bilden deren Produkt gemäß Satz 4.4.8. Dann gilt für den n-ten Summanden der Pro-
duktreihe
n n
X xk y n−k X n! 1 Satz 2.6.17 1
cn = = xk y n−k = (x + y)n
k! (n − k)! n! k! · (n − k)! n!
k=0 k=0
Daraus folgt
∞ ∞
X X 1
exp(x) · exp(y) = cn = (x + y)n = exp(x + y).
n!
n=0 n=0
Unmittelbare Konsequenzen aus Definition 4.5.1 und Satz 4.5.3 sammeln wir in
Korollar 4.5.4. Es gilt
(i) exp(0) = 1,
135
(iv) Wir benutzen das Additionstheorem und erhalten
Daraus folgt einerseits exp(x) 6= 0 (sonst würde die rechte Seite verschwinden) und
andererseits die Behauptung durch Division durch exp(x).
(v) Für x ≥ 0 gilt wie in (ii) exp(x) ≥ 1 > 0. Für x < 0 ist −x > 0 und damit
1
exp(−x) > 0 =⇒ exp(x) = > 0.
exp(−x)
(vi) Wir beweisen die Behauptung zunächst für n ∈ N, und zwar per Induktion.
exp(0) = 1 = e0 .
In Abschnitt 4.1 haben wir Dezimalbrüche kennengelernt und reelle Zahlen x ∈ R mit Hilfe
von 10er-Potenzen dargestellt als
X∞
x= kj · 10−j (4.30)
j=0
mit k0 ∈ Z und kj ∈ {0, 1, . . . , 9} für j ∈ N (vgl. Satz 4.2.27 und Bemerkung 4.2.28). Die Wahl
der Basis 10 ist willkürlich, und es ist möglich in (4.30) die Basis 10 durch eine andere zu
ersetzen. Die Babylonier haben z. B. die Basis 60 benutzt (Sexagesimalsystem). Besonders
bedeutungsvoll ist die interne Darstellung von Zahlen im Computer durch dyadische Brüche
(Dualdarstellung) mit der Basis 2. Wir modifizieren die Darstellung in (4.30) etwas, indem
wir die ganze Zahl k0 auch durch eine Summe von Potenzen schreiben.
Definition 4.6.1. Seien b ∈ N, b ≥ 2. Weiter sei l ∈ N0 . Dann heißt eine Reihe der Form
∞
X
± kj · b−j = ±(k−l bl + . . . + k−1 b + k0 + k1 b−1 + k2 b−2 + . . .) (4.31)
j=−l
136
Wie in Abschnitt 4.1 beweist man die beiden folgenden Sätze.
Satz 4.6.2. Jeder b-adische Bruch konvergiert gegen eine reelle Zahl.
Beweis. Wie im Beweis von Satz 4.2.27 beweist man, dass die Folge der Partialsummen
(xn )n≥−k mit
Xn
xn := kj b−j
j=−k
Satz 4.6.3. Sei b ∈ N mit b ≥ 2. Dann lässt sich jede reelle Zahl in durch einen b-adischen
Bruch darstellen.
Bemerkung 4.6.4. Satz 4.6.3 liefert für jede reelle Zahl zwar die Existenz einer b-adischen
Darstellung. Diese ist jedoch keinesegs eindeutig, wie das folgende Beispiel zeigt.
Beispiel 4.6.5. Die Dezimalbrüche 1.00000 . . . und 0.99999 . . . stellen die gleiche reelle Zahl
(nämlich 1) dar. Es gilt nämlich
∞ ∞ ∞ ∞
X X 9 X −j+1 9 X −j
0.99999 . . . = 9 · 10−j = 9 10−j = 10 = 10
10 10
j=1 j=1 j=1 j=0
9 1 9
= 1 = 10 − 1 = 1
10 1 − 10
Notation: Sei x ∈ R mit b-adischer Darstellung (4.31) gegeben. Dann schreiben wir auch
Für den Fall b = 10 lässt man üblicherweise die Klammern und den Index b weg.
Beispiele 4.6.6. In der Dualdarstellung (b = 2) gilt
(1111)2 = 23 + 22 + 21 + 20 = 8 + 4 + 2 + 1 = 15,
(0.01)2 := (0.0101010101 . . .)2 = 2−2 + 2−4 + 2−6 + . . .
∞ ∞
X
−2j
X 1j 1 1
= 2 = −1= 1 −1= .
4 1− 4 3
j=1 j=0
Umgekehrt versuchen wir die dyadische Darstellung von x = 1556 zu bestimmen. Die höchste
2er-Potenz kleiner oder gleich x ist 210 = 1024. Wir bilden die Differenz 1556 − 1024 = 532
und verfahren analog, d. h. 532 = 512 + 20 = 29 + 20, wobei 20 = 16 + 4 = 24 + 4 gilt. Mit
4 = 22 folgt daher
x = 1556 = 210 + 29 + 24 + 22 .
Diese Vorgehensweise liefert ein Verfahren zur Bestimmung von dyadischen Brüchen.
Bemerkung 4.6.7. Bei der praktischen Umsetzung im Rechner benötigt man noch ein zu-
sätzliches Bit zur Behandlung des Vorzeichens in (4.31) bzw. (4.32). Für die Zahl 1556 würde
man also insgesamt 12 Bits benötigen.
137
4.7 Asymptotische Notation
In diesem Abschnitt wollen wir eine neue Notation einführen, die in der Informatik häufig
Anwendung findet. Dabei geht es um die Untersuchung der Komplexität eines Algorithmus,
die wir als die Anzahl der ausgeführten Schritte bzw. als den benötigten Speicherplatz ein-
führen. Genauer spricht man von Laufzeitkomplexität bzw. Speicherkomplexität. Der
Einfachheit halber wollen wir nicht näher definieren, was unter einem „Schritt“ im Zusam-
menhang mit der Laufzeitkomplexität zu verstehen ist. Ein Schritt kann beispielsweise eine
Auswertung eines mathematischen Ausdrucks oder die Ausführung einer Anweisung sein.
Wir beschreiben die Komplexität eines Algorithmus mit einer Funktion f : N0 → R.
Die Variable n ∈ N0 hängt dabei üblicherweise monoton wachsend von der Eingabemenge
ab. Durch ein konkretes Beispiel wollen wir das näher erläutern. Dazu betrachten wir den
Algorithmus Sortieren durch Einfügen (engl. Insertionsort), wobei wir ein Feld a der
Länge n ∈ N von ganzen Zahlen a[0], . . . , a[n − 1] der Größe nach aufsteigend sortieren.
Grob gesprochen starten wir mit dem unsortierten Feld a und am Ende des j-ten Schritts
sieht das Ergebnis so aus, dass die ersten j+1 Einträge in a korrekt der Größe nach aufsteigend
sortiert sind. Dabei vergleichen wir a[j + 1] so lange mit a[j], a[j − 1], usw. und sortieren
sukzessive um, bis die Reihenfolge der Elemente a[0], a[1], . . . , a[j + 1] stimmt. Hierbei werden
die Elemente von a, die größer als a[j + 1] sind, jeweils um einen Platz nach rechts geschoben,
der frei gewordene Platz wird dann von a[j + 1] eingenommen.
Genauer sieht der Algorithmus so aus:
Zur Bestimmung der Laufzeitkomplexität des Algorithmus halten wir fest, was in diesem
138
Beispiel unter einem „Schritt“ verstehen. Ein Schritt ist hier die Ausführung einer der folgen-
den Anweisungen
(iii) die Zuweisung der Laufvariablen j und der Test ob j ≤ n gilt (Beginn der for-Schleife).
Jetzt zählen wir die einzelnen Schritte. Dazu sei g = g(j) die Anzahl der Ausführungen der
inneren Schleife im j-ten Schritt der äußeren Schleife. Dann erhalten wir für die ersten drei
Zeilen des Verfahrens für jedes j jeweils 3 Schritte und für jeden Durchlauf der inneren Schleife
3 Schritte. Die letzte Zeile liefert für jedes j einen Schritt, und vor dem Abbruch der äußeren
Schleife zählen wir einen weiteren Schritt für die Überprüfung der Bedingung. Insgesamt ergibt
sich für ein Feld der Länge n
n−1
X n−1
X n−1
X
f (n) = (1 + 3 + 3g(j) + 1) + 1 = 5(n − 1) + 1 + 3 g(j) = 5n − 4 + 3 g(j).
j=1 j=1 j=1
f (n) = 5n − 4
im ungünstigsten Fall. Wir haben damit eine untere Schranke und eine obere Schranke für die
Anzahl der Schritte: Im günstigsten liegt lineares Wachstum in n vor, im ungünstigsten Fall
liegt quadratisches Wachstum in n vor, wobei dabei alle Terme von nicht höchster Orndung
in n vernachlässigt werden. Es gilt also
3 7 10 2
5n − 4 ≤ f (n) ≤ n2 + |{z}
n −4 ≤ n =⇒ n ≤ f (n) ≤ 5n2 .
| {z } 2 2 2
|{z} 2
≥n ≤n ≤0
Um die Sachlage mathematisch gut zu beschreiben, führt man einige neue Notationen ein.
Definition 4.7.1. Sei g : N0 → R. Dann definieren wir die Landau-Symbole
139
Die Menge ω(g) enthält nur asymtotisch positive Funktionen.
Bemerkung 4.7.3 (zur Notation).
(i) O(g) ist die Menge der Funktionen, die asymptotisch höchstens so schnell wachsen wie
g.
(ii) Ω(g) ist die Menge der Funktionen, die asymptotisch mindestens so schnell wachsen wie
g.
(iii) Es gilt Θ(g) = O(g) ∩ Ω(g) und damit ist Θ(g) die Menge der Funktionen, die asym-
ptotisch genauso schnell wachsen wie g.
(iv) Man beachte, dass in den Definitionen (iv) und (v) der Quantor vor der Konstanten
c > 0 ein „∀“ statt dem „∃“ in (i) und (ii) lautet.
(v) Für asymptotisch positive Funktionen f gilt
f (n)
f ∈ o(g) ⇐⇒ lim = 0, (4.33)
n→∞ g(n)
wie man leicht anhand der Definition von Folgenkonvergenz zeigt. Die Charakterisierung
(4.34) bedeutet daher, dass f schwächer wächst als g, falls f ∈ o(g) gilt.
(vi) Analog wächst f stärker als g, falls f ∈ ω(g) gilt. Weiter gilt
g(n)
f ∈ ω(g) ⇐⇒ lim =0 (4.34)
n→∞ f (n)
140
Beispiele 4.7.5.
Weiter gilt
f (n) ≤ 4n3 + 3n3 + 6n3 + 2n3 = 15n3 für n ∈ N.
Daher folgt
0 ≤ f (n) ≤ 15n3 für n ≥ 2.
und mit n0 = 2 und c = 15 definitionsgemäß f ∈ O(n3 ).
(iv) Allgemein folgt für ein Polynom P ∈ Rm [x] vom Grad m mit
P (x) = am xm + . . . + a1 x + a0 , am > 0,
Bemerkung 4.7.6. Es gibt noch viele weitere funktionale Abhängigkeiten, die in der Be-
schreibung von Komplexitäten eine große Rolle spielen. Einige Beispiele sind
f (n) Komplexitäten
1 konstante Komplexität
n lineare Komplexität
n2 quadratische Komplexität
nm polynomiale Komplexität
log(n) logarithmische Komplexität
2n , 3n exponentielle Komplexität
Bei der Bestimmung von Komplexitäten sind folgende Rechenregeln für die Landau-Symbole
ebenso hilfreich wie einfach zu beweisen.
Satz 4.7.7. Seien f, f1 , f2 , g, g1 , g2 asymptotisch positive Funktionen. Dann gilt
(i) f1 (n) ∈ O(g1 (n)) ∧ f2 (n) ∈ O(g2 (n)) =⇒ (f1 + f2 )(n) ∈ O(max{g1 (n), g2 (n)}),
(ii) (Spezialfall von (i)) f1 (n) ∈ O(g(n))∧f2 (n) ∈ O(g(n)) =⇒ (f1 +f2 )(n) ∈ O(g(n)),
141
(iv) f (n) ∈ O(g(n)) =⇒ (f + g)(n) ∈ Θ(g(n)).
Beispiele 4.7.8.
142
Literaturverzeichnis
143