Théorème d'Erdős-Rado

Le théorème d'Erdős-Rado, nommé d'après Paul Erdős et Richard Rado, est un théorème mathématique de la théorie des ensembles. Il indique la taille que doit avoir un ensemble pour posséder une certaine propriété de décomposition. C'est un résultat qui étend le théorème de Ramsey aux ensembles non dénombrables. Il doit son nom à Paul Erdős et Richard Rado^[1]. Il est parfois également attribué à Đuro Kurepa qui l'a prouvé sous l'hypothèse supplémentaire de l'hypothèse du continu généralisé^[2], et par conséquent également appelé théorème d'Erdős-Rado-Kurepa .

Pour énoncer le théorème, on utilise une notation particulière appelée notation fléchée. Pour un ensemble ${\displaystyle A}$, soit ${\displaystyle [A]^{n}}$ l'ensemble des sous-ensembles à ${\displaystyle n}$ éléments d'éléments de ${\displaystyle A}$, où ${\displaystyle n}$ est un entier naturel. Pour des nombres cardinaux ${\displaystyle \kappa }$, ${\displaystyle \lambda }$, ${\displaystyle m}$ on écrit

${\displaystyle \kappa \rightarrow (\lambda )_{m}^{n}}$,

lorsque dans toute décomposition ${\displaystyle [\kappa ]^{n}=\bigcup _{\alpha <m}X_{\alpha }}$ de ${\displaystyle [\kappa ]^{n}}$ en ${\displaystyle m}$ sous-ensembles deux-à-deux disjoints, l'un au moins des ensembles ${\displaystyle X_{\alpha }}$ contient un sous-ensemble de la forme ${\displaystyle [H]^{n}}$, où ${\displaystyle H\subset \kappa }$ est de cardinal ${\displaystyle \lambda }$.

Cette notation fléchée remonte à Paul Erdős et Richard Rado ; la voici illustrée par quelques exemples.

Le cas ${\displaystyle n=1}$ signifie que dans une décomposition de ${\displaystyle \kappa }$ en ${\displaystyle m}$ parties, au moins une des parties a cardinalité ${\displaystyle \lambda }$. Par des arguments de cardinalité, on a donc, pour des nombres cardinaux infinis ${\displaystyle \kappa >\lambda }$, que ${\displaystyle \kappa \rightarrow (\lambda )_{2}^{1}}$ ou ${\displaystyle \kappa \rightarrow (\lambda )_{\aleph _{0}}^{1}}$, où ${\displaystyle \aleph _{0}}$ est la notation aleph pour le plus petit nombre cardinal infini. Des énoncés plus intéressants, c'est-à-dire moins triviaux, ne sont obtenus que pour le cas ${\displaystyle n\geq 2}$.

Le théorème de Ramsey peut être formulé en notation fléchée comme suit :

On a ${\displaystyle \aleph _{0}\rightarrow (\aleph _{0})_{m}^{n}}$ pour tous entiers naturels ${\displaystyle m,n}$.

L'énoncé ${\displaystyle \kappa \rightarrow (\lambda )_{m}^{n}}$ reste valide en passant à des nombres cardinaux ${\displaystyle \kappa }$ plus grands ou quand on diminue ${\displaystyle \lambda ,m,n}$.

La négation de la déclaration ${\displaystyle \kappa \rightarrow (\lambda )_{m}^{n}}$ se note ${\displaystyle \kappa \not \rightarrow (\lambda )_{m}^{n}}$.

Wacław Sierpiński a prouvé que, pour les nombres cardinaux infinis ${\displaystyle \kappa }$, on

${\displaystyle 2^{\kappa }\not \rightarrow (\kappa ^{+})^{2}}$ ou plus précisément ${\displaystyle 2^{\kappa }\not \rightarrow (\kappa ^{+})_{2}^{2}}$,

où ${\displaystyle \kappa ^{+}}$ désigne le nombre cardinal successeur de ${\displaystyle \kappa }$ .

En utilisant la notation fléchée ci-dessus et la fonction Beth ${\displaystyle \beth }$, le théorème d’Erdős-Rado est :

