théorème de Cantor-Bernstein

Imaginez deux collections. On peut ranger chaque objet de la première dans une place distincte de la seconde, puis faire l’inverse, sans jamais mettre deux objets à la même place. Le théorème affirme qu’il existe alors un appariement parfait : chaque objet d’une collection correspond à un seul objet de l’autre, sans oubli.

Cette conclusion vaut aussi pour les ensembles infinis, où comparer le nombre d’éléments à l’œil ne suffit plus.

Le théorème de Cantor-Bernstein, ou théorème de Cantor-Schröder-Bernstein, compare les cardinaux de deux ensembles. Une injection associe à deux éléments distincts de l’ensemble de départ deux images distinctes. Une bijection est une correspondance à la fois injective et surjective : tout élément de l’ensemble d’arrivée possède alors un unique antécédent.

Soient E et F deux ensembles. Si une injection nommée f va de E vers F et qu’une injection nommée g va de F vers E, le théorème garantit l’existence d’une bijection nommée h de E sur F : $f:E\hookrightarrow F,g:F\hookrightarrow E⟹h:E\stackrel{\sim }{\to }Ff:E\backslash hookrightarrow\; F,\backslash quad\; g:F\backslash hookrightarrow\; E\backslash quad\backslash Longrightarrow\backslash quad\; h:E\backslash xrightarrow\{\backslash sim\}F$. Les ensembles E et F sont donc équipotents, c’est-à-dire de même cardinal.

Le résultat ne suppose ni que les ensembles soient finis, ni qu’une formule pour h soit déjà connue. Il transforme deux comparaisons injectives, chacune dans un sens, en une correspondance parfaite. Cette force est particulièrement utile pour les ensembles infinis.

Soient E et F deux ensembles. S’il existe une injection f de E dans F et une injection g de F dans E, alors il existe une bijection h de E sur F. En notation cardinale, les deux hypothèses donnent |E| ≤ |F| et |F| ≤ |E| ; la conclusion est |E| = |F|.

Le théorème affirme l’existence de h. Il n’affirme pas que f et g sont réciproques l’une de l’autre.

Le domaine est celui des ensembles et des applications entre eux. Il faut disposer de deux injections : la première part de E et arrive dans F ; la seconde part de F et arrive dans E. Pour chacune, deux éléments distincts du départ doivent toujours avoir des images distinctes. Aucune finitude ni relation d’ordre n’est requise.

Une seule injection ne suffit pas. Par exemple, l’ensemble {1} s’injecte dans {a, b}, mais aucune injection ne va de {a, b} vers {1}. Le théorème ne permet donc pas de conclure à une bijection ; pour des ensembles finis, on compare alors directement leurs nombres d’éléments.

Comparons l’ensemble N = {0, 1, 2, 3, …} des entiers naturels et l’ensemble P = {0, 2, 4, 6, …} des entiers naturels pairs.
Données : N contient tous les entiers naturels ; P contient exactement ceux qui s’écrivent 2n avec n dans N.

1. On définit de N vers P l’application f par $f(n)=2nf(n)=2n$. Deux entiers distincts ont des doubles distincts : f est injective.

2. On définit de P vers N l’application g par $g(p)=pg(p)=p$. Il s’agit de l’inclusion des nombres pairs parmi les entiers naturels ; elle est injective.

3. Les deux injections existent en sens contraires. Cantor-Bernstein garantit donc une bijection entre N et P. Ici, f est déjà cette bijection : chaque pair p possède l’unique antécédent p/2.

Contrôle : les premières correspondances sont 0 ↔ 0, 1 ↔ 2, 2 ↔ 4, 3 ↔ 6 et 4 ↔ 8. Aucun pair n’est oublié et aucun n’apparaît deux fois.

Pour comparer deux ensembles infinis, on cherche souvent deux codages injectifs, un dans chaque sens. Cette stratégie évite de construire immédiatement une bijection explicite, parfois plus délicate.

Pour vérifier une injection proposée, on contrôle qu’une même image ne peut pas venir de deux éléments distincts. Si ce contrôle échoue, il faut modifier le codage avant d’invoquer le théorème.

Quand une bijection simple est déjà visible, comme n ↦ 2n entre les entiers naturels et les pairs, on l’utilise directement. Cantor-Bernstein devient surtout utile lorsque seules les deux injections sont faciles à décrire.

Injection et bijection. Une injection interdit que deux éléments du départ aient la même image, mais elle peut laisser des éléments d’arrivée sans antécédent. Une bijection ne laisse aucun élément d’arrivée de côté. L’inclusion de {1} dans {1, 2} est injective, pas bijective.

Même cardinal et égalité des ensembles. Deux ensembles de même cardinal peuvent avoir des éléments différents. {1, 2} et {a, b} sont équipotents grâce à l’appariement 1 ↔ a, 2 ↔ b, sans être le même ensemble.

Les injections ne se composent pas pour donner la bijection cherchée. La composée g ∘ f revient de E vers E, pas de E vers F. Il faut appliquer le théorème ou construire séparément une bijection.

Les deux injections n’ont pas à être inverses. Leur existence suffit. Dans l’exemple des entiers naturels et des pairs, g est l’inclusion p ↦ p, tandis que l’inverse de f est p ↦ p/2.

L’existence n’est pas une recette immédiate. Le théorème garantit une bijection même si les injections données ne l’exhibent pas directement. Lorsqu’une correspondance explicite est demandée, il reste à la construire ou à extraire celle fournie par une preuve du théorème.

L’article injection précise le critère qui garantit qu’aucune image ne représente deux éléments distincts.

La fiche bijection développe la correspondance parfaite obtenue dans la conclusion du théorème.

La fiche Dénombrable montre comment une bijection avec les entiers naturels organise certains ensembles infinis.

L’article Georg Cantor : passer du fini à l'infini replace ces comparaisons de cardinaux dans leur histoire mathématique.