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 .

Notation

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

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

,

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

Exemples et discussion

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

Le cas $n=1$ signifie que dans une décomposition de $\kappa$ en $m$ parties, au moins une des parties a cardinalité $\lambda$ . Par des arguments de cardinalité, on a donc, pour des nombres cardinaux infinis $\kappa >\lambda$ , que $\kappa \rightarrow (\lambda )_{2}^{1}$ ou $\kappa \rightarrow (\lambda )_{\aleph _{0}}^{1}$ , où $\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 $n\geq 2$ .

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

On a

\aleph _{0}\rightarrow (\aleph _{0})_{m}^{n}

pour tous entiers naturels

m,n

.

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

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

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

2^{\kappa }\not \rightarrow (\kappa ^{+})^{2}

ou plus précisément

2^{\kappa }\not \rightarrow (\kappa ^{+})_{2}^{2}

,

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

Ènoncé du théorème

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

Théorème (Erdős-Rado) — $\beth _{n}^{+}\rightarrow (\aleph _{1})_{\aleph _{0}}^{n+1}$ pour tout entier naturel $n$ .

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

L'énoncé formulé plus haut et qui remonte à Sierpiński, stipule que pour $\kappa =\aleph _{0}$ , on a $2^{\aleph _{0}}\not \rightarrow (\aleph _{1})_{2}^{2}$ ou, par monotonie, que $\kappa \not \rightarrow (\aleph _{1})_{2}^{2}$ pour tout $\kappa \leq 2^{\aleph _{0}}$ . Le théorème d'Erdős-Rado donne l'énoncé positif : $\kappa \rightarrow (\aleph _{1})_{2}^{2}$ pour tous $\kappa >2^{\aleph _{0}}$ , parce que pour $n=1$ on a $(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 $\kappa$ , on définit récursivement

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

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

.

On a alors

Théorème — $\exp _{n}(\kappa )^{+}\rightarrow (\kappa ^{+})_{\kappa }^{n+1}$ pour tout entier naturel $n$ et tous les nombres cardinaux $\kappa$

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 $\mu$ pour que la propriété de partition $\mu \rightarrow (\kappa ^{+})_{\kappa }^{2}$ est satisfaite : on doit avoir $\mu \,>\,\exp _{n}(\kappa )$ .

Pour $\kappa =\aleph _{0}$ on a $\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 $n=1$ du théorème d'Erdős-Rado donne

(2^{\kappa })^{+}\rightarrow (\kappa ^{+})^{2}

pour tous les cardinaux infinis

\kappa

.

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

Notation

Exemples et discussion

Ènoncé du théorème

Notes et références

Bibliographie

Related Articles