🔢 mathematics

On a problem of Erdos and Hajnal

Dit artikel lost een door Erdős en Hajnal gestelde vraag op door de negatieve partitierelatie $\aleph_{\omega+1}\nrightarrow(\aleph_{\omega+1},(3)_{\aleph_0})^2$ vast te stellen en het resultaat uit te breiden naar beneden tot $\aleph_{\omega}$ .

Oorspronkelijke auteurs: Shimon Garti, Yair Hayut, Saharon Shelah

Gepubliceerd 2026-06-29

📖 5 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Shimon Garti, Yair Hayut, Saharon Shelah

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

Stel je voor dat je een gigantisch feest organiseert met een oneindig aantal gasten. Je wilt weten of je, ongeacht hoe je kleuren toewijst aan de handdrukken tussen gasten, gegarandeerd een specifiek patroon zult vinden.

In de wereld van de wiskunde is dit een probleem over grafen (gasten zijn stippen, handdrukken zijn lijnen) en kleuring (het toewijzen van een kleur aan elke lijn).

De Grote Vraag

De beroemde wiskundigen Paul Erdős en András Hajnal stelden een specifieke vraag over een zeer grote, "rommelige" soort oneindigheid genaamd $\aleph_\omega$ (denk aan een toren van oneindigheden die op elkaar zijn gebouwd).

Ze wilden weten: Als je een enorme groep mensen hebt waarbij bijna iedereen met iedereen verbonden is (niemand is geïsoleerd), en je kleurt elke handdruk met één van $\aleph_0$ (aftelbaar oneindige) kleuren, vind je dan onvermijdelijk een "monochromatische driehoek"?

Een monochromatische driehoek is drie mensen die allemaal handdrukken met elkaar, en waarbij alle drie de handdrukken exact dezelfde kleur hebben.

Wiskundigen wisten al dat als de "spelregels van het universum" (specifiek de Gegeneraliseerde Continuümhypothese, of GCH) strikt waren, het antwoord NEE was. Je kon de handdrukken op een slimme manier inkleuren om monochromatische driehoeken te vermijden.

Erdős en Hajnal vroegen: Is dit "Nee"-antwoord afhankelijk van die strikte regels? Of is het ook waar als het universum "losser" is en meer mogelijkheden toelaat (waarbij $2^\lambda > \lambda^+$ )?

De Ontdekking van het Papier

De auteurs van dit papier, Garti, Hayut en Shelah, zeggen: Ja, het "Nee"-antwoord is nog steeds mogelijk, zelfs in dat lossere universum.

Ze bewezen dat je een wiskundige wereld kunt construeren waarin:

De "losse" regels van toepassing zijn (de grootte van de machtsverzameling is groter dan de volgende kardinaal).
De specifieke oneindigheid $\aleph_\omega$ een "sterke limiet" is (een zeer robuust type oneindigheid).
Ondanks dit alles, kun je de handdrukken inkleuren om monochromatische driehoeken te vermijden.

Dit betekent dat het negatieve resultaat (dat je de driehoeken kunt vermijden) consistent is met het falen van de strikte regels. Het bewijst niet dat het altijd zo is, maar het bewijst dat het mogelijk is om een universum te bouwen waarin dit gebeurt.

Hoe Deden Ze Het? (De Metaforen)

Het papier gebruikt twee hoofdstrategieën om deze "partij" te bouwen waar driehoeken worden vermeden.

Strategie 1: De "Ladder"-benadering (pcf-theorie)

Stel je voor dat je probeert een brug te bouwen naar een verafgelegen eiland (de enorme oneindigheid $\lambda^+$ ). Meestal heb je een stevig fundament nodig (de strikte regels van GCH) om zo'n brug te bouwen.

De auteurs realiseerden zich dat ze niet het hele fundament nodig hadden. In plaats daarvan bouwden ze een ladder bestaande uit kleinere, beheersbare sporten (kleinere oneindigheden onder de grote een).

