Théorème 3Relations, fonctions

Théorème de Cantor

Énoncé

Pour tout ensemble $A$ , il n'existe aucune surjection de $A$ sur ${\mathcal P}(A)$ . En particulier, $A \preccurlyeq \mathcal P(A)$ , mais $A$ et $\mathcal P(A)$ ne sont pas équipotents.

Démonstration

Soit $f : A \to \mathcal P(A)$ une application. L'ensemble $D = \{a \in A : a \notin f(a)\}$ existe par séparation, et c'est une partie de $A$ . Supposons $D = f(d)$ pour un $d \in A$ . Par définition de $D$ , on a $d \in D \iff d \notin f(d) = D$ , ce qui est contradictoire. Donc $D$ n'a pas d'antécédent, et $f$ n'est pas surjective.

Un point plein dans la ligne de

f(y)

et la colonne de

x

signifie

x \in f(y)

, un point creux

x \notin f(y)

. La partie

D

, en rouge, s'obtient en inversant la diagonale encadrée : elle diffère de chaque

f(x)

au moins en

x

, et ne peut donc être aucune des lignes. Seules quelques lignes sont dessinées ; l'argument vaut pour un ensemble

A

quelconque.

L'application $A \to \mathcal P(A)$ , $a \mapsto \{a\}$ , de graphe $\{(a, S) \in A \times \mathcal P(A) : S = \{a\}\}$ , est injective, puisque $\{a\} = \{a'\}$ entraîne $a = a'$ . Une bijection de $A$ sur $\mathcal P(A)$ serait une surjection, ce qui vient d'être exclu.

□

Remarque

L'argument diagonal est celui du paradoxe de Russell, appliqué à $x \notin f(x)$ au lieu de $x \notin x$ . Il montre qu'aucun ensemble n'est « le plus grand » : $\mathcal P(A)$ est toujours strictement plus gros que $A$ . Cantor l'a publié en 1891, sous la forme équivalente des fonctions d'un ensemble dans $\{0, 1\}$ .

Repose sur

Équipotence et comparaison des ensembles

Sert à

Aucune fiche de ce graphe ne l'utilise encore.