5. Unendliche Kombinatorik

Die Themen der unendlichen Kombinatorik sind vielgestaltig, und das Gebiet selbst ist nicht einfach zu umschreiben. Ein Hauptthema ist sicherlich das unendliche Zählen: Wieviele Objekte eines bestimmten Typs gibt es? Damit wäre auch die Kontinuumshypothese und allgemeiner die Kardinalzahlarithmetik der unendlichen Kombinatorik zuzuordnen. Traditionell wird aber dieses Gebiet für sich betrachtet, während folgende Version der Frage der Kombinatorik zugeordnet wird: Wieviele Objekte gibt es, wenn eine Identifikation von Objekten unter einer bestimmten Äquivalenzrelation vorgenommen wird? Und weiter: Welche Struktureigenschaften besitzt die − zumeist partiell geordnete − Menge der Äquivalenzklassen?

 Die beiden wichtigsten Äquivalenzen, die wir hier untersuchen, sind die Faktorisierungen von Mengen und Funktionen nach einem der beiden prominenten Kleinheitsbegriffe der Mengenlehre. Zum einen betrachten wir hier für Kardinalzahlen κ ≥ ω das Ideal der Mengen der Mächtigkeit kleiner κ, und zum anderen für reguläre Kardinalzahlen κ ≥ ω₁ das umfassendere und subtilere Ideal der nichtstationären oder dünnen Mengen. Unser Hauptaugenmerk liegt auf der stationären Kombinatorik der ersten überabzählbaren Kardinalzahl. Wir diskutieren hier eine Reihe von natürlichen und einfach zu formulierenden Prinzipien, die allesamt in ZFC weder beweisbar und modulo der Konsistenz großer Kardinalzahlen auch nicht widerlegbar sind.

 Ein anderer intensiv erforschter Gegenstand der unendlichen Kombinatorik sind die Bäume, die wir als eine Verallgemeinerung der Wohlordnungen ansehen können: Wir verzichten auf die Eindeutigkeit von Nachfolgern und von Suprema, sodass sich die Strukturen also an jeder Stelle beliebig verzweigen können, während die Wohlfundiertheit erhalten bleibt. Auch hier spielt die Kardinalzahl ω₁ eine Hauptrolle. Insbesondere übersetzen wir die Suslin-Hypothese in eine gleichwertige Hypothese über die Existenz gewisser Bäume der Höhe ω₁, der so genannten Suslin-Bäume. In dieser Form werden wir später die Unabhängigkeit der Suslin-Hypothese nachweisen. Bereits hier führen wir aber ein starkes kombinatorisches Prinzip ein, das uns die Konstruktion von Suslin-Bäumen erlaubt. Im zweiten Abschnitt werden wir zeigen, dass dieses Prinzip in Gödels Modell L richtig ist.

 Schließlich betrachten wir Partitionen und homogene Teilmengen. Das übergeordnete Thema ist hier die Existenz von großen einfach strukturierten Teilen von großen komplizierten Systemen.

 Im Verlauf der Untersuchung werden wir auch zwei neue große Kardinalzahlprinzipien kennen lernen, nämlich die schwach kompakten und die Ramsey-Kardinalzahlen. Die schwach kompakten Kardinalzahlen erlauben dabei sowohl eine Formulierung über Eigenschaften von Bäumen als auch eine Formulierung über Partitionen.

 Insgesamt versteht sich dieses Kapitel als eine kompakte Einführung in ein großes Teilgebiet der Mengenlehre. Viele Dinge können wir nur kurz ansprechen oder referieren, ohne sie dann weiter zu verfolgen. Der Leser sei hierzu auf die Literatur verwiesen. Im zweiten Abschnitt werden wir vor allem die Theorie der Bäume wieder aufgreifen, und der Leser, der primär an einem Beweis der Unabhängigkeit der Suslin-Hypothese interessiert ist, kann sich auf den Zwischenabschnitt über Bäume beschränken. Daneben setzen wir im Folgenden nur ein Grundverständnis der stationären Mengen voraus.

Fast disjunkte Mengen und Funktionen

 Für jede Kardinalzahl κ gibt es 2^κ-viele Teilmengen von κ. Andererseits kann es offenbar nur κ-viele paarweise disjunkte nichtleere Teilmengen von κ geben. Ist κ eine unendliche Kardinalzahl, so gibt es wegen |κ × κ| = κ sogar κ-viele paarweise disjunkte Teilmengen von κ der Größe κ. Denn ist b : κ × κ → κ bijektiv, so setzen wir

A  =  { b″(κ × { α }) | α < κ }.

Dann gilt |x| = κ für alle x  ∈  A und x ∩ y = ∅ für alle x, y  ∈  A mit x ≠ y.

 Fragen, wie groß eine Familie von paarweise „fast disjunkten“ Teilmengen von κ sein kann, sind wesentlich schwieriger zu beantworten. Allgemein liefert jedes Ideal I auf κ eine Abschwächung des Begriffs der Disjunktheit: Zwei Teilmengen x und y von κ sind fast disjunkt im Sinne des Ideals I, falls x ∩ y  ∈  I. Die Ideale mit der geringsten Unschärfe sind die Mächtigkeitsideale

I_{< κ}  =  { x ⊆ κ | |x| < κ },

und wir definieren entsprechend:

 Am vertrautesten ist der Fall κ = ω. Hier sind x, y ⊆ ω fast disjunkt, falls x ∩ y endlich ist. Ein A ⊆ ℘(ω) ist fast disjunkt, falls A aus unendlichen Mengen besteht, die paarweise einen endlichen Schnitt haben.

 Ist A ⊆ ℘(κ) fast disjunkt, so gilt trivialerweise |A| ≤ 2^κ. Nach der einleitenden Bemerkung gibt es sogar ganz disjunkte A ⊆ ℘(κ) mit |A| = κ. Die natürlichen Fragen sind nun:

