02_Concepts.tex

% Concepts
% =========

\chapter{Concepts}
\label{ch:concepts}

\section{Ensembles, langages, relations et fonctions}
\label{sec:ensembles_langages_relations_et_fonctions}

\subsection{Ensembles}
\label{subsec:ensembles}
\begin{mydef}
    Un \emph{ensemble} est une collection d'objets formels, sans répétition,
    appelés les éléments de l'ensemble.
\end{mydef}
\begin{mydef}\label{def:cardinal}
    On appelle le \textbf{cardinal} d'un ensemble le nombre d'élément contenu dans cet ensemble, et le note $|A|$.
\end{mydef}

\noindent Un ensemble peut être de plusieurs type, il peut être ...
\begin{enumerate}
    \item \textbf{Vide} : par définition, l'ensemble vide est noté $\emptyset$.
    \item \textbf{Fini} : c'est à dire qu'il contient un nombre fini d'éléments. Par exemple : $\{1,2,3,4,5,6\}$ ou $\{0,1\}$
    \item \textbf{Infini dénombrable} : c'est à dire qu'il contient un nombre infini d'éléments mais qu'il existe une manière de les compter (voir section \ref{sec:ensemble_num_rables} sur les Ensembles Enumérables). Par exemple : $ \mathbb{N} = \{1,2,3,4,...\}$ ou $ \mathbb{Z} = \{1,-1,2,-2,...\}$
    \item \textbf{Infini non-dénombrable} : c'est à dire qu'il contient un nombre infini d'élements et qu'il n'existe pas de manière de les compter. Par exemple : $\mathbb{R}$ ou $\mathbb{C}$ (qui n'est en fait qu'un cas particulier de $\mathbb{R}^2$ dans lequel les opérateurs sont un peu différents)
\end{enumerate}
\begin{myrem}
  Les points 3 et 4 seront abordés plus en détails dans les sections suivantes, ils ne sont donc que brièvement illustrés ici.
\end{myrem}

