Théorème de Cantor-Bernstein

On commence par montrer que si ${\displaystyle u}$ est une application injective d'un ensemble ${\displaystyle A}$ vers une de ses parties, ${\displaystyle B}$, alors il existe une bijection ${\displaystyle v}$ de ${\displaystyle A}$ sur ${\displaystyle B}$.

Théorème de Cantor-Bernstein.

Soit ${\displaystyle (C_{n})_{n\in \mathbb {N} }}$ la suite définie par :

${\displaystyle \left\{{\begin{matrix}C_{0}=A\setminus B\\\forall n\in \mathbb {N} ^{*},C_{n}=u(C_{n-1})\end{matrix}}\right.}$

Soit ${\displaystyle C}$ la réunion de tous les ensembles ${\displaystyle (C_{n})_{n\in \mathbb {N} }}$ : ${\displaystyle C=\bigcup _{n\in \mathbb {N} }C_{n}}$.

Soit alors ${\displaystyle v}$ l'application de ${\displaystyle A}$ dans ${\displaystyle B}$ définie par :

${\displaystyle {\begin{matrix}v:&x\in C&\mapsto &u(x)\\&x\notin C&\mapsto &x\end{matrix}}}$

${\displaystyle v}$ est bien définie à valeurs dans ${\displaystyle B}$, car ${\displaystyle u}$ est à valeurs dans ${\displaystyle B}$, et si ${\displaystyle x\notin C}$ alors ${\displaystyle x\notin C_{0}}$ et donc ${\displaystyle x\in B}$.

${\displaystyle v}$ envoie injectivement ${\displaystyle C}$ dans ${\displaystyle u(C)=\cup _{n\in \mathbb {N} }u(C_{n})=\cup _{m\in \mathbb {N} ^{*}}C_{m}\subset C}$ ; et le complémentaire de ${\displaystyle C}$ identiquement dans lui-même. C'est donc une injection.

Montrons que ${\displaystyle v}$ est surjective. Soit ${\displaystyle y\in B}$. Montrons qu'il existe un ${\displaystyle x\in A}$ tel que ${\displaystyle v(x)=y}$.

• Si ${\displaystyle y\in C}$ : alors il existe ${\displaystyle i\in \mathbb {N} ^{*}}$ tel que ${\displaystyle y\in C_{i}}$ (${\displaystyle i}$ est strictement positif car ${\displaystyle y\in B}$, donc ${\displaystyle y\notin C_{0}}$). Il existe donc ${\displaystyle x\in C_{i-1}\subset C}$ tel que ${\displaystyle v(x)=u(x)=y}$.
• Si ${\displaystyle y\notin C}$ : alors ${\displaystyle v(y)=y}$

Ainsi, ${\displaystyle v}$ est bijective, ce qui démontre la première proposition.

On peut donner une interprétation du résultat montré ci-dessus. A est l'ensemble (infini) des spectateurs d'un théâtre (infini). Chaque spectateur a réservé une place, et initialement, on suppose que chaque place est occupée par un spectateur, mais pas forcément par le spectateur qui a réservé cette place. B est alors l'ensemble des spectateurs assis. Par ailleurs, les ensembles étant infinis, il peut rester des spectateurs debout. L'application u est l'application qui associe, à un spectateur x, le spectateur y = u(x) assis à la place de x.

${\displaystyle C_{0}}$ est l'ensemble des spectateurs initialement debout. Ces spectateurs se rendent à leur place et en délogent les occupants. Ceux-ci forment alors l'ensemble ${\displaystyle C_{1}}$. Ces derniers procèdent de même. ${\displaystyle C_{n}}$ désigne les spectateurs debout à la n-ème étape. Ils vont aux places qu'ils ont réservées et en chassent leurs occupants. On itère une infinité de fois. C désigne l'ensemble des spectateurs qui se sont levés au moins une fois (y compris ceux qui étaient debout initialement).

L'application v désigne l'application qui associe, à un spectateur x qui doit se lever, le spectateur y qu'il va déloger, ou bien qui, à un spectateur x qui reste toujours assis, associe x lui-même. L'application réciproque de v est l'application qui, à un spectateur y qui est dérangé, associe le spectateur x qui vient prendre sa place, ou bien qui associe, à un spectateur y jamais dérangé, y lui-même.

Montrons alors le théorème initial.

Soit B = g(F) l'image de F par l'injection g. L'application u = g o f est une injection de E dans B, avec ${\displaystyle B\subset E}$. Donc il existe une bijection v de E sur B. Comme g est une injection et g(F) = B, elle définit par restriction une bijection h de F sur B. La composée h^-1∘v est une bijection de E sur F, ce qui démontre le théorème de Cantor-Bernstein[15].

Cette démonstration repose sur le lemme suivant, cas particulier du théorème de Knaster-Tarski.

Soit ${\displaystyle E}$ un ensemble, ${\displaystyle P(E)}$ l'ensemble de ses parties et ${\displaystyle G:P(E)\to P(E)}$ une application croissante, c'est-à-dire telle que ${\displaystyle A\subset B\Rightarrow G(A)\subset G(B)}$. Alors ${\displaystyle G}$ admet un point fixe, c'est-à-dire qu'il existe une partie ${\displaystyle M}$ de ${\displaystyle E}$ telle que ${\displaystyle G(M)=M}$.

Soient maintenant ${\displaystyle f}$ injective de ${\displaystyle E}$ dans ${\displaystyle F}$ et ${\displaystyle g}$ injective de ${\displaystyle F}$ dans ${\displaystyle E}$. Pour toute partie ${\displaystyle A}$ de ${\displaystyle E}$, on pose ${\displaystyle G(A)=E\setminus g\left[F\setminus f(A)\right]}$, c'est-à-dire que ${\displaystyle G(A)}$ s'obtient en prenant l'image directe ${\displaystyle f(A)}$, puis le complémentaire dans ${\displaystyle F}$ de cette image, puis l'image directe par ${\displaystyle g}$ de ce complémentaire, et enfin le complémentaire dans ${\displaystyle E}$ de cette image. Il n'est pas difficile de vérifier que ${\displaystyle G:P(E)\to P(E)}$ est croissante.

On introduit alors la partie ${\displaystyle M}$ du lemme préliminaire. Cette partie est invariante par ${\displaystyle G}$, ce qui signifie que ${\displaystyle g\left[F\setminus f(M)\right]}$ est le complémentaire de ${\displaystyle M}$ dans ${\displaystyle E}$.

Théorème de Cantor-Bernstein.

On définit une bijection ${\displaystyle h:E\to F}$ en posant :

si ${\displaystyle x\in M,h(x)=f(x)}$ ;

si ${\displaystyle x\notin M,h(x)=g^{-1}(x)}$.

${\displaystyle M}$ joue un rôle comparable à la partie ${\displaystyle C}$ dans la première démonstration ou à ${\displaystyle E_{E}\cup E_{\infty }}$ dans la démonstration qui suit.

Cette démonstration est essentiellement celle publiée par Julius König en 1906[16], et souvent reprise depuis[17].

Supposons, sans perte de généralité, que ${\displaystyle E}$ et ${\displaystyle F}$ sont disjoints.

Théorème de Cantor-Bernstein (les ensembles ${\displaystyle E_{E}}$, ${\displaystyle E_{F}}$, ${\displaystyle F_{F}}$ et ${\displaystyle F_{E}}$ sont notés ici respectivement ${\displaystyle E_{p}}$, ${\displaystyle E_{i}}$, ${\displaystyle F_{p}}$ et ${\displaystyle F_{i}}$).

À élément ${\displaystyle x}$ de ${\displaystyle E}$, on associe une suite ${\displaystyle (x_{0},x_{1},\dots )}$ finie ou infinie définie par récurrence de la façon suivante. La valeur initiale est ${\displaystyle x_{0}=x}$. Supposons ${\displaystyle x_{n}}$ défini (sinon ${\displaystyle x_{n+1}}$ n'est pas défini), alors :

• si ${\displaystyle x_{n}\in E}$ possède un antécédent par g, alors ${\displaystyle x_{n+1}}$ est cet (unique) antécédent (remarque : dans ce cas n est pair) ;
• si ${\displaystyle x_{n}}$ est défini et ${\displaystyle x_{n}\in F}$ possède un antécédent par f, alors ${\displaystyle x_{n+1}}$ est cet (unique) antécédent (remarque : dans ce cas n est impair) ;
• dans les autres cas ${\displaystyle x_{n+1}}$n'est pas défini.

Trois cas sont alors possibles pour la suite ${\displaystyle (x_{0},x_{1},\dots )}$ qui permettent de partitionner ${\displaystyle E}$ en trois ensembles :

• ${\displaystyle E_{E}}$ est l'ensemble des ${\displaystyle x\in E}$ tels que la suite ${\displaystyle (x_{0},x_{1},\dots )}$ correspondante est finie et s'arrête sur un élément de ${\displaystyle E}$ (de façon équivalente, l'indice du dernier élément est pair) ;
• ${\displaystyle E_{F}}$ est l'ensemble des ${\displaystyle x\in E}$ tels que la suite ${\displaystyle (x_{0},x_{1},\dots )}$ correspondante est finie et s'arrête sur un élément de ${\displaystyle F}$ (de façon équivalente, l'indice du dernier élément est impair) ;
• ${\displaystyle E_{\infty }}$ est l'ensemble des ${\displaystyle x\in E}$ tels que la suite ${\displaystyle (x_{0},x_{1},\dots )}$ correspondante est infinie.

On partitionne ${\displaystyle F}$ de façon analogue en ${\displaystyle F_{F}}$, ${\displaystyle F_{E}}$ et ${\displaystyle F_{\infty }}$. Alors :

• ${\displaystyle f}$ est une bijection de ${\displaystyle E_{E}}$ sur ${\displaystyle F_{E}}$, ainsi que de ${\displaystyle E_{\infty }}$ sur ${\displaystyle F_{\infty }}$ ;
• ${\displaystyle g}$ est une bijection de ${\displaystyle F_{F}}$ sur ${\displaystyle E_{F}}$, et sa réciproque est donc une bijection de ${\displaystyle E_{F}}$ sur ${\displaystyle F_{F}}$.

On obtient ainsi une bijection de ${\displaystyle E}$ sur ${\displaystyle F}$[18].

• Théorème de comparabilité cardinale
• Propriété de Cantor-Bernstein (en)

• (en) Marcel Crabbé, « Cantor-Bernstein’s Theorem in a Semiring », The Mathematical Intelligencer, vol. 33, n^o 3,‎ 2011, p. 80 (lire en ligne)
• (en) Arie Hinkis, Proofs of the Cantor-Bernstein theorem, a mathematical excursion, Birkhäuser, 2013, 456 p. (ISBN 978-3-0348-0788-3, DOI 10.1007/978-3-0348-0224-6)