Gibt es ein fast disjunktes A ⊆ ℘(κ) mit |A| = κ⁺?

Gibt es sogar ein fast disjunktes A ⊆ ℘(κ) mit |A| = 2^κ?

Was kann man in ZFC über die Existenz fast disjunkter A ⊆ ℘(κ) sagen?

 Bevor wir uns der weiteren Untersuchung dieser Fragen zuwenden, ist es nützlich, auch fast disjunkte Funktionen zu betrachten. Der Leser kann vorab versuchen, ein fast disjunktes A ⊆ ℘(ω) der Größe ω₁ zu konstruieren. Mit Hilfe von fast disjunkten Funktionen und einem kleinen Trick wird diese Aufgabe sehr einfach (vgl. das Korollar unten).

 Durch ein (wie immer sehr ansprechendes) Diagonalargument können wir recht einfach beweisen:

 Mit Hilfe dieses Satzes können wir unsere erste Frage positiv beantworten:

 Einen direkteren Beweis des Korollars für reguläre κ liefert folgende Übung, die die Methode der disjunkten Ausdünnung verwendet.

 Nach dem Korollar (und auch nach der Übung) existieren ω₁-viele fast disjunkte unendliche Teilmengen von ω. Unter einer bestimmten Voraussetzung existieren nun sogar größtmögliche fast disjunkte Familien, und wir können damit die zweite Frage für den Fall κ = ω bejahen:

 Für ω₁ existiert ein fast disjunktes A ⊆ ℘(ω₁) der Größe ω₂, aber wir können ohne eine zusätzliche Voraussetzung nicht mehr zeigen, dass eine fast disjunkte Menge A ⊆ ℘(ω₁) der Größe 2^ω₁ existiert. Die Existenz einer solchen Menge ist in ZFC weder beweisbar noch widerlegbar.

Kardinalzahlinvarianten

 Bevor wir uns den stationären Mengen auf überabzählbaren Kardinalzahlen zuwenden, betrachten wir noch die Struktur ^ωω unter der partiellen Ordnung der schließlichen Dominanz:

 Wir definieren zwei „Kardinalzahlinvarianten“, die die Komplexität der partiellen Ordnung ≼ messen:

 Es gilt ω₁ ≤ 𝔟 ≤ 𝔡 ≤ 2^ω. Die Kardinalzahlen 𝔟 und 𝔡 und allgemeiner kombinatorische Eigenschaften von ^ωω sind der kardinalen Untersuchung der Lebesgue-Meßbarkeit und der Baire-Meßbarkeit auf den reellen Zahlen von hohem Interesse. Wir geben einen knappen Einblick in dieses Themengebiet, und verweisen den Leser auf [ Bartoszyński 200? ] für eine umfassende Darstellung.

 Für jedes Ideal I auf einer Menge M können wir eine Reihe von Kardinalzahlen definieren, die bestimmte Struktureigenschaften des Ideals beschreiben:

 Hierbei steht add für additivity,  cov für covering,  cof für cofinality und out für outside.

 Ein klassisches Zentrum des Interesses bilden die Ideale der Lebesgue-Nullmengen und der mageren Teilmengen von ℝ (oder gleichwertig des Cantorraumes ^ω2 oder des Baireraumes ^ωω). Wir setzen:

I_n  =  { X ⊆ ℝ | X hat Lebesgue-Maß Null }

I_m  =  { X ⊆ ℝ | X ist mager }

und schreiben add_n statt add(I_n), cov_m statt cov(I_m), usw.

 Das folgende Ergebnis von Miller und Bartoszyński ist ein Beispiel dafür, wie sich die Kardinalzahlinvarianten von I_n und I_m durch kombinatorische Aussagen über ^ωω formulieren lassen. Es gilt:

 Die Kardinalzahlen 𝔟 und 𝔡 spielen eine wichtige Rolle bei der Untersuchung der Größenverhältnisse der Kardinalzahlinvarianten der Ideale I_n und I_m.

 Das sog. Cichoń-Diagramm zeigt die in ZFC beweisbaren Größenverhältnisse der betrachteten Kardinalzahlen:

 Einige Ungleichungen und Zusammenhänge des Diagramms sind nichttrivial, etwa

 Gilt (CH), so sind alle 10 Kardinalzahlen des Diagramms gleich ω₁. Mit Hilfe der Erwingungsmethode lassen sich aber verschiedene Konstellationen in Modellen realisieren, und insbesondere lässt sich zeigen, dass in ZFC keine weiteren Ungleichungen bestehen.

Stationäre Mengen

 Wir stellen die wichtigsten Begriffe und Ergebnisse über stationäre Mengen zusammen.

 Das Kunstwort club steht dabei für engl. closed unbounded.

 Für X ⊆ λ sei Lim(X) die Menge der (inneren) Limespunkte von X, also

Lim(X)  =  { δ < λ | δ Limes und δ = sup(X ∩ δ) }.

Ein unbeschränktes X ⊆ λ ist also genau dann club in λ, wenn Lim(X) ⊆ X. Für jedes unbeschränkte X ist X ∪ Lim(X) die kleinste X umfassende club-Menge in λ. Die Menge X ∪ Lim(X) heißt der Abschluss von X in λ.

 Sei nun λ ein Limes mit überabzählbarer Konfinalität. Ist dann X ⊆ λ unbeschränkt in λ, so ist Lim(X) club in λ. Insbesondere ist Lim(C) club in λ für alle club-Mengen C ⊆ λ.

 Ist λ ein Limes und ist f : γ → λ aufsteigend konfinal und stetig in λ, so ist rng(f) club in λ. Umgekehrt ist die monotone Aufzählung f einer club-Menge C ⊆ λ eine strikt aufsteigende konfinale und stetige Funktion in λ, und genauer ist f : o. t.(C) → C bijektiv.

 Folgendes „Einholphänomen“ taucht an vielen Stellen auf:

 Ist z. B. α₀ < κ beliebig, so sei rekursiv α_n + 1 = sup(f ″α_n) für alle n  ∈  ω. Wir setzen dann α* = sup_{n  ∈  ω} α_n. Dann gilt