Ze namen aan dat je op elke kleine sport al in staat bent om de driehoeken te vermijden.
Met behulp van een geavanceerd wiskundig hulpmiddel genaamd pcf-theorie (die bestudeert hoe oneindigheden met elkaar interageren), lieten ze zien dat als je op de sporten driehoeken kunt vermijden, je het vermogen om dat te doen naar de top van de ladder kunt "tillen".
De Addendum: Deze eerste methode werkte voor veel oneindigheden, maar kon de specifieke "bodem" van de toren ( $\aleph_\omega$ ) niet bereiken omdat de sporten daar te veel van elkaar verschilden.

Strategie 2: De "Magische Filter"-benadering (Stick-principe)

Voor het specifieke geval van $\aleph_\omega$ gebruikten ze een andere truc waarbij een concept genaamd "Stick" (of tiltan) betrokken is.

Stel je voor dat je een magische stok (de "stick") hebt die in de toekomst kan kijken.

Het "Stick"-principe zegt: Er is een collectie van kleine groepen mensen (verzamelingen van grootte $\lambda$ ) zodanig dat voor elke enorme groep mensen die je kiest (grootte $\lambda^+$ ), ten minste één van jouw kleine groepen volledig binnen die groep valt.
De auteurs gebruikten deze "Stick" om de partij te organiseren. Ze arrangeerden de gasten zodat de "Stick" kon voorspellen waar de kleuren geplaatst moesten worden om eventuele potentiële driehoeken te doorbreken.
Ze bewezen dat als deze "Stick" bestaat, je de handdrukken succesvol kunt inkleuren om de verboden driehoeken te vermijden, zelfs in het "lossere" universum.

De "Catch" en het Open Mysterie

Het papier is een triomf van "consistentie". Het laat zien dat het scenario mogelijk is.

Echter, de auteurs geven toe dat ze niet weten of het onvermijdelijk is.

De Vraag: Is het in ons standaard wiskundige universum (ZFC) altijd zo dat je deze driehoeken kunt vermijden?
Het Onbekende: Ze weten het niet. Ze hebben laten zien dat je een huis kunt bouwen waar dit gebeurt, maar ze hebben niet bewezen dat elk huis op deze manier gebouwd moet worden.

Ze merken ook een moeilijkheid op: Om de "Stick" in dit specifieke "lossere" universum te laten werken, moet de "Stick" gemaakt zijn van stukken die even groot zijn als de oneindigheid zelf. Het is also[f] een gigantisch visnet proberen te gebruiken om een piepkleine vis te vangen; het werkt, maar het is moeilijk om dat net in de eerste plaats te construeren.

Samenvatting

Het Probleem: Kun je handdrukken inkleuren in een enorme menigte om gelijk gekleurde driehoeken te vermijden?
Het Oude Antwoord: Ja, maar alleen als het universum de strikte regels volgt.
Het Antwoord van dit Papier: Ja, je kunt het zelfs doen als het universum "losser" is en andere regels volgt.
De Methode: Ze bouwden een wiskundige "ladder" en gebruikten een "magische stok" om te bewijzen dat het mogelijk is om een dergelijke wereld te construeren.
De Limiet: Ze bewezen dat het mogelijk is, maar hebben niet bewezen dat het altijd zo is in elk mogelijk wiskundig universum.

Technische Samenvatting: Over een probleem van Erdős en Hajnal

Probleemstelling
Het artikel behandelt een specifieke vraag gesteld door Erdős en Hajnal met betrekking tot de gewone partitie-relatie $\lambda^+ \nrightarrow (\lambda^+, (3)_{\text{cf}(\lambda)})^2$ . Deze relatie stelt dat voor elke kleuring van de paren van $\lambda^+$ met $\text{cf}(\lambda)$ kleuren, er ofwel een monochromatische driehoek of een monochromatische verzameling van grootte $\lambda^+$ bestaat (geïnterpreteerd als een onafhankelijke verzameling in de grafentheorie).

