Repräsentation abgeschlossener Mengen durch Bäume
Auch für die abgeschlossenen Mengen eines Folgenraumes bietet sich eine natürliche und anschauliche Darstellung durch endliche Folgen an: Die abgeschlossenen Mengen entsprechen den Bäumen auf A. Die grundlegenden Begriffe über Bäume bestehend aus endlichen Folgen versammelt die folgende Definition.
Definition (Mengen aus endlichen Folgen und Bäume, Tr(S), [ S ])
Sei A eine Menge, und sei S ⊆ SeqA.
(i) | Jedes s ∈ S heißt ein Knoten von S. |
(ii) | f ∈ ℕA heißt ein unendlicher Pfad oder ein unendlicher Zweig von S, falls f|n ∈ S für unendlich viele n ∈ ℕ. |
(iii) | Der Körper von S, in Zeichen [ S ] ist definiert durch: [ S ] = { f ∈ ℕA | f ist ein unendlicher Pfad von S }. |
(iv) | S heißt ein Baum auf A, falls für alle s ∈ S gilt: Ist n < |s|, so ist s|n ∈ S. |
(v) | Tr(S) = { t ∈ SeqA | t ≤ s für ein s ∈ S } heißt der von S erzeugte Baum auf A. |
Bäume werden durch die Anfangsstück-Ordnung < partiell geordnet. Ein nichtleerer Baum enthält immer die leere Folge ∅ als Wurzel, d. h. als <-kleinstes Element. Die leere Menge gilt als Baum.
Die Folgenmengen Seq und Seqm für m ≥ 2 sind Bäume auf ℕ. Seq2 heißt auch der vollständige binäre Baum.
Ein T ⊆ SeqA ist genau dann ein Baum, falls T abgeschlossen unter Anfangsstücken ist. Ist T ein Baum, so ist [ T ] = { f ∈ ℕA | f|n ∈ T für alle n ∈ ℕ }.
Der Baum Tr(S) ist der ⊆-kleinste Baum, der S umfasst, und insbesondere gilt Tr(T) = T, falls T ein Baum ist. Jedes S ist dicht „nach oben“ in Tr(S): Für alle t ∈ Tr(S) existiert ein s ∈ S mit t ≤ s. Für alle S ⊆ SeqA ist [ S ] eine Teilmenge von [ Tr(S) ], aber die Umkehrung ist i. A. falsch:
Übung
(i) | Hat A mindestens zwei Elemente, so existiert eine Antikette S in SeqA mit [ Tr(S) ] ≠ ∅. |
(ii) | Ist S eine Antikette in SeqA, so ist [ S ] = ∅. |
Neben Mengen S ⊆ SeqA erzeugen auch Punktmengen P ⊆ ℕA Bäume auf A:
Definition (von Mengen erzeugte Bäume)
Sei A eine Menge, und sei P ⊆ ℕA. Dann heißt
TP = { s ∈ SeqA | s < f für ein f ∈ P }
der zu P gehörige oder von P erzeugte Baum auf A.
Der Übergang von P zu TP ist nicht injektiv. Es gilt:
Übung
Sei A eine Menge, und sei P ⊆ ℕA. Dann sind äquivalent:
(i) | P ist dicht in ℕA. |
(ii) | Es gilt TP = SeqA. |
Wir geben einigen ins Auge springenden Eigenschaften eines Baumes noch spezielle Namen.
Definition (endlich verzweigte und perfekte Bäume, Blätter, sucT(s))
Sei A eine Menge, und sei T ⊆ SeqA ein Baum auf A.
(i) | T heißt endlich verzweigt, falls für alle s ∈ T die Menge sucT(s) = { sa | a ∈ A und sa ∈ T } der direkten Nachfolger von s in T endlich ist. |
(ii) | Ein s ∈ T heißt ein Blatt von T, falls sucT(s) = ∅ gilt. |
(iii) | T heißt blattfrei, falls T keine Blätter besitzt. |
(iv) | T heißt perfekt, falls für alle s ∈ T ein t ∈ T existiert mit:
|
Blattfreie Bäume haben also keine toten Äste, und perfekte Bäume spalten sich sogar oberhalb jedes Knotens irgendwann in mindestens zwei neue Äste auf: Für jedes s ∈ T existieren inkompatible Fortsetzungen t1 und t2 von s in T. Ein blattfreier nicht perfekter Baum hat dagegen mindestens einen ab einer Stelle einsam vor sich hinwachsenden unendlichen Zweig.
Für alle m ≥ 2 ist Seqm ein endlich verzweigter perfekter Baum. Endlich verzweigte Bäume T sind aber oftmals nicht derartig homogen verzweigt. Die Kardinalität von sucT(s) kann von s abhängen.
Übung
Sei A eine Menge, und sei T ⊆ SeqA ein Baum. Dann sind äquivalent:
(i) | T ist endlich verzweigt. |
(ii) | T hat endliche Stufen, d. h. für alle n ist { s ∈ T | |s| = n } endlich. |
Bei der Betrachtung von Bäumen und ihren unendlichen Zweigen spielt der folgende Satz eine Schlüsselrolle. Für sich schon ansprechend genug ist er insbesondere bei Kompaktheitsargumenten ein bewährtes Qualitätswerkzeug. Er garantiert die Existenz eines unendlichen Zweiges in endlich verzweigten Bäumen mit unendlich vielen Knoten.
Satz (Lemma von Denes König)
Sei A eine Menge, und sei T ⊆ SeqA ein endlich verzweigter Baum.
Weiter sei T unendlich.
Dann ist [ T ] ≠ ∅. Insbesondere gilt:
Ist A endlich und S ⊆ SeqA unendlich, so ist [ Tr(S) ] ≠ ∅.
Beweisidee in einem Satz als Lebensweisheit: Gehe den Pfad, der dir stets unendlich viele Möglichkeiten offen hält. Zugegeben ist der mathematische Beweis auch nicht wesentlich länger:
Beweis
Wir definieren rekursiv für n ∈ ℕ Knoten sn von T durch:
| s0 | = ∅, |
| sn + 1 | = „ein s ∈ sucT(sn), für welches { t ∈ T | s ≤ t } unendlich ist“. |
Ein solches s existiert wegen sucT(sn) endlich, da
{ t ∈ T | sn < t } = ⋃s ∈ sucT(sn) { t ∈ T | s ≤ t }
unendlich ist: Für n = 0 gilt dies wegen T unendlich, und andernfalls gilt es nach Induktionsvoraussetzung.
Wir setzen f = ⋃n ∈ ℕ sn. Dann ist f ∈ [ T ].
Zum Zusatz: Für unendliche S ⊆ SeqA und endliche A ist Tr(S) ein unendlicher endlich verzweigter Baum, und damit [ Tr(S) ] ≠ ∅.
T = { s ∈ Seq | |s| ≤ 1 } ist ein unendlicher Baum mit [ T ] = ∅. Die Voraussetzung „Baum“ im Lemma von König ist aber ebenso wesentlich wie die endliche Verzweigung:
Übung
Es gibt ein unendliches S ⊆ Seq2 mit [ S ] = ∅.
Dagegen gilt:
Übung
Sei A eine Menge, und sei S ⊆ SeqA derart, dass Tr(S) blattfrei ist (d. h. S hat keine maximalen Elemente). Dann sind äquivalent:
(i) | [ S ] = [ Tr(S) ]. |
(ii) | [ S ] ist abgeschlossen. |
Im Umfeld des Lemmas von König und beim Nachdenken über den Unterschied zwischen [ S ] und [ Tr(S) ] stößt man auch auf den folgenden Begriff:
Definition (Barrieren in Bäumen)
Sei A eine Menge, und sei T ⊆ SeqA ein Baum auf A.
B ⊆ T heißt eine Barriere in T, falls gilt:
Für alle f ∈ [ T ] existiert ein n ∈ ℕ mit f|n ∈ B.
Eine Barriere B′ heißt Teilbarriere von B, falls B′ ⊆ B gilt.
Eine einfache Folgerung aus dem Lemma von König ist nun der folgende Satz über die Existenz endlicher Teilbarrieren:
Satz (Fächersatz)
Sei A eine Menge, und sei T ⊆ SeqA ein endlich verzweigter Baum auf A.
Dann hat jede Barriere B in T eine endliche Teilbarriere in T.
Beweis
Sei B′ die offene Reduzierung von B. Dann ist B′ eine Barriere in T.
B′ ist eine Antikette in SeqA, und wegen B′ Barriere in T gilt [ Tr(B′) ] = ∅.
Nach dem Lemma von König ist dann Tr(B′) und damit B′ endlich.
Übung
Beweisen Sie das Lemma von König mit Hilfe des Fächersatzes.
Wir zeigen nun einen Darstellungssatz für abgeschlossene Mengen.
Satz (Repräsentation abgeschlossener Mengen)
Sei P ⊆ ℕA. Dann sind äquivalent:
(i) | P ist abgeschlossen. |
(ii) | Es gibt einen Baum T auf A mit P = [ T ]. |
Beweis
(i) ↷ (ii): Sei T = TP. Wir zeigen [ T ] = P.
Sei f ∈ P. Für alle n ist f|n ∈ T. Also ist f ∈ [ T ]. Also P ⊆ [ T ].
Sei nun f ∈ [ T ]. Dann existiert für jedes n ein fn ∈ P mit f|n = fn|n.
Also f = limn → ∞ fn. Wegen P abgeschlossen ist also f ∈ P.
Also auch [ T ] ⊆ P.
(ii) ↷ (i): Sei P = [ T ] für einen Baum T.
Sei f ∈ ℕA − P. Dann existiert ein n mit s = f|n ∉ T.
Dann ist aber NAs ⊆ ℕA − P, da T Baum.
Also ist ℕA − P offen und damit P abgeschlossen.
Der Beweis zeigt: Für abgeschlossene P gilt [ TP ] = P. Der Übergang von P zu TP ist also injektiv für die abgeschlossenen Mengen. Offenbar ist TP der einzige blattfreie Baum T mit P = [ T ]. Wir definieren:
Definition (kanonischer Kode einer abgeschlossenen Menge)
Sei P ⊆ ℕA abgeschlossen.
Dann heißt TP der kanonische (abgeschlossene) Kode von P in ℕA.
Die beiden Kodierungen zeigen einmal mehr: Abgeschlossene Mengen sind komplizierter als offene Mengen.
Für Mengen U ⊆ ℕA, die zugleich offen und abgeschlossen sind, haben wir zwei verschiedene Kodes definiert. Den Kode S = SU für offene U und den Kode T = TU für abgeschlossene U. Es gilt T = { t ∈ SeqA | es gibt ein s ∈ S mit t ≤ s oder s ≤ t }. Ist S der Kode einer beliebigen offenen Menge U, so liefert diese Definition den Kode T von cl(U).
Allgemein gilt:
Übung
Sei A eine Menge, und sei P ⊆ ℕA. Dann gilt [ TP ] = cl(P).
Perfekte Mengen
Wir betrachten nun noch spezielle abgeschlossene Mengen. Hierzu definieren wir für topologische Räume diejenigen Begriffe, deren Untersuchung für den Raum ℝ im letzten Viertel des 19. Jahrhunderts die Mengenlehre und in der Folge auch die Topologie und Maßtheorie in Gang setzte. Sie gehen auf Cantor zurück.
Definition (isolierte Punkte, Häufungspunkte, perfekte Räume, perfekte Mengen)
Sei 𝒳 = 〈 X, 𝒰 〉 ein topologischer Raum, und sei P ⊆ X.
(i) | Ein x ∈ P heißt ein isolierter Punkt von P, falls es ein offenes U gibt mit U ∩ P = { x }. |
(ii) | Ein x ∈ X heißt ein Häufungspunkt oder Limespunkt von P, falls für alle offenen U mit x ∈ U gilt: U ∩ P ist unendlich. |
(iii) | P heißt perfekt (in 𝒳), falls P abgeschlossen ist und keine isolierten Punkte besitzt. |
(iv) | 𝒳 heißt perfekt, falls X perfekt ist. |
In der Definition von „Häufungspunkt“ lassen wir beliebige x ∈ X zu; sie können zu P gehören oder nicht. Ist x ∈ P kein isolierter Punkt von P, so ist x ein Häufungspunkt von P.
Da X immer abgeschlossen in 𝒳 ist, ist 𝒳 genau dann perfekt, wenn X keine isolierten Punkte besitzt.
Ist P ⊆ 𝒩 und f ∈ P, so ist f genau dann ein isolierter Punkt von P, wenn es ein s ∈ Seq gibt mit Ns ∩ P = { f }. Ist f ein Häufungspunkt von P, so laufen für alle s < f unendlich viele Elemente von P durch s. Umgekehrt gilt bereits:
Übung
Ist f ∈ P, und läuft durch jedes s < f noch mindestens ein weiteres g ∈ P (d. h. es gibt ein g ∈ P mit s < g und g ≠ f), so ist f ein Häufungspunkt von P.
Die perfekten Teilmengen von 𝒩 entsprechen nun genau den perfekten Bäumen. Allgemein gilt der einfach zu zeigende Satz:
Satz (Darstellung perfekter Mengen durch perfekte Bäume)
Sei A eine Menge, und sei P ⊆ ℕA. Dann sind äquivalent:
(i) | P ist perfekt. |
(ii) | P ist abgeschlossen und TP ist perfekt. |
Die leere Menge und der leere Baum gelten als perfekt.
Dem Begriff der perfekten Menge kommt eine Schlüsselrolle in der Approximation des Kontinuumsproblems zu. Wir werden ihn in der Folge noch genauer untersuchen.