f ″α*  =  ⋃_{n  ∈  ω} f ″ α_n  ⊆  ⋃_{n  ∈  ω} α_n + 1  =  α*.

Wir haben also f an der Stelle α* wieder eingeholt, so stark die Funktion auch ansteigen mag.

 „Stationär“ bedeutet einfach „nicht dünn“, sodass ein eigener Begriff vielleicht überflüssig erscheint. Der Begriff wird aber häufig verwendet, und statt „dünn“ findet man häufig auch „nichtstationär“. Aus der Definition folgt leicht, dass ein S ⊆ λ genau dann stationär ist, wenn S ∩ C ≠ ∅ für alle club-Mengen C ⊆ λ gilt.

 Über den club-Filter gilt:

 Für überabzählbare reguläre Kardinalzahlen gilt stärker:

 Äquivalent zur Normalität ist:

 Dass der club-Filter 𝒞_κ kein Ultrafilter ist, ist bereits für κ = ω₁ eine nichttriviale Aussage. Hierzu sind Ulam-Matrizen nützlich:

 Eine Ulam-Matrix auf κ = μ⁺ können wir einfach konstruieren. Für β < κ sei

g_β  =  „ein surjektives g : μ → β + 1“.

Für ν < μ und α < κ sei X_{ν, α} = { β < κ | g_β(ν) = α }. Dann ist 〈 X_{ν, α} | ν < μ, α < κ 〉 eine Ulam-Matrix.

 Aus der Existenz einer Ulam-Matrix auf κ = μ⁺ folgt, dass sich jedes stationäre S ⊆ κ in stationäre Mengen 〈 S_α | α < κ 〉 zerlegen lässt. Wir zeigen nun stärker, dass sich jede stationäre Teilmenge einer regulären überabzählbaren Kardinalzahl κ in κ-viele paarweise disjunkte stationäre Teilmengen zerlegen lässt. Für den Beweis brauchen wir ein für sich interessantes Ergebnis über nichtstationäre Reflexion:

 Damit können wir nun zeigen:

Stationäre Kombinatorik von ω₁

 Bereits der club-Filter auf ω₁ wirft viele natürliche kombinatorische Fragen auf, die sich in ZFC nicht beantworten lassen.

 Im Folgenden sei 𝒞 = 𝒞_ω1 und ℐ = ℐ_ω1. Es ist oft hilfreich, modulo ℐ zu denken und zu rechnen. Wir definieren also für X, Y ⊆ ω₁:

X ∼_ℐ Y,  falls  X Δ Y  =  X − Y ∪ Y − X   ∈  ℐ,

X ⊆_ℐ Y,  falls  X − Y  ∈  ℐ.

Es gilt X ∼_ℐ Y genau dann, wenn X ⊆_ℐ Y und Y ⊆_ℐ X. Wir setzen:

Ω  =  ℘(ω₁)/∼_ℐ  und  Ω*  =  Ω − { ℐ }.

Die partielle Ordnung ⊆_ℐ überträgt sich auf Ω, d. h. wir setzen

X/∼ ⊆_ℐ Y/∼,  falls X ⊆_ℐ Y.

Dann ist 𝒞 das maximale und ℐ das minimale Element von 〈 Ω, ⊆_ℐ 〉.

 Wir wissen, dass Ω eine „Breite“ größergleich ω₁ besitzt, denn es existiert eine ω₁-Folge paarweise disjunkter stationärer Mengen in ω₁. Nach dem Satz von Solovay besitzt Ω sogar unterhalb jedes Elements von Ω* eine Breite größergleich ω₁. Die folgende Eigenschaft besagt, dass Ω so „schmal“ wie möglich ist:

 Ist 𝒞 saturiert, so besitzt also jede Teilmenge von Ω* der Größe ω₂ zwei Elemente, die beide oberhalb von einem dritten Element von Ω* liegen.

 Folgende Eigenschaft besagt stärker, dass Ω so „flach“ wie möglich ist:

 Beide Eigenschaften des club-Filters sind in ZFC nicht beweisbar und modulo der Konsistenz großer Kardinalzahlen auch nicht widerlegbar.

 Eine andere kombinatorische Analyse von 𝒞 untersucht Funktionen von κ nach κ modulo des club-Filters:

 Die partielle Ordnung 〈 ^κκ, <* 〉 ist wohlfundiert, da es aufgrund der ω₁-Vollständigkeit von 𝒞 keine unendlichen absteigenden Folgen

f₀  >*  f₁  >*  …  >*  f_n  >*  …

geben kann: Sonst wäre C = ⋂_{n  ∈  ω} { α < ω₁ | f_n + 1(α) < f_n(α) }  ∈  𝒞, also insbesondere C ≠ 0. Und für ein α  ∈  C wäre dann f_n + 1(α) > f_n(α) für alle n  ∈  ω, was nicht sein kann. Wir können also wie üblich einen Rang auf 〈 ^κκ, <* 〉 definieren:

 Wir definieren nun eine <*-aufsteigende Folge der Länge ω₂ in ^κκ. Wir fixieren hierzu für jeden Limes λ < ω₂ eine in λ konfinale Folge 〈 λ_i | i < cf (λ) 〉. Es wird sich herausstellen, dass die mit Hilfe dieser Hilfsfolgen definierten Funktionen modulo der Äquivalenz =* unabhängig von diesen Folgen sind.

 Im Limesschritt bilden wir also mit Hilfe unserer Hilfsfolgen das punktweise Supremum bzw. das punktweise diagonale Supremum der bereits konstruierten Funktionen. Die Konstruktion können wir suggestiv wie folgt notieren:

h₀  =  0,  h_ν + 1  =  h_ν + 1  für alle ν

h_λ  =  sup _{i  <  cf (λ)} h_λi,  falls  cf (λ) = ω

h_λ  =  diagsup _{i  <  κ} h_λi,  falls  cf (λ) = ω₁

 Die Folge der kanonischen Funktionen ist offenbar <*-aufsteigend, d. h. für alle ν < ν′ < ω₂ gilt h_ν <* h_ν′. Weitere elementare Eigenschaften dieser Funktionen sind:

 Allgemeiner gilt:

 Es ist überraschend, dass wir die kanonischen Funktionen auch ohne Verwendung von Rekursion definieren können (modulo =*):

 Die vielleicht wichtigste Anwendung des Satzes ist:

 Eine natürliche Frage ist, ob wir das durch <* partiell geordnete System aller Funktionen von κ nach κ mit der <*-aufsteigenden ω₂-Folge 〈 h_ν | ν < ω₂ 〉 bis an sein Ende durchwandert haben. Zwei Hypothesen in diesem Umfeld sind:

 Die beiden Domininierungseigenschaften sind in ZFC nicht beweisbar und modulo großer Kardinalzahlen auch nicht widerlegbar.

 Direkte Implikationen zwischen in ZFC unbeweisbaren kombinatorischen Aussagen können wir i. A. nicht erwarten. Es gilt nun aber, dass die starke Dominierungseigenschaft aus der Saturiertheit von 𝒞 folgt. Damit haben wir die Implikationen:

 Wir betrachten schließlich noch eine natürliche Verstärkung der schwachen Dominierungseigenschaft. Ist f : ω₁ → ω₁ eine Funktion mit h_ν <* f für alle ν, so existieren ω₂-viele Funktionen g_ν : ω₁ → ω, mit der Eigenschaft:

{ α < ω₁ | g_ν(α) = g_μ(α) } ist dünn für alle ν < μ < ω₂.

Denn f (α) ist abzählbar für alle α < ω₁, und eine Abzählung aller f (α) liefert die Funktionen g_ν: Sei b_α : f (α) → ω injektiv für alle α < ω₁. Wir setzen dann g_ν(α) = b_α(h_ν(α)), falls h_ν(α) < f (α), und g_ν(α) = 0 sonst. Der „sonst“-Fall betrifft für alle ν < ω₂ nur eine dünne Menge von α < ω₁, und damit sind die Funktionen g_ν wie gewünscht. Wir definieren:

 Obiges Argument zeigt also, dass aus der Transversalen-Hypothese die schwache Dominierungseigenschaft folgt. Andererseits gilt wieder:

Ultrafilter auf ω₁

 Aus der Existenz einer Ulam-Matrix auf ω₁ folgt, dass kein ω₁-vollständiger uniformer Ultrafilter U auf ω₁ existieren kann. Anders formuliert: Es gibt kein nichttriviales 0-1-wertiges σ-additives Maß, das auf der ganzen Potenzmenge von ω₁ definiert ist. (Allgemeiner zeigt eine Ulam-Matrix, dass kein reellwertiges Maß existieren kann.) Wir können die unmögliche Forderung nach einem vollen Maß auf ω₁ aber in mancherlei Hinsicht abschwächen, und es ergeben sich dann wieder kombinatorische Fragen, die in ZFC weder beweisbar und modulo der Konsistenz großer Kardinalzahlen auch nicht widerlegbar sind.

Überdeckung von ℘(ω₁) durch Filter

 Eine nahe liegende Abschwächung ist die Frage, wie viele partielle Maße wir brauchen, um die ganze Potenzmenge von ω₁ ausmessen zu können. Der folgende Satz besagt, dass abzählbar viele partielle Maße nicht ausreichen:

 Wir brauchen also mindestens ω₁-viele ω₁-vollständige uniforme Filter, um jede Teilmenge von ω₁ mit zumindest einem dieser Filter messen zu können.

 Zwischen der Saturiertheit von 𝒞 und der Ulam-Eigenschaft bestehen keine Implikationen. Es gilt aber:

Abschwächungen der Vollständigkeit

 Eine andersartige Abschwächung der unmöglichen Messbarkeit besteht darin, die Ultrafilter-Eigenschaft beizubehalten, aber dafür die starken Schnitteigenschaften zu lockern. Eine derartige Lockerung besteht in einer Variation der Normalität. Ein Ultrafilter auf ω₁ ist genau dann normal, wenn es für jedes regressive f : ω₁ → ω₁ ein γ < ω₁ gibt mit { α < ω₁ | f (α) = γ }  ∈  U. Eine natürliche Abschwächung dieser für ω₁ zu starken Forderung ist:

 Eine subtile Abschwächung der ω₁-Vollständigkeit ist:

 Zwischen den beiden Begriffen besteht der folgende Zusammenhang:

 Es gilt auch die Umkehrung des Satzes: Jeder nichtreguläre Ultrafilter, der den club-Filter umfasst, ist schwach normal. Dies werden wir unten beweisen.

 Die Existenz eines schwach normalen Ultrafilters folgt, mit nichttrivialen Argument, aus der ω₁-Dichtheit von 𝒞. Andererseits gilt:

 Das Argument des Beweises liefert nun auch:

 In ZFC lässt sich zudem zeigen: Existiert ein nichtregulärer uniformer Ultrafilter U auf ω₁, so existiert ein nichtregulärer Ultrafilter U auf ω₁ mit U ⊇ 𝒞. Damit ist in ZFC die Existenz eines schwach normalen und eines nichtregulären Ultrafilters auf ω₁ gleichwertig.

