\Annee{2002}
\Titre{Parties d'un ensemble et proc\'ed\'e diagonal}
\Auteur{Vincent \textsc{Guirardel}}

\Date{2002/12/04} % Format AAAA/MM/JJ. pour le 5 mars 2001: \Date{2001/03/05}

\Niveau{\DEUGi} %Le niveau principal. Typiquement: \DEUGi (=1ere annee), \DEUGii (=2eme annee), \Licence, ...

\NiveauxSecondaires{} %Eventuellement, les niveaux secondaires separes par des virgules 

\AnglePedagogique{\Langage} %l'angle pedagogique principal. Typiquement: \AQuoiCaSert, \Experimental, ...

\AnglesSecondaires{} %Eventuellement, les angles pedagogiques secondaires separes par des virgules

\Theme{\Ensembles} %Theme principal. Typiquement: \AlgLin, \Suites, \Series, ...

\ThemesSecondaires{} %Eventuellement, les themes secondaires separes par des virgules

\Objectif{L'exercice commence par introduire le codage des parties d'un
ensemble par leur fonction caract\'eristique, 
puis leur montre le proc\'ed\'e diagonal de Cantor.
L'exercice fait manipuler aux \'etudiants les notions de bijections, injections, applications, compl\'ementaire.

C'est volontairement qu'on parle d'ensemble quelconque (sans preciser que cela signifie fini ou infini),
et c'est la derniere question qui doit leur faire realiser que la construction marche aussi pour un ensemble infini.
On peut alors les faire r\'efl\'echir sur l'existence d'infinis plus grand que d'autres...
} % Partie objectifs et commentaires.


\begin{exo}

\qst{Codage des parties d'un ensemble fini}

Dans tout l'exercice, on notera $B = \{0,1\}$ (\emph{ensemble
des "bits"}). 

