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}
Un \emph{ensemble} est une collection d'objets, sans répétition,
appelés les éléments de l'ensemble.
\paragraph{Notations}

\begin{description}
	\item [Ensemble vide :] $\emptyset$
	\item [Ensemble fini :] $\{ 0, 1, 2\}$, $\{00, 01, 10, 11\}$
	\item [Ensemble infini :] $\{ 0, 1, 2, 3, 4,\, \ldots\,\}$, $\{0, 1, -1, 2, -2, 3, -3, \, \ldots\,\}$,
	\subitem $\{a, aa, aaa, aaaa,\, \ldots\,\}$, $\{a, b, aa, ab, ba, bb, aaa, aab, \, \ldots\,\}$
	\item [Produit cartésien :] $A \times B$
    \item [Le nombre d'éléments :] $\abs{A}$
    \item [Ensemble des sous-ensembles :] $2^A$ ou $\mathcal{P}(A)$, e.g. $2^{\{2,4\}} = \{\{\}, \{2\}, \{4\}, \{2,4\}\}$. \\
      On peut remarquer que $|2^A| = 2^{|A|}$
	\item [Complément :] $\stcomp{\mathrm{A}}$
\end{description}

% subsubsection ensembles (end)

\subsection{Langages}
\label{subsec:Langages}
Notations :
\begin{itemize}
    \item Une \emph{chaîne de caractères} ou un \emph{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.
	\item Chaîne de caractères vide : $\epsilon$
    \item Un \emph{alphabet} $\Sigma$ est un ensemble fini de symboles.
    	\subitem $\Sigma = \{1, 2\}\qquad\Sigma = \{a, b, c\}\qquad\Sigma = \{\ding{189},\ding{129},a,9\}$
    \item Un mot défini sur un alphabet est une séquence finie d'éléments de cet alphabet.
    \item Un \emph{langage} est un ensemble de mots constitués de symboles d'un alphabet donné.

    	\subitem Ex : l'ensemble des palindromes définis sur $\{a, b\}$ : $\epsilon, a, b, aa, aaa, aba, babaabab, aababbbabaa$
	\item L'ensemble de tous les mots possibles sur l'alphabet $\Sigma$ :\; $\Sigma^*$
		\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{itemize}

% subsubsection Langages (end)

\subsection{Relations}
\label{subsec:relations}
Soient $A$, $B$ des ensembles.
\begin{itemize}
	\item Une \emph{relation} $R$ sur $A$, $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$.
	\item Une relation est définie par sa table
	\item Elle peut s'écrire $\la a,b \ra \in R$ ou $aR b$ ou $R(a,b)$.
\end{itemize}

% subsubsection relations (end)

\subsection{Fonctions}
\label{subsec:fonctions}
Soient $A$, $B$ des ensembles.
\begin{itemize}
  	\item 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$.
	\item Écrire $f(a)=b$ est équivalent à $\langle a,b \rangle \in f$.
	\item S'il n'existe pas de $b \in B$ tel que $f(a)=b$ alors $f(a)$ est indéfini,
		$f(a) = \perp$. Le symbole $\perp$ est appelé \emph{bottom}.
\end{itemize}

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

Si $\dom(f) \subseteq A$, alors $f$ est appelée \emph{partielle} et si $\dom(f) = A$, alors $f$ est appelée \emph{totale}.
Notez qu'avec cette définition, une fonction totale est partielle.
Pour dire que $\dom(f) \subset A$, il faut dire que $f$ n'est pas totale.

Une fonction est \emph{surjective} si $\image(f) = B$ et \emph{injective} si $\forall a,a' \in A : a \neq a' \implies f(a) \neq f(a')$.

Une fonction est \emph{bijective} si elle est totale, injective et surjective.

On utilise aussi le concept d'\emph{extension} :
$f \colon A \rightarrow B$ est une extension de $g \colon A \rightarrow B$ si $\forall x \in A : g(x)\neq \perp \implies f(x) = g(x)$.
Autrement dit, $f$ a la même valeur que $g$ partout où $g$ est définie.

La fonction $\mathrm{sqrt}(x) = \sqrt{x}$ en mathématique n'est valable que pour $x\geq0$. En revanche, un programme implémentant cette fonction, par exemple $\mathrm{mysqrt}(x) = \sqrt{x}$, retourne une valeur si $x\geq0$ ou \textit{Erreur} sinon. $\mathrm{mysqrt}(x)$ est une extension de la fonction $\mathrm{sqrt}(x)$ de base.

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

Ex : $f(x) = \left\{\begin{array}{ll} 1 & \text{s'il y a de la vie autre part que sur terre,} \\ 0 & \text{sinon.}\end{array}\right.$\\(en supposant qu'il n'y ait pas d'ambiguïté sur le terme \og vie\fg).\\
% 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 ?

Avant de dire ce qu'est un ensemble énumérable, on doit savoir que deux ensembles
ont le même cardinal 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$.
\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.

\begin{myprop}
Un ensemble infini $E$ est énumérable s'il existe une liste de 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$.
\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.
  \begin{proof}
  Le principe reste le même: on peut établir une bijection entre l'ensemble des nombres pairs et $\N$.

   \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).
	 \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$).
\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). Donc 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 sont énumérables.
	\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{Cantor}
\label{sec:cantor}
On va montrer qu'il existe des ensembles 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 ci-dessus.
 \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 mot binaire infini.
   Par exemple, 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.}.

% subsection conclusion (end)
\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 qu'un grand nombre de problèmes ne sont pas calculables.
% section concepts (end)