Kombinatorische Implikationen

 Nach obigen Ergebnissen gelten die folgenden Implikationen (von oben nach unten) der betrachteten kombinatorischen Prinzipien auf ω₁:

 In Gödels Modell L ist die schwache Dominierungs-Eigenschaft verletzt, und damit gelten in diesem Modell die Negationen dieser Prinzipien. Um Modelle zu konstruieren, in denen die Prinzipien gelten können, werden relativ starke große Kardinalzahlen benötigt. Die optimalen großen Kardinalzahl-Hypothesen sind für die Ulam-Eigenschaft und für die Existenz nichtregulärer Ultrafilter noch unbekannt.

 Die betrachteten Prinzipien lassen sich auch für größere Kardinalzahlen als ω₁ formulieren. Sie werden dann noch stärker, und ob sie überhaupt noch konsistent sind, ist vielfach noch unklar.

 Unser Ausflug in die unendliche Kombinatorik auf ω₁ zeigt, wie vielfältig die Fragen sind, die das Licht von ZFC nicht erreicht. Zudem müssen − im Gegensatz zur Kontinuumshypothese − oft große Kardinalzahlen herangezogen werden, um zu zeigen, dass ein betrachtetes Prinzip nicht zu Widersprüchen führt. Alle Prinzipien im obigen Diagramm implizieren, dass ZFC widerspruchsfrei ist, und damit müssen wir nach dem zweiten Gödelschen Unvollständigkeitssatz ZFC substantiell verstärken, um Modelle dieser Prinzipien konstruieren zu können. Wir kommen auf diese Dinge im zweiten Abschnitt noch zurück.

 Subtile Implikationen sind ein typisches Kennzeichen für Theorien, denen ein starkes ordnendes Axiom fehlt. Neben ZFC ist auch ZF ein Beispiel für eine solche Theorie. Auch hier erhalten wir komplexe Implikationen zwischen vielen Aussagen, die sich mit Hilfe von AC beweisen lassen. Welches Axiom könnte nun für die kombinatorischen Prinzipien die ordnende Rolle übernehmen? Sollen wir annehmen, dass der club-Filter ω₁-dicht ist, weil wir dadurch viele kombinatorische Fragen lösen? Oder sollen wir Gödels konstruktibles Axiom annehmen, das scheinbar alle kombinatorischen Fragen beantwortet, aber alle starken Hypothesen im obigen Diagramm verwirft? Oder belassen wir es oberhalb von ZFC mit der Untersuchung von Implikationen in ZFC und der Konstruktion von Modellen mit Hilfe möglichst schwacher großer Kardinalzahlaxiome? Der gefundene Strukturreichtum ist bemerkenswert, aber viele Fragen bleiben offen.

Stetige Folgen in stationären Mengen

 Einige Eigenschaften lassen sich für stationäre Teilmengen von ω₁ in ZFC beweisen, aber nicht für stationäre Teilmengen von ω₂ und darüber hinaus. Ein Beispiel ist die Existenz langer stetiger Folgen in stationären Mengen. Für ω₁ gilt:

 Eine analoge Aussage für ω₂ lässt sich in ZFC nicht mehr beweisen und modulo der Konsistenz großer Kardinalzahlen auch nicht widerlegen.

Bäume

 Bäume sind spezielle wohlfundierte Strukturen, die die Ordinalzahlen verallgemeinern: Wir verzichten auf die Eindeutigkeit von Nachfolgern.

 Wir schreiben im Folgenden oft auch nur T statt ausführlich 〈 T, < 〉.

 Um über Bäume angemessen reden zu können, brauchen wir noch einige Begriffe.

 Ist T fest, so unterdrücken wir Indizes und schreiben etwa o. t.(s) statt o. t._T(s). Es gilt offenbar:

height(T)  =  „das kleinste α  ∈  On mit T_{= α} = ∅“.

 Für alle Bäume T ist T_{= 0} die Menge aller s  ∈  T, die keine Vorgänger in T haben. T = 〈 ∅, ∅ 〉 ist der eindeutige Baum der Höhe 0. Für alle nichtleeren Mengen x ist T = 〈 x, ∅ 〉 ein Baum der Höhe 1 mit T_{= 0} = { x }. Für alle Ordinalzahlen α ist 〈 α,  ∈  〉 ein Baum der Höhe α mit T_{= β} = { β } für alle β < α.

 〈 T, < 〉 ist also ein Wurzelbaum, falls die partielle Ordnung 〈 T, < 〉 ein kleinstes Element besitzt. Die Blätter des Baumes T sind genau die maximalen Elemente der Ordnung 〈 T, < 〉.

 Eine wichtige Klasse bilden die Bäume, die aus Folgen gebildet sind:

Es gilt dann height(T) ≤ γ, und für alle α < γ gilt

T_{= α}  =  { s  ∈  T | dom(s)  =  α }.

Speziell ist T_{= 0} = { ∅ }. Die leere Folge 〈   〉 = ∅ ist die Wurzel jedes Folgenbaumes.

 Jedem Baum können wir in natürlicher Weise einen Folgenbaum zuordnen: Ist nämlich 〈 T, < 〉 ein Baum, so sei für alle s  ∈  T f_s die <-monotone Aufzählung von pred_T(s) ∪ { s }. Wir setzen nun T′ = { f_s|α | s  ∈  T, α ≤ dom(f_s) } und ordnen T′ durch strikte Inklusion. Dann ist 〈 T′, < 〉 ein Folgenbaum auf T. Die Abbildung G : T → T′ mit