Soit $E = \{a_{1},\ldots,a_{n}\}$ un ensemble \`a $n$ \'el\'ements
($n \geq 1$). \`A toute partie $A$ de $E$, on associe son
\emph{application caract\'eristique}:
$$
\chi_{A} \;:\;
\begin{cases}
E \rightarrow B \\
x \mapsto 
\begin{cases} 
1 \text{~si~} x \in A \\ 0 \text{~si~} x \not\in A 
\end{cases}
\end{cases}
$$
On peut coder l'application $\chi_{A}$ par un \emph{vecteur de bits}
("bit vector") $V_{A} = (\epsilon_{1},\ldots,\epsilon_{n})$, o\`u
$\epsilon_{i} = \chi_{A}(a_{i})$. Autrement dit, le $i$-\`eme bit
$\epsilon_{i}$ est mis \`a $1$ si $a_{i}$ est \'el\'ement de $A$,
sinon, il est mis \`a $0$
\footnote{C'est la m\'ethode utilis\'ee dans le langage \textsc{Pascal} (par exemple)
pour coder le type de donn\'ees \emph{ensemble}.}. 

\sq On prend ici $n = 3$ et $E = \{1,2,3\}$. Enum\'erer toutes les
parties de $E$. Pour chacune, expliciter son application 
caract\'eristique ainsi que le vecteur de bits associ\'e. 
On pr\'esentera les r\'esultats sous forme de tableau. 

\sq \ssq On se replace dans le cas g\'en\'eral ($n$ quelconque). 
Montrer que l'application de $\mathcal{P}(E)$ dans 
$\mathcal{F}(E,B)$ qui \`a une partie $A$ de $E$ associe
sa fonction caract\'eristique $\chi_{A}$ est bijective. 
Pour cela, on explicitera son application r\'eciproque. 

\ssq Montrer de m\^eme que l'application $\mathcal{P}(E)$ dans 
$B^{n}$  qui \`a une partie $A$ de $E$ associe son vecteur
de bits $V_{A}$ est bijective. 

La bijectivit'e de cette application a-t-elle un int\'er\^et, en termes du codage mentionn\'e au dessus ?

\ssq En d\'eduire le cardinal de $\mathcal{P}(E)$. 

\sq \ssq On note $\overline{0} = 1$ et $\overline{1} = 0$ 
(\emph{bit compl\'ementaire}); autrement dit,
$\forall \epsilon \in B \;,\; \overline{\epsilon} = 1 - \epsilon$.
Pour tout vecteur de bits 
$V =  (\epsilon_{1},\ldots,\epsilon_{n}) \in B^{n}$,
on note 
$\overline{V} = (\overline{\epsilon_{1}},\ldots,\overline{\epsilon_{n}})$. 
A quelle partie de $E$ correspond le vecteur de bits $\overline{V_{A}}$ ? 

\ssq D\'ecrire de m\^eme le vecteur de bits associ\'e \`a $A \cup A'$,
\`a $A \cap A'$.


\qst{Le proc\'ed\'e diagonal de Cantor}

\sq Montrer que pour tout entier naturel $n$, 
$2^{n} > n$. En d\'eduire que, pour tout ensemble fini $E$, il
n'existe aucune application surjective de $E$ sur $\mathcal{P}(E)$. 

\sq On prend maintenant $E = \{1,\ldots,n\}$. On consid\`ere
$n$ parties de $E$, not\'ees $A_{1},\ldots,A_{n}$. Pour tout
$i \in \{1,\ldots,n\}$, on note 
$V_{A_{i}} = (\epsilon_{i,1},\ldots,\epsilon_{i,n})$ 
le vecteur de bits associ\'e. Puis, pour tout $i \in \{1,\ldots,n\}$, 
on note $\epsilon'_{i} = \overline{\epsilon_{i,i}}$.
On note enfin $V' = (\epsilon'_{1},\ldots,\epsilon'_{n})$
et $A'$ l'unique partie de $E$ dont le vecteur de bits associ\'e
est $V'$. 

\ssq Donner un exemple de ces constructions, sous forme de tableau,
lorsque $n = 10$. 

\ssq En g\'en\'eral, montrer que $A'$ n'est \'egal \`a aucune des
parties $A_{i}$. On raisonnera par l'absurde: si l'on avait
$A' = A_{i}$ pour un certain $i \in \{1,\ldots,n\}$, quelle serait
la valeur du $i$-\`eme bit du vecteur associ\'e \`a cette partie ? 

\ssq Retrouver ainsi le r\'esultat de la question a. Indication : si
$f$ est une application de $E$ dans $\mathcal{P}(E)$, on note 
$A_{1} = f(1),\ldots,A_{n} = f(n)$; on constate alors que la partie
$A'$ construite ci-dessus n'appartient pas \`a l'ensemble image de $f$. 

\ssq V\'erifier que $A' = \{i \in E \;/\; i \not\in A_{i}\}$. 

\sq On s'inspire ici de la question b pour d\'emontrer le th\'eor\`eme 
suivant: $E$ \'etant un ensemble \emph{quelconque}, il n'existe aucune 
application surjective de $E$ sur $\mathcal{P}(E)$. Supposons donc que
$f$ est une application de $E$ dans $\mathcal{P}(E)$. Posons:
$$
A' = \{x \in E \;/\; x \not\in f(x)\}.
$$

\ssq V\'erifier que cette d\'efinition a bien un sens. 

\ssq Montrer qu'il n'existe aucun \'el\'ement $x$ de $E$ tel que 
$A' = f(x)$. On raisonnera par l'absurde: si l'on avait $A' = f(x)$,
aurait-on $x \in A'$ ou $x \not\in A'$ ? 

\ssq Conclure. 

\ssq Pourquoi, dans l'\'enonc\'e du th\'eor\`eme, a-t-on pr\'ecis\'e
que l'ensemble $E$ \'etait "quelconque" ?



\end{exo}

%%% Local Variables: 
%%% mode: latex
%%% TeX-master: t
%%% End: 