Erdős, Hajnal en Rado stelden vast dat als $\lambda$ een singuliere kardinaal is en de Algemene Continuüm Hypothese (GCH) geldt bij $\lambda$ (d.w.z. $2^\lambda = \lambda^+$ ), de negatieve relatie $\lambda^+ \nrightarrow (\lambda^+, (3)_{\text{cf}(\lambda)})^2$ standhoudt. Zij vroegen zich af of de aanname $2^\lambda = \lambda^+$ onmisbaar is. Specifiek vraagt Vraag 0.2 of de relatie $\aleph_{\omega+1} \nrightarrow (\aleph_{\omega+1}, (3)_{\aleph_0})^2$ bewezen kan worden zonder GCH aan te nemen. Hoewel het bekend is dat de negatieve relatie standhoudt als $2^{\text{cf}(\lambda)} \ge \lambda^+$ , bleef de status van de relatie wanneer $\lambda$ een strong limit singuliere kardinaal is met $2^\lambda > \lambda^+$ open.

Methodologie
De auteurs hanteren drie verschillende strategieën om de consistentie van de negatieve relatie $\lambda^+ \nrightarrow (\lambda^+, (3)_{\text{cf}(\lambda)})^2$ met het falen van GCH ( $2^\lambda > \lambda^+$ ) voor strong limit singuliere kardinalen $\lambda$ aan te tonen.

Eenvoudige pcf-argumenten (Sectie 1):
De eerste benadering maakt gebruik van de theorie van mogelijke cofinaliteiten (pcf). De auteurs nemen het bestaan aan van een supercompacte kardinaal $\mu$ en forceren een model waarin $\mu$ een strong limit singuliere kardinaal wordt. Zij construeren een onbegrensde sequentie van reguliere kardinalen $(\mu_i \mid i \in \theta)$ onder $\mu$ zodanig dat $\text{tcf}(\prod \mu_i^+, J_{\text{bd}}^\theta) = \mu^+$ . Door aan te nemen dat GCH geldt onder $\mu$ (specifiek $2^{\mu_i} = \mu_i^+$ ), verkrijgen zij negatieve partitie-relaties bij elk $\mu_i^+$ . Door een schaal (scale) in het product en een specifieke kleuring-constructie te gebruiken, tillen zij deze lokale negatieve relaties naar $\mu^+$ .
- Beperking: Deze methode vereist dat $\mu$ een limiet is van singuliere kardinalen met dezelfde cofinaliteit. Bijgevolg is dit van toepassing op kardinalen zoals $\aleph_{\omega_2}$ , maar faalt het voor $\aleph_\omega$ , dat geen singuliere kardinalen onder zich heeft.
Verfijnde pcf-argumenten voor $\aleph_\omega$ (Sectie 2):
Om de casus $\lambda = \aleph_\omega$ aan te pakken, verfijnen de auteurs de pcf-benadering om reguliere kardinalen (specifiek $\aleph_n$ ) te behandelen in plaats van enkel de successoren van singuliere kardinalen.
- Claim 2.1: Zij bewijzen dat er voor een reguliere $\kappa < \lambda$ een kleuring $c: [\lambda]^2 \to \{0,1\}$ en een $\kappa$ -complete filter $D$ bestaat zodanig dat er geen 1-monochromatische driehoeken zijn en geen 0-monochromatische verzamelingen van grootte $\lambda$ modulo $D$ .
- Forcing-strategie: Zij maken gebruik van een $(<\lambda)$ -strategisch-gesloten forcing-notie om een schaal te construeren die specifieke filtereigenschappen bezit (Lemma 2.3). Vervolgens gebruiken zij een Laver-stijl voorbereiding (Lemma 2.5) om een supercompacte kardinaal $\lambda$ onverwoestbaar te maken onder deze specifieke forcing. Ten slotte gebruiken zij Extender-gebaseerde Prikry-forcing met geïntegreerde collapses (volgens Merimovich) om $\lambda$ te singulariseren tot $\aleph_\omega$ terwijl $2^\lambda$ wordt vergroot naar $\lambda^{++}$ . Dit behoudt de noodzakelijke pcf-structuur en de negatieve relaties afgeleid uit het grondmodel.
Voorspellingsprincipes (Stick) (Sectie 3):
De derde benadering vervangt de pcf-aannames door het "stick"-principe, aangeduid als $\bullet(\lambda)$ . Dit principe stelt de existentie van een familie van deelverzamelingen van $\lambda^+$ van grootte $\lambda$ die elke deelverzameling van $\lambda^+$ van grootte $\lambda^+$ "raadt" (d.w.z. voor elke $A \in [\lambda^+]^{\lambda^+}$ is er een $B$ in de familie zodanig dat $B \subseteq A$ ).
- Stelling 3.3: De auteurs bewijzen dat als $\bullet(\lambda)$ geldt, dan $\lambda^+ \nrightarrow (\lambda^+, (3)_{\text{cf}(\lambda)})^2$ . Het bewijs construeert een partitie van $[\lambda^+]^2$ gebaseerd op set-mappings afgeleid van de stick-sequentie en een free set lemma (Lemma 3.2).
- Restrictie: Het bewijs rust kritisch op het feit dat de raadende verzamelingen van grootte $\lambda$ zijn. De auteurs merken op dat het momenteel onbekend is of $\bullet(\lambda)$ consistent is met $2^\lambda > \lambda^+$ wanneer $\lambda$ een strong limit singuliere kardinaal is.

