🔢 mathematics

On a problem of Erdos and Hajnal

Diese Arbeit löst eine von Erdős und Hajnal aufgeworfene Frage, indem sie die negative Partitionsrelation $\aleph_{\omega+1}\nrightarrow(\aleph_{\omega+1},(3)_{\aleph_0})^2$ etabliert und das Ergebnis bis hinunter zu $\aleph_{\omega}$ erweitert.

Ursprüngliche Autoren: Shimon Garti, Yair Hayut, Saharon Shelah

Veröffentlicht 2026-06-29

📖 5 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Shimon Garti, Yair Hayut, Saharon Shelah

Originalarbeit lizenziert unter CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

Stellen Sie sich vor, Sie organisieren eine riesige Party mit einer unendlichen Anzahl von Gästen. Sie möchten wissen, ob Sie – egal wie Sie die Farben den Händeschütteln zwischen den Gästen zuweisen – garantiert ein bestimmtes Muster finden werden.

In der Welt der Mathematik ist dies ein Problem über Graphen (Gäste sind Punkte, Händeschütteln sind Linien) und Färbung (einer Linie eine Farbe zuweisen).

Die große Frage

Der berühmte Mathematiker Paul Erdős und András Hajnal stellten eine spezifische Frage über eine sehr große, „chaotische“ Art von Unendlichkeit namens $\aleph_\omega$ (denken Sie an einen Turm von Unendlichkeiten, die übereinander gebaut sind).

Sie wollten wissen: Wenn Sie eine riesige Gruppe von Menschen haben, in der fast jeder mit fast jedem verbunden ist (niemand ist isoliert), und Sie jedes Händeschütteln mit $\aleph_0$ (abzählbar unendlich vielen) Farben färben, müssen Sie dann zwangsläufig ein „monochromatisches Dreieck“ finden?

Ein monochromatisches Dreieck bedeutet, dass drei Personen sich alle die Hände schütteln und alle drei Händeschüttelungen exakt dieselbe Farbe haben.

Mathematiker wussten bereits, dass, wenn die „Regeln des Universums“ (speziell die Verallgemeinerte Kontinuumshypothese oder GCH) streng sind, die Antwort NEIN lautet. Man könnte die Händeschüttelungen auf eine kluge Weise färben, um farbige Dreiecke zu vermeiden.

Erdős und Hajnal fragten jedoch: Hängt diese „Nein“-Antwort von diesen strengen Regeln ab? Oder gilt sie auch, wenn das Universum „lockerer“ ist und mehr Möglichkeiten zulässt (wo $2^\lambda > \lambda^+$ )?

Die Entdeckung des Papers

Die Autoren dieses Papers, Garti, Hayut und Shelah, sagen: Ja, die „Nein“-Antwort ist auch in diesem „lockeren“ Universum möglich.

Sie haben bewiesen, dass man eine mathematische Welt konstruieren kann, in der:

Die „lockeren“ Regeln gelten (die Größe der Potenzmenge ist größer als die nächste Kardinalzahl).
Die spezifische Unendlichkeit $\aleph_\omega$ eine „starke Grenze“ (eine sehr robuste Art von Unendlichkeit) ist.
Trotz all dessen kann man die Händeschüttelungen so färben, dass man farbige Dreiecke vermeidet.

Das bedeutet, dass das negative Ergebnis (dass man die Dreiecke vermeiden kann) konsistent mit dem Scheitern der strengen Regeln ist. Es beweist nicht, dass es immer so ist, aber es beweist, dass es möglich ist, eine Welt zu erschaffen, in der dies geschieht.

Wie haben sie es gemacht? (Die Metaphern)

Das Paper verwendet zwei Hauptstrategien, um diese „Party“ aufzubauen, bei der Dreiecke vermieden werden.

Strategie 1: Der „Leiter“-Ansatz (pcf-Theorie)

