En théorie des ensembles, pour comparer les « tailles » (cardinalités) de deux ensembles $A$ et $B$, on utilise les notions d’injection et de bijection.
- Dire que $|A| \le |B|$ signifie qu’il existe une injection de $A$ dans $B$ (on peut associer à chaque élément de $A$ un élément unique de $B$).
- Dire que $|A| = |B|$ signifie qu’il existe une bijection entre $A$ et $B$ (une correspondance parfaite un à un).
Il est évident que si $|A|=|B|$, alors $|A| \le |B|$ et $|B| \le |A|$. Le théorème de Cantor-Bernstein établit la réciproque, qui est beaucoup moins intuitive.
Soient $A$ et $B$ deux ensembles. S’il existe une injection de $A$ dans $B$ et une injection de $B$ dans $A$, alors il existe une bijection entre $A$ et $B$.
En termes de cardinalité, cela s’écrit : $$ \text{Si } |A| \le |B| \text{ et } |B| \le |A|, \text{ alors } |A| = |B| $$
Démonstration (Esquisse d’une preuve classique)
La démonstration consiste à construire explicitement une bijection $h: A \to B$ à partir des deux injections données.
Soient $f: A \to B$ et $g: B \to A$ deux injections.
Étape 1 : Chaînes de prédécesseurs
Pour un élément quelconque $a \in A$, on peut construire la « chaîne de ses prédécesseurs » en appliquant alternativement les injections inverses $g^{-1}$ et $f^{-1}$ (qui sont définies sur les images de $g$ et $f$). On obtient une suite : $$ a, \quad g^{-1}(a), \quad f^{-1}(g^{-1}(a)), \quad g^{-1}(f^{-1}(g^{-1}(a))), \quad \dots $$ Cette chaîne peut être finie (si à un moment un élément n’a plus de prédécesseur) ou infinie.
Étape 2 : Partition de l’ensemble de départ A
On partitionne l’ensemble $A$ en trois sous-ensembles disjoints, en fonction de la nature de la chaîne de prédécesseurs de chaque élément :
- $A_A$ : L’ensemble des éléments de $A$ dont la chaîne de prédécesseurs se termine par un élément de $A$. (La chaîne a une « origine » dans A).
- $A_B$ : L’ensemble des éléments de $A$ dont la chaîne de prédécesseurs se termine par un élément de $B$. (La chaîne a une « origine » dans B).
- $A_\infty$ : L’ensemble des éléments de $A$ dont la chaîne de prédécesseurs est infinie.
On a bien $A = A_A \cup A_B \cup A_\infty$. On peut de même partitionner l’ensemble $B$ en $B_A$, $B_B$ et $B_\infty$.
Étape 3 : Construction de la bijection h
On observe comment les injections $f$ et $g$ agissent sur ces partitions :
- L’injection $f$ envoie bijectivement $A_A$ sur $B_A$.
- L’injection $f$ envoie bijectivement $A_B$ sur $B_B$.
- L’injection $f$ envoie bijectivement $A_\infty$ sur $B_\infty$.
- L’injection $g$ envoie bijectivement $B_A$ sur $A_B$.
On peut alors construire la bijection $h: A \to B$ « par morceaux » : $$ h(x) = \begin{cases} f(x) & \text{si } x \in A_A \cup A_\infty \\ g^{-1}(x) & \text{si } x \in A_B \end{cases} $$
On vérifie que cette application est bien définie et qu’elle est bijective.
- Pour un élément $x \in A_A \cup A_\infty$, son image $f(x)$ est dans $B_A \cup B_\infty$.
- Pour un élément $x \in A_B$, son image $g^{-1}(x)$ est dans $B_B$.
La fonction $h$ est une bijection de $A_A \cup A_\infty$ sur $B_A \cup B_\infty$ et une bijection de $A_B$ sur $B_B$. Elle est donc une bijection de $A$ sur $B$.
Implications et Utilisation
Ce théorème est extrêmement utile pour prouver l’égalité de cardinalités entre ensembles infinis, où construire une bijection explicite peut être très difficile.
Par exemple, pour montrer que l’intervalle $[0, 1]$ a la même cardinalité que $]0, 1[$, il est difficile de trouver une bijection directe. Mais il est facile de trouver une injection dans chaque sens :
- $f: ]0,1[ \to [0,1]$ définie par $f(x)=x$ est une injection évidente.
- $g: [0,1] \to ]0,1[$ définie par $g(x) = \frac{x+1}{3}$ est aussi une injection (elle envoie $[0,1]$ dans $[1/3, 2/3]$).
Puisqu’il existe une injection dans les deux sens, le théorème de Cantor-Bernstein nous permet de conclure que $|[0,1]| = |]0,1[|$ sans avoir à construire la bijection complexe.