Démonstration - Théorème de Cantor
« Cet article présente le théorème de Cantor ainsi que sa démonstration."
Définition
Soit $E$ un ensemble, il n’existe pas d’application bijective entre $E$ et $2^E$.
Cela implique qu’aucun ensemble n’est équipotent à son ensemble de parties. Mais pas seulement. Pour en savoir plus, la page wikipédia sur le théorème de Cantor est très complète (paragraphe : “Conséquences du théorème”).
Démonstration
Afin de démontrer ce théorème, raisonnons par l’absurde :
Soit $f : E \rightarrow 2^E$ une application bijective.
Posons $X := \{e \in E : e \notin f(e) \}$.
$X$ est une partie de $E$ (= élément de $2^E$) définie comme l’ensemble des éléments de $E$ qui n’appartiennent pas à leur image par $f$.
Pour comprendre pourquoi nous prenons ce $X$, prenons un exemple : Pour $E = \{a,b,c\}$, et $f(a) = \{a,b\}$ et $f(b) = \{\}$, $f(c)=\{a\}, $ $X =\{b,c\}$, $X$ est bien une partie de $E$, pourtant elle n’a pas d’antécédent par $f$. Voir Argument diagonale de Cantor
$\exists y \in E$ tel que $f(y) = X$.
Une application $f$ de $E$ dans $2^E$ est dite surjective si pour tout élément $y$ de $2^E$, il existe au moins un élément $e$ de $E$ tel que $f(e) = y$. Formellement, nous avons : $\forall y \in 2^E \ \exists e \in E ; f(e)=y$. Etant un élément de $2^E$, $X$ doit admettre un antécédent $y$ par $f$ car $f$ est surjective.
Nous avons 2 cas :
- Si $y \in X$, alors, par définition de $X$, $y \notin f(y)$. Donc $y \notin X$, ce qui est contradictoire.
- Si $y \notin X$, alors par définition de $X$, $y \in \bar{X}^E$. Ainsi $y \in f(y)$, donc $y \in X$, ce qui est encore une fois contradictoire.
$X$, bien que élément de $2^E$ n’a pas d’antécédent par $f$. $f$ n’est donc pas surjective, ni bijective. D’où le théorème de Cantor.
Complément
Le théorème de Cantor peut également être décliné de la façon suivante : Pour tout ensemble $E$, $|E|\textless |2^E|$. Cela se démontre naturellement par la non existance de la sujectivité (démontrée ci-dessus) et l’existance de l’application injective $f(x)=\{x\}$.
Par exemple, pour $E = \{a,b\}$, $2^E = \{\{\},\{a\},\{b\},\{a,b\}\}$, $a$ est associé à $\{a\}$ et $b$ à $\{b\}$.