Le théorème de Cantor-Bernstein-Schröder

Etant donnés deux ensembles E et F, il peut être important de savoir s’ils sont de même « taille ». Evidemment, cette formulation est bien trop vague et il va falloir préciser ce qu’on entend par là …

Dans le cas où ces ensembles sont supposés finis, il s’agit simplement de savoir s’ils ont le même nombre d’éléments (le même cardinal). Mais pour des ensembles infinis, cette notion de nombre d’éléments est dénuée de sens : elle doit être remplacée par autre chose.

Le bon point de vue est la notion d’équipotence. Par définition, E et F sont dits équipotents s’il existe une bijection $u:E\to F$ .

Bien sûr, cette relation est symétrique puisque s’il existe une bijection $u$ dans un sens, alors sa réciproque $u^{-1}$ fera l’affaire en sens inverse.

Si vous souhaitez, avant d’aller plus loin, réviser les notions d’application, injection, surjection, bijection et bijection réciproque, je vous suggère de consulter cette vidéo puis cette vidéo (dans cet ordre), déjà un peu anciennes, mais qui reprennent ces notions à la base.

Quatre petites questions, pour voir si vous suivez …

Les deux premières sont assez faciles, les deux suivantes sont moins immédiates :

Les ensembles $\mathbb{N}$ et $\mathbb{N}^\star$ sont-ils équipotents ?
Les ensembles $]0,1[$ et $\mathbb{R}$ sont-ils équipotents ?
Les ensembles $\mathbb{N}$ et $\mathbb{Z}$ sont-ils équipotents ?
Les ensembles $\mathbb{N}$ et $\mathcal{P}(\mathbb{N})$ sont-ils équipotents ?

Lorsque les ensembles E et F sont finis, le fait qu’ils soient équipotents équivaut à l’égalité de leurs cardinaux. Cette notion exprime donc de manière précise l’idée que deux ensembles – finis ou non – sont « de même taille ».

Le théorème de Cantor-Bernstein-Schröder (théorème CBS en abrégé) constitue un outil puissant pour montrer que deux ensembles E et F sont équipotents. Il stipule qu’il suffit d’établir l’existence d’une injection de E vers F et d’une injection de F vers E.

L’idée sous-jacente est naturelle : dans le cas où E et F sont finis, il suffit de voir que $\text{card}(E)\leqslant\text{card}(F)$ et que $\text{card}(F)\leqslant\text{card}(E)$ pour conclure que $\text{card}(E)=\text{card}(F)$ et donc que E et F sont équipotents. Or justement, pour des ensembles $E$ et $F$ supposés finis, la condition $\text{card}(E)\leqslant\text{card}(F)$ équivaut à l’existence d’une injection de $E$ vers $F$ .

➣ En 1887, G. Cantor (1845-1918) énonce ce théorème sans toutefois le démontrer.

➣ Presque simultanément, R. Dedekind (1831-1916) le démontre mais ne publie pas sa preuve (il en publiera une, dix ans plus tard environ).

➣ En 1897, F. Bernstein (alors âgé de 19 ans …) produit une démonstration à l’occasion d’un séminaire dirigé par Cantor.

➣ La même année, E. Schröder (1841-1902) publie, indépendamment, sa propre démonstration (qui se révèlera incorrecte… ce qui conduit certains à parler plutôt du « théorème de Cantor-Bernstein »).

Quant à la preuve que nous allons voir (section 3), elle s’appuie sur un résultat (voir section 2) publié bien après l’intuition initiale de Cantor.

Commençons par une simple observation…

1 – Accouplement de deux bijections

Considérons deux ensembles $A,B$ disjoints, deux ensembles $A',B'$ disjoints et supposons l’existence d’une bijection $f:A\to A'$ et d’une bijection $g:B\to B'$ .

Il est alors facile de construire une bijection $A\cup B\to A'\cup B'$ , en posant :

$\boxed{h:A\cup B\to A'\cup B',\,x\mapsto\left\{\begin{array}{cc}f(x) & \text{si }x\in A\\g(x) & \text{si }x\in B\\\end{array}\right.}$

Pour justifier le caractère bijectif de $h$ , le plus simple est de considérer l’application :

$k:A'\cup B'\to A\cup B,\,y\mapsto\left\{\begin{array}{cc}f^{-1}(y) & \text{si }y\in A'\\g^{-1}(y) & \text{si }y\in B'\\\end{array}\right.$

et de constater que :

$\begin{equation*}\begin{split}k\circ h & = \text{id}_{A\cup B}\\h\circ k & = \text{id}_{A'\cup B'}\\\end{split}\end{equation*}$

La première égalité montre notamment que $h$ est injective, et la seconde que $h$ est surjective.

2 – Une histoire de point fixe

Rappelons pour commencer qu’étant donnés un ensemble $E$ et une application $\varphi:E\to E$ , on appelle point fixe de $\varphi$ tout élément $x\in E$ vérifiant $\varphi(x)=x$ .

La proposition suivante est un cas particulier d’un résultat connu sous le nom de théorème de Knaster-Tarski. Elle va jouer un rôle-clef dans la preuve que nous verrons du théorème de CBS. Historiquement, ce résultat est apparu en 1928 sous la plume de B. Knaster (1893-1980), mais sous une forme restreinte, puis généralisé en 1955 par A. Tarski (1901-1983).

Proposition

Soit $E$ un ensemble et soit $f:\mathcal{P}(E)\to\mathcal{P}(E)$ une application croissante au sens de l’inclusion, c’est-à-dire vérifiant :

$\forall(A,B)\in\mathcal{P}(E)^2,\,A\subset B\Rightarrow f(A)\subset f(B)$

Alors $f$ possède au moins un point fixe.

Cliquer pour voir / masquer la preuve

Notons $\mathcal{F}$ l’ensemble des parties de $E$ qui contiennent leur image :

$\mathcal{F}=\left\{X\subset E;\,f(X)\subset X\right\}$

Comme $E\in\mathcal{F}$ , on voit déjà que $\mathcal{F}\neq\emptyset$ . Considérons alors :

$Y=\bigcap_{X\in\mathcal{F}}X$

et montrons, par double-inclusion, que $f(Y)=Y$ .

Si $X\in\mathcal{F}$ , alors $Y\subset X$ , car l’intersection d’une famille $(S_i)_{i\in I}$ d’ensembles est contenue dans $S_i$ pour tout $i$ .

Par croissance de $f$ , il en résulte que $f(Y)\subset f(X)$ et donc (vu que $f(X)\subset X$ et par transitivité de l’inclusion) : $f(Y)\subset X.$ Comme cette dernière inclusion vaut pour tout $X\in\mathcal{F}$ , il s’ensuit que $f(Y)\subset Y$ .

On a déjà établi une première inclusion. Comme $f$ est croissante, on en déduit que $f(f(Y))\subset f(Y)$ , ce qui signifie exactement que $f(Y)\in\mathcal{F}$ , et ceci entraîne que $Y\subset f(Y)$ .
Il est maintenant prouvé que $Y$ est un point fixe de $f$ .

Remarque – on aurait pu conclure tout aussi bien en considérant plutôt :

$\mathcal{G}=\left\{X\subset E;\,X\subset f(X)\}\right.$

ainsi que :

$Z=\bigcup_{X\in\mathcal{G}}X$

Le détail de cette preuve alternative (mais très similaire) est laissé au lecteur 🙂

3 – Le théorème de Cantor-Bernstein-Schröder

Comme annoncé dans l’introduction, il s’agit du résultat suivant :

Théorème CBS

Soient $E$ , $F$ des ensembles.

On suppose qu’il existe une injection $\alpha:E\to F$ et une injection $\beta:F\to E$ .

Dans ces conditions, $E$ et $F$ sont équipotents.

Cliquer pour voir / masquer la preuve

Pour lire ce qui suit, vous aurez notamment besoin d’être à l’aise avec les notions d’image directe et d’image réciproque. A toutes fins utiles, je vous signale cet article, qui expose ces notions fondamentales en partant de zéro.

Commençons par observer qu’étant donnée une application $\varphi:U\to V$ , l’application

$\mathcal{P}(U)\to\mathcal{P}(V),\,X\mapsto\varphi\left<X\right>$

est croissante pour l’inclusion (propriété $\heartsuit$ ) et l’application

$\mathcal{P}(U)\to\mathcal{P}(U),\,X\mapsto U-X$

est décroissante pour l’inclusion (propriété $\heartsuit\heartsuit$ ).

Considérons alors l’application :

$\boxed{\begin{array}{cccc}c\,: & \mathcal{P}(E) & \to & \mathcal{P}(E)\\& A & \mapsto & E-\beta\left<F-\alpha\left<A\right>\right>\end{array}}$

On constate (grâce aux propriétés $\heartsuit$ et $\heartsuit\heartsuit$ ) que $c$ est croissante pour l’inclusion et possède donc (d’après la proposition de la section 2) un point fixe $Y$ . On a donc :

$Y=E-\beta\left<F-\alpha\left<Y\right>\right>$

c’est-à-dire :

$E-Y=\beta\left<F-\alpha\left<Y\right>\right>\qquad\left(\star\right)$

On dispose alors de la bijection

$\begin{array}{cccc}\overline{\alpha}\,: & Y & \to & \alpha\left<Y\right>\\& x & \mapsto & \alpha(x)\end{array}$

et de la bijection

$\begin{array}{cccc}\overline{\beta}\,: & E-Y & \to & F-\alpha\left<Y\right>\\& x & \mapsto & \beta^{-1}(x)\end{array}$

La notation $\beta^{-1}(x)$ est valable (bien que $\beta$ ne soit pas supposée bijective) puisque, d’après $(\star)$ , tout élément de $E-Y$ possède un antécédent par $\beta$ (antécédent unique, en raison de l’injectivité de $\beta$ ).

Il ne reste alors plus qu’à accoupler $\overline{\alpha}$ et $\overline{\beta}$ , comme expliqué à la section 1, pour obtenir une bijection de $E$ vers $F$ .

Corollaire

Il est clair que si $A$ , $B$ et $C$ sont trois ensembles finis tels que $A\subset B\subset C$ et si de plus $\text{card}(A)=\text{card}(C)$ , alors $A=B=C$ .

Que reste-t-il de cette affirmation en remplaçant finis par infinis et l’hypothèse d’égalité des cardinaux par celle d’équipotence de $A$ et $C$ ?

Sous ces hypothèses modifiées, la conclusion ne persiste pas (contre-exemple : $4\mathbb{N}\subset2\mathbb{N}\subset\mathbb{N}$ et l’application $\mathbb{N}\to4\mathbb{N},n\mapsto4n$ est bijective, mais les deux inclusions sont strictes !) mais on peut tout de même dire que $A$ , $B$ et $C$ sont équipotents.

En effet, l’inclusion $A\subset B$ montre l’existence d’une injection $A\to B$ . Il existe, de même, une injection $B\to C$ et donc (vu que $C$ et $A$ sont équipotents par hypothèse) un injection $B\to A$ . On termine en invoquant le théorème CBS.

Le corollaire ci-dessus déclenche, à son tour, une nouvelle question. On sait que $\mathbb{N}$ et $\mathbb{R}$ ne sont pas équipotents (résultat célèbre dû à Cantor). Que peut-on alors dire d’une partie $X$ de $\mathbb{R}$ contenant $\mathbb{N}$ ? Est-elle nécessairement équipotente soit à $\mathbb{N}$ , soit à $\mathbb{R}$ ?

La réponse est tout à fait extraordinaire : cette question est indécidable dans le cadre de l’axiomatique de Zermelo-Fraenkel. Ceci signifie que les « règles du jeu » que constituent les axiomes de la théorie usuelle des ensembles ne suffisent pas pour se prononcer. C’est une sorte de vide juridique, que l’on peut combler en rajoutant un axiome supplémentaire ! Pour en savoir plus, on pourra regarder ici.

Passons maintenant à quelques exemples d’utilisation du théorème CBS.

4 – L’ensemble $\mathbb{Q}$ des rationnels est dénombrable

Rappelons qu’un ensemble est dit dénombrable lorsqu’il est équipotent à $\mathbb{N}$ .

Attention !

Cette terminologie n’est pas respectée par certains auteurs, pour lesquels « dénombrable » signifie : fini ou équipotent à $\mathbb{N}$ .

Il nous suffit de construire une injection de $\mathbb{Q}$ dans $\mathbb{N}$ . Lorsque ce sera fait, il restera à :

remarquer qu’il existe évidemment une injection en sens inverse (puisque $\mathbb{N}\subset\mathbb{Q}$ ),
appliquer le théorème CBS.

On sait que tout nombre rationnel $r$ peut s’écrire, de manière unique sous la forme :

$r=\frac pq\qquad\text{avec }(p,q)\in\mathbb{Z}\times\mathbb{N}^\star\text{ et }p,q\text{ premiers entre eux}$

Notons $(N(r),D(r))$ cet unique couple et considérons l’application :

$\boxed{\begin{array}{ccccccc}f\,: & \mathbb{Q} & \to & \mathbb{N}, & r & \mapsto & \left\{\begin{array}{cc}2^{N(r)}\,3^{D(r)} & \text{si }N(r)\geqslant0\\2^{N(r)}\,3^{D(r)}\,5 & \text{sinon}\end{array}\right.\end{array}}$

$f$ est injective, en raison de l’unicité de la décomposition en facteurs premiers d’un entier naturel plus grand que 1, ce qui prouve le résultat annoncé.

Cette démonstration repose sur une astuce arithmétique, que l’on retrouve sous une forme similaire dans une preuve courte de la dénombrabilité de $\mathbb{N}^2$ . Les détails sont accessibles en dépliant le paragraphe ci-dessous.

Une preuve courte de la dénombrabilité de $\mathbb{N}^2$ (cliquer pour déplier / replier)

L’application $\omega:\mathbb{N}^2\to\mathbb{N}^\star,(p,q)\mapsto 2^p(2q+1)$ est bijective. En effet :

Soient $(p,q)$ et $(r,s)$ deux couples d’entiers naturels tels que $2^p(2q+1)=2^r(2s+1).$ En supposant $p<r$ , on aurait $2q+1=2^{r-p}(2s+1)$ , ce qui est absurde puisque le membre de gauche de cette égalité est impair, tandis que son membre de droite est pair. Pour la même raison, l’hypothèse $p>r$ ne tient pas et donc $p=r$ . Il s’ensuit que $q=s$ et finalement que $(p,q)=(r,s)$ . Ceci montre que $\omega$ est injective.
D’évidence : $1=\omega(0,0)$ . Et si $a\in\mathbb{N}-\{0,1\},$ alors on voit en décomposant $a$ en produit de facteurs premiers qu’il existe $(p,q)\in\mathbb{N}^2$ tel que $a=\omega(p,q)$ (il suffit de regrouper les facteurs premiers impairs).

Ainsi, $\mathbb{N}^2$ et $\mathbb{N}^\star$ sont équipotents. Comme $\mathbb{N}^\star$ et $\mathbb{N}$ sont équipotents (évident : considérer la bijection $\mathbb{N}^\star\to\mathbb{N},\,n\mapsto n-1$ ), il s’ensuit que $\mathbb{N}^2$ et $\mathbb{N}$ sont équipotents.

Noter qu’il existe d’autres façons d’établir ce résultat. Le dessin ci-dessous doit pouvoir vous inspirer (solution en annexe) :

5 – Equipotence de $\mathbb{R}$ et $\{0,1\}^\mathbb{N}$

Utilisons le théorème CBS et commençons par montrer l’existence d’une injection de $\mathbb{R}$ dans $\{0,1\}^\mathbb{N}$ .

Pour cela, donnons-nous une énumération $(r_n)_{n\in\mathbb{N}}$ de $\mathbb{Q}$ (c’est-à-dire une suite injective dont l’ensemble des termes est $\mathbb{Q}$ ).

Pour tout entier naturel $n$ et tout réel $x$ , posons :

$f_n(x)=\left\{\begin{array}{cc}0 & \text{si }x\leqslant r_n\\1 & \text{sinon}\end{array}\right.$

L’application $\varphi\,:\,\mathbb{R}\to\{0,1\}^\mathbb{N},\,x\mapsto(f_n(x))_{n\in\mathbb{N}}$ est injective.

En effet, si $x,y$ sont deux réels distincts, disons par exemple $x<y$ , alors (comme $\mathbb{Q}$ est une partie dense de $\mathbb{R}$ ), il existe $a\in\mathbb{Q}$ tel que $x<a<y$ . Par conséquent, si l’on note $p$ l’unique entier naturel tel que $a=r_p$ :

$f_p(x)=0\qquad\text{tandis que}\qquad f_p(y)=1$

et donc $\varphi(x)\neq\varphi(y)$ .

Il nous reste à prouver l’existence d’une injection de $\{0,1\}^\mathbb{N}$ dans $\mathbb{R}$ .

On peut penser au développement dyadique d’un réel. Associons donc, à toute suite $(b_n)_{n\in\mathbb{N}}$ à termes dans $\{0,1\}$ , le réel :

$\delta(b)=\sum_{n=0}^\infty\frac{b_n}{2^n}$

mais il y a un petit souci … car cette application $\delta$ n’est pas injective ! En effet, il existe des éléments de $[0,1]$ admettant deux écritures de ce type (autrement dit, des réels qui possède par $\delta$ deux antécédents distincts dans $\{0,1\}^\mathbb{N}$ ); par exemple :

$\frac12=\sum_{n=2}^\infty\frac{1}{2^n}$

ou, si vous préférez :

$\frac01+\frac12+\frac04+\frac08+\frac0{16}+\cdots=\frac01+\frac02+\frac14+\frac18+\frac1{16}+\cdots$

ce qui revient encore à dire que les suites $(0,1,0,0,0,\cdots)$ et $(0,0,1,1,1,\cdots)$ ont la même image par $\delta$ .

C’est d’ailleurs tout le problème de l’écriture dyadique d’un nombre réel. On définit d’ailleurs ce qu’on appelle le développement dyadique propre, où l’on interdit précisément aux chiffres binaires de valoir tous 1 à partir d’un certain rang.

Mais il y a un remède assez simple pour rétablir l’injectivité 🙂

Il suffit de considérer plutôt l’application :

$\begin{array}{cccc}\psi\,: & \{0,1\}^\mathbb{N} & \to & \mathbb{R}\\\\& b & \mapsto & \displaystyle{\sum_{n=0}^\infty\frac{b_n}{3^n}}\end{array}$

En gros, le succès de cette idée (remplacement de 2 par 3) résulte du fait que la seule façon de ne pas avoir unicité avec ce type d’écriture serait de permettre aux chiffres $b_n$ de valoir tous 2 à partir d’un certain rang … Mais ceci ne peut pas se produire, et pour cause : il n’y a aucun chiffre 2 mais seulement des 0 et des 1.

Mais soyons précis et montrons rigoureusement l’injectivité de $\psi.$ Soient donc deux suites distinctes $b$ et $c$ à termes dans $\{0,1\}$ . Notons :

$q=\min\{n\in\mathbb{N};\,b_n\neq c_n\}$

de sorte que :

$\forall n\in\llbracket0,q-1\rrbracket,\,b_n=c_n\qquad\text{et}\qquad \vert b_q-c_q\vert=1$

Quitte à intervertir $b$ et $c$ , on peut même supposer que $b_q=1$ et $c_q=0$ .

On observe alors que :

$\begin{equation*}\begin{split}\psi(b)-\psi(c) & = \sum_{n=q}^\infty\frac{b_n-c_n}{3^n}\\& = \frac{1}{3^q}+\sum_{n=q+1}^\infty\frac{b_n-c_n}{3^n}\end{split}\end{equation*}$

et donc :

$\begin{equation*}\begin{split}\vert\psi(b)-\psi(c)-\frac{1}{3^q}\vert & = \left\vert\sum_{n=q+1}^\infty\frac{b_n-c_n}{3^n}\right\vert\\& \leqslant \sum_{n=q+1}^\infty\frac{1}{3^n}\\& = \frac{1}{3^{q+1}}\,\frac{1}{1-\frac13}\\& = \frac{1}{2\times3^q}\\& < \frac{1}{3^q}\end{split}\end{equation*}$

ce qui entraîne que $\psi(b)\neq\psi(c)$ et l’injectivité de $\psi$ est établie.

6 – Equipotence de $\mathbb{R}^\mathbb{R}$ et $\mathcal{P}(\mathbb{R})$

Par commodité, on indiquera l’équipotence de deux ensembles $A$ et $B$ par la notation $A\simeq B$ .

Rappelons qu’étant donnés deux ensembles $A$ et $B$ , on désigne par $B^A$ l’ensemble des applications de $A$ dans $B$ et par $\mathcal{P}(A)$ l’ensemble des parties de $A$ .

Nous allons démontrer le résultat général suivant :

Théorème

Si $A$ est un ensemble infini tel que $A\simeq A^2$ , alors $A^A\simeq\mathcal{P}(A)$ .

Pour cela, nous aurons besoin du :

Lemme

Si $A$ est un ensemble infini tel que $A\simeq A^2$ , alors $\mathcal{P}(A)\simeq \mathcal{P}(A)^2$ .

Remarque

Ce lemme n’est plus valable si $A$ est supposé fini.

En effet, si $A=\left\{a\right\}$ , alors $A^2=\left\{\left(a,a\right)\right\}$ donc $A\simeq A^2$ .

Pourtant

$\mathcal{P}(A)=\left\{\emptyset,\left\{a\right\}\right\}\qquad\text{ et }\qquad\mathcal{P}(A)^2=\left\{\left(\emptyset,\emptyset\right),\left(\emptyset,\left\{a\right\}\right),\left(\left\{a\right\} ,\emptyset\right),\left(\left\{a\right\} ,\left\{a\right\}\right)\right\}$

ne sont pas équipotents (ensembles finis de cardinaux distincts).

Signalons, avant de démontrer ce lemme, puis ce théorème, qu’il y a quelque chose de redondant dans l’énoncé de chacun d’eux, à savoir l’hypothèse $A\simeq A^2$ . On peut en effet prouver que cette condition est vérifiée par tout ensemble infini (cela exige l’usage de l’axiome du choix). Mais nous n’allons pas détailler ce point et nous contenter de ces énoncés.

Preuve du lemme (cliquer pour déplier / replier)

D’une manière générale, et pour tout ensemble $E$ , l’application $E\to E^{2},e\mapsto\left(e,e\right)$ est injective. En particulier, il existe une injection de $\mathcal{P}(A)$ dans $\mathcal{P}(A)^{2}$ .

Montrons l’existence d’une injection en sens inverse.

Comme $\mathcal{P}(A)$ est infini (puisque $A$ est infini et que $A\to\mathcal{P}(A),\,a\mapsto\left\{a\right\}$ est injective), alors $\mathcal{P}(A)\simeq\mathcal{P}(A)-\left\{\emptyset\right\}$ . Il en résulte que $\mathcal{P}(A)^2\simeq\left(\mathcal{P}(A)-\left\{\emptyset\right\}\right)^2$ . Il suffit donc d’établir l’existence d’une injection $\left(\mathcal{P}(A)-\left\{\emptyset\right\} \right)^2\to\mathcal{P}(A)$ . Or, par hypothèse, il existe une injection $\varphi\,:\,A^2\to A$ . Considérons l’application :

$\Phi:\left(\mathcal{P}(A)-\left\{\emptyset\right\}\right)^{2}\to\mathcal{P}(A),\,\left(X,Y\right)\mapsto\varphi\left\langle X\times Y\right\rangle$

et montrons que $\Phi$ est injective.

Soient $\left(X,Y\right)$ et $\left(X',Y'\right)$ deux couples de parties non vides de $A$ , tels que $\varphi\left\langle X\times Y\right\rangle =\varphi\left\langle X'\times Y'\right\rangle$ . Soient $x\in X$ et $y\in Y$ ; alors $\varphi\left(x,y\right)\in\varphi\left\langle X'\times Y'\right\rangle$ , donc il existe $\left(x',y'\right)\in X'\times Y'$ tel que $\varphi\left(x,y\right)=\varphi\left(x',y'\right)$ . Vue l’injectivité de $\varphi$ , ceci impose $\left(x,y\right)=\left(x',y'\right)$ , d’où en particulier $x\in X'$ et $y\in Y'$ . On a montré que $X\subset X'$ et $Y\subset Y'$ . Pour des raisons évidentes de symétrie, ces inclusions sont en fait des égalités.

On a établi l’existence d’une injection de $\mathcal{P}(A)$ dans $\mathcal{P}(A)^2$ et d’une injection de $\mathcal{P}(A)^2$ dans $\mathcal{P}(A)$ . Il reste à invoquer le théorème CBS pour conclure.

Preuve du théorème (cliquer pour déplier / replier)

Notons 0 et 1 deux éléments distincts de A. L’application :

$\mathcal{P}(A)\to A^{A},\,X\mapsto\left[A\to A,\,a\mapsto1\text{ si }a\in X\text{ et }0\text{ sinon}\right]$

est injective.

Par ailleurs, si l’on note $\Gamma_f$ le graphe de $f\in A^A$ , alors l’application

$A^A\to\mathcal{P}\left(A^{2}\right),\,f\mapsto\Gamma_{f}$

est injective.

Or $\mathcal{P}\left(A^{2}\right)\simeq\mathcal{P}\left(A\right)$ (il est en effet facile de voir que si $E\simeq F$ , alors $\mathcal{P}(E)\simeq\mathcal{P}(F)$ ), donc il existe une injection $A^A\to\mathcal{P}(A)$ .

A nouveau, le théorème CBS donne la conclusion.

Comme l’indique le titre de cette section, nous souhaitons prouver que $\mathbb{R}^{\mathbb{R}}$ et $\mathcal{P}\left(\mathbb{R}\right)$ sont équipotents. D’après le théorème ci-dessus, il suffit d’expliquer pourquoi $\mathbb{R}$ et $\mathbb{R}^2$ sont équipotents. Proposons deux points de vue :

1er point de vue

Nous savons, d’une part, que $\mathcal{P}(\mathbb{N})\simeq\{0,1\}^\mathbb{N}$ (puisque $\mathcal{P}(E)\simeq\{0,1\}^E$ pour n’importe quel ensemble $E$ ) et, d’autre part, que $\{0,1\}^\mathbb{N}\simeq\mathbb{R}$ (cf. section 5). Il s’ensuit que $\mathcal{P}(\mathbb{N})\simeq\mathbb{R}$ .

Par ailleurs, en appliquant le lemme à $A=\mathbb{N}$ , on voit que $\mathcal{P}(\mathbb{N})\simeq\mathcal{P}(\mathbb{N})^2$ . Ainsi : $\mathbb{R}\simeq\mathbb{R}^2$ .

2ème point de vue

Comme $\mathbb{R}$ s’injecte trivialement dans $\mathbb{R}^2$ , il nous suffit de construire une injection de $\mathbb{R}^2$ dans $\mathbb{R}$ , pour conclure avec le théorème CBS. Et comme $\mathbb{R}\simeq\left]0,1\right[$ , une injection de $\left]0,1\right[^2$ dans $\mathbb{R}$ fera l’affaire.

A chaque réel $x\in]0,1[$ , on peut associer son développement décimal propre, qui est une suite $(x_i)_{i\geqslant1}$ à termes dans $\llbracket0,9\rrbracket$ , dont les termes ne valent pas tous 9 à partir d’un certain rang. Etant donné $(x,y)\in]0,1[^2$ , posons :

$M(x,y)=\sum_{i=1}^\infty\frac{x_i}{10^{2i-1}}+\sum_{i=1}^\infty\frac{y_i}{10^{2i}}$

c’est-à-dire :

$M(x,y)=0,x_1y_1x_2y_2\cdots$

Grâce à l’unicité du développement décimal propre d’un réel, on voit que $M:\left]0,\right1[^2\to\mathbb{R}$ est injective.

Annexe : une preuve géométrique de la dénombrabilité de $\mathbb{N}^2$

Le dessin doit suggérer qu’on énumère les couples d’entiers naturels par diagonales successives :

sur la première diagonale, il n’y a que $(0,0)$ ,
sur la seconde, on trouve $(1,0)$ puis $(0,1)$ ,
sur la troisième, on trouve successivement $(2,0)$ , $(1,1)$ puis $(0,2)$ ,
etc …

Sur chaque « diagonale », les couples partagent une propriété commune : la somme des coordonnées est fixe. Par conséquent, le couple générique $(p,q)$ appartient à la diagonale qui commence par $(p+q,0)$ .

Et ce point $(p+q,0)$ est précédè par $(0,p+q-1)$ , qui termine la diagonale précédente.

Les points $(0,0)$ , $(1,0)$ , $(1,1)$ , $(2,0)$ , … portent les numéros d’ordre 0, 1, 2, 3 …

Quel est, dans ces conditions, le numéro d’ordre de $(p,q)$ ?

Il n’est pas difficile de voir que les diagonales successives comportent un nombre croissant de couples : un couple pour la première, deux pour la suivante, puis trois etc …

Si l’on prend en compte toutes les diagonales depuis la toute première jusqu’à la diagonale précédent celle qui porte le couple $(p,q)$ , on totalise un nombre de couples égal à :

$1+2+3+\cdots+(p+q)=\frac{(p+q)(p+q+1)}{2}$

Il reste à ajouter les couples $(p+q,0)$ , …, $(p,q)$ , qui sont au nombre de $q+1$ . Finalement, nous avons deviné la formule qui donne le numéro d’ordre du couple générique $(p,q)$ et qui, par là-même, nous donne explicitement une bijection de $\mathbb{N}^2$ vers $\mathbb{N}$ :

$\begin{array}{cccc}F\,: & \mathbb{N}^2 & \to & \mathbb{N}\\& (p,q) & \mapsto & \frac{(p+q)(p+q+1)}{2}+q\end{array}$

Il reste à vérifier proprement que cette application $F$ est effectivement une bijection (et, cerise sur le gateau, à expliciter sa bijection réciproque), mais cela, je vous le laisse en exercice 🙂

Vos questions ou remarques sont les bienvenues. Vous pouvez laisser un commentaire ci-dessous ou bien passer par le formulaire de contact.

Partager cet article