Pour comprendre le théorème de Cantor, il faut se familiariser avec deux notions de base de la théorie des ensembles :
- Cardinalité : La cardinalité d’un ensemble, notée $|A|$, est une mesure du « nombre d’éléments » de cet ensemble. Deux ensembles ont la même cardinalité s’il existe une bijection (une correspondance un à un) entre eux. On dit que $|A| \le |B|$ s’il existe une injection de $A$ dans $B$.
- Ensemble des parties (ou ensemble puissance) : Pour un ensemble $A$, l’ensemble de toutes ses parties (ou sous-ensembles) est noté $\mathcal{P}(A)$. Par exemple, si $A = \{1, 2\}$, alors $\mathcal{P}(A) = \{\emptyset, \{1\}, \{2\}, \{1, 2\}\}$.
Pour tout ensemble $A$, la cardinalité de son ensemble des parties $\mathcal{P}(A)$ est strictement plus grande que la cardinalité de $A$ lui-même. $$ |A| < |\mathcal{P}(A)| $$
Cela signifie qu’il n’existe aucune surjection (et donc aucune bijection) d’un ensemble $A$ sur l’ensemble de ses propres parties $\mathcal{P}(A)$.
Démonstration (Argument Diagonal de Cantor)
La démonstration est un exemple classique de raisonnement par l’absurde, utilisant l’argument dit « diagonal ».
- Partie facile ($|A| \le |\mathcal{P}(A)|$) : Il est facile de montrer que la cardinalité de $A$ est inférieure ou égale à celle de $\mathcal{P}(A)$. Il suffit de trouver une injection de $A$ dans $\mathcal{P}(A)$. L’application $g: A \to \mathcal{P}(A)$ qui à chaque élément $x \in A$ associe le singleton $\{x\}$ est clairement injective.
- Partie difficile ($|A| \neq |\mathcal{P}(A)|$) : Nous devons montrer qu’il n’existe aucune bijection entre $A$ et $\mathcal{P}(A)$. Pour cela, il suffit de montrer qu’il n’existe aucune surjection de $A$ sur $\mathcal{P}(A)$.
Procédons par l’absurde. Supposons qu’il existe une fonction surjective $f: A \to \mathcal{P}(A)$. Cela signifie que chaque sous-ensemble de $A$ est l’image d’au moins un élément de $A$ par $f$.
Considérons maintenant l’ensemble « diagonal » de Cantor, $B$, qui est un sous-ensemble très particulier de $A$. Il est défini comme l’ensemble des éléments de $A$ qui n’appartiennent pas à leur propre image par $f$ : $$ B = \{ x \in A \mid x \notin f(x) \} $$ Puisque $B$ est un sous-ensemble de $A$, $B$ est un élément de $\mathcal{P}(A)$.
Comme nous avons supposé que $f$ est surjective, il doit exister un antécédent pour $B$. Autrement dit, il doit exister un élément $b \in A$ tel que $f(b) = B$.
Posons-nous maintenant la question : l’élément $b$ appartient-il à l’ensemble $B$ ?
-
Cas 1 : Supposons que $b \in B$.
Par la définition de l’ensemble $B$, si un élément $x$ est dans $B$, alors il doit satisfaire la condition $x \notin f(x)$. En appliquant cela à $b$, on obtient que si $b \in B$, alors $b \notin f(b)$. Mais comme $f(b)=B$, cela signifie $b \notin B$. C’est une contradiction. -
Cas 2 : Supposons que $b \notin B$.
Par la définition de l’ensemble $B$, si un élément $x$ n’est pas dans $B$, alors il ne satisfait pas la condition, c’est-à-dire que l’on a $x \in f(x)$. En appliquant cela à $b$, on obtient que si $b \notin B$, alors $b \in f(b)$. Mais comme $f(b)=B$, cela signifie $b \in B$. C’est à nouveau une contradiction.
Conclusion : Dans les deux cas, nous arrivons à une contradiction. L’hypothèse de départ, à savoir l’existence d’une fonction surjective $f$ de $A$ sur $\mathcal{P}(A)$, doit donc être fausse.
Il n’existe donc pas de surjection de $A$ sur $\mathcal{P}(A)$, ce qui prouve que $|A| \neq |\mathcal{P}(A)|$. Combiné à la première partie, cela démontre que $|A| < |\mathcal{P}(A)|$.
Implications du Théorème
Le théorème de Cantor a des conséquences profondes :
- Il n’y a pas d’infini « le plus grand » : Pour tout ensemble infini, on peut en construire un autre qui est « strictement plus grand ». En partant de l’ensemble des entiers naturels $\mathbb{N}$, on peut construire une hiérarchie infinie de cardinaux infinis : $|\mathbb{N}| < |\mathcal{P}(\mathbb{N})| < |\mathcal{P}(\mathcal{P}(\mathbb{N}))| < \dots$
- Il n’existe pas d’ensemble de tous les ensembles : Si un tel ensemble $U$ existait, son ensemble des parties $\mathcal{P}(U)$ devrait être un sous-ensemble de $U$. Cela impliquerait $|\mathcal{P}(U)| \le |U|$, ce qui contredit directement le théorème de Cantor.