Première version gittée du poly.

[poly_gics_20-100.git] / Infinis et Dénombrabilité.tex

\documentclass[10pt, a4paper]{article}

\usepackage[latin1]{inputenc}
\usepackage[francais]{babel}
\usepackage{a4}
\usepackage{amsfonts, amssymb, amsmath, stmaryrd}
\usepackage{ae, aecompl}
\usepackage{color}
\usepackage{graphicx}
\usepackage{geometry}
\usepackage{fancyhdr}
\usepackage{eurosym}
\usepackage{lmodern}
\usepackage{mathrsfs}

\setlength{\headheight}{83pt}   % Haut de page pour la première





\renewcommand{\headrulewidth}{0pt}
\renewcommand{\footrulewidth}{0.2pt}

\pagestyle{plain}

\title{Infinis et Dénombrabilité}
\date{}
\author{\textit{Groupe pour l'initiative et la culture scientifiques}}


\begin{document}
\maketitle
\thispagestyle{fancy}
\tableofcontents

\lhead{\includegraphics[scale=0.5]{big_gics.png}}
\rfoot{Vincent \textsc{Le Gallic}}

\newpage
\setlength{\headheight}{10pt}   % Haut de page pour les suivantes
\setlength{\textheight}{700pt}  % Hauteur de la zone de texte

\section{Notion d'infini : L'hôtel de Hilbert}
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 !
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...

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.

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. »

Le réceptionniste, sûr de lui, demande \\
«  - Très bien, combien êtes-vous ?  \\
 - Une infinité ! »

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 ! »

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.


\section{Soyons un peu plus rigoureux}
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}.

Qu'est-ce qu'un ensemble dénombrable ?

Pour cela, on a besoin de \textbf{l'ensemble des entiers naturels} $\mathbb{N}$ et de la notion de \textbf{bijection}.

\newpage

\begin{center}
 \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)$.
\end{center}
Cela signifie que deux éléments différents ont des images différentes.

\begin{figure}[h]
\centering
\includegraphics[scale=0.6]{injection.png}
\caption{f n'est pas injective, g l'est.}
\end{figure}
Si on a une injection de $X$ dans $Y$, on a "moins" d'éléments dans $X$ que dans $Y$.

\begin{center}
 \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$.
\end{center}

Cela signifie que tout élément dans l'ensemble d'arrivée a un antécédent dans l'ensemble de départ.

\begin{figure}[h]
\centering
\includegraphics[scale=0.6]{surjection.png}
\caption{f est surjective, g ne l'est pas.}
\end{figure}


\begin{center}
 \textsc{Définition} : Une bijection est une application à la fois injective et surjective.
\end{center}

C'est-à-dire que chaque élément de $Y$ a un et un seul antécédent dans $X$.

\begin{figure}[!h]
\centering
\includegraphics[scale=0.65]{bijection.png}
\caption{h est une bijection.}
\end{figure}

On a en fait établit une correspondance exacte entre les éléments de A et ceux de B.
\medskip

\textbf{Exemples} :

Avec des ensembles finis :

Prenons les ensembles $A=\{1,2,3\}, B=\{10,27,342\}$ et $C = \{a,b\}$ et définissons les fonctions suivantes :
$$\begin{array}{ccccccccccc}
        f :& C \rightarrow B    & & g :& A \rightarrow C & & h_1 :& A \rightarrow B & & h_2 :&  A \rightarrow B \\
     & a \mapsto 10     & &    & 1 \mapsto a     & &     & 1 \mapsto10     & &     &  1 \mapsto 342 \\
     & b \mapsto 27     & &    & 2 \mapsto a     & &     & 2 \mapsto 27    & &     &  2 \mapsto 10 \\
     &                  & &    & 3 \mapsto b     & &     & 3 \mapsto 10    & &     &  3 \mapsto 27 \\
\end{array}$$
$f$ est injective, mais pas surjective car 342 n'a pas antécédent.\\
$g$ est surjective, mais pas injective car $g(1)=g(2)=a$.\\
$h_1$ n'est ni surjective (342 n'a pas d'antécédent) ni injective ($h_1(1)=h_1(3)$).\\
$h_2$ est injective et surjective, elle est bijective.

Avec des ensembles infinis :

$\begin{array}{cc}
   f :& \mathbb{Z} \rightarrow \mathbb{Z} \\
      & n \mapsto n+1
\end{array}$

$f$ est une bijection.

$\begin{array}{cc}
   g :& \mathbb{R} \rightarrow \mathbb{R} \\
      & x \mapsto x^2
\end{array}$

$g$ n'est pas une bijection, en effet, elle n'est pas surjective (-1 par exemple, n'a pas d'antécédent).

$\begin{array}{cc}
   g_2 :& \mathbb{R} \rightarrow \mathbb{R}^+ \\
      & x \mapsto x^2 \\
\end{array}$

$g_2$ est bien surjective, mais elle n'est pas injective $g_2(-1)=(-1)²=1=1²=g_2(1)$.

$\begin{array}{cc}
   g_3 :& \mathbb{R}^+ \rightarrow \mathbb{R}^+ \\
      & x \mapsto x^2 \\
\end{array}$

$g_3$ est bien une bijection.

\bigskip

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$.

\textbf{Exemple} : $\mathbb{R}$ et $\mathbb{R}_+^*$ sont en bijection. (Grâce à $x\mapsto e^x$, qui est bijective)

\bigskip

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.)

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$.

\bigskip

Il ne reste nous plus qu'à définir ce qu'est un ensemble dénombrable :

\begin{center}
 \textsc{Définition} : Un ensemble est dénombrable si il existe une application bijective de $\mathbb{N}$ dans cet ensemble.
\end{center}

On a tout de suite évidemment que $\mathbb{N}$ est dénombrable. (l'identité est une bijection)

Mais $\mathbb{N}^*=\{n+1/n \in\mathbb{N}\}={1,2,3,4,\ldots}$ est aussi dénombrable.
En effet, avec l'application $n\mapsto n+1$ on a une bijection de $\mathbb{N}$ dans $\mathbb{N}^*$.

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 ».

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).
On voit bien le rapport avec la 2ème intervention du directeur.

\section{Un plus gros infini... ou pas}
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) ?

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.

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 !