\subsubsection{Opérations sur les ensembles}
Maintenant que nous avons définis ce qu'était un ensemble, il est nécéssaire de définir les opérations qui s'appliquent sur ceux-ci. 
\begin{mydef}
    \textbf{L'union} de deux ensembles $A$ et $B$, notée $A \cup B$ est une opération entre 2 ensembles initiaux dont le résultat est un nouvel ensemble dans lequel tous les éléments appartiennent soit à $A$ soit à $B$. Formellement, cet opérateur peut être décrit comme ceci :
    $$ \text{Soient A et B deux ensembles :} A \cup B = C \text{ est tel que } \forall c \in C, c \in A \textbf{ ou } c\in B  $$ ou encore, autrement écris :
    $$ A \cup B = \{ c | c \in A \textbf{ ou } c \in B \} $$
\end{mydef}
\begin{mydef}
    \textbf{L'intersection} de deux ensembles $A$ et $B$, notée $A \cap B$ est une opération entre 2 ensembles initiaux dont le résultat est un nouvel ensemble dans lequel tous les éléments appartiennent à $A$ et à $B$. Formellement, cet opérateur peut être décrit comme ceci :
    $$ \text{Soient A et B deux ensembles :} A \cap B = C \text{ est tel que } \forall c \in C, c \in A \textbf{ et } c\in B  $$ ou encore, autrement écris :
    $$ A \cap B = \{ c | c \in A \textbf{ et } c \in B \} $$ 
\end{mydef}
\begin{myrem}
  Les définitions d'union et d'intersection nous amène également à la définition du \textbf{complémentaire} d'un ensemble. \\
  Soient $A,B$ deux ensembles tel que $A \subset B$, la complémentaire de $A$, noté $\stcomp{\mathrm{A}}$ est l'ensemble des éléments de $B$ qui ne sont pas compris dans $A$, c'est à dire :
  $$ A \cup \stcomp{\mathrm{A}} = B$$
\end{myrem}
\begin{mydef}\label{def:produit_cartésien}
    \textbf{Le produit cartésien} entre deux ensembles $A$ et $B$, noté $A \times B$ est une opération dont le résultat est l'ensemble des paires $(a,b)$ tel que $a\in A$ et $b \in B$, soit :
    $$ \text{Soient A et B deux ensembles :} A \times B = \{(a,b)|a\in A , b\in B\} $$
\end{mydef}
\begin{myrem}
  Le produit cartésien peut par exemple avoir des applications dans le domaine des probabilités, et surtout dans le cas des épreuves répétées. Imaginons un dés à 6 faces, lorsque je lance ce dés, l'univers de possibilités est $\Omega = \{1,2,3,4,5,6\}$, par contre, lorsque je jette 2 dés, l'univers des possibilités devient :
  \begin{center}
      \begin{tabular}{lllllll}
        $\Omega$ &       1 &       2 &       3 &       4 &       5 &       6 \\
        1 &  (1, 1) &  (1, 2) &  (1, 3) &  (1, 4) &  (1, 5) &  (1, 6) \\
        2 &  (2, 1) &  (2, 2) &  (2, 3) &  (2, 4) &  (2, 5) &  (2, 6) \\
        3 &  (3, 1) &  (3, 2) &  (3, 3) &  (3, 4) &  (3, 5) &  (3, 6) \\
        4 &  (4, 1) &  (4, 2) &  (4, 3) &  (4, 4) &  (4, 5) &  (4, 6) \\
        5 &  (5, 1) &  (5, 2) &  (5, 3) &  (5, 4) &  (5, 5) &  (5, 6) \\
        6 &  (6, 1) &  (6, 2) &  (6, 3) &  (6, 4) &  (6, 5) &  (6, 6) \\
      \end{tabular}
  \end{center}
\end{myrem}

Lorsque l'on effectue le produit cartésien d'un ensemble avec lui même, ceci peut être noté $A \times A = A^2$, ce qui paraît logique si l'on en suit la notation multiplicative. Le produit cartésien peut être généralisé à plus de deux ensembles.
\begin{mydef}\label{def:produit_cartésien_généralisé}
    On peut généraliser le produit cartésien à plus de deux ensembles, le résultat ne sera alors plus l'ensemble des doublets, mais l'ensemble des triplets si l'on effectue le produit cartésien de 3 ensembles, des quadruplets si l'on effectue le produit cartésien de 4 ensembles, etc.
    Cela peut être noté assez lourdement comme ceci :
    $$ \Pi_{i=1}^n A_i = \{(a_1, a_2, ..., a_n)| a_j \in A_j \forall j \in \{1,2,...,n\}\} $$
    On parle également de puissance nième d'un ensemble lorsque l'on effectue n produits cartésiens de cet ensemble avec lui-même, et on le note $A^n$.
\end{mydef}
Cette définition peut sembler lourde voire inutilisable, mais il existe en fait plein de cas où elle devient utile. Elle est extrêmement utile en probabilité et combinatoire, mais elle peut également servir à exprimer des ensembles de manière compacte. Ainsi la notation $ \{0,1\}^n$ peut être utilisée pour désigner \textbf{l'ensemble} de tous les chiffres binaires des longueur $n$.
\begin{myprop}
  On peut appliquer la définition \ref{def:cardinal} au produit cartésien, mais également au produit cartésien généralisé. Ce qui donne lieu à cette propriété :
  $$ \text{Soient deux ensembles A et B :} |A\times B| = |A| \cdot |B| $$
  Qui peut également être appliquée dans le ce cas-ci : $|A^n| = |A|^n$
\end{myprop}
Cette propriété peut être utilisée pour facilement déterminer la taille de l'ensemble des possibilités d'un phénomène.
\begin{myexem}
  Par exemple, si l'on souhaite savoir combien de programmes différents de 200 caractères il serait possible d'écrire\footnote{Ce qui est très peu probable j'en conviens.}. Il suffit de déterminer $A$ et $n$, ici on connaît déjà $n$ qui est donné et vaut 200. Et on peut définir $A$ comme l'ensemble des caractères de la table ASCII, soit 256 possibilités. De là on peut déterminer que $|A|^n = 256^{200}$. On aurait également pu déconstruire ce problème jusqu'à sa forme la plus fondamentale. En effet on sait que la table ASCII est basée sur un encodage à 8 bits, soit $A = \{0,1\}^8$ et on aurait alors eu :
  $$ |A|^{200} = |\{0,1\}^8|^{200} = |\{0,1\}|^{8^{200}} = 2^{1600}$$
\end{myexem}
\begin{mydef}
    L'ensemble des sous-ensembles d'un ensemble $A$ est dénoté par $\mathcal{P}(A)$ ou $2^A$.
    Par exemple, si $A = \{2,4\} \rightarrow \mathcal{P}(A) = \{ \emptyset, \{2\}, \{4\}, \{2,4\} \} $
\end{mydef}

% subsubsection ensembles (end)

\subsection{Langages}
\label{subsec:Langages}

\begin{mydef}
    Une \textbf{chaîne de caractères} ou un \textbf{mot} est une séquence \textbf{\underline{finie}} de \emph{symboles} (ou \emph{caractères}). Par exemple :
    	\begin{itemize}
    		\item $abceced$ ;
    		\item $010101101$ ;
     		\item \ding{168}\ding{169}\ding{170}\ding{171}\ding{40}\ding{109}\ding{112}
    	\end{itemize}

    Les symboles peuvent être représentés par n'importe quel glyphe, cela n'a pas d'importance.\\
    La chaine de caractère vide est conventionnellement représentée par $\epsilon$
\end{mydef}
\begin{mydef}
    Un \emph{alphabet} $\Sigma$ est un ensemble fini de symboles. Par exemple :
    \begin{itemize}
        \item $\Sigma = \{1, 2\}$
        \item $\Sigma = \{a, b, c\}$
        \item $\Sigma = \{\ding{189},\ding{129},a,9\}$
    \end{itemize}
\end{mydef}
\begin{myrem}
    Un mot défini sur un alphabet est une séquence finie d'éléments de cet alphabet.
\end{myrem}
\begin{mydef}
    Un \textbf{langage} est un ensemble de mots constitués de symboles d'un alphabet donné. Par exemple, l'ensemble des palindromes définis sur $\{a, b\}$ est : $\{\epsilon, a, b, aa, aaa, aba, babaabab, aababbbabaa, ...\}$
\end{mydef}
\begin{myrem}
  Par convention, on note l'ensemble de tous les mots possibles sur l'alphabet $\Sigma$ :\; $\Sigma^*$
  Par exemple :
  \begin{itemize}
		\item $\Sigma = \phi,\quad \Sigma^* = \{\epsilon\}$
		\item $\Sigma = \{a\},\quad \Sigma^* = \{\epsilon, a,aa,aaa,aaaa, \ldots\}$
		\item $\Sigma = \{0,1\},\quad \Sigma^* = \{\epsilon, 0,1,00,01,10,11,000,001,010,011, \ldots\}$
  \end{itemize}
\end{myrem}

% subsubsection Langages (end)

\subsection{Relations} \label{subsec:relations}
\begin{mydef}
    Soient $A$, $B$ des ensembles, une \textbf{relation} $R$ allant de $A$ vers $B$ est un sous-ensemble de $A \times B$. C'est-à-dire un ensemble de paires $\la a,b \ra$ avec $a\in A$, $b\in B$.
\end{mydef}

\begin{myrem}
  Une relation, comme une fonction (voir section \ref{subsec:fonctions}) est définie par sa table, c'est à dire quelque chose définissant entièrement son comportement. Si un couple $(a,b)$ est un élément de la relation, on note  $\la a,b \ra \in R$ ou $aR b$ ou encore $R(a,b)$.
\end{myrem}


% subsubsection relations (end)

\subsection{Fonctions}
\label{subsec:fonctions}

\begin{mydef}
    Soient $A$, $B$ des ensembles. Une \emph{fonction} $f \colon A \rightarrow B$ est une relation telle que pour tout $a \in A$, il existe au plus un $b \in B$ tel que $\langle a,b \rangle \in f$.
\end{mydef}
\begin{myrem}
    Écrire $f(a)=b$ est équivalent à $\langle a,b \rangle \in f$.
\end{myrem}
\begin{myrem}
    S'il n'existe pas de $b \in B$ et de $a \in A$ tel que $f(a)=b$ alors on dit que $f(a)$ est indéfini, et on note : $f(a) = \perp$. Le symbole $\perp$ est appelé \textbf{bottom}. Mathématiquement, cela se traduit par :
    $$ \text{si } \nexists a \in A, b \in B \text{ tel que } f(a) = b \implies f(a) = \perp $$
    On pourrait aussi écrire : 
    $$ \text{si }\forall \la a, b \ra \in A \times B : f(a) \neq b \implies f(a) = \perp $$
\end{myrem}

\subsubsection{Définition d'une fonction}
\label{par:d_finition_d_une_fonciton}
On définit une fonction par sa "table", celle-ci peut aussi bien être finie qu'infinie.\\
\begin{mydef}
    La table d'une fonction est une spécification qui permet de déduire le comportement \emph{exact} de la fonction associée. Celle-ci peut être définie de plusieurs manières, par exemple par un texte non ambigu, un algorithme ou encore en définissant toutes les paires possibles de la fonction avec son ensemble de définition.
\end{mydef}

\begin{myexem}\label{exemple:def_func_texte}
  Définition de la table d'une fonction par un texte : "Cette fonction prend en argument un nombre entier naturel et retourne son double."
\end{myexem}

\begin{myexem}\label{exemple:def_func_algo}
  Définition de la table d'une fonction par un algorithme : 
  \begin{lstlisting}
    declare fun {MultBy2 N}
        N*2
    end
  \end{lstlisting}
  On voit par les exemples \ref{exemple:def_func_texte} et \ref{exemple:def_func_algo} qu'il est possible de définir la même fonction de plusieurs manières différentes.
\end{myexem}
\begin{myexem}
  En écrivant toutes les paires de la fonction, soit en listant $$ \{ \la x, f(x) \ra | x \in dom(f)\}$$
\end{myexem}

Il est par contre important de noter que l'on ne doit pas forcément avoir une connaissance préalable exacte des phénomènes traités par la fonction.
\begin{myexem}
  $$
  f(x) = \begin{cases} 1 \text{  s'il y a de la vie autre part que sur terre,} \\ 
  0 \text{  sinon.}\end{cases}.
  $$
  (en supposant qu'il n'y ait pas d'ambiguïté sur le terme \og vie\fg).


\subsubsection{Propriétés des fonctions}
\label{par:proprietes_des_fonctions}
Soit $f\colon A \to B$, on définit le \emph{domaine} et l'\emph{image} d'une fonction respectivement comme suit
\begin{align*}
  \dom(f)   & = \{\, a \in A \mid f(a) \neq \bot \,\},\\
  \image(f) & = \{\, b \in B \mid \exists a \in A : b = f(a) \,\}.
\end{align*}

On peut dénoter le domaine d'une fonction comme l'ensemble des inputs pour lesquels la fonction donne un résultat qui n'est pas bottom. L'image d'une fonction est quant à elle l'ensemble des résultats possibles.

\noindent Une fonction peut être :
\begin{enumerate}
    \item \emph{partielle} : si $\dom(f) \subseteq A$, soit que le domaine de définition de la fonction est un sous-ensemble au sens large de $A$.
    \item \emph{totale} : si $\dom(f) = A$, soit que le domaine de définition de la fonction est exactement le même que l'ensemble $A$.
    \item \emph{surjective} : si $image(f) = B$.
    \item \emph{injective} : si $\forall a,a' \in A : a \neq a' \implies f(a) \neq f(a')$.
    \item \emph{bijective} : si elle est totale, injective et surjective.
\end{enumerate}

\begin{myrem}
    Notez qu'avec les deux premières définitions, une fonction totale est partielle.
    Pour dire que $\dom(f) \subset A$, il faut dire que $f$ n'est pas totale.
\end{myrem}


\textbf{Clarification sur les notions d'inclusions entre ensembles :}

\vspace{0.3cm}


\noindent Soient deux ensembles $A, B$ :

\vspace{0.3cm}

\noindent Si l'on écrit $ A \subset B $ cela signifie que $A$ est un sous-ensemble \textbf{au sens strict} de $B$. C'est à dire que : $$ A \subset B \implies \forall x \in A : x \in B \text{ et } A \subset B \implies A \cap B \ne B$$ soit que tous les éléments se trouvant dans $A$ se trouvent également dans $B$ mais que tous les éléments se trouvant dans $B$ ne se trouvent \emph{pas forcément} dans $A$. Intuitivement, on pourrait dire que "la taille de $B$ est plus grande que la taille de $A$" (ou pourrait parler rigoureusement de cardinal).

\vspace{0.3cm}

\noindent Si l'on écrit $ A \subseteq B $ cela signifie que $A$ est un sous-ensemble \textbf{au sens large} de $B$. C'est à dire que : $$ A \subseteq B \implies \forall x \in A : x \in B \text{ et } A \subset B \nRightarrow  A \cap B \ne B$$ soit que tous les éléments se trouvant dans $A$ se trouvent également dans $B$. Intuitivement on pourrait sire que "la taille de $B$ est plus grande ou égale à la taille de $A$".

\vspace{0.3cm}

\noindent Et finalement, si l'on écrit  $ A = B $ cela signifie que les ensembles $A$ et $B$ sont exactement égaux et peuvent êtres utilisés de manière interchangeable.
\newpage
\subsubsection{Extension de fonction}
\begin{mydef}
    Soient deux fonctions : $$ f : A \mapsto B \text{ et } g : A \mapsto B$$ On dit que $f$ est \emph{une extension} de $g$ si $f$ retourne la même valeur que $g$ partout où $g$ est définie et que $dom(g) \subset dom(f)$. On peut alors noter rigoureusement $$ \forall x \in dom(g) \implies f(x) = g(x)$$ par contre 
    $$ \forall x \in dom(f) \nRightarrow f(x) = g(x) $$
\end{mydef}
\vspace{0.3cm}
\begin{myexem}
    La fonction racine carrée définie comme $f : \mathbb{R} \mapsto \mathbb{R} : x \mapsto \sqrt{x}$ n'est définie que sur $\mathbb{R}^+$ (cette fonction n'est donc pas surjective). Par contre la fonction racine carrée d'une calculatrice comme ma TI-30 est définie comme :
    $$ \text{sqrt} : \mathbb{R} \mapsto \mathbb{R} : x \mapsto \begin{cases}
    \sqrt{x} \text{ si } x \geq 0 \\
    \texttt{DomainError } \text{sinon}
    \end{cases}
    $$
    La fonction racine carrée de ma TI-30 (sqrt) est donc une extension de la fonction racine carrée définie mathématiquement (f).
\end{myexem}

\subsubsection{Définition d'une fonction}
\label{par:d_finition_d_une_fonciton}
On définit une fonction par sa table qui peut être infinie.\\
On peut définir (la table d') une fonction de plusieurs façons :
\begin{itemize}
	\item par \emph{un texte fini} déterminant sans contradiction ni ambiguïté le contenu ;
		de la table.
	\item par un algorithme. Dans ce cas elle détermine la fonction \textit{ainsi} qu'un moyen de la calculer ;
		\subitem Ex: $f(x) = 2x^3+5$
	\item en écrivant toutes les paires de la relation ;
\end{itemize}
Il n'est toutefois pas nécessaire de décrire ou de connaître un moyen de la calculer
pour pouvoir la définir sans ambiguïté ni contradiction.

% paragraph d_finition_d_une_fonction (end)
% subsection fonctions (end)
% section ensembles_langages_relations_et_fonctions (end)

\section{Ensemble énumérable}
\label{sec:ensemble_num_rables}
Quelle est la taille d'un ensemble ?  Comment comparer la taille d'ensembles infinis ? Ce sont deux questions importantes pour lesquelles le concept d'énumérabilité nous permettra d'y répondre.

Avant de dire ce qu'est un ensemble énumérable, on doit savoir que deux ensembles
ont le même cardinal (le même nombre d'éléments), s'il existe une bijection entre eux.

\begin{mydef}[Ensemble énumérable]
	Un ensemble est \emph{énumérable} ou \emph{dénombrable} s'il est fini ou s'il a le même cardinal que $\N$. On dit que l'ensemble est \emph{équipotent} à $\N$.
\end{mydef}
Une autre manière plus intuitive de voir si un ensemble infini est énumérable est de voir s'il existe une énumération de ses éléments. Cela veut dire que nous pouvons trouver une numérotation (parmis les entiers $\N$) pour chaque élément de l'ensemble. A chaque élément de l'ensemble sera lié un numéro dans $\N$ et vice-versa, ce qui montre bien l'idée de bijection entre l'ensemble et $\N$.

\begin{myprop}
Un ensemble infini $E$ est énumérable s'il est possible de lister ses éléments.
\[
e_0, e_1, e_2, \ldots , e_n, \ldots
\]
Cette liste doit contenir tous les éléments de cet ensemble, sans répétition.  La bijection est alors la fonction $f(i) = e_i$ où $i$, l'indice des éléments de la liste, est l'entier faisant le lien avec l'ensemble $\N$.
\end{myprop}

\subsection{Exemples}
\label{subsec:exemples}

\begin{myexem}
  L'ensemble des entiers $\mathit{\Z=\{0,-1,1,2,-2,\ldots\}}$.
  \begin{proof}
     On peut avoir une bijection entre $\Z$ et $\N$, ils peuvent être énumérés et on peut donner un numéro pour chaque élément, il existe donc une énumération.

  \begin{tabular}{ l | c c c c c c c r }
     $\N$ & 0 & 1 & 2  & 3 & 4 & 5 & 6 & \ldots \\
     $\Z$ & 0 & -1 & 1 & -2 & 2 & -3 & 3  & \ldots \\

    \end{tabular}
  \end{proof}
\end{myexem}

\begin{myexem}
 L'ensemble des nombres pairs positifs.
  \begin{proof}
  Le principe reste le même: on peut établir une bijection entre l'ensemble des nombres pairs et $\N$. Nous verrons par la suite que cet exemple est en fait un cas particulier du fait que les sous-ensembles d'un ensemble énumérable (ici $\N$) sont également énumérables. A noter que ce raisonnement fonctionne donc également pour les nombres pairs appartenant à $\Z$ en se basant sur la démonstration précédente.

   \begin{tabular}{ l c c c c c c c r }
    $\N$ & 0 & 1 & 2  & 3 & 4 & 5 & 6 & \ldots \\
      Nombres pairs & 0 & 2 & 4 & 6 & 8 & 10 & 12  & \ldots \\
    \end{tabular}
  \end{proof}
\end{myexem}

\begin{myexem}
\label{exem:paire_entiers}
  L'ensemble des paires d'entiers, des triplets, \ldots
    \begin{proof}
        Il existe une énumération, il existe une bijection comme celle-ci:

		\begin{tabular}{ l c c  c  c c c  r }
			$\N$  & 0 & 1 & 2  & 3 & 4 & 5 & \ldots  \\
			Ensemble des paires d'entiers & {0,0} & {1,0} & {0,1} & {0,2} & {2,0} & {1,2}  & \ldots \\
			Ensemble des triplets d'entiers & {0,0,0} & {0,0,1} & {0,1,0} & {1,0,0} & {0,1,1} & {1,0,1}  & \ldots \\

		\end{tabular}

	Pour énumérer les paires d'entiers, on énumère les paires de somme 0, les paires de sommes $1, \ldots$ De même avec les triplets, quadruplets, \dots \\
	Dans le cas des paires d'entiers, cela revient à construire un tableau à deux dimensions de toutes les paires, et à parcourir ce tableau en suivant les différentes diagonales montantes.
    \end{proof}
\end{myexem}

\begin{myexem}
 Les rationnels, même s'ils ont une représentation décimale infinie, peuvent être représentés de manière finie en fraction d'entiers.
	 \begin{proof}
	 	 Comme tout rationnel peut s'écrire sous la forme d'un numérateur et d'un dénominateur, un rationnel est équivalent à une paire d'entiers (cette équivalence est univoque en prenant un numérateur et un dénominateur premiers entre eux, un dénominateur toujours positif et la paire $(0,1)$ pour le nombre $0$). On peut donc faire une démonstration similaire à celle des paires d'entiers pour prouver que les rationnels sont en bijection avec l'ensemble $\N$ (quitte à ne pas prendre certaines paires qui ne correspondent pas à un rationnel). De plus, il faut sauter les éléments déjà référencés. Par exemple, si (1,1) est déjà référencé, il faut éviter (2,2), (3,3), \ldots car ces derniers pointent vers la même valeur unitaire. Cela poserait problème avec la définition d'une bijection, car surjective et injective.
	 \end{proof}
 \end{myexem}

\begin{myexem}
  L'ensemble des sous-ensembles finis d'entiers.
  \begin{proof}
  Par l'exemple~\ref{exem:paire_entiers}, les ensembles des sous-ensembles de tailles 2, 3, 4, 5,\dots sont tous énumérables. On peut alors créer un tableau reprenant tous les sous-ensembles finis possibles et dans lequel la ligne $n$ comprend tous les sous-ensembles de taille $n$. Ces ensembles sont en bijection avec les naturels ($\N$).

    \begin{tabular}{ l c c  c  c c c  c }
 	 $\N$ & 0 & 1 & 2  & 3 & 4 & 5 & 6  \\
 	 sous-ensembles  taille 0  & {} & {} & {} & {} & {} & {}  & $\cdots$ \\
 	 sous-ensembles  taille 1  & {0} & {1} & {2} & {3} & {4} & {5} & $\cdots$ \\
 	 sous-ensembles  taille 2  & {0,0} & {1,0} & {0,1} & {0,2} & {2,0} & {1,2}  & $\cdots$ \\
 	 sous-ensembles  taille 3  & {0,0,0} & {0,0,1} & {0,1,0} & {1,0,0} & {0,1,1} & {1,0,1}  & $\cdots$ \\
 	 \vdots  & {\vdots} & {\vdots} & {\vdots} & {\vdots} & {\vdots} & {\vdots}  & $\ddots$ \\
	\end{tabular}
  \end{proof}
\end{myexem}

\begin{myexem}
\label{exem:chaines_finies}
  L'ensemble des chaînes finies de caractères sur un alphabet fini.
\begin{proof}
 Variante de la démonstration précédente, la technique reste la même (l'alphabet admet $k$ éléments au lieu de $10$). Chaque élément du sous-ensemble correspond à une lettre de la chaîne finie de caractères qui décrit le sous-ensemble en question.
\end{proof}
\end{myexem}

\begin{myexem}
 L'ensemble des fonctions de  $\{0, 1\}$ vers $\N$ est énumérable.
 \begin{proof}
  Une fonction de $\{0, 1\}$ vers $\N$ peut être représentée par deux couples de deux entiers $(0, f(0))$ et $(1, f(1))$, donc est un quadruple. L'ensemble des fonctions de $\{0, 1\}$ vers $\N$ est équivalent à l'ensemble des quadruples et est donc énumérable.
 \end{proof}
\end{myexem}

 \begin{myexem}
 \label{exem:programme_java}
  L'ensemble des programmes Java.
  \begin{proof}
   Un programme Java est une séquence finie d'un alphabet fini (ASCII étendu). De fait, on peut représenter chaque lettre du programme dans l'alphabet ASCII comme un nombre. Bien que chaque nombre mis bout à bout forme un nombre final très grand, cela est suffisant pour trouver un entier dans $\N$ qui correspond au programme étudié. Les programmes Java sont donc bien énumérables. Il y a potentiellement autant de programmes qu'il y a de naturels, ni plus ni moins, ce qui nous donne une bijection entre les programmes et $\N$.
  \end{proof}
\end{myexem}

\begin{myexercice} \label{exerc:ensembleEnumNumAlgebrique}
% Enoncé de l'exercice
Un nombre réel x est appelé algébrique si x est la racine d'un polynôme d'équation\\
\indent $a_0 + a_1x + a_2x^2 + ... + a_nx^n$.  avec $a_i$ entier\\
Démontrer que x est énumérable.
\end{myexercice}

\subsection{Propriétés}
\label{subsec:proprietes}

\begin{myprop}
	Tout sous-ensemble d'un ensemble énumérable est énumérable.
	\begin{proof}
Soit $A$ un sous-ensemble (infini) d'un ensemble $E$ énumérable. Comme $E$ est énumérable, il existe une énumération de ses éléments
\[
e_0, e_1, \ldots , e_n, \ldots
\]
Enlevons de cette liste les éléments qui ne sont pas dans $A$. On obtient une nouvelle liste qui énumère les éléments de $A$.
	\end{proof}
\end{myprop}

\begin{myprop}
	L'union et l'intersection de deux ensembles énumérables est énumérable.
	\begin{proof}
		Soient $A$ et $B$ deux ensembles énumérables infinis (le cas fini étant trivial). Leur intersection est énumérable car elle est un sous-ensemble de $A$, par la propriété précédente. Les éléments des ensembles $A$ et $B$ peuvent être listés
\[
A = \{ a_0, a_1, \ldots , a_n, \ldots\}  \quad
B = \{ b_0, b_1, \ldots , b_n, \ldots\}
\]
Les éléments de $A \cup B$ peuvent être également listés
\[
a_0, b_0, a_1, b_1, \ldots, a_n, b_n, \ldots
\]
en y retirant ensuite les doublons. Donc, $A \cup B$ est énumérable.
	\end{proof}
\end{myprop}

\begin{myprop}
	L'union d'une infinité énumérable d'ensembles énumérables est énumérable.
    \begin{proof}
      La démonstration est similaire à la démonstration de l'énumérabilité de $\Q$.
      On met chaque ensemble en ligne. Il y a un nombre énumérable de lignes qu'on peut numéroter par des naturels.
      On énumère l'union des ensembles en parcourant le tableau en diagonale montante en partant de $(0,0)$.
    \end{proof}
\end{myprop}

\begin{myprop}
 Tout ensemble de chaînes finies de caractères sur un alphabet fini est énumérable.
 \begin{proof}
C'est un sous-ensemble de l'ensemble de toutes les chaînes finies de caractères, qui est énumérable par l'exemple~\ref{exem:chaines_finies}.
 \end{proof}
\end{myprop}

\begin{myprop} \label{prop:programme_enumerable}
 L'ensemble des programmes Java est énumérable.
 \begin{proof}
  Voir exemple~\ref{exem:programme_java}.
 \end{proof}
\end{myprop}


\begin{myprop}
 Tout langage (avec un alphabet fini) est énumérable.
 \begin{proof}
 Un langage est un ensemble de chaînes finies de caractères d'un alphabet fini. Il est donc énumérable.
 \end{proof}
\end{myprop}

\begin{myprop}
L'union d'une infinité non énumérable d'ensembles énumérables peut ne pas être énumérable.
\end{myprop}
\begin{proof}
Par exemple, l'union des singletons $\{x\}$ pour tout réel $x$ forme l'ensemble des réels $\R$ qui n'est pas énumérable:
\[ \bigcup_{x \in \R} \{x\} = \R. \]
C'est un contre-exemple.
\end{proof}

\begin{myrem}
  Une bonne intuition à avoir:
  tout ensemble dont les éléments peuvent être représentés de manière finie est énumérable.
\end{myrem}

Dans le cours, lorsqu'on devra montrer qu'un ensemble est énumérable,
les techniques suivantes pourront être utilisées:
\begin{itemize}
	\item montrer qu'il y a une bijection avec $\N$;
	\item montrer que l'ensemble est fini;
	\item écrire un programme qui énumère l'ensemble;
	\item utiliser une des propriétés ci-dessus.
\end{itemize}

% subsection ensemble_num_rables (end)

\section{Diagonalisation de Cantor}
\label{sec:cantor}
On va montrer qu'il existe des ensembles infinis non énumérables par diagonalisation. Par exemple, l'ensemble des réels, $\R$.
\begin{myexem}
	Exemple de démonstration par diagonalisation:
	\begin{enumerate}
		\item On construit une table, dans laquelle on fait l'hypothèse qu'on a réussi à lister \textsc{tous} les grands mathématiciens.\\
			\begin{tabular}{lllllllllll}
				\emph{\textbf{D}}&E& M&O&R&G&A&N&&& \\
				A&\emph{\textbf{B}}&E&L&&&&&&&\\
				B&O&\emph{\textbf{O}}&L&E&&&&&&\\
				B&R&O&\emph{\textbf{U}}&W&E&R&&&&\\
				S&I&E&R&\emph{\textbf{P}}&I&N&S&K&I&\\
				W&E&I&E&R&\emph{\textbf{S}}&T&R&A&S&S\\
			\end{tabular}
		\item Sélectionner la diagonale : $\diag = $ DBOUPS
		\item Modifier l'élément égal à la diagonale : $\diag' =$ CANTOR (prendre à chaque fois la lettre précédente dans l'alphabet)
		\item Montrer que l'élément n'est pas dans la liste $\implies$ Contradiction
		\item Conclusion :
			\begin{itemize}
				\item Soit on sait que la liste est complète
					\subitem $ \implies$ CANTOR n'est pas un grand
					mathématicien (cas utilisé pour démontrer halt).
				\item Soit on sait que CANTOR est un grand
					mathématicien
					\subitem $ \implies$ la liste est incomplète (cas utilisé pour la diagonalisation de CANTOR)
			\end{itemize}
	\end{enumerate}
\end{myexem}

\begin{mytheo}[Diagonalisation de Cantor]
	Soit $E = \{ x \text{ réel }| 0<x\leq1\}$, $E$ est non énumérable.

	\begin{proof}
		Démonstration par l'absurde.  En supposant que $E$ soit énumérable, on va montrer qu'un nombre $d'$ n'est pas dans l'énumération alors qu'on sait
		que $d'$ est un nombre réel compris entre 0 et 1.

		On suppose $E$ énumérable. Donc il existe une énumération des éléments de $E$.  Soit
		$x_0, x_1,\dots,x_k,\dots$ cette énumération. On peut représenter un nombre $x_k$ comme étant une
		suite de chiffres $x_{ki}$ : $x_k = 0.x_{k0}x_{k1}\dots x_{kk}\dots$\footnote{Certains nombres ont deux écritures décimales : par exemple, $0.999\ldots = 1.000\ldots$. Il suffit d'en choisir une des deux pour que l'écriture décimale d'un nombre soit définie de façon univoque.}

		\begin{enumerate}
			\item On peut donc construire une table infinie : \\
				\begin{tabular}{|c||c|c|c|c|c|c|}
					\hline
					& 1 digit & 2 digit & 3 digit & \dots & k+1 digit & \dots \\
					\hline
					$x_0$ & $x_{00}$ & $x_{01}$ & $x_{02}$ & \dots & $x_{0k}$ & \dots \\
					$x_1$ & $x_{10}$ & $x_{11}$ & $x_{12}$ & \dots & $x_{1k}$ & \dots \\
					$x_2$ & $x_{20}$ & $x_{21}$ & $x_{22}$ & \dots & $x_{2k}$ & \dots \\
					$\vdots$& $\vdots$& $\vdots$& $\vdots$& $\ddots$& $\vdots$& $\vdots$\\
					$x_k$ & $x_{k0}$ & $x_{k1}$ & $x_{k2}$ & \dots & $x_{kk}$ & \dots \\
					$\vdots$& $\vdots$& $\vdots$& $\vdots$& $\vdots$& $\vdots$& $\ddots$\\
					\hline
				\end{tabular}
			\item Sélection de la diagonale (celle-ci est un nombre réel compris
				entre 0 et 1)
				\[ d=0.x_{00}x_{11}\dots x_{kk}\dots \]
			\item Modification de cet élément $d$ pour obtenir
				\[ d'=0.x_{00}'x_{11}'\dots x_{kk}'\dots \]
				Où
                $$x_{ii}'=5\text{ si }x_{ii}\neq 5\quad\text{et}\quad x_{ii}'=6\text{ si }x_{ii}= 5$$
				On a toujours que cet élément $d'$ est un réel compris entre 0 et 1\footnote{De plus, puisqu'il ne contient que des $5$ et des $6$ il n'a qu'une écriture décimale, donc notre choix quant à l'écriture décimale n'a pas d'influence et il appartient forcément au tableau.}.
			\item Le nombre $d'$ est dans l'énumération, car $E$ est
				énumérable (par hypothèse). Il existe donc $p$ tel que $x_p=d'$,
				\[ x_p=0.x_{p0}x_{p1}\dots x_{pp}\dots \]
				\[=\]
				\[ d'=0.x_{00}'x_{11}'\dots x_{pp}'\dots \]
				Il y a une contradiction car $x_{pp}' \neq
			       	x_{pp}$ par la définition de $x_{pp}'$. Donc $d' \neq x_p$ ce qui implique que $d'$ n'est pas
				dans l'énumération.
			\item Conclusion : $E$ n'est pas énumérable.
		\end{enumerate}
	\end{proof}
\end{mytheo}

\subsection{Exemples}
\label{subsec:exemples_non_enum}

Quelques ensembles non énumérables :
\begin{myexem}
 L'ensemble $\R$
 \begin{proof}
   Voir la partie sur la diagonalisation de Cantor.
 \end{proof}
\end{myexem}

\begin{myexem}
 L'ensemble des sous-ensembles de $\N$, $\mathcal{P}(\N)$
 \begin{proof}
   Rappelons-nous tout d'abord que comme $\N$ est infini, ses sous-ensembles peuvent l'être aussi.
   Il est adéquat de visualiser un ensemble à l'aide d'un mot binaire
   où le bit $i$ vaut 1 si le $i^{\mathrm{ième}}$ élément est pris dans le sous-ensemble.
   Par exemple, le sous-ensemble $\{1,4\}$ de $\{1,3,4\}$ peut être représenté par $101$.
   Seulement, comme il y a un nombre infini de nombre naturels, on a un mot binaire infini.
   Par exemple, pour les nombres pairs, c'est le mot $10101010101\ldots$:
   \begin{verbatim}
		0123456789...
		1010101010... nombres pairs

		0123456789...
		0011010100... nombres premiers

		0123456789...
		0001001001... multiples de 3 non-nuls
    \end{verbatim}
   On voit maintenant la bijection entre les sous-ensembles de $\N$ et $[0,1]$.
   En effet, chaque suite $m$ de $0$ et de $1$ peut être associée à l'écriture binaire $0.m$, qui correspond à un réel dans $[0,1]$\footnote{Comme dans la diagonalisation de Cantor, il faut aussi s'occuper des cas où un réel a plusieurs écritures binaires pour avoir une bijection parfaite. Ces détails techniques ne sont pas importants dans ce cours.}. Par exemple, on associe l'ensemble des nombres au réel $0.101010101\ldots = 2^{-1}+2^{-3}+2^{-5}+\ldots = 2/3$.
 \end{proof}
\end{myexem}

\begin{myexem}
 L'ensemble des chaînes infinies de caractères sur un alphabet fini.
 \begin{proof}
   On utilise le même raisonnement que pour les sous-ensembles de $\N$ sauf que pour un alphabet de $k$ symboles,
   on utilise la représentation en base $k$ des réels.
 \end{proof}
\end{myexem}

\begin{myexem}
  \label{exem:fNN}
 L'ensemble des fonctions de $\N$ dans $\N$ (Cas important) et de $\N$ dans $\{0, 1\}$.
 \begin{proof}
   Si c'était énumérable, soit $f_0, f_1, f_2, \ldots$ leur dénombrement.
   On construit le tableau
   \[
     \begin{array}{ccccc}
       f_0(0) & f_0(1) & f_0(2) & f_0(3) & \cdots\\
       f_1(0) & f_1(1) & f_1(2) & f_1(3) & \cdots\\
       f_2(0) & f_2(1) & f_2(2) & f_2(3) & \cdots\\
       \vdots & \vdots & \vdots & \vdots & \ddots\\
     \end{array}
   \]
   et on conclut par diagonalisation de façon semblable à $\R$
   en construisant $d\colon \N \to \N$ tel que $d(k) = f_k(k)+1$.
   On a ainsi une fonction $d(x)$ qui ne se trouve pas dans le tableau.
 \end{proof}
\end{myexem}

Dans le cours, lorsqu'on devra montrer qu'un ensemble est non énumérable,
les techniques suivantes pourront être utilisées
\begin{itemize}
	\item montrer qu'il y a une bijection avec $\R$ ;
	\item utiliser la diagonalisation (cf. Cantor) ;
\end{itemize}

\begin{myexercice}\label{exerc:conceptfct}
L'ensemble des fonctions de $\N$ vers $\{0,1\}$ est-il énumérable ?
\end{myexercice}

% subsection cantor (end)

\begin{myexercice} \label{exerc:ensembleNonEnumNumTranscendantaux}
% Enoncé de l'exercice
Un nombre réel x est appelé transcendantaux si x n'est pas algébrique. (Un nombre réel x est appelé algébriques si x est la racine d'un polynôme d'équation $a_0 + a_1x + a_2x^2 + ... + a_nx^n$.  avec $a_i$ entier).
Démontrer que x est non-énumérable s'il est transcendantaux.
\end{myexercice}

\subsection{Au delà de l'énumérable}
\label{subsec:au_dela_de_l_enumerable}
On a d'abord parlé d'ensembles finis, ensuite nous avons introduit le concept d'infini
énumérable qui est plus grand que tous les ensembles finis. Mais il existe plus grand
que l'infini énumérable. L'ensemble des réels $\R$, l'ensemble des fonctions de $\N$ dans $\N$, ainsi que
l'ensemble des sous-ensemble de $\N$ ($2^{\N}$) sont non énumérables et ont la même taille. Ils ont la puissance du continu.

Peut-on encore aller plus loin?  Oui, il suffit de considérer l'ensemble des fonctions de $\R$ dans $\R$, ainsi que
l'ensemble des sous-ensembles de $\R$ ($2^{\R}$). Ces ensembles ne peuvent pas être mis en bijection avec $\R$.

Encore plus loin ? Oui, en prenant l'ensemble des sous-ensembles de l'ensemble défini juste avant (on peut montrer que pour tout ensemble $E$, $|E|<|\mathcal{P}(E)|=2^{|E|}$). On obtient alors $2^{2^{\R}}$, et ainsi de suite\ldots

On peut ainsi schématiser la taille des ensembles comme ceci:
$$|\emptyset| < |\{1,2,3\}| < |\N| < |2^\N| = |\R| < |2^{\R}| < |2^{2^{\R}}| < |2^{2^{2^{\R}}}| \dots$$
Est-ce qu'il existe encore plus grand? Oui, effectivement, l'union de tous ces ensembles
est plus grand que chacun de ces ensembles\footnote{
Pour aller plus loin : en théorie des ensembles ZFC, cette construction s'écrit avec la lettre $\beth$ (prononcé \textbf{beth}), telle que $\beth_0 = \N, \beth_1 = 2^\N = \R,\dots$. L'union de tous ces ensembles est plus grande que chacun d'eux, et se note $\beth_\N$. On peut continuer la construction à partir de là, et obtenir des ensembles encore plus grands.

Par ailleurs, l'ensemble de \emph{tous} les cardinaux est noté avec la lettre $\aleph$ (prononcé \textbf{aleph}), avec $\aleph_0 = \abs{\N}$. On pourrait être tenté de prendre l'ensemble de tous les cardinaux pour avoir un ensemble encore plus grand. Mais ce ne serait plus un ensemble (c'est une classe dans la théorie des ensembles NBG) !

Finalement, l'hypothèse du continu stipule que $\beth_1 = \aleph_1$, c'est-à-dire qu'il n'y a pas de cardinal entre $\N$ et $\R$. Ce n'est qu'en 1963 qu'on s'est rendu compte qu'elle était en fait indépendante de la théorie des ensembles ZFC : on peut supposer qu'elle soit vrai ou qu'elle soit fausse sans obtenir de contradiction.}.


\section{Conclusion}
\label{sec:concept_conclusion}

Les ensembles énumérables sont importants pour la suite du cours. En
informatique, on ne considère que les ensembles énumérables. En effet, on constate que l'univers des programmes (Java ou autres) est énumérable (voir propriété \ref{prop:programme_enumerable}), alors que l'univers des problèmes (fonctions de $\N$ dans $\N$) est non énumérable (voir exemple \ref{exem:fNN}).
On ne peut donc forcément pas faire correspondre un programme à chaque problème et on en conclut donc que la très grande majorité des problèmes ne sont pas calculables et ne peuvent donc pas être résolus.
% subsection conclusion (end)
% section concepts (end)