Théorème de Cantor : démonstration par diagonale

Le théorème de Cantor (1891) affirme que pour tout ensemble $E$, il n'existe pas de surjection de $E$ vers $\mathcal{P}(E)$. La démonstration, par argument diagonal, est l'une des plus élégantes des mathématiques.

Énoncé

Soit $E$ un ensemble. Il n'existe pas de surjection $f : E \to \mathcal{P}(E)$.

Corollaire immédiat : $\mathrm{Card}(E) < \mathrm{Card}(\mathcal{P}(E))$. Il n'existe pas de plus grand cardinal.

Démonstration

Supposons par l'absurde qu'il existe une surjection $f : E \to \mathcal{P}(E)$. On construit l'ensemble diagonal :

$$B = \{x \in E \mid x \notin f(x)\}$$

Puisque $B \subseteq E$, on a $B \in \mathcal{P}(E)$. Par surjectivité, il existe $a \in E$ tel que $f(a) = B$.

Deux cas : si $a \in B$, alors par définition de $B$, $a \notin f(a) = B$ — contradiction. Si $a \notin B$, alors $a \notin f(a)$, donc $a \in B$ par définition — contradiction.

Dans les deux cas, contradiction. Donc $f$ n'est pas surjective. $\blacksquare$

Conséquences

En prenant $E = \mathbb{N}$, on obtient que $\mathcal{P}(\mathbb{N})$ est indénombrable. Comme $\mathcal{P}(\mathbb{N})$ est en bijection avec $\mathbb{R}$ (via l'écriture binaire), on retrouve le résultat : $\mathbb{R}$ est indénombrable.

L'argument se relance indéfiniment : $\mathrm{Card}(\mathbb{N}) < \mathrm{Card}(\mathcal{P}(\mathbb{N})) < \mathrm{Card}(\mathcal{P}(\mathcal{P}(\mathbb{N}))) < \dots$ Il existe une infinité de cardinaux infinis.

Une question ou une suggestion ? Écrivez-nous.