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”).

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\}$ .

Définition

Démonstration

Complément

Sources :