Comment ? Là, ça devient un petit peu plus compliqué.
\newpage
On cherche en fait $f:\mathbb{N}^2 \rightarrow \mathbb{N}$ qui soit bijective.
Parce qu'un beau dessin, vaut mieux qu'un long discours :

\begin{figure}[!h]
\centering
\includegraphics[scale=0.3]{bijection_N_N2.png}
\caption{Une bijection "visuelle" de $\mathbb{N}^2$ dans $\mathbb{N}$.}
\end{figure}
\bigskip
\bigskip
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.

%\begin{center}
%\begin{tabular}{|c|c|c|c|c|c|}
%  \hline
%  n\ m & 0 & 1 & 2 & 3 &  $\ldots$ \\ \hline
%    0  & 0 & 1 & 3 & 6 & $\swarrow$ \\ \hline
%    1  & 2 & 4 & 7 & $\swarrow$ & $\swarrow$  \\ \hline
%    2  & 5 & 8 & $\swarrow$ & $\swarrow$ & \\ \hline
%    3  & 9 & $\swarrow$ &  $\swarrow$  & & \\ \hline
%  \ldots & $\swarrow$ & $\swarrow$   & & & \\ \hline
%\end{tabular}
%\end{center}

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.

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}$.

\medskip

\textbf{Exemple} : $\mathbb{Z} \simeq \mathbb{N}$
\begin{center}
\begin{tabular}{cccc}
  $f$ : & $\mathbb{Z}$ & $\rightarrow$ & $\mathbb{N}$ \\
        &    $n>0$     &   $\mapsto$   &   $2n+1$ \\
        &  $n\leq0$    &   $\mapsto$   &   $-2n$ \\
\end{tabular}
\end{center}

 
 
