Exercice corrigé : Théorème de Cantor-Bernstein

Voici l’énoncé d’un exercice qui permet de faire la démonstration du théorème de Cantor-Bernstein. C’est un exercice à la frontière entre le chapitre des ensembles et celui des injections, surjections et bijections. C’est un exercice tout à fait faisable en première année dans le supérieur mais il peut rester difficile pour un deuxième année. En voici l’énoncé :

Et voici sa correction !

Un lemme préliminaire

Tout d’abord, montrons le lemme suivant :
Si u est une application injective d’un ensemble A vers une de ses parties B alors il existe une bijection de A vers B.
Prenons maintenant la suite d’ensembles (C_n) définie par ;

\begin{array}{l}
C_0 = A \backslash B\\
\forall n \in \mathbb{N^*}, C_n = u(C_{n-1})
\end{array}

On pose ensuite C la réunion de tous les ensembles :

C = \bigcup_{n \in \mathbb{N}} C_n

Posons ensuite v l’application de A dans B définie par :

\begin{array}{ll}
v: & x\in C \rightarrow u(x) \\
&x \notin C \rightarrow x
\end{array}

v est bien à valeur dans B :

\begin{array}{l}
\text{Si } x \in C, u(x) \in B\\
\text{Si } x \notin C \Rightarrow  x \notin C_0 = A \backslash  B \Rightarrow x \in B
\end{array}

Montrons alors que v est bijective.
v est injective :

Soient x et y dans B tels que

v(x) = v(y) 

3 choix :

• Si x \in C et y \in C : Dans ce cas : v(x) = u(x) = v(y) = u(y). Comme u est injective, on a x = y
• Si x \in C et y \notin C ​ou x \notin C et y \in C . Dans ce cas v(x) = u(x) \in C et v(y) = y \notin C. Ce cas est impossible
• Si x \notin C et y \notin C. Dans ce cas v(x) = x et v(y) = y et donc x = y

v est surjective :
Soit y \in B . On cherche x tel que v(x) = y. On a cette fois 2 cas :

• y \in C . Dans ce cas, comme C_0 = A \backslash B, y \notin C_0 . Donc il existe un k > 0 tel que y \in C_k,. Et donc, y\in u(C_{k-1}). Donc on peut trouver x\in C_{k-1} tel que y = u(x)
• y \notin C. Dans ce cas x = y convient.

On en conclut donc que v est bijective, ce qui démontre notre lemme préliminaire.

Démonstration du théorème de Cantor-Bernstein

Notons f l’injection de E vers F et g l’injection de F vers E.
Notons aussi B = g(F). g est donc bijective de F vers B. Notons h cette restriction à B.
On a obtient donc que u = g o f est une injection (en tant que composée d’injections) de E dans B, sous ensemble de E.
D’après le lemme préliminaire, on sait qu’il existe une bijection v de E sur B.

Si on résume, on a obtenu que :

• h est une bijection de F vers B
• v est une bijection de E vers B

Considérons donc k = h^-1o v. Par composition de bijection, k est une bijection de E vers F.
Avec ceci on a bien démontré le théorème de Cantor-Bernstein !

Cet exercice vous a plu ?