]> gitweb.pimeys.fr Git - poly_gics_20-100.git/blob - Infinis et Dénombrabilité.tex
Première version gittée du poly.
[poly_gics_20-100.git] / Infinis et Dénombrabilité.tex
1 \documentclass[10pt, a4paper]{article}
2
3 \usepackage[latin1]{inputenc}
4 \usepackage[francais]{babel}
5 \usepackage{a4}
6 \usepackage{amsfonts, amssymb, amsmath, stmaryrd}
7 \usepackage{ae, aecompl}
8 \usepackage{color}
9 \usepackage{graphicx}
10 \usepackage{geometry}
11 \usepackage{fancyhdr}
12 \usepackage{eurosym}
13 \usepackage{lmodern}
14 \usepackage{mathrsfs}
15
16 \setlength{\headheight}{83pt} % Haut de page pour la première
17
18
19
20
21
22 \renewcommand{\headrulewidth}{0pt}
23 \renewcommand{\footrulewidth}{0.2pt}
24
25 \pagestyle{plain}
26
27 \title{Infinis et Dénombrabilité}
28 \date{}
29 \author{\textit{Groupe pour l'initiative et la culture scientifiques}}
30
31
32 \begin{document}
33 \maketitle
34 \thispagestyle{fancy}
35 \tableofcontents
36
37 \lhead{\includegraphics[scale=0.5]{big_gics.png}}
38 \rfoot{Vincent \textsc{Le Gallic}}
39
40 \newpage
41 \setlength{\headheight}{10pt} % Haut de page pour les suivantes
42 \setlength{\textheight}{700pt} % Hauteur de la zone de texte
43
44 \section{Notion d'infini : L'hôtel de Hilbert}
45 Dans notre histoire, nous allons considérer un hôtel avec un nombre infini de chambres, numérotées avec les entiers naturels 1,2,3,4,... Évidemment, il n'existe pas d'hôtel comme celui-ci, mais nous allons tout de même jouer un peu avec. Cet hôtel se vante donc partout de toujours pouvoir accueillir des clients, il n'affiche jamais complet !
46 Cependant, arrive un jour où débarquent les lapins des myriades, qui, comme chacun sait, sont une infinité à force de se multiplier. Heureusement, chacun trouve une chambre. Mais maintenant, toutes les chambres sont occupées ! Cependant, le directeur demande à ce qu'on n'affiche pas que l'hôtel est complet...
47
48 Arrive alors un voyageur qui demande une chambre. Le réceptionniste, affolé (toute la réputation de l'hôtel est en jeu), demande de l'aide au directeur. Celui-ci, malin, demande simplement à tous les lapins de se décaler d'une chambre. Celui qui occupait la chambre 1 va dans la 2, celui de la 2 dans la 3, et ainsi de suite. Aucun lapin ne se retrouve à coucher dehors, puisque pour tout entier $n$ dans $\mathbb{N}, n+1 \in \mathbb{N}.$ Il ne reste plus qu'à placer le nouvel arrivant dans la 1\up{ère} chambre. Le réceptionniste est rassuré, et il se dit qu'il pourra résoudre le problème de la même façon même si des centaines de nouveaux clients se présentent, il suffira de décaler tout le monde d'autant de chambres.
49
50 Le lendemain arrive un car dont on ne voit pas la fin sur la route. Le responsable de ce voyage organisé se présente au réceptionniste : « Nous sommes le 1\up{er} car des particules de l'univers, nous avions une réservation. »
51
52 Le réceptionniste, sûr de lui, demande \\
53 « - Très bien, combien êtes-vous ? \\
54 - Une infinité ! »
55
56 C'est la catastrophe ! Impossible de demander à tout le monde de se décaler d'une infinité de chambres, cela prendrait un temps infini ! Le directeur arrive de nouveau à la rescousse de son réceptionniste et lui donne la bonne solution : « Demandez à chaque occupant actuel de se déplacer dans la chambre qui porte le double du numéro de la leur. Le voyageur, qui est en chambre numéro 1 va dans la 2, le lapin de la 2, dans la 4, celui de la 3 dans la 6 et ainsi de suite... Ainsi, seules des chambres de numéro pair seront occupées, il vous restera donc l'infinité des chambres de numéro impair, ce sera suffisant pour loger les particules ! »
57
58 Bien entendu, la méthode proposée par le directeur marche toujours si plusieurs cars de particules arrivent. S'ils viennent à 9 cars, chacun se déplacera dans la chambre portant le numéro de celle qu'il occupait fois 10, et il restera toutes les chambres de numéros se terminant par 1,2,3,4,5,6,7,8 ou 9 pour loger du même coup les voyageuses des 9 cars.
59
60
61 \section{Soyons un peu plus rigoureux}
62 Toute cette histoire, malgré son côté un peu farfelu, est en fait rigoureuse d'un point de vue mathématique. Il s'agit en fait de montrer que certains ensembles sont \textbf{dénombrables}.
63
64 Qu'est-ce qu'un ensemble dénombrable ?
65
66 Pour cela, on a besoin de \textbf{l'ensemble des entiers naturels} $\mathbb{N}$ et de la notion de \textbf{bijection}.
67
68 \newpage
69
70 \begin{center}
71 \textsc{Définition} : Une application $f : X \rightarrow Y$ est \textbf{injective} lorsque $\forall x,y \in X, \quad x \neq y \Rightarrow f(x) \neq f(y)$.
72 \end{center}
73 Cela signifie que deux éléments différents ont des images différentes.
74
75 \begin{figure}[h]
76 \centering
77 \includegraphics[scale=0.6]{injection.png}
78 \caption{f n'est pas injective, g l'est.}
79 \end{figure}
80 Si on a une injection de $X$ dans $Y$, on a "moins" d'éléments dans $X$ que dans $Y$.
81
82 \begin{center}
83 \textsc{Définition} : Une application $f : X \rightarrow Y$ est \textbf{surjective} lorsque $\forall y\in Y, \exists x \in X$ tel que $f(x)=y$.
84 \end{center}
85
86 Cela signifie que tout élément dans l'ensemble d'arrivée a un antécédent dans l'ensemble de départ.
87
88 \begin{figure}[h]
89 \centering
90 \includegraphics[scale=0.6]{surjection.png}
91 \caption{f est surjective, g ne l'est pas.}
92 \end{figure}
93
94
95 \begin{center}
96 \textsc{Définition} : Une bijection est une application à la fois injective et surjective.
97 \end{center}
98
99 C'est-à-dire que chaque élément de $Y$ a un et un seul antécédent dans $X$.
100
101 \begin{figure}[!h]
102 \centering
103 \includegraphics[scale=0.65]{bijection.png}
104 \caption{h est une bijection.}
105 \end{figure}
106
107 On a en fait établit une correspondance exacte entre les éléments de A et ceux de B.
108 \medskip
109
110 \textbf{Exemples} :
111
112 Avec des ensembles finis :
113
114 Prenons les ensembles $A=\{1,2,3\}, B=\{10,27,342\}$ et $C = \{a,b\}$ et définissons les fonctions suivantes :
115 $$\begin{array}{ccccccccccc}
116 f :& C \rightarrow B & & g :& A \rightarrow C & & h_1 :& A \rightarrow B & & h_2 :& A \rightarrow B \\
117 & a \mapsto 10 & & & 1 \mapsto a & & & 1 \mapsto10 & & & 1 \mapsto 342 \\
118 & b \mapsto 27 & & & 2 \mapsto a & & & 2 \mapsto 27 & & & 2 \mapsto 10 \\
119 & & & & 3 \mapsto b & & & 3 \mapsto 10 & & & 3 \mapsto 27 \\
120 \end{array}$$
121 $f$ est injective, mais pas surjective car 342 n'a pas antécédent.\\
122 $g$ est surjective, mais pas injective car $g(1)=g(2)=a$.\\
123 $h_1$ n'est ni surjective (342 n'a pas d'antécédent) ni injective ($h_1(1)=h_1(3)$).\\
124 $h_2$ est injective et surjective, elle est bijective.
125
126 Avec des ensembles infinis :
127
128 $\begin{array}{cc}
129 f :& \mathbb{Z} \rightarrow \mathbb{Z} \\
130 & n \mapsto n+1
131 \end{array}$
132
133 $f$ est une bijection.
134
135 $\begin{array}{cc}
136 g :& \mathbb{R} \rightarrow \mathbb{R} \\
137 & x \mapsto x^2
138 \end{array}$
139
140 $g$ n'est pas une bijection, en effet, elle n'est pas surjective (-1 par exemple, n'a pas d'antécédent).
141
142 $\begin{array}{cc}
143 g_2 :& \mathbb{R} \rightarrow \mathbb{R}^+ \\
144 & x \mapsto x^2 \\
145 \end{array}$
146
147 $g_2$ est bien surjective, mais elle n'est pas injective $g_2(-1)=(-1)²=1=1²=g_2(1)$.
148
149 $\begin{array}{cc}
150 g_3 :& \mathbb{R}^+ \rightarrow \mathbb{R}^+ \\
151 & x \mapsto x^2 \\
152 \end{array}$
153
154 $g_3$ est bien une bijection.
155
156 \bigskip
157
158 On dit que deux ensembles $X$ et $Y$ sont \textbf{en bijection} si il existe une application bijective entre les deux. On note souvent $X\simeq Y$.
159
160 \textbf{Exemple} : $\mathbb{R}$ et $\mathbb{R}_+^*$ sont en bijection. (Grâce à $x\mapsto e^x$, qui est bijective)
161
162 \bigskip
163
164 On remarquera que cette notion est \textbf{transitive}. C'est-à-dire si $X\simeq Y$ et $Y\simeq Z$, alors $X\simeq Z$. (Il suffit de prendre la composée des deux bijections, qui est toujours une bijection.)
165
166 Cela se comporte bien aussi vis à vis du \textbf{produit cartésien} : si $A_1\simeq B_1$ et $A_2\simeq B_2$ alors $A_1\times A_2 \simeq B_1\times B_2$.
167
168 \bigskip
169
170 Il ne reste nous plus qu'à définir ce qu'est un ensemble dénombrable :
171
172 \begin{center}
173 \textsc{Définition} : Un ensemble est dénombrable si il existe une application bijective de $\mathbb{N}$ dans cet ensemble.
174 \end{center}
175
176 On a tout de suite évidemment que $\mathbb{N}$ est dénombrable. (l'identité est une bijection)
177
178 Mais $\mathbb{N}^*=\{n+1/n \in\mathbb{N}\}={1,2,3,4,\ldots}$ est aussi dénombrable.
179 En effet, avec l'application $n\mapsto n+1$ on a une bijection de $\mathbb{N}$ dans $\mathbb{N}^*$.
180
181 C'est exactement ce qu'a fait le directeur de l'hôtel à sa première intervention : il s'est aperçu que « une infinité de chambre » + 1 c'était toujours « une infinité de chambres ».
182
183 Maintenant si on écrit $2\mathbb{N}=\{2\times n/n \in \mathbb{N}\}$ l'ensemble des nombres pairs, on peut montrer qu'il est dénombrable. On prend l'application $n\mapsto n/2$ (elle est bien définie car nous n'avons que des nombres pairs).
184 On voit bien le rapport avec la 2ème intervention du directeur.
185
186 \section{Un plus gros infini... ou pas}
187 Mais que se passe-t-il si on considère $\mathbb{N}^2=\{ (n,m) / n \in\mathbb{N}, m\in\mathbb{N} \}$ (les couples d'entiers) ?
188
189 En effet, ce qu'on ne vous a pas dit, c'est que les particules de l'univers ne possèdent pas 1 ou 9 ou même 1000 cars (car le problème se résoudrait toujours de la même façon), mais une infinité. Il est facile de représenter ça dans en prenant $n$ le numéro du car et $m$ le numéro de la particule dans le car.
190
191 On sait bien qu'on ne peut pas décemment multiplier le numéro d'une chambre par l'infini, alors que se passera-t-il si tous les cars de particules arrivent à l'hôtel ?... Eh bien ils pourront les loger !
192
193 Comment ? Là, ça devient un petit peu plus compliqué.
194 \newpage
195 On cherche en fait $f:\mathbb{N}^2 \rightarrow \mathbb{N}$ qui soit bijective.
196 Parce qu'un beau dessin, vaut mieux qu'un long discours :
197
198 \begin{figure}[!h]
199 \centering
200 \includegraphics[scale=0.3]{bijection_N_N2.png}
201 \caption{Une bijection "visuelle" de $\mathbb{N}^2$ dans $\mathbb{N}$.}
202 \end{figure}
203 \bigskip
204 \bigskip
205 On pourrait aussi donner la belle formule qui y correspond ($f(p,q) = \frac{(p+q)(p+q+1)}{2}+q$) et essayer (laborieusement) de prouver que ça marche. Mais le dessin est suffisamment explicite, en effet, montrer qu'un ensemble est dénombrable, c'est en fait trouver un moyen de compter ses éléments dans l'ordre.
206
207 %\begin{center}
208 %\begin{tabular}{|c|c|c|c|c|c|}
209 % \hline
210 % n\ m & 0 & 1 & 2 & 3 & $\ldots$ \\ \hline
211 % 0 & 0 & 1 & 3 & 6 & $\swarrow$ \\ \hline
212 % 1 & 2 & 4 & 7 & $\swarrow$ & $\swarrow$ \\ \hline
213 % 2 & 5 & 8 & $\swarrow$ & $\swarrow$ & \\ \hline
214 % 3 & 9 & $\swarrow$ & $\swarrow$ & & \\ \hline
215 % \ldots & $\swarrow$ & $\swarrow$ & & & \\ \hline
216 %\end{tabular}
217 %\end{center}
218
219 Ainsi, quand on peut écrire tous les éléments d'un ensemble dans un ordre particulier (sans en oublier un seul), l'ensemble est dénombrable.
220
221 On notera qu'il est possible de le faire autrement. On peut remarquer que chaque entier s'écrit de manière unique sous la forme $n=2^p(2q+1)$. En effet, il suffit de diviser $n$ par 2 tant que le résultat est pair, on obtient la partie $2^q$ et il reste un facteur impair. Donc $f_2 : (p,q) \mapsto 2^p(2q+1)$ fournit une autre bijection de $\mathbb{N}^2$ dans $\mathbb{N}$.
222
223 \medskip
224
225 \textbf{Exemple} : $\mathbb{Z} \simeq \mathbb{N}$
226 \begin{center}
227 \begin{tabular}{cccc}
228 $f$ : & $\mathbb{Z}$ & $\rightarrow$ & $\mathbb{N}$ \\
229 & $n>0$ & $\mapsto$ & $2n+1$ \\
230 & $n\leq0$ & $\mapsto$ & $-2n$ \\
231 \end{tabular}
232 \end{center}
233
234
235
236 \textbf{Exemple} : $\mathbb{Z}^2 \simeq \mathbb{N}$
237 \begin{center}
238 $\begin{array}{|c|c|c|c|c|c|c|}
239 \hline
240 \downarrow & \leftarrow & \leftarrow & \leftarrow & \leftarrow & \leftarrow & \leftarrow \\ \hline
241 \downarrow & \downarrow & \leftarrow 15 & \leftarrow 14 & \leftarrow 13 & \leftarrow 12 & \uparrow \\ \hline
242 \downarrow & \downarrow & \downarrow 4 & \leftarrow 3 & \leftarrow 2 & 11 \uparrow & \uparrow \\ \hline
243 \downarrow & \downarrow & \downarrow 5 & 0 \rightarrow & 1 \uparrow & 10 \uparrow & \uparrow \\ \hline
244 \downarrow & \downarrow & 6 \rightarrow & 7 \rightarrow & 8 \rightarrow & 9 \uparrow & \uparrow \\ \hline
245 \downarrow & \rightarrow & \rightarrow & \rightarrow & \rightarrow & \rightarrow & \uparrow \\ \hline
246 \rightarrow & \rightarrow & \ldots & & & & \\ \hline
247 \end{array}$
248 \end{center}
249
250 \bigskip
251 \bigskip
252
253 Mais qu'en est-il des rationnels alors ?
254
255 En effet, les ensembles que nous avons vu jusqu'ici étaient discrets (il y a une distance minimale connue à l'avance entre deux éléments (deux éléments de $\mathbb{Z}^2$ sont toujours au moins distants de $1$)). Mais ce n'est plus le cas dans $\mathbb{Q}$. Comme on vient de le dire, on aimerait « compter les éléments dans un certain ordre ». Mais trouver le plus petit rationnel qui vient juste après 0, c'est difficile... Il n'y en a pas ! Dès qu'on en trouve un, on peut en effet le diviser par 2 pour en trouver un strictement plus petit (donc entre 0 et celui qu'on avait) et qui est toujours un rationnel. ($\forall r \in \mathbb{Q}_+^*, \frac{r}{2} \in \mathbb{Q}$ et $\frac{r}{2}<r$)
256
257 Et pourtant, on va y arriver quand même !
258
259 Pour cela, remarquons que $\mathbb{Q} = \{ \frac{p}{q} / p\in\mathbb{Z}, q\in\mathbb{N}^* \text{ et $p$ et $q$ premiers entre eux} \}$. On pose alors $f : \mathbb{Q} \rightarrow \mathbb{Z}\times\mathbb{N}^*, \quad r=\frac{p}{q} \mapsto (p,q)$
260
261 \newpage
262 Attention :
263 \begin{itemize}
264 \item $f$ est bien injective : $(p_1,q_1)=(p_2,q_2) \quad \Rightarrow \quad p_1=p_2 \land q_1=q_2\quad \Rightarrow \frac{p_1}{q_1}=\frac{p_2}{q_2}$
265 \item $f$ n'est \textbf{pas} surjective : En effet, $(2,4)$ ne sera jamais atteint car l'image du rationnel $\frac{2}{4}=\frac{1}{2}$ sera $(1,2)$. En fait tous les couples $(p,q) \in \mathbb{Z}\times\mathbb{N}^*$ tels que $p$ et $q$ ne sont pas premiers entre eux ne sont pas dans l'image de $f$.
266 \end{itemize}
267
268 L'ennui n'est pas seulement que $f$ n'est pas bijective, mais aussi qu'il est très difficile d'obtenir vraiment une bijection. On résout donc le problème autrement. En effet, prouver que deux ensembles sont en bijection peut se faire autrement qu'en trouvant une bijection entre les deux. Si on veut prouver que $E\simeq F$, il est suffisant de trouver $u:E\rightarrow F$ injective et $v:F\rightarrow E$ injective elle aussi. Cela est possible avec ni $u$ ni $v$ bijective, mais alors on sait qu'il existe une bijection de $E$ dans $F$. (On ne peut pas forcément l'écrire...).
269
270 Voici ce que ça signifie : $u$ est injective, donc il y a "moins" d'éléments dans $E$ que dans $F$, $v$ est injective donc il y a "moins" d'éléments dans $F$ que dans $E$, donc il y en a "autant" dans $E$ que dans $F$. (Attention quand même : nous parlons d'ensembles infinis, mais le résultat est cependant vrai.)
271
272 Ce résultat est connu sous le nom de Théorème de \textsc{Cantor-Bernstein} \footnote{Voir partie Compléments pour la démonstration.}.
273
274 Nous avons ici $f:\mathbb{Q} \rightarrow \mathbb{Z}\times\mathbb{N}^*$ injective.
275 Cherchons donc $g:\mathbb{Z}\times\mathbb{N}^* \rightarrow \mathbb{Q}$ injective aussi.\footnote{Notons que la recherche de $g$ est une simple formalité, sur les deux applications injectives, il arrive très souvent qu'une seule soit intéressante et que l'autre soit très facile.}
276
277 On peut poser $g:(p,q)\mapsto 2^p\times3^q$. (En n'oubliant pas que $2^{-n}=\frac{1}{2^n}$) $g$ est bien injective car si on suppose $2^{p_1}\times3^{q_1}=2^{p_2}\times3^{q_2}$, ça ne peut être vrai que si $p_1$ et $p_2$ sont de même signe. S'ils sont positifs, on applique l'unicité de la décomposition en facteurs premiers dans $\mathbb{N}$. S'ils sont négatifs, on a $\displaystyle \frac{3^{q_1}}{2^{-p_1}}=\frac{3^{q_2}}{2^{-p_2}}$ et comme $2$ et $3$ sont premiers entre eux, on a égalité des numérateurs et des dénominateurs. Dans les deux cas on conclut $(p_1,q_1)=(p_2,q_2)$.
278
279 $g$ n'est bien évidemment pas surjective, mais comme on a $f$ injective dans un sens, $g$ injective dans l'autre sens, le théorème de \textsc{Cantor-Bernstein} nous dit que $\mathbb{Q} \simeq \mathbb{Z} \times \mathbb{N}^*$.
280
281 De plus, on a vu que $\mathbb{Z} \simeq \mathbb{N}$ et que $\mathbb{N}^* \simeq \mathbb{N}$, en utilisant la règle sur le produit cartésien on a alors $\mathbb{Z} \times \mathbb{N}^* \simeq \mathbb{N}\times\mathbb{N} = \mathbb{N}^2$.
282 On a vu aussi que $\mathbb{N}^2 \simeq \mathbb{N}$ et on sait que $\simeq$ est transitive. Donc $\mathbb{Q}\simeq \mathbb{N}$, tous les nombres rationnels peuvent loger dans l'hôtel de Hilbert.
283
284
285 \section{Toutes les bonnes choses ont une fin}
286 C'est bien tout ça $\mathbb{N} \simeq \mathbb{N}^* \simeq 2\mathbb{N} \simeq \mathbb{Z} \simeq \mathbb{N}^2 \simeq \mathbb{Q}$.
287 Mais alors tous les ensemble, c'est \textit{grosso modo} la même chose que $\mathbb{N}$ ?
288
289 Eh bien non ! Pour $\mathbb{R}$, ça ne marche plus. Pour le voir, ça devient plus ardu.
290
291 Pour commencer, on ne va pas travailler avec $\mathbb{R}$ tout entier, c'est trop grand. On va prendre l'ensemble $]0,1[$, plus manipulable, mais qui pourtant contient "autant d'éléments" que $\mathbb{R}$, c'est-à-dire qu'il est en bijection avec lui. Pour prouver $]0,1[ \simeq \mathbb{R}$ on peut utiliser une fonction du genre de tangente en procédant ainsi :
292 \begin{itemize}
293 \item On sait que $x\mapsto \tan(x)$ donne une bijecton de $]-\frac{\pi}{2},\frac{\pi}{2}[$ dans $\mathbb{R}$.
294 \item $]-\frac{\pi}{2},\frac{\pi}{2}[$ n'est pas exactement $]0,1[$ mais on peut passer de l'un à l'autre avec une bijection très simple : $x \mapsto \frac{(x+\frac{\pi}{2})}{\pi}$ (C'est-à-dire une dilatation autour de 0 suivie d'une translation).
295 \item Si on veut la formule directement de $]0,1[$ dans $\mathbb{R}$ cela donne : $x \mapsto \tan(\pi x - \frac{\pi}{2})$
296 \end{itemize}
297
298 Ensuite, que fait-on de nos réels de $]0,1[$ ?
299 Si on prend un nombre réel, on peut l'écrire sous sa forme décimale (qui commencera par $0,\ldots$ puisqu'on est dans $]0,1[$).
300
301 Par exemple $\pi-3=0,1415926535897932384626\ldots$ L'écriture est bien entendue infinie, mais ce n'est pas gênant.
302 On écrira $d_i$ la $i$-ème décimale de $x$.
303 Ainsi, $\displaystyle x= \sum_{i=1}^{+\infty} \frac{d_i}{10^i} = 0,d_1d_2d_3d_4\ldots$ (C'est une somme infinie, mais c'est mathématiquement rigoureux).
304
305 On fera cependant attention à ce que la suite ne soit pas composée de seulement des $9$ à partir d'un certain rang. En effet, $0,9999999999\ldots$ est égal à $1$. En faisant attention à ce détail, on a \textbf{unicité} de cette écriture. \footnote{On notera qu'il ne s'agit de rien de plus que de l'écriture en base 10 qu'on utilise communément sans se poser de questions.}
306
307 \bigskip
308
309 Maintenant, il va falloir montrer que dans $]0,1[$, il y a "beaucoup" plus de monde que dans $\mathbb{N}$.
310 On va démontrer par l'absurde $\mathbb{R}$ que n'est pas dénombrable.
311 On commence donc par supposer qu'il l'est, c'est-à-dire qu'on possède une application bijective de $\mathbb{N}$ dans $\mathbb{R}$. Avec la remarque précédente, on sait qu'on peut obtenir facilement $f$ une application bijective de $\mathbb{N}$ dans $]0,1[$. Ce qu'on va montrer, c'est que, en fait, il n'est pas possible que $f$ soit surjective.
312
313 Notons alors $x_n=f(n)$ . On a une suite de réels, et on est sensés avoir tous ceux de $]0,1[$.
314 Écrivons-les comme précédemment avec leurs décimales.
315 $$ x_n = \sum_{i=1}^{+\infty} \frac{d_i^n}{10^i} = 0,d^{n}_{0}d^{n}_{1}d^{n}_{2}d^{n}_{3}d^{n}_{4}\ldots $$
316 c'est-à-dire que pour $d_i^j$, $j$ est le numéro du nombre, et $i$ le numéro de la décimale dans ce nombre.
317 On a alors :
318 \medskip
319 \begin{center}
320 $\begin{array}{c}
321 x_0 = 0,d^{0}_{0}d^{0}_{1}d^{0}_{2}d^{0}_{3}d^{0}_{4}\ldots \\
322 x_1 = 0,d^{1}_{0}d^{1}_{1}d^{1}_{2}d^{1}_{3}d^{1}_{4}\ldots \\
323 \vdots \\
324 x_n = 0,d^{n}_{0}d^{n}_{1}d^{n}_{2}d^{n}_{3}d^{n}_{4}\ldots
325 \end{array}$
326 \end{center}
327 \medskip
328 Maintenant, construisons le réel $y=0,e_{0}e_{1}e_{2}e_{3}e_{4}\ldots$ tel que : $\forall i, e_i \neq d^i_i$ on peut très bien le faire puisque $e_i$ peut être n'importe quel chiffre dans $\{1,2,3,4,5,6,7,8\}$ (on évite $9$ pour être certain de ne pas écrire une suite infinie de $9$ et $0$ pour ne pas avoir $y=0$) et $d^i_i$ n'est qu'un seul de ces chiffres.
329
330 Ensuite, on a $y\in]0,1[$. Or, on a supposé que $f$ était une bijection, donc a fortiori, elle est sensé être surjective. Donc il existe un $n_0$ tel que $y=f(n_0)$. Mais alors, c'est que $y=x_{n_0}$, et à ce moment-là, si on regarde la $n_0$-ième décimale, on voit que $e_{n_0}=d^{n_0}_{n_0}$. Il y a alors contradiction avec la définition des $e_i$. En effet, $y$ ne peut être nulle-part dans la liste des $x_i$ avec la façon dont on a définit les $e_i$.
331 C'est donc que l'application $f$ bijective n'existe pas.
332
333 On a bien prouvé que $\mathbb{R}$ n'est pas dénombrable. On se doute bien que si $\mathbb{R}\not\simeq\mathbb{N}$ c'est parce que $\mathbb{R}$ est "plus grand" que $\mathbb{N}$. On peut dire que "Card($\mathbb{N}$) < Card($\mathbb{R}$)" (sans perdre de vue qu'il s'agit de cardinaux infinis).
334
335 \section{Un peu plus...}
336 \subsection{$\mathbb{R}^2$}
337 Que penser de $\mathbb{R}^2$, c'est quand même l'infini fois l'infini, avec un "gros" infini, qui plus est.
338 Rappelons que bien que ce soit surprenant, on a montré $\mathbb{N}^2\simeq \mathbb{N}$. Pour $\mathbb{R}^2$, on a de même $\mathbb{R}^2\simeq \mathbb{R}$
339
340 Toujours en utilisant \textsc{Cantor-Bernstein}, bâclons d'abord la partie facile : l'injection de $\mathbb{R}$ dans $\mathbb{R}^2$.
341
342 $f:x\mapsto(x,x)$ fait très bien l'affaire. (Ou bien $g:x\mapsto(x,42)$)
343
344 La vraie question est dans l'autre sens.
345
346 On prend $(x,y) \in \mathbb{R}^2$ et on écrit $\displaystyle x = \sum_{i = 1}^{+\infty} \frac{d_i}{10^i}, \quad y = \sum_{j = 1}^{+\infty} \frac{e_j}{10^j}.$
347
348 On pose alors $h : (x,y) \mapsto z$, où z s'écrit $\displaystyle \sum_{k = 1}^{+\infty} \frac{f_k}{10^k}$: avec $f_{3k}=d_k, f_{3k+1}=e_k,f_{3k+2}=0$.
349
350 \bigskip
351 Avec un dessin :
352
353 $\begin{array}{cccccccccccccc}
354 x & = & 0, & d_0 & & d_1 & & d_2 & & d_3 & & d_4 & & \ldots \\
355 y & = & 0, & & e_0 & & e_1 & & e_2 & & e_3 & & e_4 & \ldots \\
356 y & = & 0, & d_0 & e_0 & d_1 & e_1 & d_2 & e_2 & d_3 & e_3 & d_4 & e_4 & \ldots \\
357 \end{array}$
358
359
360 Donc à partir de $(x,y)\in ]0,1[^2$ on peut former un $z\in]0,1[$ et évidemment, quand on a un nombre dans l'ensemble d'arrivée, on peut revenir au couple qui est son antécédent. On a donc $h$ injective (mais pas bijective car si on prend $0,909090909090\ldots$ il devrait avoir pour antécédent $(0,999999\ldots, 0)$ qui est un développement impropre).
361
362 Nous avons une injection dans chaque sens, on peut donc bien conclure $\mathbb{R}^2\simeq \mathbb{R}$.
363
364 \subsection{$\mathcal{P}(\mathbb{N})\simeq\mathbb{R}$}
365
366 $\mathcal{P}(\mathbb{N}) = \{ \emptyset, \{0\}, \{1\}, \ldots, \{0,1\}, \{0,2\}, \ldots , \{0,1,2,3,4,5,6,7,8,9,10\}, \ldots, \mathbb{N}^*, 2\mathbb{N},\ldots, \mathbb{N} \}$
367
368 L'ensemble des sous-ensembles de $\mathbb{N}$ est très riche, il contient beaucoup de monde. On va en fait pouvoir montrer qu'il y a "autant" d'éléments que dans $\mathbb{R}$. Ici, aucune des deux injections n'est triviale.
369
370 Pour faciliter la suite des opérations, nous allons utiliser une nouvelle notion : nous allons écrire les nombres, non plus en base 10 (décimale) comme on le fait toujours, mais en base 2 (binaire).
371
372 $83052_{\mathcal{D}}$ en base 10 représente le nombre $2\times1(=10^0)+5\times10+0\times10^2+3\times10^3+8\times10^4$. En base 2, on ne peut écrire qu'avec des 0 et des 1, et le nombre $11001_{\mathcal{B}}$ par exemple, représente $1\times2^0+0\times2^1+0\times2^2+0\times2^3+1\times2^4+1\times2^5=25_{\mathcal{D}}$.
373
374 Bien entendu, comme en base 10, on peut aussi représenter les nombres entre 0 et 1 : $0,1101_{\mathcal{B}}$ sera $1\times2^{-1}+1\times2^{-2}+0\times2^{-3}+1\times2^{-4}=0,8125_{\mathcal{D}}$.
375
376 En numérotant les décimales à partir de 0, on peut coder une partie de $\mathbb{N}$ en disant successivement si chaque entier naturel est dedans ou pas. En effet, si on veut coder la partir $X$, on écrit $x=0,b_0b_1b_2\ldots b_i\ldots$, alors $b_i=1 \Leftrightarrow i\in X$
377
378 \medskip
379
380 \textbf{Exemple} : $X \in \mathcal{P}(\mathbb{N}), X=\{1,2,5,\text{etc...} \}$
381
382 \medskip
383
384 $\begin{array}{cccccccc}
385 x= 0,& 0 & 1 & 1 & 0 & 0 & 1 & \text{etc...} \\
386 & 0 \notin X & 1 \in X & 2 \in X & 3 \notin X & 4 \notin X & 5 \in X & \\
387 \end{array}$
388
389 Attention cependant : on se souvient qu'une suite infinie de 9 posait problème car \\
390 $0,9999\ldots_{\mathcal{D}}~=~1$, donc $0,1111\ldots_{\mathcal{B}} = 1$, or ici on a besoin d'un éventuelle suite infinie de 1. Par exemple, $\mathbb{N}^*$ se coderait $0,0111111\ldots$ puisqu'il contient tous les entiers naturels sauf 0. Or $0,0111111\ldots=0,1$ qui est le codage de $\{0\}$. On s'aperçoit qu'on rencontre le même problème. Même problème, même solution, ajoutons des 0. Le vrai codage de la partie $X$ de l'exemple ci-dessus sera donc :
391
392 $\begin{array}{cccccccccccccc}
393 x= 0,& 0 &0& 1 &0& 1 &0& 0 &0& 0 &0& 1 &0& \text{etc...} \\
394 & 0 \notin X & & 1 \in X & & 2 \in X & & 3 \notin X & & 4 \notin X & & 5 \in X & & \\
395 \end{array}$
396
397 Ceci nous donne une injection de $\mathcal{P}(\mathbb{N})$ dans $]0,1[$ (donc dans $\mathbb{R}$).
398
399 Il ne reste plus qu'à en trouver une dans l'autre sens. Ce n'est pas si difficile que ça. L'application $x=0,b_0b_1b_2b_3\ldots \mapsto \{n / b_n = 1 \}$ est bien injective. (On notera qu'elle n'est pas surjective, toujours pour les mêmes raisons : les parties qui contiennent tous les entiers à partir d'un certain rang ne seront pas atteintes parce que leur antécédent aurait une écriture impropre.)
400
401
402 \subsection{$|\mathcal{P}(E)|>|E|$}
403 On sait que si $E$ est un ensemble fini, le cardinal de $\mathcal{P}(E)$ est $2^{|E|}$.
404 En effet, pour définir une partie de $E$, il faut choisir, pour chaque élément de $E$ si on le met ou pas. On a donc $2$ possibilités pour le premier, puis deux possibilités pour le suivant : $2\times2\times2\times\ldots\times2$ autant de fois qu'il y a d'éléments dans E. Donc $2^{|E|}$.
405
406 Comme on a montré $|\mathbb{N}|<|\mathcal{P}(\mathbb{N})|=|\mathbb{R}|$, on aimerait montrer dans le cas général $|E|<|\mathcal{P}(E)|$.
407
408 On va utiliser un argument de type que celui qu'on a utilisé pour $\mathbb{N}$, à savoir l'argument diagonal de Cantor.
409
410 Il est déjà certain que $|E|\leqslant|\mathcal{P}(E)|$ puisqu'on peut créer l'injection $x\mapsto\{x\}$.
411
412 Montrons qu'il n'y a pas d'application $E\rightarrow\mathcal{P}(E)$ surjective. On le montre par l'absurde en en prenant une, $f$, qu'on suppose l'être. On pose alors $A = \{x \in E / x \notin f(x) \}$ (par exemple si $f(1) = \{2,3\}, \quad 1\notin f(1)$). Alors $A\in\mathcal{P}(E)$ donc, comme $f$ est sensée être surjective, $\exists y\in E, A=f(y)$.
413
414 La question intéressante à se poser maintenant est $y\in f(y)$ ?
415 \begin{itemize}
416 \item Si $y\in f(y)=A=\{x \in E / x \notin f(x) \}$ alors $y\notin f(y)$.
417 \item Si $y\notin f(y)=A=\{x \in E / x \notin f(x) \}$ alors $y\in f(y)$.
418 \item Ça pose problème...
419 \end{itemize}
420
421 On a donc une contradiction, ce qui prouve que notre hypothèse était fausse, une telle fonction $f$ n'existe pas.
422
423 Donc $|E|<\mathcal{P}(E)|$.
424
425
426
427
428
429
430 \section{Compléments}
431 \subsection{Le Théorème de \textsc{Cantor-Bernstein}}
432
433 Rappelons les hypothèses : nous avons $f:E\rightarrow F$ injective et $g:F\rightarrow E$ injective également.
434
435 Lorsqu'un fonction est injective, on peut prendre sa réciproque seulement sur son ensemble image. En effet, par définition de $f(E)$, $f$ est toujours surjective sur $f(E)$. Donc comme ici $f$ est injective, elle est bijective de $E$ sur $f(E)$.
436 Alors pour $y\in f(E)\subset F$ on peut définir le premier antécédent de $y$, c'est $f^{-1}(y)$. De même, pour $x\in g(F) \subset E$, on peut définir le premier antécédent de $x$ par $g^{-1}(x)$.
437
438 Ainsi, si on prend $y\in f(E)$, on peut créer son premier antécédent $y_1$, mais si celui-ci est dans $g(F)$, on peut à nouveau en prendre son antécédent $y_2=g^{-1}(y_1)=g^{-1}(f^{-1}(y))$ et ainsi de suite jusqu'à ce qu'un $y_i$ ne soit plus ni dans $f(E)$ ni dans $g(F)$. On peut faire de même pour $x\in g(F)$. On appelle alors ancêtres d'un élément la suite de tous ses antécédents successifs.
439
440 On pose ensuite $E_p=\{ x \in E/ x \text{ a un nombre pair d'ancêtres (y compris 0)} \}$,\\ $E_i = \{x \in E/ x \text{ a un nombre impair d'ancêtres} \}$ , et $E_{\infty}=\{x \in E/ x\text{ a une infinités d'ancêtres} \}$. On crée de même $F_p, F_i$ et $F_{\infty}$.
441
442 Alors $E_p,E_i$ et $E_{\infty}$ forment une partition de $E$ et $F_p,F_i$ et $F_{\infty}$ forment une partition de $F$.
443
444 Nous avons alors que $f$ est une bijection de $E_p$ sur $F_i$. (Quand on prend l'image d'un élément, on augmente sa suite d'ancêtres de 1, donc de longueur paire, elle devient impaire). Plus exactement, on sait déjà que $f$ est injective. Si un élément est dans $F_i$, c'est que la longueur de sa suite d'ancêtres est au moins de 1, donc que cet élément est dans $f(E)$, donc $F_i\subset f(E)$, sur lequel $f$ est surjective.
445
446 On a également $g$ bijection de $F_p$ sur $E_i$ pour les mêmes raisons. Donc $g^{-1}$ (qui n'est pas définie partout rappelons-le, mais qui l'est sur $E_i\subset g(F)$) est une bijection de $E_i$ sur $F_p$. Du reste, on voit facilement que $f$ et $g$ établissent toutes les deux une bijection entre $E_{\infty}$ et $F_{\infty}$ (si l'élément a une infinité d'antécédents, son image également).
447
448 Voyons tout cela sur un dessin :
449 \begin{figure}[h]
450 \centering
451 \includegraphics[scale=0.6]{cantor_bernstein.png}
452 \end{figure}
453
454 On peut donc construire une bijection entre $E$ et $F$ :
455 $\begin{array}{cccc}
456 h : & E & \rightarrow & F \\
457 & x \in E_p & \mapsto & f(x) \in F_i \\
458 & x \in E_i & \mapsto & g^{-1}(x) \in F_p \\
459 & x \in E_{\infty} & \mapsto & f(x) \in F_{\infty} \\
460 \end{array}$\\
461 (on aurait aussi pu prendre $g^{-1}(x)$ pour le troisième cas).
462 Et ainsi $E\simeq F$.
463
464 \subsection{Vous n'imaginez pas tout ce qui est réel...}
465
466 On sait bien que $\sqrt{2},\sqrt{3}$ ne sont pas des rationnels. Cependant, on a un moyen pour les écrire. Simplement parce qu'il sont racine respectivement des polynômes $X^2-2$ et $X^2-3$. Les nombres de ce type sont appelés les nombres algébriques, c'est-à-dire les nombres réels qui sont racine d'un polynôme à coefficients entiers (dans $\mathbb{Z}$).
467 On note $\mathbb{Z}[X]=\{a_0+a_1X+a_2X^2+\ldots+a_nX^n / n\in \mathbb{N}, (a_0,\ldots,a_n)\in \mathbb{Z}^{n+1} \}$ l'ensemble des polynômes dont les coefficients sont des entiers relatifs. On remarque tout de suite que cet ensemble est simplement celui des suites finies à valeur dans $\mathbb{Z}$ (il suffit "d'enlever" les $X$ et les +).
468
469 On remarque que $\mathbb{Z} \subset \mathbb{Z}[X]$ (les polynômes de degré 0 = les constantes = les entiers relatifs). En fait on va voir qu'on a aussi "l'autre sens", à savoir que $\mathbb{Z}[X]$ est dénombrable. Pour commencer, comme on sait que $\mathbb{Z} \simeq \mathbb{N}$, on voit facilement que $\mathbb{Z}[X] \simeq \mathbb{N}[X] \simeq \mathbb{N}^{(\mathbb{N})}$, (où $\mathbb{N}^{(\mathbb{N})}$ est la notation pour l'ensemble des suites \textbf{finies} à valeurs dans $\mathbb{N}$). Il ne reste qu'à montrer que ces suites finies sont en bijection avec les entier naturels.
470
471 Toujours en utilisant le théorème de \textsc{Cantor-Bernstein} (fraîchement démontré), l'injection dans un sens étant triviale (on peut associer à chaque entier la suite finie constituée de lui-même), concentrons-nous sur l'autre.
472
473 Et pour cela posons $\mathscr{P}=\{p_0,p_1,p_2,\ldots\}=\{2,3,5,7,11,13,17,19,23,\ldots\}$ l'ensemble des nombres premiers.
474 Alors à une suite finie $(a_i)_{i\in\{0,\ldots,n\}}$ on associe $\displaystyle \prod_{i=0}^{n} p_i^{a_i}$. L'injectivité nous est donnée par l'unicité de la décomposition en produit de facteurs premiers dans $\mathbb{N}$.
475
476 On a alors montré $\mathbb{Z}[X] \simeq \mathbb{N}$. De plus, on sait que chaque polynôme a un nombre fini de racines (a priori on ne sait pas exactement combien, puisqu'on ne s'intéresse qu'à celles dans $\mathbb{R}$). On les numérote de $1$ à $n_P$ pour chaque polynôme $P$ (leur nombre dépend de $P$). Il suffit ensuite de "compter" les racines d'un polynôme avant de passer au "suivant". On sait à chaque fois qu'on finira de compter les racines d'un polynôme particulier puisqu'elles sont en nombre fini, et on sait quel est le polynôme suivant puisqu'on a une bijection de $\mathbb{Z}[X]$ dans $\mathbb{N}$.
477
478 On a donc montré $\mathbb{A}$lg$\simeq\mathbb{N}$, et c'est beaucoup plus profond que ça en a l'air. En effet, rappelez-vous, $|\mathbb{N}|<|\mathbb{R}|$, donc il y a à peu près "autant" de nombre algébriques que d'entiers naturels, alors qu'il y a beaucoup plus de nombre réels. Des nombres aussi affreux que $\displaystyle \frac{\sqrt[3]{\sqrt{52}-3}+19^{27}}{\sqrt[23]{11}-29}$ sont algébriques, mais il reste des immensités de réels qu'on ne peut en fait même pas écrire. Ces nombres sont appelés \textbf{transcendants}. $e$ et $\pi$ en sont des exemples, mais on vient de voir qu'il en existe une infinité non dénombrable.
479 \end{document}