G(s)  =  f_s  =  „das eindeutige f  ∈  T′ mit s = f (max(dom(f)))“

ist ordnungstreu und insbesondere also injektiv. G ist allerdings nicht surjektiv: Der Wurzel ∅ und den Limeselementen von T′ entsprechen keine Elemente von T. Hat T eine Wurzel s, so ist G(s) = 〈  s  〉.

 Wir definieren weiter:

 Dabei steh „B“ für engl. branch. Wir nennen auch eine <-aufsteigende Folge 〈 x_α | α < β 〉 einen Zweig, falls ihr Wertebereich ein Zweig nach der obigen Definition ist. Es gilt dann x_α  ∈  T_{= α} für alle α < β.

 Für alle t  ∈  T ist pred_T(t) ∪ { t } ein Zweig in T. Dieser Zweig ist genau dann konfinal in T, wenn t ein Blatt von T ist.

 Ein Zweig eines Folgenbaumes T ⊆ ^{< γ}M hat die Form

B = { f|α | α < dom(f) }

für ein f mit dom(f) ≤ γ. Wir können dann B mit f identifizieren.

 Bei der Untersuchung von Bäumen spielen die folgenden Begriffe eine wichtige Rolle:

 Ist 〈 T, < 〉 ein Baum, so ist jede Stufe T_{= α} eine Antikette in T. Existiert für alle s  ∈  T mit o. t.(s) < α ein t  ∈  T_{= α} mit s < t, so ist die Stufe T_{= α} sogar eine maximale Antikette in T.

 Eine Ansammlung von nützlichen Strukturvoraussetzungen vereint der folgende Begriff:

 Ein normaler Baum T hat nach (iii) nur dann Blätter, wenn seine Höhe eine Nachfolgerordinalzahl α + 1 ist. In diesem Fall ist dann T_{= α} die Menge der Blätter von T.

Suslin-Bäume und Aronzajn-Bäume

 Wir studieren Bäume der Höhe ω₁, die keine überabzählbaren Zweige besitzen. Zwei wichtige Klassen sind:

 Jeder Suslin-Baum ist ein Aronzajn-Baum, da die Stufen eines Baumes Antiketten sind. Die Umkehrung ist, wie wir sehen werden, nicht richtig.

 Insbesondere ist also jeder normale Baum der Höhe ω₁, der keine überabzählbaren Antiketten besitzt, ein Suslin-Baum.

 Man kann in ZFC zeigen, dass ein Aronzajn-Baum existiert. Hier spielt der Ordnungstyp der rationalen Zahlen eine entscheidende Rolle:

 Die Existenz von Suslin-Bäumen ist dagegen zum Suslin-Problem gleichwertig. Wir betrachten hierzu (vgl. auch die „Einführung“):

 Dabei erfüllt eine lineare Ordnung 〈 M, < 〉 die Antiketten-Bedingung, wenn jede Menge von offenen paarweise disjunkten Intervallen von M abzählbar ist.

 Die Suslin-Hypothese ist motiviert durch die Frage:

 Suslin-Geraden sind Gegenbeispiele zur Suslin-Hypothese. Genauer ist die Existenz einer Suslin-Geraden äquivalent zur Negation von (SH), wie eine Dedekind-Vervollständigung zeigt. Wir werden später zeigen, dass in Gödels konstruktiblem Modell L eine Suslin-Gerade existiert. Mit der Erzwingungsmethode werden wir dagegen ein Modell konstruieren, in dem keine Suslin-Gerade existiert. Zur Gewinnung dieser Resultate verwenden wir folgende Äquivalenz:

Das Karo-Prinzip

 Suslin-Bäume liefern also Gegenbeispiele zur Suslin-Hypothese. Wir betrachten nun ein kombinatorisches Prinzip, mit dessen Hilfe wir Suslin-Bäume konstruieren können. Später werden wir zeigen, dass dieses Prinzip im Gödelschen Universum L gültig ist.

 Wir können uns die linke obere Hälfte des Quadrats ω₁ × ω₁ abgedunkelt vorstellen, einschließlich der Diagonale D = { (α, α) | α < ω₁ }. Die Mengen S_α tragen wir nun in der rechten unteren Hälfte ein. Nun ziehen wir eine beliebige Teilmenge S von ω₁ von links nach rechts durch das Quadrat. Dabei wird ein immer größeres Anfangsstück von S sichtbar. Wir notieren alle α, für die S_α mit dem sichtbaren Anfangsstück S ∩ α von S übereinstimmt. Eine ◇-Folge „rät“ in diesem Sinne die Anfangsstücke jeder beliebigen Teilmenge von ω₁ stationär oft richtig. Dadurch wird die Potenzmenge von ω₁ in vielerlei Hinsicht gebändigt und gut analysierbar.

 Man kann zeigen, dass das Karo-Prinzip äquivalent ist zu der scheinbar schwächeren Version, die in (ii) für alle S ⊆ ω₁ lediglich die Existenz eines einzigen unendlichen α < ω₁ fordert mit S ∩ α = S_α. Dagegen ist die Forderung „für club-viele α < ω₁“ statt „für stationär viele α < ω₁“ in (ii) unmöglich, wie man sich leicht überlegt.

 Eine der einfachsten Folgerungen des Karo-Prinzips ist:

 Das Karo-Prinzip können wir also als eine starke Version der Kontinuumshypothese ansehen.

 Wir zeigen nun den folgenden Satz von Jensen:

 Der Beweis führte zur Isolation des Karo-Prinzips. Eine maximale Antikette A in einem beliebigen Baum T auf ω₁ reflektiert sehr häufig auf die Stufen des Baumes: Die Menge A ∩ λ ist für club-viele λ eine maximale Antikette von T_{< λ}. Die Karo-Folge wird eingesetzt, um die Anfangsstücke der Antikette zu raten. Die spezielle Eigenschaft der rekursiven Baumkonstruktion ist nun, dass die Zweige { s′ < s | s′  ∈  T_{< λ} }, die den Elementen s einer Limesstufe T_{= λ} zugeordnet sind, die Mengen S_λ treffen, falls diese eine maximale Antikette in T_{< λ} sind. Diese Eigenschaft sichert, dass wir nicht nur die Anfangsstücke von Antiketten richtig raten, sondern die Antikette selbst.

 Das Karo-Prinzip hat viele kombinatorische Konsequenzen. Zwei Beispiele behandeln die folgenden Übungen.