\textbf{Exemple} : $\mathbb{Z}^2 \simeq \mathbb{N}$
\begin{center}
$\begin{array}{|c|c|c|c|c|c|c|}
  \hline
  \downarrow & \leftarrow & \leftarrow    & \leftarrow    & \leftarrow    & \leftarrow    & \leftarrow \\ \hline
  \downarrow & \downarrow & \leftarrow 15 & \leftarrow 14 & \leftarrow 13 & \leftarrow 12 & \uparrow \\ \hline
  \downarrow & \downarrow & \downarrow  4 & \leftarrow  3 & \leftarrow  2 & 11 \uparrow   & \uparrow \\ \hline
  \downarrow & \downarrow & \downarrow  5 & 0 \rightarrow & 1 \uparrow    & 10 \uparrow   & \uparrow \\ \hline
  \downarrow & \downarrow & 6 \rightarrow & 7 \rightarrow & 8 \rightarrow &  9 \uparrow   & \uparrow \\ \hline
  \downarrow & \rightarrow & \rightarrow  &  \rightarrow  &  \rightarrow  &  \rightarrow  & \uparrow \\ \hline
  \rightarrow & \rightarrow & \ldots        &               &               &               &          \\ \hline
\end{array}$
\end{center}

\bigskip
\bigskip

Mais qu'en est-il des rationnels alors ?

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$)

Et pourtant, on va y arriver quand même !

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)$

\newpage
Attention :
\begin{itemize}
        \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}$
        \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$.
\end{itemize}

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...).

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.)

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.}.

Nous avons ici $f:\mathbb{Q} \rightarrow \mathbb{Z}\times\mathbb{N}^*$ injective.
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.}

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)$.

$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}^*$.

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$.
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.


\section{Toutes les bonnes choses ont une fin}
C'est bien tout ça $\mathbb{N} \simeq \mathbb{N}^* \simeq 2\mathbb{N} \simeq \mathbb{Z} \simeq \mathbb{N}^2 \simeq \mathbb{Q}$.
Mais alors tous les ensemble, c'est \textit{grosso modo} la même chose que $\mathbb{N}$ ?

Eh bien non ! Pour $\mathbb{R}$, ça ne marche plus. Pour le voir, ça devient plus ardu.

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 :
\begin{itemize}
        \item On sait que $x\mapsto \tan(x)$ donne une bijecton de $]-\frac{\pi}{2},\frac{\pi}{2}[$ dans $\mathbb{R}$.
        \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).
        \item Si on veut la formule directement de $]0,1[$ dans $\mathbb{R}$ cela donne : $x \mapsto \tan(\pi x - \frac{\pi}{2})$
\end{itemize}

Ensuite, que fait-on de nos réels de $]0,1[$ ?
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[$).

Par exemple $\pi-3=0,1415926535897932384626\ldots$ L'écriture est bien entendue infinie, mais ce n'est pas gênant.
On écrira $d_i$ la $i$-ème décimale de $x$.
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).

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.}

\bigskip

Maintenant, il va falloir montrer que dans $]0,1[$, il y a "beaucoup" plus de monde que dans $\mathbb{N}$.
On va démontrer par l'absurde $\mathbb{R}$ que n'est pas dénombrable.
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.

Notons alors $x_n=f(n)$ . On a une suite de réels, et on est sensés avoir tous ceux de $]0,1[$.
Écrivons-les comme précédemment avec leurs décimales.
$$ 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 $$
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.
On a alors :
\medskip
\begin{center}
$\begin{array}{c}
x_0 = 0,d^{0}_{0}d^{0}_{1}d^{0}_{2}d^{0}_{3}d^{0}_{4}\ldots \\
x_1 = 0,d^{1}_{0}d^{1}_{1}d^{1}_{2}d^{1}_{3}d^{1}_{4}\ldots \\
\vdots \\
x_n = 0,d^{n}_{0}d^{n}_{1}d^{n}_{2}d^{n}_{3}d^{n}_{4}\ldots 
\end{array}$
\end{center}
\medskip
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.

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$.
C'est donc que l'application $f$ bijective n'existe pas.

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).

\section{Un peu plus...}
\subsection{$\mathbb{R}^2$}
Que penser de $\mathbb{R}^2$, c'est quand même l'infini fois l'infini, avec un "gros" infini, qui plus est.
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}$

Toujours en utilisant \textsc{Cantor-Bernstein}, bâclons d'abord la partie facile : l'injection de $\mathbb{R}$ dans $\mathbb{R}^2$.

$f:x\mapsto(x,x)$ fait très bien l'affaire. (Ou bien $g:x\mapsto(x,42)$)