Pour ${\displaystyle n=0}$ on a ${\displaystyle \beth _{0}^{+}=\aleph _{0}^{+}=\aleph _{1}}$ et le théorème d'Erdős-Rado énonce simplement que ${\displaystyle \aleph _{1}\rightarrow (\aleph _{1})_{\aleph _{0}}^{1}}$, c'est-à-dire que lors d'une décomposition de ${\displaystyle \aleph _{1}}$ en un nombre dénombrable de parties, au moins une des parties doit avoir la cardinalité ${\displaystyle \aleph _{1}}$, et cela signifie que ${\displaystyle \aleph _{1}}$ est une union non dénombrable d'ensembles dénombrables. Ce n'est que pour ${\displaystyle n\geq 1}$ on obtient des énoncés non triviaux.

L'énoncé formulé plus haut et qui remonte à Sierpiński, stipule que pour ${\displaystyle \kappa =\aleph _{0}}$, on a ${\displaystyle 2^{\aleph _{0}}\not \rightarrow (\aleph _{1})_{2}^{2}}$ ou, par monotonie, que ${\displaystyle \kappa \not \rightarrow (\aleph _{1})_{2}^{2}}$ pour tout ${\displaystyle \kappa \leq 2^{\aleph _{0}}}$. Le théorème d'Erdős-Rado donne l'énoncé positif : ${\displaystyle \kappa \rightarrow (\aleph _{1})_{2}^{2}}$ pour tous ${\displaystyle \kappa >2^{\aleph _{0}}}$, parce que pour ${\displaystyle n=1}$ on a${\displaystyle (2^{\aleph _{0}})^{+}\rightarrow (\aleph _{1})_{\aleph _{0}}^{2}}$, et par la monotonie de la notation fléchée on obtient à l'énoncé souhaité.

Le théorème admet la généralisation suivante à un cardinal supérieur, également appelé théorème d'Erdős-Rado : Pour un nombre cardinal infini ${\displaystyle \kappa }$, on définit récursivement

${\displaystyle \exp _{0}(\kappa )\,=\,\kappa }$

${\displaystyle \exp _{n+1}(\kappa )\,=\,2^{\exp _{n}(\kappa )}}$.

On a alors

Ce résultat est extrémal au sens que le nombre cardinal à gauche de la flèche ne peut être remplacé par un nombre plus petit. Par conséquent, le théorème d'Erdős-Rado donne la grandeur d'un nombre cardinal ${\displaystyle \mu }$ pour que la propriété de partition ${\displaystyle \mu \rightarrow (\kappa ^{+})_{\kappa }^{2}}$ est satisfaite : on doit avoir ${\displaystyle \mu \,>\,\exp _{n}(\kappa )}$.

Pour ${\displaystyle \kappa =\aleph _{0}}$ on a ${\displaystyle \exp _{n}(\kappa )=\beth _{n}}$, et on obtient le théorème d'Erdős-Rado ci-dessus comme cas particulier. Par les propriétés de monotonie de la notation fléchée, le cas ${\displaystyle n=1}$ du théorème d'Erdős-Rado donne

${\displaystyle (2^{\kappa })^{+}\rightarrow (\kappa ^{+})^{2}}$ pour tous les cardinaux infinis ${\displaystyle \kappa }$.

• (de) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en allemand intitulé « Satz von Erdős-Rado » (voir la liste des auteurs).

• Paul Erdős, András Hajnal, Attila Máté et Richard Rado, Combinatorial set theory: partition relations for cardinals, vol. 106, Amsterdam, North-Holland Publishing Co., coll. « Studies in Logic and the Foundations of Mathematics », 1984 (ISBN 0-444-86157-2, MR 0795592)
• Paul Erdős et Richard Rado, « A partition calculus in set theory », Bull. Amer. Math. Soc., vol. 62, n^o 5,‎ 1956, p. 427–489 (DOI 10.1090/S0002-9904-1956-10036-0 , MR 0081864, lire en ligne)
• Paul Erdős, András Hajnal et Richard Rado, « Partition relations for cardinal numbers », Acta Math. Acad. Sci. Hung., vol. 16, n^os 1–2,‎ 1965, p. 93–196 (DOI 10.1007/BF01886396, MR 202613, CiteSeer^x 10.1.1.299.7622, lire en ligne)
• Thomas Jech : Set Theory, Springer-Verlag (2003), (ISBN 3-540-44085-2), notamment chapitre 9.

• Portail des mathématiques