Themen: Hilberts Hotel Mächtigkeit von Mengen Zahlenfolgen

5 Mengen und Folgen
Themen:
◮
Hilberts Hotel
◮
Mächtigkeit von Mengen
◮
Zahlenfolgen
◮
Stellenwertsysteme
Hilberts Hotel
Hilberts Hotel hat unendlich viele Zimmer, die durch 1, 2, 3, . . .
nummeriert sind.
Hilberts Hotel
Hilberts Hotel hat unendlich viele Zimmer, die durch 1, 2, 3, . . .
nummeriert sind.
Eines Tages kommt ein Gast zum Portier und bittet um ein
Zimmer. Das Hotel ist aber komplett ausgebucht.
Hilberts Hotel
Hilberts Hotel hat unendlich viele Zimmer, die durch 1, 2, 3, . . .
nummeriert sind.
Eines Tages kommt ein Gast zum Portier und bittet um ein
Zimmer. Das Hotel ist aber komplett ausgebucht.
Was macht der Portier?
Hilberts Hotel
Hilberts Hotel hat unendlich viele Zimmer, die durch 1, 2, 3, . . .
nummeriert sind.
Eines Tages kommt ein Gast zum Portier und bittet um ein
Zimmer. Das Hotel ist aber komplett ausgebucht.
Was macht der Portier?
Er quartiert den Gast in Zimmer 1 nach Zimmer 2, den Gast in
Zimmer 2 nach Zimmer 3 usw. Den neuen Gast bringt er in Zimmer
1 unter.
Hilberts Hotel
Eines Tages kommt ein Busfahrer zum Portier. Er hat unendlich
viele Personen in seinem Bus, die alle ein Zimmer wollen. Das Hotel
ist aber komplett ausgebucht.
Hilberts Hotel
Eines Tages kommt ein Busfahrer zum Portier. Er hat unendlich
viele Personen in seinem Bus, die alle ein Zimmer wollen. Das Hotel
ist aber komplett ausgebucht.
Was macht der Portier?
Hilberts Hotel
Eines Tages kommt ein Busfahrer zum Portier. Er hat unendlich
viele Personen in seinem Bus, die alle ein Zimmer wollen. Das Hotel
ist aber komplett ausgebucht.
Was macht der Portier?
Er bringt den Gast von Zimmer 1 nach Zimmer 2, den Gast von
Zimmer 2 nach Zimmer 4, den Gast von Zimmer 3 nach Zimmer 6
usw.
Hilberts Hotel
Eines Tages kommt ein Busfahrer zum Portier. Er hat unendlich
viele Personen in seinem Bus, die alle ein Zimmer wollen. Das Hotel
ist aber komplett ausgebucht.
Was macht der Portier?
Er bringt den Gast von Zimmer 1 nach Zimmer 2, den Gast von
Zimmer 2 nach Zimmer 4, den Gast von Zimmer 3 nach Zimmer 6
usw.
Anschließend bringt er die Personen aus dem Bus in den
ungeradzahligen Zimmern unter.
Hilberts Hotel
Eines Tages kommen unendlich viele Busfahrer zum Portier. Sie
haben alle unendlich viele Personen in ihrem Bus, die alle ein
Zimmer wollen. Das Hotel ist aber komplett ausgebucht.
Hilberts Hotel
Eines Tages kommen unendlich viele Busfahrer zum Portier. Sie
haben alle unendlich viele Personen in ihrem Bus, die alle ein
Zimmer wollen. Das Hotel ist aber komplett ausgebucht.
Was macht der Portier?
Hilberts Hotel
Eines Tages kommen unendlich viele Busfahrer zum Portier. Sie
haben alle unendlich viele Personen in ihrem Bus, die alle ein
Zimmer wollen. Das Hotel ist aber komplett ausgebucht.
Was macht der Portier?
Er holt David Hilbert, den Besitzer des Hotels.
Hilberts Hotel
Die Busfahrer stellen sich nebeneinander hin und die Passagiere
stellen sich hinter ihren Busfahrer.
Hilberts Hotel
10
12
4
9
13
3
5
8
14
1
2
6
7
Hilbert zählt nun alle Passagiere ab!
15
Hilberts Hotel
Jeder Passagier hat nun eine Nummer und kann wie vorher in
einem Zimmer mit ungerader Nummer untergebracht werden.
Mächtigkeiten von Mengen
Für den Anfang reicht es, drei Typen von Mengen zu unterscheiden.
◮
Endliche Mengen: In diesem Fall gibt es eine natürliche Zahl n,
so dass wir die Elemente der Menge von 1 bis n nummerieren
können.
Beispiel: Das deutsche Alphabet hat 30 Buchstaben.
Mächtigkeiten von Mengen
Für den Anfang reicht es, drei Typen von Mengen zu unterscheiden.
◮
Endliche Mengen: In diesem Fall gibt es eine natürliche Zahl n,
so dass wir die Elemente der Menge von 1 bis n nummerieren
können.
Beispiel: Das deutsche Alphabet hat 30 Buchstaben.
Besonderheit: Ist X endlich und f : X → X , so gilt
f injektiv ⇔ f surjektiv ⇔ f bijektiv
Mächtigkeiten von Mengen
◮
Abzählbare Mengen: In diesem Fall können wir die Elemente
der Menge durch die natürlichen Zahlen nummerieren.
Mächtigkeiten von Mengen
◮
Abzählbare Mengen: In diesem Fall können wir die Elemente
der Menge durch die natürlichen Zahlen nummerieren.
Beispiel: × , das sind die Punkte der Ebene der Form
(m, n) mit natürlichen Zahlen m und n.
N N
:
:
:
:
:
:
:
:
:
:
.....
10
.....
6
9
3
5
8
1
2
4
.....
7
.....
Mächtigkeiten von Mengen
◮
Abzählbare Mengen: In diesem Fall können wir die Elemente
der Menge durch die natürlichen Zahlen nummerieren.
Beispiel: × , das sind die Punkte der Ebene der Form
(m, n) mit natürlichen Zahlen m und n.
N N
:
:
:
:
:
:
:
:
:
:
.....
10
.....
6
9
3
5
8
1
2
4
.....
7
.....
Hilberts Hotel zeigt: Die abzählbare Vereinigung abzählbarer
Mengen ist abzählbar
Mächtigkeiten von Mengen
◮
überabzählbare Mengen sind weder endlich noch abzählbar.
Hier kann man noch weiter unterscheiden mit Hilfe von
Kardinalzahlen, im Moment brauchen wir das nicht (ist nämlich
schwer).
Strenge Formulierung
Zwei Mengen A und B heißen gleichmächtig, wenn es eine bijektive
Abbildung f : A → B gibt.
Strenge Formulierung
Zwei Mengen A und B heißen gleichmächtig, wenn es eine bijektive
Abbildung f : A → B gibt.
Gleichmächtigkeit ist eine Äquivalenzrelation. Zu bijektivem
f : A → B existiert die Umkehrfunktion f (−1) : B → A.
Strenge Formulierung
Zwei Mengen A und B heißen gleichmächtig, wenn es eine bijektive
Abbildung f : A → B gibt.
Gleichmächtigkeit ist eine Äquivalenzrelation. Zu bijektivem
f : A → B existiert die Umkehrfunktion f (−1) : B → A.
◮
A heißt endlich, wenn A zu einem Abschnitt
{0, 1, 2, . . . , n − 1} von 0 gleichmächtig ist. n heißt die
Kardinalität von A, Schreibweise |A| = n.
N
Strenge Formulierung
Zwei Mengen A und B heißen gleichmächtig, wenn es eine bijektive
Abbildung f : A → B gibt.
Gleichmächtigkeit ist eine Äquivalenzrelation. Zu bijektivem
f : A → B existiert die Umkehrfunktion f (−1) : B → A.
◮
A heißt endlich, wenn A zu einem Abschnitt
{0, 1, 2, . . . , n − 1} von 0 gleichmächtig ist. n heißt die
Kardinalität von A, Schreibweise |A| = n.
◮
A heißt abzählbar oder abzählbar unendlich, wenn A und
gleichmächtig sind.
N
N
Strenge Formulierung
Zwei Mengen A und B heißen gleichmächtig, wenn es eine bijektive
Abbildung f : A → B gibt.
Gleichmächtigkeit ist eine Äquivalenzrelation. Zu bijektivem
f : A → B existiert die Umkehrfunktion f (−1) : B → A.
◮
A heißt endlich, wenn A zu einem Abschnitt
{0, 1, 2, . . . , n − 1} von 0 gleichmächtig ist. n heißt die
Kardinalität von A, Schreibweise |A| = n.
◮
A heißt abzählbar oder abzählbar unendlich, wenn A und
gleichmächtig sind.
◮
A heißt überabzählbar oder überabzählbar unendlich, wenn A
weder endlich nach abzählbar ist.
N
N
Vorsicht
Bei unendlichen Mengen gilt keine Implikation in: Ist X endlich und
f : X → X , so gilt
f injektiv ⇔ f surjektiv ⇔ f bijektiv
Vorsicht
Bei unendlichen Mengen gilt keine Implikation in: Ist X endlich und
f : X → X , so gilt
f injektiv ⇔ f surjektiv ⇔ f bijektiv
Beispiele für X =
N
1. f (n) = 2n,
Vorsicht
Bei unendlichen Mengen gilt keine Implikation in: Ist X endlich und
f : X → X , so gilt
f injektiv ⇔ f surjektiv ⇔ f bijektiv
Beispiele für X =
N
1. f (n) = 2n,
2. f (2n) = f (n), f (2n − 1) = f (n)
Minimum und Maximum
Endliche Mengen von reellen Zahlen besitzen ein Minimum und ein
Maximum.
Minimum und Maximum
Endliche Mengen von reellen Zahlen besitzen ein Minimum und ein
Maximum.
Ist M = {x1 , x2 , . . . , xm }, so können wir das maximale Element
durch folgenden Algorithmus finden:
y1 = max{x1 , x2 }
y2 = max{y1 , x3 }
y3 = max{y2 , x4 }
..
.
ym−1 = max{ym−2 , xm }
ym−1 ist dann das Maximum von M und stimmt mit einem Element
aus M überein.
Minimum und Maximum
R
Ist M eine endliche Menge und f : M → eine Abbildung, so
nimmt f auf M Maximum und Minimum an. D.h, es gibt
xmin , xmax ∈ M mit
f (xmin ) ≤ f (x) ∀x ∈ M,
f (xmax ) ≥ f (x) ∀x ∈ M.
Konstruktion von xmin und xmax mit dem gleichen Algorithmus wie
zuvor.
Minimum und Maximum
R
Ist M eine endliche Menge und f : M → eine Abbildung, so
nimmt f auf M Maximum und Minimum an. D.h, es gibt
xmin , xmax ∈ M mit
f (xmin ) ≤ f (x) ∀x ∈ M,
f (xmax ) ≥ f (x) ∀x ∈ M.
Konstruktion von xmin und xmax mit dem gleichen Algorithmus wie
zuvor.
Bei unendlichen Mengen wird alles falsch:
-
N besitzt kein Maximum.
Minimum und Maximum
R
Ist M eine endliche Menge und f : M → eine Abbildung, so
nimmt f auf M Maximum und Minimum an. D.h, es gibt
xmin , xmax ∈ M mit
f (xmin ) ≤ f (x) ∀x ∈ M,
f (xmax ) ≥ f (x) ∀x ∈ M.
Konstruktion von xmin und xmax mit dem gleichen Algorithmus wie
zuvor.
Bei unendlichen Mengen wird alles falsch:
N
besitzt kein Maximum.
- f (n) = n1 , f : → , besitzt kein Minimum.
N Q
Zahlenfolgen
Ein unendliche Folge reeller Zahlen heißt Zahlenfolge. Im Beispiel
0, 1, 0, 11, 0, 111, 0, 1111, 0, 11111, . . .
ist 0, 1 das erste Folgenglied, 0, 11 ist das zweite Folgenglied usw.
Zahlenfolgen
Ein unendliche Folge reeller Zahlen heißt Zahlenfolge. Im Beispiel
0, 1, 0, 11, 0, 111, 0, 1111, 0, 11111, . . .
ist 0, 1 das erste Folgenglied, 0, 11 ist das zweite Folgenglied usw.
Allgemein schreiben wir
(xk )k∈N = (xk ) = (x1 , x2 , x3 , . . .),
xk ∈
R,
wobei x1 das erste Folgenglied ist, x2 ist das zweite Folgenglied,
und xk , k ∈ , ist das k-te Folgenglied.
N
Beispiele von Zahlenfolgen
◮
1, 2, 3, 4, . . . ist die Folge der natürlichen Zahlen. Für das k-te
Folgenglied gilt xk = k.
Beispiele von Zahlenfolgen
◮
1, 2, 3, 4, . . . ist die Folge der natürlichen Zahlen. Für das k-te
Folgenglied gilt xk = k. Eine andere Schreibweise ist
(xk ) = (1, 2, 3, . . .).
Beispiele von Zahlenfolgen
◮
1, 2, 3, 4, . . . ist die Folge der natürlichen Zahlen. Für das k-te
Folgenglied gilt xk = k. Eine andere Schreibweise ist
(xk ) = (1, 2, 3, . . .).
◮
xk = 1 oder (xk ) = (1, 1, 1, . . .) (=konstante Folge).
Beispiele von Zahlenfolgen
◮
1, 2, 3, 4, . . . ist die Folge der natürlichen Zahlen. Für das k-te
Folgenglied gilt xk = k. Eine andere Schreibweise ist
(xk ) = (1, 2, 3, . . .).
◮
◮
xk = 1 oder (xk ) = (1, 1, 1, . . .) (=konstante Folge).
xk = (−1)k oder (xk ) = (−1, 1, −1, 1, . . .) (=alternierende
Folge)
Beispiele von Zahlenfolgen
◮
1, 2, 3, 4, . . . ist die Folge der natürlichen Zahlen. Für das k-te
Folgenglied gilt xk = k. Eine andere Schreibweise ist
(xk ) = (1, 2, 3, . . .).
◮
◮
◮
xk = 1 oder (xk ) = (1, 1, 1, . . .) (=konstante Folge).
xk = (−1)k oder (xk ) = (−1, 1, −1, 1, . . .) (=alternierende
Folge)
(xk ) = (3, 3, 1 , 3, 14, 3, 141, . . .)
Wie viele Zahlenfolgen gibt es?
Wir betrachten nur Zahlenfolgen von natürlichen Zahlen. Sind die
abzählbar oder überabzählbar?
Wie viele Zahlenfolgen gibt es?
Wir betrachten nur Zahlenfolgen von natürlichen Zahlen. Sind die
abzählbar oder überabzählbar?
Wir zeigen, dass bereits die Zahlenfolgen mit Werten in 0,1
überabzählbar sind. Diese nennen wir kurz 0,1-Folgen.
Wie viele Zahlenfolgen gibt es?
Wir betrachten nur Zahlenfolgen von natürlichen Zahlen. Sind die
abzählbar oder überabzählbar?
Wir zeigen, dass bereits die Zahlenfolgen mit Werten in 0,1
überabzählbar sind. Diese nennen wir kurz 0,1-Folgen.
Angenommen, wir könnten alle 0,1-Folgen nummerieren. Dann
hätten wir eine Liste, die alle 0,1-Folgen umfaßt:
Wie viele Zahlenfolgen gibt es?
1:
0 1 1 1 0 0 1 0 0 . . .
2:
1 1 1 0 0 0 0 1 0 . . .
3:
0 1 1 1 0 0 1 0 0 . . .
4:
1 1 1 0 0 0 0 1 0 . . .
5:
0 1 1 1 0 0 1 0 0 . . .
:
Wie viele Zahlenfolgen gibt es?
1:
0 1 1 1 0 0 1 0 0 . . .
2:
1 1 1 0 0 0 0 1 0 . . .
3:
0 1 1 1 0 0 1 0 0 . . .
4:
1 1 1 0 0 0 0 1 0 . . .
5:
0 1 1 1 0 0 1 0 0 . . .
:
Wir konstruieren aus den eingekreisten Diagonalelementen eine
neue Folge:
neu:
1 0 0 1 1
. . .
Diese ist nicht in der Liste enthalten. Damit sind die 0,1-Folgen
überabzählbar.
Teilmenge und Potenzmenge
A⊂B
⇔
∀x (x ∈ A ⇒ x ∈ B).
Teilmenge und Potenzmenge
A⊂B
⇔
∀x (x ∈ A ⇒ x ∈ B).
Warum gilt ∅ ⊂ A für jede Menge A ?
Teilmenge und Potenzmenge
A⊂B
⇔
∀x (x ∈ A ⇒ x ∈ B).
Warum gilt ∅ ⊂ A für jede Menge A ?
Die Voraussetzung x ∈ ∅ ist immer falsch, die Implikation daher
immer richtig.
Teilmenge und Potenzmenge
A⊂B
⇔
∀x (x ∈ A ⇒ x ∈ B).
Warum gilt ∅ ⊂ A für jede Menge A ?
Die Voraussetzung x ∈ ∅ ist immer falsch, die Implikation daher
immer richtig.
Die Potenzmenge P(A) einer Menge A besteht aus allen
Teilmengen von A.
Teilmenge und Potenzmenge
A⊂B
⇔
∀x (x ∈ A ⇒ x ∈ B).
Warum gilt ∅ ⊂ A für jede Menge A ?
Die Voraussetzung x ∈ ∅ ist immer falsch, die Implikation daher
immer richtig.
Die Potenzmenge P(A) einer Menge A besteht aus allen
Teilmengen von A.
Beispiel: Für A = {1, 2, 3} gilt
P(A) = ∅, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3} .
Ein weiteres Resultat mit vorigem Beweis
Satz Die Potenzmenge von
N ist überabzählbar.
Ein weiteres Resultat mit vorigem Beweis
Satz Die Potenzmenge von
N ist überabzählbar.
Wie kann man die Elemente der Potenzmenge als 0, 1-Folgen
schreiben?
Ein weiteres Resultat mit vorigem Beweis
Satz Die Potenzmenge von
N ist überabzählbar.
Wie kann man die Elemente der Potenzmenge als 0, 1-Folgen
schreiben?
Ist A ⊂
N so definiere eine 0, 1-Folge xA durch
xA (n) =
(
1 falls n ∈ A
0 falls n ∈
/A
Ein weiteres Resultat mit vorigem Beweis
Satz Die Potenzmenge von
N ist überabzählbar.
Wie kann man die Elemente der Potenzmenge als 0, 1-Folgen
schreiben?
Ist A ⊂
N so definiere eine 0, 1-Folge xA durch
xA (n) =
(
1 falls n ∈ A
0 falls n ∈
/A
Dies liefert eine bijektive Abbildung zwischen den 0, 1-Folgen und
P( ).
N
Wie viele Zahlenfolgen gibt es?
Wie viele definierbare 0,1-Folgen gibt es?
Wie viele Zahlenfolgen gibt es?
Wie viele definierbare 0,1-Folgen gibt es?
Dabei ist ”definierbar” hier etwas schwammig. Wir stellen uns vor,
dass wir eine Sprache haben, in der wir 0,1-Folgen definieren
können, z.B. eine Programmiersprache, in der wir Programme
scheiben, die 0,1-Folgen liefern.
Wie viele solcher Programme gibt es?
Wie viele Zahlenfolgen gibt es?
Wie viele definierbare 0,1-Folgen gibt es?
Dabei ist ”definierbar” hier etwas schwammig. Wir stellen uns vor,
dass wir eine Sprache haben, in der wir 0,1-Folgen definieren
können, z.B. eine Programmiersprache, in der wir Programme
scheiben, die 0,1-Folgen liefern.
Wie viele solcher Programme gibt es?
Allgemein können wir höchstens abzählbare Objekte formal
definieren. Deshalb ist es wichtig zu wissen, ob eine Menge
abzählbar oder überabzählbar ist.
Beschränkte Folgen
Eine Folge (xk )k∈N heißt beschränkt, wenn es eine Zahl M gibt mit
|xk | ≤ M für alle k ∈ .
N
Beschränkte Folgen
Eine Folge (xk )k∈N heißt beschränkt, wenn es eine Zahl M gibt mit
|xk | ≤ M für alle k ∈ .
N
Man schreibe dies formal hin. Man formuliere die Aussage, dass
eine Folge unbeschränkt ist und schreibe auch dieses formal hin.
Beschränkte Folgen
Eine Folge (xk )k∈N heißt beschränkt, wenn es eine Zahl M gibt mit
|xk | ≤ M für alle k ∈ .
N
Man schreibe dies formal hin. Man formuliere die Aussage, dass
eine Folge unbeschränkt ist und schreibe auch dieses formal hin.
(xk ) beschränkt
⇔
∃M ∀k ∈
N
|xk | ≤ M
Beschränkte Folgen
Eine Folge (xk )k∈N heißt beschränkt, wenn es eine Zahl M gibt mit
|xk | ≤ M für alle k ∈ .
N
Man schreibe dies formal hin. Man formuliere die Aussage, dass
eine Folge unbeschränkt ist und schreibe auch dieses formal hin.
(xk ) beschränkt
⇔
∃M ∀k ∈
N
|xk | ≤ M
Eine Folge ist unbeschränkt, wenn es zu jedem M ein k ∈
mit |xk | > M.
N gibt
Beschränkte Folgen
Eine Folge (xk )k∈N heißt beschränkt, wenn es eine Zahl M gibt mit
|xk | ≤ M für alle k ∈ .
N
Man schreibe dies formal hin. Man formuliere die Aussage, dass
eine Folge unbeschränkt ist und schreibe auch dieses formal hin.
(xk ) beschränkt
⇔
∃M ∀k ∈
N
|xk | ≤ M
Eine Folge ist unbeschränkt, wenn es zu jedem M ein k ∈
mit |xk | > M.
Formal ist eine Folge unbeschränkt, wenn
∀M ∃k ∈
N
|xk | > M.
N gibt
Beschränkte Folgen
Ist die folgende Aussage zu ”(xk ) ist beschränkt” äquivalent?
Es gibt ein K ∈
N, so dass die Folge
(xk )k≥K = (xK , xK +1 , xK +2 , . . .)
beschränkt ist.
Beschränkte Folgen
Ist die folgende Aussage zu ”(xk ) ist beschränkt” äquivalent?
Es gibt ein K ∈
N, so dass die Folge
(xk )k≥K = (xK , xK +1 , xK +2 , . . .)
beschränkt ist.
Beschränkte Folgen
Ist die folgende Aussage zu ”(xk ) ist beschränkt” äquivalent?
Es gibt ein K ∈
N, so dass die Folge
(xk )k≥K = (xK , xK +1 , xK +2 , . . .)
beschränkt ist.
Ja. Sei M eine Schranke der Folge (xk )k≥K . Dann ist
Mges = max{|x1 |, |x2 |, . . . , |xK −1 |, M}
eine Schranke für die Ausgangsfolge.
Folgerung
Die Beschränktheit ist ein einfaches Beispiel für einen Begriff, der
nur vom Verhalten der Folgenglieder im ”Unendlichen” abhängt:
Folgerung
Die Beschränktheit ist ein einfaches Beispiel für einen Begriff, der
nur vom Verhalten der Folgenglieder im ”Unendlichen” abhängt:
Die Beschränktheit oder Unbeschränktheit einer Folge ändert sich
nicht,
◮
wenn man endlich viele Folgenglieder weglässt,
Folgerung
Die Beschränktheit ist ein einfaches Beispiel für einen Begriff, der
nur vom Verhalten der Folgenglieder im ”Unendlichen” abhängt:
Die Beschränktheit oder Unbeschränktheit einer Folge ändert sich
nicht,
◮
wenn man endlich viele Folgenglieder weglässt,
◮
wenn man endlich viele Folgenglieder der Folge hinzufügt.
Konvergente Folgen
Eine Folge (xk ) konvergiert gegen ein x ∈
ε > 0 ein K ∈ gibt mit
N
R, wenn es zu jedem
|xk − x| < ε für alle k ≥ K .
Konvergente Folgen
Eine Folge (xk ) konvergiert gegen ein x ∈
ε > 0 ein K ∈ gibt mit
N
R, wenn es zu jedem
|xk − x| < ε für alle k ≥ K .
x+ε
x
x-ε
k
K
Ab einem Index K liegen alle Folgenglieder im Schlauch
{y : |y − x| < ε}.
Beispiele zur Konvergenz
1. Die konstante Folge xk = 1 konvergiert gegen x = 1 wegen
|xk − x| = |1 − 1| = 0 < ε ∀k ∈
N.
Beispiele zur Konvergenz
1. Die konstante Folge xk = 1 konvergiert gegen x = 1 wegen
|xk − x| = |1 − 1| = 0 < ε ∀k ∈
2. Die Folge xk =
es ein K ∈ mit
N
1
k
1
K
N.
konvergiert gegen x = 0. Zu jedem ε > 0 gibt
< ε.
Beispiele zur Konvergenz
1. Die konstante Folge xk = 1 konvergiert gegen x = 1 wegen
|xk − x| = |1 − 1| = 0 < ε ∀k ∈
2. Die Folge xk =
es ein K ∈ mit
N
1
k
1
K
N.
konvergiert gegen x = 0. Zu jedem ε > 0 gibt
< ε.
Für k ≥ K gilt daher
|xk − x| =
1
1
≤
< ε.
k
K
Beispiele zur Konvergenz
3. Die alternierende Folge xk = (−1)k konvergiert nicht. Wir
wählen ε = 12 .
Beispiele zur Konvergenz
3. Die alternierende Folge xk = (−1)k konvergiert nicht. Wir
wählen ε = 12 .
x+1/2
x
x-1/2
k
R
Gleichgültig, welches x ∈ wir wählen, es liegen immer unendlich
viele Folgenglieder außerhalb des Schlauchs.
Beispiele zur Konvergenz
4. Sei xk der k−te Abschnitt in der Dezimaldarstellung von π, also
x1 = 3, 1, x2 = 3, 14, x3 = 3, 141, x4 = 3, 1415, . . . .
Dann gilt |π − xk | ≤ 0, |0 .{z
. . 0} 999 . . . ≤ 10−k+1 .
k -mal
Beispiele zur Konvergenz
4. Sei xk der k−te Abschnitt in der Dezimaldarstellung von π, also
x1 = 3, 1, x2 = 3, 14, x3 = 3, 141, x4 = 3, 1415, . . . .
Dann gilt |π − xk | ≤ 0, |0 .{z
. . 0} 999 . . . ≤ 10−k+1 .
k -mal
Zu ε > 0 gibt es ein K mit 10−K +1 < ε. Für k ≥ K gilt dann
|π − xk | ≤ 10−k+1 ≤ 10−K +1 < ε.
Konvergente Folgen
Eine Folge (xk ) konvergiert gegen ein x ∈
ε > 0 ein K ∈ gibt mit
N
R, wenn es zu jedem
|xk − x| < ε für alle k ≥ K .
Konvergente Folgen
Eine Folge (xk ) konvergiert gegen ein x ∈
ε > 0 ein K ∈ gibt mit
N
R, wenn es zu jedem
|xk − x| < ε für alle k ≥ K .
Man formuliere dies mit eigenen Worten und schreibe es
anschließend formal hin.
Konvergente Folgen
Eine Folge (xk ) konvergiert gegen ein x ∈
ε > 0 ein K ∈ gibt mit
N
R, wenn es zu jedem
|xk − x| < ε für alle k ≥ K .
Man formuliere dies mit eigenen Worten und schreibe es
anschließend formal hin.
Der Abstand zwischen xk und x wird für große Indizes k beliebig
klein.
Oder formal:
∀ε > 0 ∃K ∈
N ∀k ≥ K
|xk − x| < ε
Konvergente Folgen
Man formuliere mit eigenen Worten, dass eine Folge nicht gegen
x ∈ konvergiert und schreibe dies anschließend formal hin.
R
Konvergente Folgen
Man formuliere mit eigenen Worten, dass eine Folge nicht gegen
x ∈ konvergiert und schreibe dies anschließend formal hin.
R
Beispiel für eine Formulierung mit eigenen Worten (kann jede(r)
auch anders ausdrücken):
Es gibt ein ε > 0, so dass |xk − x| ≥ ε für unendlich viele k.
Konvergente Folgen
Man formuliere mit eigenen Worten, dass eine Folge nicht gegen
x ∈ konvergiert und schreibe dies anschließend formal hin.
R
Beispiel für eine Formulierung mit eigenen Worten (kann jede(r)
auch anders ausdrücken):
Es gibt ein ε > 0, so dass |xk − x| ≥ ε für unendlich viele k.
Oder formal:
∃ε > 0 ∀K ∈
N ∃k ≥ K
|xk − x| ≥ ε.
Konvergente Folgen
Eine Folge (xk ) konvergiert gegen ein x ∈
ε > 0 ein K ∈ gibt mit
N
R, wenn es zu jedem
|xk − x| < ε für alle k ≥ K .
Konvergente Folgen
Eine Folge (xk ) konvergiert gegen ein x ∈
ε > 0 ein K ∈ gibt mit
N
R, wenn es zu jedem
|xk − x| < ε für alle k ≥ K .
Eine Eigenschaft trifft für fast alle Folgenglieder zu, wenn sie für
alle bis auf endlich viele Folgenglieder zutrifft.
Konvergente Folgen
Eine Folge (xk ) konvergiert gegen ein x ∈
ε > 0 ein K ∈ gibt mit
N
R, wenn es zu jedem
|xk − x| < ε für alle k ≥ K .
Eine Eigenschaft trifft für fast alle Folgenglieder zu, wenn sie für
alle bis auf endlich viele Folgenglieder zutrifft.
Welche der folgenden Aussagen sind zu ”(xk ) konvergiert gegen x”
äquivalent?
Für jedes ε > 0 gilt |xk − x| < ε für fast alle Folgenglieder.
Konvergente Folgen
Eine Folge (xk ) konvergiert gegen ein x ∈
ε > 0 ein K ∈ gibt mit
N
R, wenn es zu jedem
|xk − x| < ε für alle k ≥ K .
Eine Eigenschaft trifft für fast alle Folgenglieder zu, wenn sie für
alle bis auf endlich viele Folgenglieder zutrifft.
Welche der folgenden Aussagen sind zu ”(xk ) konvergiert gegen x”
äquivalent?
Für jedes ε > 0 gilt |xk − x| < ε für fast alle Folgenglieder.
Für jedes m ∈
N gilt |xk − x| < m1 für fast alle Folgenglieder.
Konvergente Folgen
Im Hinblick auf Konvergenz ist es gleichgültig, was eine Folge auf
endlichen Abschnitten macht. Konvergenz einer Folge ist ein
wichtiges Beispiel dafür, wie die Mathematik einen infinitesimalen
Begriff in den Griff bekommt.
Konvergente Folgen
Im Hinblick auf Konvergenz ist es gleichgültig, was eine Folge auf
endlichen Abschnitten macht. Konvergenz einer Folge ist ein
wichtiges Beispiel dafür, wie die Mathematik einen infinitesimalen
Begriff in den Griff bekommt.
Wir können das letzte Beispiel aus der vorigen Folie noch
verschärfen. Sei (yk ) eine positive Nullfolge, also yk > 0 und
yk → 0. Ein Beispiel dafür ist yk = k1 wie in der letzten Folie. Dann:
Konvergente Folgen
Im Hinblick auf Konvergenz ist es gleichgültig, was eine Folge auf
endlichen Abschnitten macht. Konvergenz einer Folge ist ein
wichtiges Beispiel dafür, wie die Mathematik einen infinitesimalen
Begriff in den Griff bekommt.
Wir können das letzte Beispiel aus der vorigen Folie noch
verschärfen. Sei (yk ) eine positive Nullfolge, also yk > 0 und
yk → 0. Ein Beispiel dafür ist yk = k1 wie in der letzten Folie. Dann:
Eine Folge (xk ) konvergiert genau dann gegen x, wenn für jedes
m ∈ gilt |xk − x| < ym für fast alle Folgenglieder.
N
Konvergente Folgen
Im Hinblick auf Konvergenz ist es gleichgültig, was eine Folge auf
endlichen Abschnitten macht. Konvergenz einer Folge ist ein
wichtiges Beispiel dafür, wie die Mathematik einen infinitesimalen
Begriff in den Griff bekommt.
Wir können das letzte Beispiel aus der vorigen Folie noch
verschärfen. Sei (yk ) eine positive Nullfolge, also yk > 0 und
yk → 0. Ein Beispiel dafür ist yk = k1 wie in der letzten Folie. Dann:
Eine Folge (xk ) konvergiert genau dann gegen x, wenn für jedes
m ∈ gilt |xk − x| < ym für fast alle Folgenglieder.
Wir müssen durch unsere Definition nur garantieren, dass die
Abstände der Folgenglieder zum Grenzwert beliebig klein werden.
N
Dezimalsystem
Eine ganze Zahl n schreibt man gewöhnlich im Dezimalsystem in
der Form
ak ak−1 . . . a0 ,
ai ∈ {0, 1, . . . , 9}, ak 6= 0.
Dezimalsystem
Eine ganze Zahl n schreibt man gewöhnlich im Dezimalsystem in
der Form
ai ∈ {0, 1, . . . , 9}, ak 6= 0.
ak ak−1 . . . a0 ,
Dies bedeutet
k
k−1
n = ak · 10 + ak−1 · 10
+ . . . + a1 · 10 + a0 =
k
X
i=0
ai · 10i .
Dezimalsystem
Eine ganze Zahl n schreibt man gewöhnlich im Dezimalsystem in
der Form
ai ∈ {0, 1, . . . , 9}, ak 6= 0.
ak ak−1 . . . a0 ,
Dies bedeutet
k
k−1
n = ak · 10 + ak−1 · 10
+ . . . + a1 · 10 + a0 =
k
X
ai · 10i .
i=0
Es handelt sich hierbei um ein Stellenwertsystem, weil der „Wert“
der Ziffer von der Position abhängt.
Dezimalsystem
Eine ganze Zahl n schreibt man gewöhnlich im Dezimalsystem in
der Form
ai ∈ {0, 1, . . . , 9}, ak 6= 0.
ak ak−1 . . . a0 ,
Dies bedeutet
k
k−1
n = ak · 10 + ak−1 · 10
+ . . . + a1 · 10 + a0 =
k
X
ai · 10i .
i=0
Es handelt sich hierbei um ein Stellenwertsystem, weil der „Wert“
der Ziffer von der Position abhängt.
Im Gegensatz dazu ist das römische Zahlsystem ein additives
System: Die Position eines Zeichens spielt bis auf wenige
Ausnahmen keine Rolle.
Andere Grundzahlen
Die Grundzahl g = 10 in unserem Dezimalsystem wird auf das
Zählen mit 10 Fingern zurückgeführt. Es waren und sind aber viele
andere Grundzahlen g als g = 10 in Gebrauch:
Andere Grundzahlen
Die Grundzahl g = 10 in unserem Dezimalsystem wird auf das
Zählen mit 10 Fingern zurückgeführt. Es waren und sind aber viele
andere Grundzahlen g als g = 10 in Gebrauch:
◮
g = 12: Davon gibt es hauptsächlich noch sprachliche
Überreste wie Dutzend= 12 und Gros= 144 = 12 · 12. Auch
der aus dem Franösischen stammende Ausdruck „en gros“ für
eine große Menge geht auf das Gros zurück.
Andere Grundzahlen
Die Grundzahl g = 10 in unserem Dezimalsystem wird auf das
Zählen mit 10 Fingern zurückgeführt. Es waren und sind aber viele
andere Grundzahlen g als g = 10 in Gebrauch:
◮
g = 12: Davon gibt es hauptsächlich noch sprachliche
Überreste wie Dutzend= 12 und Gros= 144 = 12 · 12. Auch
der aus dem Franösischen stammende Ausdruck „en gros“ für
eine große Menge geht auf das Gros zurück.
◮
g = 2: Ein Computer kann nur solche Binärzahlen verarbeiten.
Da solche Zahlen sehr lang werden, fasst man mehrere
Binärziffern zusammen zu Oktalzahlen g = 8 oder
Hexadezimalzahlen g = 16.
Andere Grundzahlen
Die Grundzahl g = 10 in unserem Dezimalsystem wird auf das
Zählen mit 10 Fingern zurückgeführt. Es waren und sind aber viele
andere Grundzahlen g als g = 10 in Gebrauch:
◮
g = 12: Davon gibt es hauptsächlich noch sprachliche
Überreste wie Dutzend= 12 und Gros= 144 = 12 · 12. Auch
der aus dem Franösischen stammende Ausdruck „en gros“ für
eine große Menge geht auf das Gros zurück.
◮
g = 2: Ein Computer kann nur solche Binärzahlen verarbeiten.
Da solche Zahlen sehr lang werden, fasst man mehrere
Binärziffern zusammen zu Oktalzahlen g = 8 oder
Hexadezimalzahlen g = 16.
◮
g = 60: Überreste dieses Systems findet man bei Zeit- und
Winkelabschnitten.
Andere Grundzahlen
◮
g = 20: In manchen Sprachen werden die Zehner als Vielfache
der Zahl 20 benannt, was auf eine frühere Verwendung des
Zwanzigersystems hindeutet. Reste findet man auch im
Französischen und im Dänischen.
Andere Grundzahlen
◮
g = 20: In manchen Sprachen werden die Zehner als Vielfache
der Zahl 20 benannt, was auf eine frühere Verwendung des
Zwanzigersystems hindeutet. Reste findet man auch im
Französischen und im Dänischen.
◮
g = 4: Das wird sicher nicht zum Zählen benutzt. Das
römische Münzsystem folgt weitgehend dem Vierersystem, bei
dem man zum Zahlen nicht so viele Münzen bereit halten
muss.
Zahldarstellung in einem Stellenwertsystem
Die Darstellung einer Zahl n in einem Stellenwertsystem zur
Grundzahl g lässt sich leicht bestimmen. Wir teilen die Zahl durch
g mit Rest,
n = n0 = n1 g + a0 ,
n1 = n2 g + a1 , . . .
Zahldarstellung in einem Stellenwertsystem
Die Darstellung einer Zahl n in einem Stellenwertsystem zur
Grundzahl g lässt sich leicht bestimmen. Wir teilen die Zahl durch
g mit Rest,
n = n0 = n1 g + a0 ,
n1 = n2 g + a1 , . . .
und erhalten schließlich die Darstellung
n=
k
X
i=0
ai g i .
Zahldarstellung in einem Stellenwertsystem
Die Darstellung einer Zahl n in einem Stellenwertsystem zur
Grundzahl g lässt sich leicht bestimmen. Wir teilen die Zahl durch
g mit Rest,
n = n0 = n1 g + a0 ,
n1 = n2 g + a1 , . . .
und erhalten schließlich die Darstellung
n=
k
X
ai g i .
i=0
Als Beispiel stellen wir die Zahl 18 in einigen Stellenwertsystemen
dar
1810 = 1216 = 1612 = 228 = 100102 .
Die geometrische Summenformel
Die geometrische Summenformel lautet für q 6= 1
n
X
i=0
qi =
1 − q n+1
.
1−q
Die geometrische Summenformel
Die geometrische Summenformel lautet für q 6= 1
n
X
qi =
i=0
1 − q n+1
.
1−q
Man beweist sie, in dem man den „Teleskopeffekt“ beachtet,
n
X
i=0
i
q (1 − q) =
n
X
i=0
i
q −
n
X
i=0
q i+1 = 1 − q n+1 .
Die geometrische Summenformel
n
X
i=0
qi =
1 − q n+1
.
1−q
Die geometrische Summenformel
n
X
i=0
qi =
1 − q n+1
.
1−q
Für |q| < 1 konvergiert q i gegen Null.
Die geometrische Summenformel
n
X
i=0
qi =
1 − q n+1
.
1−q
Für |q| < 1 konvergiert q i gegen Null.
Wir können daher für diese q in der geometrischen Sumenformel
zum Grenzwert übergehen und erhalten
∞
X
i=0
qi =
1
,
1−q
für |q| < 1.
Dezimalbrüche
Bekanntlich wird mit einem unendlichen Dezimalbruch der Form
0, a1 a2 a3 . . ., ai ∈ {0, 1, 2, . . . 9} die reelle Zahl
∞
X
ai
10i
i=1
dargestellt.
Dezimalbrüche
Bekanntlich wird mit einem unendlichen Dezimalbruch der Form
0, a1 a2 a3 . . ., ai ∈ {0, 1, 2, . . . 9} die reelle Zahl
∞
X
ai
10i
i=1
dargestellt.
Wegen ai ≤ 9 lässt sich diese Reihe mit ci = 9 · 10−i durch die
geometrische Reihe majorisieren.
Dezimalbrüche
Bekanntlich wird mit einem unendlichen Dezimalbruch der Form
0, a1 a2 a3 . . ., ai ∈ {0, 1, 2, . . . 9} die reelle Zahl
∞
X
ai
10i
i=1
dargestellt.
Wegen ai ≤ 9 lässt sich diese Reihe mit ci = 9 · 10−i durch die
geometrische Reihe majorisieren.
Betrachte auch allgemeinere Entwicklungen nach beliebigen
Grundzahlen g ∈ \ {1}
N
∞
X
ai
,
gi
i=1
ai ∈ {0, 1 . . . , g − 1}.
Dezimalbrüche
Ein Fall ist in dieser Darstellung nicht eindeutig, nämlich
∞
∞
X
g −1X 1
g −1 1
g −1
=
=
i
i
g
g
g
g 1−
i=1
i=0
1
g
= 1.
Dezimalbrüche
Ein Fall ist in dieser Darstellung nicht eindeutig, nämlich
∞
∞
X
g −1X 1
g −1 1
g −1
=
=
i
i
g
g
g
g 1−
i=1
i=0
1
g
= 1.
Wir vereinbaren daher, dass unsere Entwicklungen nicht auf Periode
g − 1 enden dürfen.
Der Hauptsatz
Für eine reelle Zahl a bezeichnen wir mit [a] die größte ganze Zahl
≤ a, es ist also
[1, 3] = 1 und [−1, 3] = −2.
Der Hauptsatz
Für eine reelle Zahl a bezeichnen wir mit [a] die größte ganze Zahl
≤ a, es ist also
[1, 3] = 1 und [−1, 3] = −2.
Satz: Sei g eine natürliche Zahl ≥ 2. Zu jeder nichtnegativen
reellen Zahl a gibt es eindeutige Zahlen
a0 ∈
N0
und a1 , a2 , a3 , . . . ∈ {0, 1, . . . , g − 1}
mit
a = a0 +
∞
X
ai
.
gi
i=1
Beweis
Sei a0 = [a].
Beweis
Sei a0 = [a].
Dann gilt
a − a0 ∈ [0, 1).
Beweis
Sei a0 = [a].
Dann gilt
a − a0 ∈ [0, 1).
Wir setzen
a1 = [g (a − a0 )] ∈ {0, . . . , g − 1}.
Beweis
Sei a0 = [a].
Dann gilt
a − a0 ∈ [0, 1).
Wir setzen
a1 = [g (a − a0 )] ∈ {0, . . . , g − 1}.
Es gilt dann g (a − a0 ) − a1 ∈ [0, 1) und wir können das Verfahren
mit
a2 = g g (a − a0 ) − a1
fortsetzen.
Beweis
Sei a0 = [a].
Dann gilt
a − a0 ∈ [0, 1).
Wir setzen
a1 = [g (a − a0 )] ∈ {0, . . . , g − 1}.
Es gilt dann g (a − a0 ) − a1 ∈ [0, 1) und wir können das Verfahren
mit
a2 = g g (a − a0 ) − a1
fortsetzen.
Auf diese Weise erhalten wir die gewünschten „Ziffern“ a1 , a2 , . . ..
Beispiel
Wir wollen
1
3
im Binärsystem entwickeln. Es ist
h 1i h2i
h 2i h4i
a0 = 0, a1 = 2 ·
=
= 0, a2 = 2 ·
=
= 1,
3
3
3
3
h 1i h2i
=
=0
a3 = 2 ·
3
3
Beispiel
Wir wollen
1
3
im Binärsystem entwickeln. Es ist
h 1i h2i
h 2i h4i
a0 = 0, a1 = 2 ·
=
= 0, a2 = 2 ·
=
= 1,
3
3
3
3
h 1i h2i
=
=0
a3 = 2 ·
3
3
und es ist klar, dass
1
= 0.012 .
3

Download Report