Le théorème de Cantor

a) Une injection. L'application $x\mapsto \{x\}$ convient : si $\{x\}=\{x^{\prime }\}$, alors $x\in \{x^{\prime }\}$, donc $x=x^{\prime }$. Ainsi $E$ « tient » dans $\mathcal{P}(E)$.

b) L'argument diagonal. Notons bien que $D$ est une partie de $E$, donc un élément de $\mathcal{P}(E)$ : la question a un sens. Supposons, par l'absurde, que $D$ ait un antécédent $a\in E$, c'est-à-dire $f(a)=D$. Posons-nous la question : $a$ appartient-il à $D$ ?

• Si $a\in D$, alors, par définition de $D$, $a\notin f(a)$ ; or $f(a)=D$, donc $a\notin D$. Contradiction.
• Si $a\notin D$, alors, par définition de $D$, la condition « $a\notin f(a)$ » est fausse, donc $a\in f(a)=D$. Contradiction.

Dans les deux cas on aboutit à une contradiction : $D$ n'a pas d'antécédent. Comme $f$ était quelconque, aucune application de $E$ dans $\mathcal{P}(E)$ n'est surjective.

Conséquence. Il n'existe donc pas non plus de bijection entre $E$ et $\mathcal{P}(E)$ : un ensemble et l'ensemble de ses parties ne sont jamais « de même taille ». Pour $E$ fini à $n$ éléments, on le savait : $\mathcal{P}(E)$ en a $2^n>n$. Pour $E$ infini, c'est nouveau, et c'est le premier résultat qui distingue des infinis entre eux.

c) Les indicatrices. À toute partie $A$ on associe sa fonction indicatrice $1_A:E\to \{0,1\}$, qui vaut $1$ sur $A$ et $0$ ailleurs.

Injectivité. Si $1_A=1_B$, alors pour tout $x$, $x\in A⟺1_A(x)=1⟺1_B(x)=1⟺x\in B$ : $A=B$.

Surjectivité. Soit $\phi :E\to \{0,1\}$ ; posons $A={\phi }^{-1}(\{1\})=\{x\in E\mid \phi (x)=1\}$. Alors $1_A(x)=1$ si et seulement si $\phi (x)=1$, et comme $\phi$ ne prend que les valeurs $0$ et $1$, $1_A=\phi$.

Donc $A\mapsto 1_A$ est une bijection de $\mathcal{P}(E)$ sur $\{0,1{\}}^E$.

Application à $\mathbb{N}$. Une suite à valeurs dans $\{0,1\}$ n'est rien d'autre qu'une application de $\mathbb{N}$ dans $\{0,1\}$. S'il existait une surjection $s$ de $\mathbb{N}$ sur $\{0,1{\}}^{\mathbb{N}}$, alors, en la composant avec la bijection réciproque de $A\mapsto 1_A$, on obtiendrait une surjection de $\mathbb{N}$ sur $\mathcal{P}(\mathbb{N})$ — la composée d'une surjection et d'une bijection est surjective — ce que le b) interdit. On ne peut donc pas numéroter les suites de $0$ et de $1$ : il y en a, en un sens précis, plus que d'entiers.

Ce que l'exercice installe. L'argument diagonal est une idée à part entière : construire un objet qui, en chaque point, contredit ce qu'on lui propose. On le retrouvera tel quel pour montrer que $\mathbb{R}$ n'est pas dénombrable, et sous d'autres habits en informatique. Et la bijection entre parties et indicatrices, elle, est l'outil qui transforme une question sur les ensembles en une question sur des fonctions à valeurs dans $\{0,1\}$ — ce qu'on avait déjà exploité pour la différence symétrique.