Ausblick: Die Hausdorff-Metrik
In einem metrischen Raum (X, d) hatten wir folgende Abstände zwischen Punkten und nichtleeren Mengen erklärt:
| d(x, A) = infy ∈ A d(x, y) | für alle x ∈ X und alle nichtleeren A ⊆ X, |
| d(A, B) = infx ∈ A, y ∈ B d(x, y) | für alle nichtleeren A, B ⊆ X. |
Die zweite Definition verallgemeinert die erste, da d(x, A) = d({ x }, A). Wir nannten d(A, B) den Abstand zwischen A und B in (X, d). Dies entspricht dem alltäglichen Abstand, den zum Beispiel zwei Häuser voneinander haben. Die Funktion d(·, ·) ist jedoch keine Metrik auf dem System der nichtleeren Teilmengen von X. Ist A ≠ B und A ∩ B ≠ ∅, so ist d(A, B) = 0. Die Symmetrie gilt, aber die Dreiecksungleichung ist verletzt. So gilt zum Beispiel in ℝ
d([ 0, 1 ], [ 2, 3 ]) = 1 > 0 = 0 + 0 = d([ 0, 1 ], [ 1, 2 ]) + d([ 1, 2 ], [ 2, 3 ]).
Es stellt sich die Frage, wie man eine Metrik für möglichst viele Teilmengen eines metrischen Raumes einführen kann. Eine Antwort ist von Felix Hausdorff (der auch den Begriff des metrischen Raumes prägte) gefunden worden. Der Grundgedanke der Konstruktion wird durch folgende Setzung zum Ausdruck gebracht (wobei „dH“ für Hausdorff-Abstand steht):
(+) dH(A, B) = max(supa ∈ A d(a, B), supb ∈ B d(b, A)).
Diese auf den ersten Blick verwickelte Formel lässt sich anschaulich erklären: Muss ein Bewohner a von A nach B umziehen oder fliehen, so braucht er hierzu mindestens d(a, B) (räumliche oder zeitliche) Einheiten. Damit kann jeder Bewohner von A die Menge B in supa ∈ Ad(a, B) Einheiten erreichen, und diese Schranke ist bestmöglich. Analoges gilt für das zweite Supremum in (+). Dass die beiden Suprema unterschiedlich sein können, zeigt:
Beispiel
Seien A = [ 0, 1 ] und B = [ 2, 100 ]. Dann gilt für die euklidische Metrik:
supa ∈ A d(a, B) = 2, supb ∈ B d(b, A) = 99.
Damit ist dH(A, B) = max(2, 99) = 99.
Damit dH eine Metrik ist, sind noch einige Einschränkungen nötig. Durch die Suprema in (+) ist der Wert ∞ möglich. Weiter gilt dH(A, B) = dH(cl(A), B), sodass die Nullbedingung verletzt sein kann. Es erscheint also günstig, lediglich abgeschlossene und beschränkte Mengen A, B in (X, d) zu betrachten. Sind die Mengen (für manche Räume stärker) kompakt, so stehen uns zudem Überdeckungsargumente und die Sätze für stetige Funktionen auf kompakten Mengen zur Verfügung. Wir gönnen uns die Kompaktheit und definieren:
Definition (Hausdorff-Metrik)
Sei (X, d) ein metrischer Raum, und sei
ℋ = { A ⊆ X | A ist kompakt und nichtleer }.
Dann definieren wir die Hausdorff-Metrik dH : ℋ2 → [ 0, ∞ [ durch
dH(A, B) = max(maxa ∈ A d(a, B), maxb ∈ B d(b, A)) für alle A, B ∈ ℋ.
Der Raum (ℋ, dH) heißt der Hyperraum der nichtleeren kompakten Teilmengen von (X, d).
In der Definition haben wir stillschweigend die Suprema in (+) durch Maxima ersetzt. Dies ist aufgrund der Kompaktheit der Mengen A, B möglich, denn die stetigen Funktionen d(·, B) und d(·, A) nehmen auf A bzw. B ihr Maximum an. In unserer Interpretation ist also die reelle Zahl c = dH(A, B) wie folgt bestimmt:
(a) | Jeder Bewohner einer der beiden Mengen kann die andere Menge in c Einheiten erreichen. |
(b) | Es gibt ein a in A oder ein b in B, das genau c Einheiten zurücklegen muss, um in die andere Menge zu kommen. |
Damit ist dH(A, B) klein, wenn jedes Element von A nahe bei B liegt und umgekehrt. Anschaulich bedeutet dies, dass A und B „fast deckungsgleich“ sind. Ausreißer können dabei nicht vernachlässigt werden, auch wenn sie nur isolierte Punkte sind. So gilt zum Beispiel dH(A, A ∪ { 2 } ) = 1 für A = [ 0, 1 ] in ℝ. Die Anschauung „fast deckungsgleich“ lässt sich wie folgt präzisieren:
Definition (ε-Expansion einer Menge)
Sei (X, d) ein metrischer Raum, und sei ε > 0. Dann definieren wir für alle P ⊆ X die ε-Expansion P+ε von P in (X, d) durch:
P+ε = ⋃p ∈ P Uε(x).
Die Menge P+ε ist eine offene Obermenge von P. Anschaulich entsteht sie, wenn wir P mit einer „ε-Unschärfe“ betrachten: Jeder Punkt p in P verschmiert zu Uε(p). Den Zusammenhang mit dH beschreibt nun:
Satz (Hausdorff-Metrik via ε-Expansionen)
Sei (ℋ, dH) der Hyperraum von (X, d). Dann gilt für alle A, B ∈ ℋ:
dH(A, B) = inf({ ε > 0 | A ⊆ B+ε und B ⊆ A+ε }).
Da A, B abgeschlossen und ε-Expansionen offen sind, ist das Infimum echt, d. h. aus A ⊆ B+ε und B ⊆ A+ε folgt immer dH(A, B) < ε.
Wir überlassen den Nachweis des Satzes dem Leser. Mit seiner Hilfe oder auch durch Anwendung der Definition möge er zudem zeigen, dass dH tatsächlich eine Metrik auf ℋ ist.
Eigenschaften der Hausdorff-Metrik
Der Hyperraum erbt wichtige Eigenschaften des Grundraums:
Satz (Vollständigkeit und Kompaktheit der Hausdorff-Metrik)
Sei (ℋ, dH) der Hyperraum von (X, d). Dann gilt:
(a) | Ist (X, d) vollständig, so auch (ℋ, dH). Genauer gilt dann: Ist (An)n ∈ ℕ eine Cauchy-Folge in ℋ, so gilt limn An = { x ∈ X | es gibt xn ∈ An mit x = limn xn in (X, d) }. |
(b) | Ist (X, d) total beschränkt, so auch (ℋ, dH). |
(c) | Ist (X, d) kompakt, so auch (ℋ, dH). |
Beweisskizze
zu (a): Sei (An)n ∈ ℕ eine Cauchy-Folge in (ℋ, dH). Dann sind die Mengen An schließlich „fast deckungsgleich“: Für alle ε > 0 existiert ein n0, sodass für alle n, m ≥ n0 gilt:
An ⊆ A+εm und Am ⊆ A+εn.
Ist (X, d) vollständig, so verliert sich im Limes die ε-Unschärfe, und der „scharfe“ Grenzwert der An ist die Menge aller Punkte von X, die durch Pfade in den Mengen An (Folgen (xn)n ∈ ℕ mit xn ∈ An für alle n) erreicht werden können.
zu (b): Ist (X, d) total beschränkt und ε > 0, so gibt es x1, …, xn in X mit
X = Uε(x1) ∪ … ∪ Uε(xn).
Jede endliche Teilmenge von { x1, …, xn } ist kompakt und damit ein Element von ℋ, sofern sie nichtleer ist. Damit ist
𝒜 = { E | E ⊆ { x1, …, xn }, E ≠ ∅ }
eine Teilmenge von ℋ. Weiter gilt
ℋ = ⋃E ∈ 𝒜 Uε(E).
Denn ist A ∈ ℋ, so ist E = { xi | Uε(xi) ∩ A ≠ ∅ } ∈ 𝒜 und es gilt
E ⊆ A+ε und A ⊆ E+ε.
Also ist dH(A, E) < ε und damit A ∈ Uε(E). Dies zeigt, dass (ℋ, dH) total beschränkt ist.
zu (c): Die Aussage folgt aus (a) und (b), da Vollständigkeit und totale Beschränktheit äquivalent zur Kompaktheit ist.
Kontraktionen auf dem Hyperraum
Auch Kontraktionen übertragen sich auf den Hyperraum, sodass der Banachsche Fixpunktsatz zur Verfügung steht. Allgemeiner können wir endlich viele Kontraktionen auf (X, d) zu einer Kontraktion auf (ℋ, dH) verschmelzen:
Satz (induzierte Kontraktionen im Hyperraum)
Sei (X, d) vollständig, und sei (ℋ, dH) der Hyperraum von (X, d). Weiter seien f1, …, fn : X → X Kontraktionen in (X, d) mit Kontraktionskonstanten c1, …, cn. Weiter sei F : ℋ → ℋ definiert durch
F(A) = f1[ A ] ∪ … ∪ fn[ A ] für alle A ∈ ℋ.
Dann ist F eine Kontraktion mit der Konstanten c = max1 ≤ k ≤ n ck, und es gibt genau ein A* ∈ ℋ mit F(A*) = A*. Für alle A ∈ ℋ gilt
A* = limn Fn(A), wobei F0(A) = A, Fn + 1(A) = F(Fn(A)) für alle n.
Beweis
Wir zeigen durch Induktion nach n ≥ 1, dass F eine Kontraktion mit der Konstanten c ist. Der Zusatz folgt aufgrund der Vollständigkeit von (ℋ, dH) aus dem Banachschen Fixpunktsatz.
Induktionsanfang n = 1:
Seien f = f1 und c = c1, sodass d(f (x), f (y)) ≤ c d(x, y) für alle x, y ∈ X. Dann gilt für alle A, B ∈ ℋ:
(+) A ⊆ B+ε impliziert f[ A ] ⊆ f[ B+ε ] ⊆ f[ B ]+cε.
Hieraus folgt dH(F(A), F(B)) = dH(f[ A ], f[ B ]) ≤ c dH(A, B).
Induktionsschritt von n nach n + 1:
Für alle A0, A1, B0, B1 ∈ ℋ gilt:
(++) dH(A0 ∪ A1, B0 ∪ B1) ≤ max(dH(A0, B0), dH(A1, B1)).
Sind nun A, B ∈ ℋ, so liefert Anwendung von (++) auf die Mengen
A0 = f1[ A ] ∪ … ∪ fn[ A ], A1 = fn + 1[ A ],
B0 = f1[ B ] ∪ … ∪ fn[ B ], B1 = fn + 1[ B ]
zusammen mit der Induktionsvoraussetzung die Behauptung.
Ist F : ℋ → ℋ wie im Satz, so gibt es also eine eindeutige kompakte Teilmenge A* von X, die alle anderen kompakten Mengen A ⊆ X unter der Operation F zu sich sich heranzieht. Starten wir bei A und wenden wir wiederholt F an, so konvergiert die so entstehende Folge von kompakten Mengen An = Fn(A) unter der Metrik dH gegen A*.
Die Fixpunkte von induzierten Kontraktionen im Hyperraum haben oft eine fraktale Gestalt und mit Hilfe des Satzes sind viele fraktale Gebilde konstruiert worden. Die Cantor-Menge ist ein instruktives Beispiel:
Die Cantor-Menge und ihre Varianten
Wir betrachten das kompakte reelle Intervall X = [ 0, 1 ] mit der euklidischen Metrik und die Kontraktionen f1, f2 : X → X mit
f1(x) = x/3, f2(x) = x/3 + 2/3 für alle x ∈ [ 0, 1 ].
Weiter sei C = ⋂n Cn die Cantor-Menge. Für alle n sei En die Menge der Mittelpunkte der aus C0, …, Cn entfernten Drittelintervalle, also
E0 = { 1/2 }, E1 = { 1/6, 1/2, 5/6 }, …
Ist nun F : ℋ → ℋ die durch f1 und f2 induzierte Kontraktion, so gilt
Fn([ 0, 1 ]) = Cn, Fn({ 1/2 }) = En, limn Cn = limn En = C.
Wir können auch mit A = A0 = { 1/10 } ∪ [ 5/7, 6/7 ] starten. Der Limes im Hyperraum ist erneut die Cantor-Menge C. Weiter sind viele Varianten möglich. Die folgenden Diagramme zeigen einige Mengen An = Fn[ A ] für A = [ 0, 1 ] und die modifizierten Kontraktionen
f1(x) = x/2, f2(x) = x/4 + 3/4 für alle x ∈ [ 0, 1 ].
Das Sierpinski-Dreieck
Auf X = [ 0, 1 ]2 (mit der euklidischen Metrik) definieren wir
f1(x, y) = (x/2, y/2),
f2(x, y) = (x/2, y/2) + (1/2, 0),
f3(x, y) = (x/2, y/2) + (1/4, /4) für alle (x, y) ∈ X.
Diese Kontraktionen lassen sich durch eine Skalierung um den Faktor 1/2 beschreiben, die für f2 und f3 durch eine Translation ergänzt wird. Die folgenden Diagramme zeigen einige An = Fn[ A ] für das gleichseitige Dreieck A mit den Ecken (0, 0), (1, 0), (1/2, /2).
Starten wir anstelle von A mit der Strecke B = [ 0, 1 ] × { 0 } von (0, 0) nach (1, 0), so erhalten wir Linienmuster Bn = Fn[ B ]:
Der Grenzwert limn An = limn Bn heißt das Sierpinski-Dreieck.
Die Koch-Kurve
Auf X = [ 0, 1 ]2 wie oben definieren wir die Kontraktionen
f1(x, y) = (x/3, y/3),
f2(x, y) = (x/6 − y/6, x/6 + y/6) + (1/3, 0),
f3(x, y) = (x/6 + y/6, − x/6 + y/6) + (1/2, /6),
f4(x, y) = (x/3, y/3) + (2/3, 0) für alle (x, y) ∈ X.
Startend mit der Strecke B von (0, 0) nach (1, 0) erhalten wir die folgenden Mengen Bn = Fn [ A ]:
Der Limes limn Bn heißt die Koch- oder Schneeflockenkurve.