Kurepa-Bäume

 Wir betrachten nun Bäume auf ω₁, die im Gegensatz zu den bislang studierten Bäumen besonders viele überabzählbare Zweige besitzen.

 Wir werden später zeigen, dass in Gödels Modell L Kurepa-Bäume existieren. Stärker existiert ein in L gültiges kombinatorisches Prinzip des ◇-Typs, das die Existenz von Kurepa-Bäumen nach sich zieht. Weiter werden wir sehen, dass die Nichtexistenz von Kurepa-Bäumen die Existenz einer unerreichbaren Kardinalzahl in L nach sich zieht. Insgesamt ist die Existenz von Kurepa-Bäumen also in ZFC nicht widerlegbar und modulo der Konsistenz von unerreichbaren Kardinalzahlen auch nicht beweisbar. Wir diskutieren dies noch genauer im zweiten Abschnitt.

 Der Begriff eines Kurepa-Baums ist aus dem folgenden Begriff über Mengensysteme hervorgegangen:

 In der Tat kann man leicht sehen:

 Die Nichtexistenz eines Kurepa-Baumes ordnet sich in unsere Reihe der kombinatorischen Prinzipien auf ω₁ unterhalb der Transversalen-Hypothese ein:

Die Baumeigenschaft

 Die Suche nach unendlichen Zweigen in Bäumen führt zu einer neuen großen Kardinalzahleigenschaft. Ausgangspunkt ist der folgende bekannte Satz:

 Der Beweis verwendet das Auswahlaxiom bei der Wahl des nächsten Knotens.

 Es stellt sich die Frage, ob diese Eigenschaft von schmalen Bäumen der Höhe ω auch für schmale Bäume überabzählbarer Höhe gilt bzw. überhaupt gelten kann. Wir definieren:

 Die Baumeigenschaft führt zu einem neuen großen Kardinalzahlbegriff:

 Schwach kompakte Kardinalzahlen liegen in der Hierarchie der großen Kardinalzahlaxiome zwischen Mahlo und Messbarkeit. Wir zeigen hier noch, dass messbare Kardinalzahlen schwach kompakt sind. Ein κ-vollständiger Ultrafilter erlaubt uns, einen Zweig in einem κ-Baum zu finden:

Partitionen und der Satz von Ramsey

 Wir erinnern an den Begriff der Zerlegung: Ein Z ⊆ ℘(M) heißt eine Zerlegung von M, falls die Elemente von Z nichtleer und paarweise disjunkt sind und weiter ⋃ Z = M gilt.

 Ist f eine Funktion mit dom(f) = M, so heißt f auch eine (funktionale) Zerlegung von M. Ist nämlich I = rng(f), so ist

Z  =  { f ⁻¹″{ i } | i  ∈  I }

eine Zerlegung von M. Z = Z(f) heißt die zu f gehörige oder von f induzierte Zerlegung von M. Ist umgekehrt Z eine Zerlegung von M, so ist f : M → Z mit

f (a)  =  „das x  ∈  Z mit a  ∈  x“  für alle a  ∈  M