Stellen Sie sich vor, Sie versuchen, eine Brücke zu einer fernen Insel (der riesigen Unendlichkeit $\lambda^+$ zu bauen. Normalerweise benötigen Sie ein solides Fundament (die strengen Regeln der GCH), um sie zu bauen.

Die Autoren erkannten, dass sie nicht das ganze Fundament brauchten. Stattdessen bauten sie eine Leiter, die aus kleineren, handhabbaren Sprossen (kleineren Unendlichkeiten unterhalb der großen) besteht.

Sie nahmen an, dass man auf jeder kleinen Sprosse bereits Dreiecke vermeiden konnte.
Unter Verwendung eines ausgeklügelten mathematischen Werkzeugs namens pcf-Theorie (die untersucht, wie Unendlichkeiten interagieren), zeigten sie, dass man die Fähigkeit, Dreiecke zu vermeiden, auf die Spitze der Leiter „heben“ kann, wenn man es auf den Sprossen bereits kann.
Der Haken: Diese erste Methode funktionierte für viele Unendlichkeiten, konnte aber nicht den spezifischen „Boden“ des Turms ( $\aleph_\omega$ ) erreichen, weil die Sprossen dort zu unterschiedlich von einander waren.

Strategie 2: Der „Magische Filter“-Ansatz (Stick-Prinzip)

Für den spezifischen Fall von $\aleph_\omega$ verwendeten sie einen anderen Trick unter Verwendung eines Konzepts namens „Stick“ (oder tiltan).

Stellen Sie sich vor, Sie haben einen magischen Stab (den „Stick“), der in die Zukunft blicken kann.

Das „Stick“-Prinzip besagt: Es gibt eine Sammlung kleiner Gruppen von Menschen (Mengen der Größe $\lambda$ ), sodass für jede riesige Gruppe von Menschen, die Sie auswählen (Größe $\lambda^+$ ), mindestens eine Ihrer kleinen Gruppen vollständig in ihr enthalten ist.
Die Autoren nutzten diesen „Stick“, um die Party zu organisieren. Sie ordneten die Gäste so an, dass der „Stick“ vorhersagen konnte, wo die Farben platziert werden mussten, um potenzielle Dreiecke aufzubrechen.
Sie bewiesen, dass, falls dieser „Stick“ existiert, man die Händeschüttelungen erfolgreich färben kann, um die verbotenen Dreiecke zu vermeiden, selbst in dem „lockeren“ Universum.

Der „Haken“ und das offene Rätsel

Das Paper ist ein Triumph der „Konsistenz“. Es zeigt, dass das Szenario möglich ist.

Die Autoren geben jedoch zu, dass sie nicht wissen, ob es unvermeidlich ist.

Die Frage: Ist es in unserem Standard-mathematischen Universum (ZFC) immer so, dass man diese Dreiecke vermeiden kann?
Das Unbekannte: Sie wissen es nicht. Sie haben gezeigt, dass man ein Haus bauen kann, in dem dies geschieht, aber sie haben nicht bewiesen, dass jedes Haus so gebaut werden muss.

Sie merken auch eine Schwierigkeit an: Um den „Stick“ in diesem speziellen „lockeren“ Universum funktionieren zu lassen, muss der „Stick“ aus Teilen bestehen, die so groß sind wie die Unendlichkeit selbst. Es ist, als versuche man, mit einem riesigen Fischernetz einen winzigen Fisch zu fangen; es funktioniert, aber es ist schwer, das Netz überhaupt erst einmal zu konstruieren.

Zusammenfassung

Das Problem: Kann man Händeschüttelungen in einer riesigen Menge so färben, dass man farbige Dreiecke vermeidet?
Die alte Antwort: Ja, aber nur, wenn das Universum strengen Regeln folgt.
Die Antwort dieses Papers: Ja, man kann das tun, selbst wenn das Universum „lockerer“ ist und anderen Regeln folgt.
Die Methode: Sie bauten eine mathematische „Leiter“ und nutzten einen „magischen Stab“, um zu beweisen, dass es möglich ist, eine solche Welt zu konstruieren.
Die Grenze: Sie haben bewiesen, dass es möglich ist, aber nicht bewiesen, dass es in jedem möglichen mathematischen Universum immer so ist.

Technisches Resümee: Über ein Problem von Erdős und Hajnal

Problemstellung
Die Arbeit befasst sich mit einer spezifischen Frage von Erdős und Hajnal bezüglich der gewöhnlichen Partitionsrelation $\lambda^+ \nrightarrow (\lambda^+, (3)_{\text{cf}(\lambda)})^2$ . Diese Relation besagt, dass für jede Färbung der Paare von $\lambda^+$ mit $\text{cf}(\lambda)$ Farben entweder ein monochromatisches Dreieck oder eine monochrome Menge der Größe $\lambda^+$ existiert (interpretiert als unabhängige Menge in der Graphentheorie).

Erdős, Hajnal und Rado zeigten, dass die negative Relation $\lambda^+ \nrightarrow (\lambda^+, (3)_{\text{cf}(\lambda)})^2$ gilt, wenn $\lambda$ eine singuläre Kardinalzahl ist und die Verallgemeinerte Kontinuumshypothese (GCH) bei $\lambda$ gilt (d. h. $2^\lambda = \lambda^+$ ). Sie fragten, ob die Annahme $2^\lambda = \lambda^+$ unverzichtbar sei. Speziell fragt Frage 0.2, ob die Relation $\aleph_{\omega+1} \nrightarrow (\aleph_{\omega+1}, (3)_{\aleph_0})^2$ ohne die Annahme von GCH bewiesen werden kann. Während bekannt ist, dass die negative Relation gilt, falls $2^{\text{cf}(\lambda)} \ge \lambda^+$ , blieb der Status der Relation, wenn $\lambda$ eine starke Limit-singuläre Kardinalzahl mit $2^\lambda > \lambda^+$ ist, offen.

Methodik
Die Autoren verwenden drei verschiedene Strategien, um die Konsistenz der negativen Relation $\lambda^+ \nrightarrow (\lambda^+, (3)_{\text{cf}(\lambda)})^2$ mit dem Scheitern der GCH ( $2^\lambda > \lambda^+$ ) für starke Limit-singuläre Kardinalzahlen $\lambda$ aufzuzeigen.

Einfache pcf-Argumente (Abschnitt 1):
Der erste Ansatz nutzt die Theorie der möglichen Kohofinalitäten (pcf). Die Autoren nehmen die Existenz einer superkompakten Kardinalzahl $\mu$ an und erzwingen ein Modell, in dem $\mu$ eine starke Limit-singuläre Kardinalzahl wird. Sie konstruieren eine unbeschränkte Folge regulärer Kardinalzahlen $(\mu_i \mid i \in \theta)$ unterhalb von $\mu$ , sodass $\text{tcf}(\prod \mu_i^+, J_{\text{bd}}^\theta) = \mu^+$ . Indem sie GCH unterhalb von $\mu$ annehmen (speziell $2^{\mu_i} = \mu_i^+$ ), erhalten sie negative Partitionsrelationen an jeder $\mu_i^+$ . Durch die Verwendung einer Skala im Produkt und einer spezifischen Färbungkonstruktion heben sie diese lokalen negativen Relationen auf $\mu^+$ an.
- Einschränkung: Diese Methode erfordert, dass $\mu$ ein Limit von singulären Kardinalzahlen derselben Kohofinalität ist. Folglich ist sie anwendbar auf Kardinalzahlen wie $\aleph_{\omega_2}$ , versagt aber bei $\aleph_\omega$ , da unter $\aleph_\omega$ keine singulären Kardinalzahlen liegen.
Verfeinerte pcf-Argumente für $\aleph_\omega$ (Abschnitt 2):
Um den Fall $\lambda = \aleph_\omega$ zu adressieren, verfeinern die Autoren den pcf-Ansatz, um reguläre Kardinalzahlen (speziell $\aleph_n$ ) statt nur Sukzessoren von Singulären zu behandeln.
- Behauptung 2.1: Sie beweisen, dass für eine reguläre $\kappa < \lambda$ eine Färbung $c: [\lambda]^2 \to \{0,1\}$ und ein $\kappa$ -vollständiger Filter $D$ existieren, sodass es keine 1-monochromatischen Dreiecke und keine 0-monochromatischen Mengen der Größe $\lambda$ modulo $D$ gibt.
- Erzwingungsstrategie: Sie nutzen ein $(<\lambda)$ -strategisch geschlossenes Erzwingungsmodell, um eine Skala zu konstruieren, die spezifische Filter-Eigenschaften erfüllt (Lemma 2.3). Anschließend verwenden sie eine Laver-artige Vorbereitung (Lemma 2.5), um eine superkompakte Kardinalzahl $\lambda$ unter diesem spezifischen Erzwingungsschema unzerstörbar zu machen. Schließlich nutzen sie Extender-basiertes Prikry-Erzwingen mit verschachtelten Kollapsen (folgend nach Merimovich), um $\lambda$ zu $\aleph_\omega$ zu singularisieren und gleichzeitig $2^\lambda$ auf $\lambda^{++}$ zu erhöhen. Dies bewahrt die notwendige pcf-Struktur und die negativen Relationen, die aus dem Grundmodell abgeleitet wurden.
Prädiktionsprinzipien (Stick) (Abschnitt 3):
Der dritte Ansatz ersetzt die pcf-Annahmen durch das „Stick“-Prinzip, bezeichnet als $\bullet(\lambda)$ . Dieses Prinzip besagt die Existenz einer Familie von Teilmengen von $\lambda^+$ der Größe $\lambda$ , die jede Teilmenge von $\lambda^+$ der Größe $\lambda^+$ „errät“ (d. h. für jedes $A \in [\lambda^+]^{\lambda^+}$ gibt es ein $B$ in der Familie, sodass $B \subseteq A$ ).
- Theorem 3.3: Die Autoren beweisen, dass falls $\bullet(\lambda)$ gilt, dann $\lambda^+ \nrightarrow (\lambda^+, (3)_{\text{cf}(\lambda)})^2$ gilt. Der Beweis konstruiert eine Partition von $[\lambda^+]^2$ basierend auf Mengenabbildungen, die aus der Stick-Sequenz abgeleitet sind, sowie einem Free-Set-Lemma (Lemma 3.2).
- Einschränkung: Der Beweis beruht entscheidend darauf, dass die ratenden Mengen die Größe $\lambda$ haben. Die Autoren merken an, dass es derzeit unbekannt ist, ob $\bullet(\lambda)$ mit $2^\lambda > \lambda^+$ konsistent ist, wenn $\lambda$ eine starke Limit-singuläre Kardinalzahl ist.

Wesentliche Beiträge und Ergebnisse

Konsistenz der negativen Relation mit $2^\lambda > \lambda^+$ : Die Arbeit etabliert, dass die negative Partitionsrelation $\lambda^+ \nrightarrow (\lambda^+, (3)_{\text{cf}(\lambda)})^2$ konsistent ist, während $\lambda$ eine starke Limit-singuläre Kardinalzahl und $2^\lambda > \lambda^+$ ist.
Lösung für $\aleph_\omega$ : Die Autoren führen das Ergebnis erfolgreich auf $\lambda = \aleph_\omega$ zurück (Theorem 2.2 und die anschließende Erzwingungskonstruktion) und beantworten damit den spezifischen Fall der Erdős-Hajnal-Frage für die erste unendliche singuläre Kardinalzahl.
Große Kardinalzahlen-Annahmen: Die Konsistenzbeweise beruhen auf der Existenz großer Kardinalzahlen (superkompakt oder stark). Speziell wird das Ergebnis für $\aleph_\omega$ aus einer superkompakten Kardinalzahl im Grundmodell abgeleitet, die mittels Prikry-artiger Erzwingung singularisiert wird.
Unzerstörbarkeit: Die Arbeit liefert eine Modifikation von Lavers Unzerstörbarkeitsbeweis (Lemma 2.4, Lemma 2.5), um zu zeigen, dass Superkompaktheit unter $(<\lambda)$ -strategisch geschlossenen Erzwingungsmodellen erhalten werden kann, was für die pcf-Konstruktion entscheidend ist.

Bedeutung und offene Fragen
Die Arbeit zeigt, dass die Annahme $2^\lambda = \lambda^+$ in der Erdős-Hajnal-Theorem nicht notwendig für die Konsistenz der negativen Relation ist; die Relation kann auch gelten, wenn GCH bei $\lambda$ scheitert. Die Autoren geben jedoch explizit an, dass sie nicht wissen, ob die Relation in ZFC gilt (d. h. ohne Annahmen über große Kardinalzahlen).

Die Arbeit schließt mit mehreren offenen Fragen:

Ist es konsistent, dass $\lambda$ eine starke Limit-singuläre Kardinalzahl ist und die positive Relation $\lambda^+ \to (\lambda^+, (3)_{\text{cf}(\lambda)})^2$ gilt?
Was ist die exakte Konsistenzstärke der negativen Relation mit $2^\lambda > \lambda^+$ für $\lambda = \aleph_\omega$ ? (Die Arbeit verwendet eine superkompakte Kardinalzahl, während Gitiks Arbeit über das Scheitern der SCH nur $o(\kappa) = \kappa^{++}$ erfordert).
Ist es konsistent, dass $\lambda$ superkompakt ist, $\bullet(\lambda)$ gilt und $2^\lambda > \lambda^+$ ist? Dies würde den Stick-basierten Ansatz mit dem Scheitern der GCH vereinigen.

Die Autoren betonen, dass zwar mächtige Methoden für Sukzessoren singulärer Kardinalzahlen existieren, dieses spezifische Problem bezüglich der Unabhängigkeit der GCH in dieser Partitionsrelation jedoch eine signifikante Herausforderung bleibt, und ihre Arbeit liefert die ersten Konsistenzresultate für das Scheitern der GCH in diesem Kontext.