La vraie question est dans l'autre sens.

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}.$

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$.

\bigskip
Avec un dessin :

$\begin{array}{cccccccccccccc}
  x & = & 0, & d_0 &     & d_1 &     & d_2 &     & d_3 &     & d_4 &     & \ldots \\
  y & = & 0, &     & e_0 &     & e_1 &     & e_2 &     & e_3 &     & e_4 & \ldots \\
  y & = & 0, & d_0 & e_0 & d_1 & e_1 & d_2 & e_2 & d_3 & e_3 & d_4 & e_4 & \ldots \\
\end{array}$


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).

Nous avons une injection dans chaque sens, on peut donc bien conclure $\mathbb{R}^2\simeq \mathbb{R}$.

\subsection{$\mathcal{P}(\mathbb{N})\simeq\mathbb{R}$}

$\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} \}$

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.

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).

$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}}$.

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}}$.

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$

\medskip

\textbf{Exemple} : $X \in \mathcal{P}(\mathbb{N}), X=\{1,2,5,\text{etc...} \}$

\medskip

$\begin{array}{cccccccc}
  x= 0,&      0     &    1    &    1    &      0     &      0     &    1    & \text{etc...} \\
    & 0 \notin X & 1 \in X & 2 \in X & 3 \notin X & 4 \notin X & 5 \in X &        \\
\end{array}$

Attention cependant : on se souvient qu'une suite infinie de 9 posait problème car \\ 
$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 :

$\begin{array}{cccccccccccccc}
  x= 0,&      0     &0&    1    &0&    1    &0&      0     &0&      0     &0&    1    &0& \text{etc...} \\
    & 0 \notin X & & 1 \in X & & 2 \in X & & 3 \notin X & & 4 \notin X & & 5 \in X & &        \\
\end{array}$

Ceci nous donne une injection de $\mathcal{P}(\mathbb{N})$ dans $]0,1[$ (donc dans $\mathbb{R}$).

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.)


\subsection{$|\mathcal{P}(E)|>|E|$}
On sait que si $E$ est un ensemble fini, le cardinal de $\mathcal{P}(E)$ est $2^{|E|}$.
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|}$.

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)|$.

On va utiliser un argument de type que celui qu'on a utilisé pour $\mathbb{N}$, à savoir l'argument diagonal de Cantor.

Il est déjà certain que $|E|\leqslant|\mathcal{P}(E)|$ puisqu'on peut créer l'injection $x\mapsto\{x\}$.

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)$.

La question intéressante à se poser maintenant est $y\in f(y)$ ?
\begin{itemize}
  \item Si $y\in f(y)=A=\{x \in E / x \notin f(x) \}$ alors $y\notin f(y)$.
  \item Si $y\notin f(y)=A=\{x \in E / x \notin f(x) \}$ alors $y\in f(y)$.
  \item Ça pose problème...
\end{itemize}

On a donc une contradiction, ce qui prouve que notre hypothèse était fausse, une telle fonction $f$ n'existe pas.

Donc $|E|<\mathcal{P}(E)|$.






\section{Compléments}
\subsection{Le Théorème de \textsc{Cantor-Bernstein}}

Rappelons les hypothèses : nous avons $f:E\rightarrow F$ injective et $g:F\rightarrow E$ injective également.

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)$.
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)$.

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.

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}$.

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$.

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.

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).

Voyons tout cela sur un dessin :
\begin{figure}[h]
\centering
\includegraphics[scale=0.6]{cantor_bernstein.png}
\end{figure}

On peut donc construire une bijection entre $E$ et $F$ :
$\begin{array}{cccc}
  h : &        E         & \rightarrow &         F           \\
      &    x \in E_p     &   \mapsto   &    f(x) \in F_i     \\
      &    x \in E_i     &   \mapsto   &  g^{-1}(x) \in F_p  \\
      & x \in E_{\infty} &   \mapsto   & f(x) \in F_{\infty} \\
\end{array}$\\
(on aurait aussi pu prendre $g^{-1}(x)$ pour le troisième cas).
Et ainsi $E\simeq F$.

\subsection{Vous n'imaginez pas tout ce qui est réel...}

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}$).
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 +).

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.

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.

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.
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}$.

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}$.

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.
\end{document}