eine funktionale Zerlegung von M mit rng(f) = Z.

 Ist ∼ eine Äquivalenzrelation auf M, so ist die Menge der Äquivalenzklassen Z = M/∼ eine Zerlegung der Menge M. Ist umgekehrt Z eine Zerlegung von M, so definiert „a ∼ b, falls ein x  ∈  Z existiert mit a, b  ∈  x“ eine Äquivalenzrelation auf M.

 Besonders suggestiv ist schließlich auch die Sprechweise der Färbung. Jede Zerlegung f : M → I heißt auch eine Färbung von M. Stellen wir uns die Elemente von I als verschiedene Farben vor, so wird jedes x  ∈  M mit der Farbe f (x) versehen.

 Im Folgenden studieren wir Färbungen von [ M ]ⁿ für n  ∈  ω mit zwei oder mehr Farben, wobei wir uns in erster Linie für unendliche Mengen M interessieren. Im Zentrum steht der Begriff einer homogenen Teilmenge.

 Die Frage ist die nach der Existenz großer homogener Teilmengen für beliebige Färbungen f von [ M ]ⁿ für n  ∈  ω . Das thematische Umfeld ist also: „Existieren einfach große Teilsysteme von komplizierten Systemen?“

 Wir nehmen ohne Einschränkung an, dass M und rng(f) Kardinalzahlen sind. Zur bequemen Formulierung ist folgende Notation nützlich:

 Die Anordnung der Variablen κ, μ, n, k sind durch folgende Auf- und Abwärtsregeln motiviert:

 Folgende Überlegung zeigt, warum wir n  ∈  ω in der Definition der Pfeilnotation fordern. Wohlordnungen auf [ κ ]^ω schließen die Existenz von unendlichen homogenen Mengen schon für bestimmte rot-blau-Färbungen aus:

 Das überraschende positive Resultat für die Pfeilnotation im Fall κ = ω ist der folgende Satz:

 Ist also f : [ ω ]² → 2 eine beliebige rot-blau-Färbung der Kanten des vollständigen Graphen 〈 ω, [ ω ]² 〉, so existiert eine unendliche Teilmenge N von ω derart, dass [ N ]² vollständig rot oder vollständig blau gefärbt ist.

 Mit Hilfe des Lemmas von König gewinnen wir eine endliche Version:

 Für natürliche Zahlen n, m, k sei r(n, m, k) = min({ r ≥ n | r → (m)ⁿ_k }). Die Funktion r : ω³ → ω heißt die Ramsey-Funktion. Die Werte von r auszurechnen ist eine diffizile Angelegenheit. Bekannt ist z.B. r(2, 3, 2) = 6 und r(2, 4, 2) = 18. Bei jedem Essen mit 6 Leuten gibt es drei Gäste, die sich untereinander kennen oder die untereinander fremd sind. In jeder Schulklasse mit 18 Schülern gibt es 4 Schüler, die sich paarweise mögen oder paarweise nicht mögen.

 Die Äquivalenz einer unendlichen und endlichen Version eines kombinatorischen Satzes ist häufig anzutreffen (z.B. beim Satz von van der Waerden über arithmetische Progressionen, siehe unten). Bei der Gewinnung der endlichen aus der unendlichen Version wird dabei oft das Lemma von König oder ein verwandtes Kompaktheitsargument angewendet.

 Die van der Waerden-Funktion w(n, k) = „das kleinste w  ∈  ω mit obiger Eigenschaft“ wächst sehr schnell. Erst kürzlich hat Shelah gute Schranken für das Wachstum dieser Funktion gefunden, zusammen mit einem neuen Beweis eines stärkeren Satzes.

 Aus dem Satz von van der Waerden folgt für jede k-Färbung von ω die Existenz einer Farbe mit beliebig langen arithmetischen Progression in dieser Farbe. Die Farbe anzugeben ist schwieriger. Ein wichtiges Ergebnis, das oftmals die Identifikation einer „guten“ Farbe erlaubt, ist der folgende Satz von Szemeredi:

 Nach dem Satz von Ramsey gilt ω → (ω)ⁿ_k für alle n, k  ∈  ω. Dagegen ist die Partitionseigenschaft ω₁ → (ω₁)ⁿ_k nicht mehr richtig. Genauer gilt:

 Neben dem Satz von Ramsey gehört der folgende Satz von Erdös und Rado, den wir ohne Beweis angeben, zu den wichtigsten positiven Pfeil-Resultaten. Für unendliche Kardinalzahlen definieren wir hierzu 2^{κ, n} für n  ∈  ω rekursiv durch

2^{κ, 0}  =  κ

2^{κ, n + 1}  =  2^{(2κ, n)}  für alle n  ∈  ω.

 Insbesondere existiert für alle n  ∈  ω und alle Kardinalzahlen μ, k ein κ mit κ → (μ)ⁿ_k. Weiter gilt (2^κ)⁺ → ${(\mathrm{\kappa }{\mathrm{}}^{+})}_2^2$. Das Ergebnis ist zudem für alle n  ∈  ω bestmöglich: Die linke Seite (2^{κ, n})⁺ kann nicht reduziert werden.

 Wir hatten schwach kompakte Kardinalzahlen als unerreichbare Kardinalzahlen eingeführt, die die Baumeigenschaft haben. Diese Kardinalzahlen sind nun genau diejenigen überabzählbaren Zahlen, für die der Satz von Ramsey mit κ statt ω gilt. Genauer gilt folgender Satz, den wir hier ebenfalls ohne Beweis angeben:

Die Partitionseigenschaft κ → (μ)^{< ω}_k

 Wir hatten oben gezeigt, dass Zerlegungen f : [ κ ]^ω → 2 von [ κ ]^ω ohne unendliche homogene Teilmengen existieren. Es ist daher vielleicht nicht überraschend, dass die folgende Forderung für Zerlegungen von [ κ ]^{< ω} = ⋃_{n  ∈  ω} [ κ ]ⁿ eine starke Eigenschaft ist.

 Für homogene N ⊆ κ kann die Farbe f ″[ N ]ⁿ mit jedem n  ∈  ω wechseln. Eine von n unabhängige Farbe zu fordern wäre nicht sinnvoll, wie die folgende Färbung f : [ κ ]^{< ω} → 2 zeigt:

$\mathrm{f}(\mathrm{x})= { \begin{array}{cc}0,\hfill & \mathit{\text{falls\hspace{1em}}}\mathrm{x}\in [\mathrm{\kappa }]{\mathrm{}}^{2\mathrm{m}}\text{für}\text{ein}\mathrm{m}\in \mathrm{\omega }\hfill \\ 1,\hfill & \mathit{\text{falls\hspace{1em}}}\mathrm{x}\in [\mathrm{\kappa }]{\mathrm{}}^{2\mathrm{m}+1}\text{für}\text{ein}\mathrm{m}\in \mathrm{\omega }\hfill \end{array}$

 Die Kardinalzahl ω erfüllt diese Partitions-Eigenschaft nicht:

 Die Partitions-Eigenschaft führt zu einem neuen großen Kardinalzahlbegriff:

 Jede Ramsey-Kardinalzahl erfüllt κ → (κ)²₂ und ist daher schwach kompakt. Weiter kann man zeigen, dass jede messbare Kardinalzahl eine Ramsey-Kardinalzahl ist.