Accéder à mon compte > Accéder à ma feuille d'exercices >

Théorème de Cantor-Bernstein - Bibm@th.net

Exercice 1

- Théorème de Cantor-Bernstein [Signaler une erreur] [Ajouter à ma feuille d'exos]

Enoncé

Le but de cet exercice est de démontrer un célèbre théorème de Cantor et Bernstein : si $E$ et $F$ sont des ensembles tels qu'il existe une injection de $E$ dans $F$ et une injection de $F$ dans $E$, alors il existe une bijection de $E$ sur $F$. On se donne donc deux ensembles $E$ et $F$ et deux applications injectives $i:E\to F$ et $j:F\to E$. On note par ailleurs $$A_0=E\backslash j(F),\ A_1=(j\circ i)(A_0),\dots, A_{n+1}=(j\circ i)(A_n)$$ et $$B=\bigcup_{n\geq 0}A_n,\ C=E\backslash B.$$

Construction de l'application.
1. Démontrer que pour tout $x\in C$, il existe un unique $z\in F$ tel que $x=j(z)$. On notera cet élément $\phi(x)$.
2. Pour $x\in B$, on note $\phi(x)=i(x)$. Démontrer que l'on a ainsi bien défini une application $\phi:E\to F$.
Injectivité de $\phi$.
1. Démontrer que les restrictions de $\phi$ à $B$ et à $C$ sont injectives.
2. Considérons maintenant $x\in C$ et $y\in B$ tels que $\phi(x)=\phi(y)$. Démontrer que $x=(j\circ i)(y)$.
3. En déduire que $\phi$ est injective.
Surjectivité de $\phi$. Démontrer que $\phi$ est surjective.
Un exemple. Pour $E=\mathbb N$, $F=\{2,3,\dots,\}$, $i:E\to F,\ n\mapsto n+4$, $j:F\to E,\ n\mapsto n$, déterminer les ensembles $A_n$, $B$, $C$ et l'application $\phi$.

Indication

Corrigé

Construction de l'application.
1. Il y a deux choses à démontrer : l'existence et l'unicité. Pour l'unicité, c'est très simple : c'est une conséquence directe du fait que $j$ est injective. L'équation $j(z)=x$ admet toujours AU PLUS une solution.
  Pour l'existence dire que l'équation $j(z)=x$ a une solution signifie que $x\in j(F)$. Autrement dit, on doit démontrer que $C\subset j(F)$. Ce n'est pas non plus très dur, mais il faut suivre un peu (un dessin peut aider!). On peut remarquer que $A_0\subset B$, et donc $E\backslash B\subset E\backslash A_0$ (le passage au complémentaire renverse les inclusions) et donc $C=E\backslash B\subset E\backslash A_0=j(F)$.
2. Puisque $B$ et $C$ sont disjoints et que leur réunion est $E$, les deux formules précédentes définissent bien une application sur $A$. De plus, dans les deux cas, l'image est bien dans $F$. Donc $\phi$ est une application de $E$ dans $F$.
Injectivité de $\phi$.
1. Commençons par la restriction à $B$. Si $x,y\in B$ sont tels que $\phi(x)=\phi(y)$, alors par construction de $\phi$ sur $B$ on a $i(x)=i(y)$ et ceci entraîne bien que $x=y$ par injectivité de $i$.
  Étudions maintenant la restriction à $C$. Si $x,y\in C$ sont tels que $\phi(x)=\phi(y)$, alors on sait que $\phi(x)$ vérifie $j(\phi(x))=x$ et que $\phi(y)$ vérifie $j(\phi(y))=y$. On en conclut que $$x=j(\phi(x))=j(\phi(y))=y.$$
2. On sait que $$x=j(\phi(x))=j(\phi(y))=j(i(y))=(j\circ i)(y)$$ en tenant compte du fait que $x\in C$ et $y\in B$.
3. Soit $x,y\in E$ tels que $\phi(x)=\phi(y)$. On a déjà démontré que si $x$ et $y$ sont tous les deux éléments de $B$ ou tous les deux éléments de $C$, alors $x=y$. Il ne reste à étudier que le cas $x\in C$ et $y\in B$ (le dernier cas est symétrique). Puisque $y\in B$, il existe un entier $n$ tel que $y\in A_n$. Mais d'après la question précédente, on a aussi $x\in A_{n+1}$ et donc $x\in B$, ce qui contredit que $x\in C$ puisque $B$ et $C$ sont disjoints. Il est donc impossible que $\phi(x)=\phi(y)$ si $x\in C$ et $y\in B$. L'application $\phi$ est bien injective.
Soit $z\in F$. On doit trouver un antécédent de $z$ par $\phi$. On sépare deux cas. Soit $j(z)\in C$. Si on note $x=j(z)$, on sait que $\phi$ a été construit de sorte que $j(\phi(x))=x$ c'est-à-dire $j(\phi(x))=j(z)$. Par injectivité de $j$, ceci donne $z=\phi(x)$ et donc $z$ est bien dans l'image de $\phi$.
L'autre possibilité est que $j(z)\in B$. Alors $j(z)\in A_n$ pour un certain $n\in\mathbb N$. Si $n\geq 1$, on a donc $j(z)=j(i(x))$ pour un certain $x\in A_{n-1}$. Mais si $x\in A_{n-1}$, alors $x\in B$ et donc $i(x)=\phi(x)$. Ceci entraîne que $j(z)=j(\phi(x))$ et on conclut une fois encore par injectivité de $j$. Si $n=0$, alors $j(z)\in E\backslash j(F)$, ce qui est impossible! Donc, dans tous les cas, on a construit un antécédent de $z$ par $\phi$ ce qui prouve que $\phi$ est bijective.
On remarque d'abord que $j(F)=F$ et donc que $A_0=\{0,1\}$. Il vient $i(A_0)=\{4,5\}$ et $A_1=(j\circ i)(A_0)=\{4,5\}$. Par récurrence, on prouve facilement que $A_n=\{4n,4n+1\}$. Ainsi, $B$ est l'ensemble des entiers qui s'écrivent $4n$ ou $4n+1$, et $C$ l'ensemble des entiers qui s'écrivent $4n+2$ ou $4n+3$. Si $x\in C$, $x=j(x)$ et donc $\phi(x)=x$. Si $x\in B$, alors $\phi(x)=i(x)$. Autrement dit, l'application $\phi$ est définie par $$\left\{ \begin{array}{rcl} \phi(4n)&=&4n+4\\ \phi(4n+1)&=&4n+5\\ \phi(4n+2)&=&4n+2\\ \phi(4n+3)&=&4n+3 \end{array} \right. $$