Belangrijkste bijdragen en resultaten

Consistentie van de negatieve relatie met $2^\lambda > \lambda^+$ : Het artikel vestigt dat de negatieve partitie-relatie $\lambda^+ \nrightarrow (\lambda^+, (3)_{\text{cf}(\lambda)})^2$ consistent is met $\lambda$ een strong limit singuliere kardinaal zijnde en $2^\lambda > \lambda^+$ .
Resolutie voor $\aleph_\omega$ : De auteurs slagen erin het resultaat door te duwen naar $\lambda = \aleph_\omega$ (Theorem 2.2 en de daaropvolgende forcing-constructie), waarmee zij de specifieke instantie van de Erdős-Hajnal vraag voor de eerste oneindige singuliere kardinaal beantwoorden.
Grote Kardinaal-aannames: De consistentiebewijzen steunen op de existentie van grote kardinalen (supercompact of sterke kardinalen). Specifiek wordt het resultaat voor $\aleph_\omega$ afgeleid van een supercompacte kardinaal in het grondmodel, die via Prikry-type forcing wordt gesingulariseerd.
Onverwoestbaarheid: Het artikel biedt een modificatie van de onverwoestbaarheidsbewijzen van Laver (Lemma 2.4, Lemma 2.5) om aan te tonen dat supercompactheid behouden kan blijven onder $(<\lambda)$ -strategisch-gesloten forcing-noties, wat cruciaal is voor de pcf-constructie.

Betekenis en Open Vragen
Het artikel toont aan dat de aanname $2^\lambda = \lambda^+$ in de Erdős-Hajnal stelling niet noodzakelijk is voor de consistentie van de negatieve relatie; de relatie kan ook standhouden wanneer GCH faalt bij $\lambda$ . De auteurs stellen echter expliciet dat zij niet weten of de relatie in ZFC geldt (d.w.z. zonder aannames van grote kardinalen).

Het artikel sluit af met enkele open vragen:

Is het consistent dat $\lambda$ een strong limit singuliere kardinaal is en de positieve relatie $\lambda^+ \to (\lambda^+, (3)_{\text{cf}(\lambda)})^2$ geldt?
Wat is de exacte consistentiekracht van de negatieve relatie met $2^\lambda > \lambda^+$ voor $\lambda = \aleph_\omega$ ? (Het artikel gebruikt een supercompacte kardinaal, terwijl Gitiks werk over het falen van SCH slechts $o(\kappa) = \kappa^{++}$ vereist).
Is het consistent dat $\lambda$ supercompact is, $\bullet(\lambda)$ geldt, en $2^\lambda > \lambda^+$ ? Dit zou de stick-gebaseerde benadering verenigen met het falen van GCH.

De auteurs benadrukken dat hoewel er krachtige methoden bestaan voor successoren van singuliere kardinalen, deze specifieke kwestie betreffende de onafhankelijkheid van GCH in deze partitie-relatie een significante uitdaging blijft, en dat hun werk de eerste consistentieresultaten biedt voor het falen van GCH in deze context.