théorème de Cantor

Prenons trois objets, notés a, b et c. On peut former huit groupes différents avec eux : le groupe vide, trois groupes d’un objet, trois groupes de deux objets et le groupe des trois objets. Il y a donc plus de groupes possibles que d’objets : huit contre trois.

Le théorème de Cantor affirme que ce dépassement se produit pour tout ensemble, même infini. Quelle que soit la tentative d’associer à chaque élément un sous-ensemble, au moins un sous-ensemble restera absent de la liste.

Soit E un ensemble. Son ensemble des parties, noté $\mathcal{P}(E)\backslash mathcal\{P\}(E)$, rassemble tous les sous-ensembles de E, y compris l’ensemble vide et E lui-même. Le cardinal d’un ensemble mesure sa taille ; le symbole $\mathrm{\mid }E\mathrm{\mid }|E|$ désigne donc le cardinal de E.

Le théorème de Cantor affirme que pour tout ensemble E. Il existe bien une injection de E dans son ensemble des parties, par exemple celle qui associe à chaque élément x le singleton contenant x. En revanche, aucune application de E vers $\mathcal{P}(E)\backslash mathcal\{P\}(E)$ ne peut être surjective : elle ne peut pas atteindre toutes les parties.

L’argument diagonal prouve l’impossibilité de cette surjection. Pour toute application f de E vers $\mathcal{P}(E)\backslash mathcal\{P\}(E)$, on construit la partie D formée des éléments x qui n’appartiennent pas à f(x). Pour chaque élément y de E, D et f(y) diffèrent au moins sur y. Ainsi, D n’est l’image d’aucun élément.

Si E est un ensemble quelconque et si $\mathcal{P}(E)\backslash mathcal\{P\}(E)$ est l’ensemble de toutes ses parties, alors le cardinal de $\mathcal{P}(E)\backslash mathcal\{P\}(E)$ est strictement supérieur à celui de E : . De manière équivalente, pour toute application $f:E\to \mathcal{P}(E)f:E\backslash to\backslash mathcal\{P\}(E)$, la partie $D=\{x\in E\mid x\mathrm{\notin }f(x)\}D=\backslash \{x\backslash in\; E\backslash mid\; x\backslash notin\; f(x)\backslash \}$ n’appartient pas à l’image de f.

Le théorème s’applique à tout ensemble E, fini ou infini. Il faut considérer toutes ses parties, sans omettre l’ensemble vide ni E lui-même. La conclusion compare des cardinaux : elle affirme à la fois qu’une injection de E dans $\mathcal{P}(E)\backslash mathcal\{P\}(E)$ existe et qu’aucune surjection en sens inverse n’existe. Aucun ordre, aucune structure algébrique et aucune hypothèse de dénombrabilité ne sont requis.

Si l’on ne retient qu’une collection particulière de sous-ensembles, la conclusion peut échouer. Pour E formé de a, b et c, la collection des trois singletons a le même cardinal que E. Il faut alors comparer cette collection à E directement ; le théorème de Cantor ne s’applique qu’à l’ensemble complet des huit parties.

Données. On prend l’ensemble E formé des trois éléments a, b et c. Une partie de E est un groupe obtenu en gardant certains de ces éléments, éventuellement aucun ou tous.

1. En ne gardant aucun élément, on obtient l’ensemble vide. En gardant un seul élément, on obtient les trois singletons {a}, {b} et {c}.

2. En gardant deux éléments, on obtient {a, b}, {a, c} et {b, c}. En gardant les trois, on retrouve E, soit {a, b, c}.

3. La liste complète contient donc huit parties. Comme E contient trois éléments, on vérifie ici .

4. Plus généralement, chacun des n éléments d’un ensemble fini peut être soit absent, soit présent dans une partie. Ces deux choix indépendants donnent $2^{n}2^n$ parties. Pour n = 3, le calcul donne bien 2³ = 8.

Contrôle. Les huit parties se répartissent en 1 groupe vide, 3 singletons, 3 paires et 1 groupe complet. La somme 1 + 3 + 3 + 1 = 8 confirme qu’aucune partie n’a été oubliée ni comptée deux fois.

Pour compter toutes les configurations oui/non portant sur n objets, on identifie chaque configuration à une partie de l’ensemble des objets. Le nombre obtenu est alors 2ⁿ. Si les choix ne sont pas indépendants, il faut plutôt compter seulement les parties autorisées.

Pour réfuter l’idée qu’une liste indexée par E contient toutes les parties de E, on applique le geste diagonal : on examine, pour chaque x, si x appartient à la partie placée à l’indice x, puis on choisit l’appartenance contraire. La partie construite manque nécessairement à la liste.

Pour produire un cardinal infini strictement plus grand qu’un cardinal donné, on passe à l’ensemble des parties. Répéter l’opération construit une hiérarchie sans dernier niveau ; comparer deux ensembles particuliers peut toutefois demander d’autres outils.

Avec le théorème de Cantor-Bernstein. Celui-ci conclut que deux ensembles ont le même cardinal lorsqu’il existe une injection dans chaque sens. Le théorème de Cantor compare un ensemble à toutes ses parties et conclut à une inégalité stricte. Deux injections opposées appellent Cantor-Bernstein ; une application vers l’ensemble des parties appelle l’argument diagonal.

Avec une collection de parties. Une famille de sous-ensembles peut avoir le même cardinal que E, ou un cardinal plus petit. Pour E = {a, b, c}, les trois singletons sont aussi nombreux que les éléments de E. Seul l’ensemble de toutes les parties, qui en contient huit, relève du théorème.

Le cas vide n’est pas une exception. Si E est vide, son ensemble des parties contient exactement l’ensemble vide comme unique élément. Les cardinaux valent donc 0 et 1, et l’inégalité stricte subsiste. Il ne faut pas retirer ce cas de l’énoncé.

L’infini ne neutralise pas le résultat. Pour un ensemble infini, ajouter un seul élément peut laisser le cardinal inchangé, mais prendre toutes les parties produit toujours un cardinal strictement supérieur. Le calcul fini $\mathrm{\mid }\mathcal{P}(E)\mathrm{\mid }=2^{\mathrm{\mid }E\mathrm{\mid }}|\backslash mathcal\{P\}(E)|=2^\{|E|\}$ se prolonge en arithmétique cardinale, sans rendre les deux tailles égales.

La partie diagonale dépend de l’application testée. Le procédé ne désigne pas une même partie D pour toutes les listes possibles. À chaque application f correspond sa propre partie absente. Il faut donc reconstruire D lorsque f change, et non chercher un sous-ensemble universellement manquant.

Le paradoxe de Cantor est une conséquence, pas une contradiction du théorème. Si un ensemble de tous les ensembles existait, son ensemble des parties devrait à la fois s’y inclure et avoir un cardinal strictement supérieur. La conclusion correcte est qu’un tel ensemble universel n’existe pas dans le cadre usuel de la théorie des ensembles.

Ensemble des parties — Détaille l’objet dont le cardinal dépasse toujours celui de l’ensemble de départ.

surjection — Précise le critère d’atteinte de toutes les valeurs que l’argument diagonal met en défaut.

paradoxe de Cantor — Développe pourquoi le théorème interdit l’existence d’un ensemble de tous les ensembles.

théorème de Cantor-Bernstein — Présente l’autre grand critère de comparaison des cardinaux fondé sur deux injections.