1 files changed, 306 insertions, 0 deletions
diff --git a/background/set.tex b/background/set.tex
new file mode 100644
index 0000000..5aaffdd
--- /dev/null
+++ b/background/set.tex
@@ -0,0 +1,306 @@
+Commencons donc cette section préliminaire avec les définitions et quelques porpiété des ensemble et de fonctions.
+Commencons par les ensembles.
+Nous utilisons ici la théorie des ensembles Zermelo–Fraenkel (ZF).
+Si nous avons, dans ce manuscrit, besoin d'objet plus grand que les ensembles, nous les appelerons classes bien qu'il soit hors de propos de présenter ici la théorie Von Neumann–Bernays–Gödel (NBG).
+Nous allons présenter ZF de manière assez succinte, juste suffisante pour réaliser les clalculs du Chapitre~\ref{sec:fini}.
+Si le lecteur souhaite plus de détail sur ces théories nous le renvoyons à \textit{Elements of set thoery} de Herbert B. Enderton~\cite{enderton1977elements}.
+
+\subsubsection{Axiomes de la théroie ZF}
+\label{sec:background-math-zf}
+Nous présentons dans cette section les axiomes de la théorie ZF.
+Ces axiomes sont la pierre angulaire des tous les dévleppoements mathématiques que nous ferons dans ce manuscrit.
+Pour un lecteur qui ne serai pas familier de cette théorie, disons qu'il s'agit de modéliser formellement le principe d'ensemble.
+C'est à dire le principe de ranger des choses, les éléments, dans des boîtes, les ensembles.
+
+\paragraph{Axiome d'Extensionnalité} 
+Deux ensemble $A$ et $B$ sont égaut si et seulement si ils ont les mêmes éléments.
+\begin{equation}
+\forall A\forall B (\forall x~x\in A \iff x\in B) \implies A=B
+\end{equation}
+
+\paragraph{Axiome de l'Ensemble vide}
+Il exite un ensemble qui ne contient aucun élément.
+Nous le notons donc $\{\}$ ou $\emptyset$.
+
+\paragraph{Axiome de la Paire}
+\begin{equation}
+\forall A \forall B \exists \{A,B\}\forall c(c\in \{A,B\}\iff c=A\vee c=B)
+\end{equation}
+
+\paragraph{Axiome de l'Union}
+Pour tout ensembles $A$, il exist un ensemble $\bigcup A$ qui soit exactement composé des éléments de chaque élément de $A$.
+\begin{equation}
+\forall A \exists \bigcup A \forall b \left(b\in\bigcup A\iff \exists a\in A~ b\in a\right)
+\end{equation}
+
+\paragraph{Axiome de l'ensemble des parties}
+Pour tout ensemble $A$ il existe un ensemble $\mathcal{P}(A)$ qui est l'ensemble des sous-ensembles (ou parties) de $A$.
+\begin{equation}
+\forall A \exists \mathcal{P}(A) ~ P\subset A \iff P\in \mathcal{P}(A)
+\end{equation}
+
+\paragraph{Axiome \textit{Aussonderung}}
+Pour toute formule $F$ (au sens du clacul des prédicats et du vocabulaire $\in$, $=$) qui ne pédend pas de $B$ et tout ensemble A, il existe un ensemble $B = \{a\in A | F\}$ qui est tel que 
+$\forall b\in B (b\in A \wedge F)$
+
+\begin{definition}[Intersection]
+    \label{def:background-math-int}
+    Pour des ensembles $A$ et $B$,
+    \begin{equation*}
+        A\cap B=\{a\in A\mid a\in B\}
+    \end{equation*}
+    et
+    \begin{equation*}
+        A\backslash B=\{a\in A\mid \neg(a\in B)\}
+    \end{equation*}
+\end{definition}
+
+\begin{definition}[Fonctions]
+    \label{def:background-fct}
+
+    \textbf{2-uplet.}
+    Nous définissons pour tout ensemble $A$ et $B$ le \emph{2-uplet} $(A,B)$ par $\{\{A\},\{A,B\}\}$.
+
+    \textbf{Relation.}
+    Nous appelons \emph{relation} un ensemble de 2-uplets.
+    L'\emph{ensemble de définision} d'une relation $R$ est 
+    $\mathcal{D}_R = \{x~|~\exists y~(x,y)\in R\}$.
+    L'\emph{image} d'une relation est $Img(R) = \{y~|~\exists x~(x,y)\in R\}$.
+    Une relation symmetrique ($\forall x\forall y~(x,y)\in R \iff (y,x)\in R$), 
+    reflexive ($\forall x~(x,x)\in R$) et
+    transitive ($\forall x\forall y\forall z~(x,y)\in R\wedge (y,z)\in R\implies (x,z)\in R $) 
+    est appelé une \emph{relation d'équivalance}.
+    Pour tout $a$, nous notons $[a]_R = \{b~|~(a,b)\in R\}$ la \emph{classes d'équivalance} de $a$.
+    Nous notons $A/R$ l'ensemble des classes d'équivlance d'une relation $R$ sur un ensemble $A$.
+
+    \textbf{Fonction.}
+    Une \emph{fonction} $f$ est un relation telle que
+    \begin{equation}
+    \forall x\in D_f\left((x,y)\in f\wedge (x,z)\in f\implies y=z\right)
+    \end{equation}
+    Pour tout ensemble $E$ et $F$ tels que $D_f\subset E$ et $Img(f)\subset F$ nous notons 
+    \begin{equation}
+        f:
+        \left\{
+        \begin{matrix}
+            E\rightarrow F\\
+           x\mapsto f(x)
+        \end{matrix}
+        \right.
+    \end{equation}
+    Où la notation $x\mapsto f(x)$ signifie que $(x,f(x))\in f$.
+    En particulier, la fonction identitée est telle que 
+    \begin{equation*}
+        id_E:\left\{
+            \begin{matrix}
+                E\rightarrow E\\
+                x\mapsto x
+            \end{matrix}
+            \right.
+    \end{equation*}
+
+    Pour deux fonctions $f:E\rightarrow F$ et $g:F\rightarrow G$ nous notons 
+    \begin{equation*}
+        g\circ f:\left\{
+            \begin{matrix}
+                E\rightarrow G\\
+                x\mapsto g(f(x))
+            \end{matrix}
+            \right.
+    \end{equation*}
+
+    Pour une expression $f(x)$, quand cela est pertinant nous noterons $f(\square)$ la fonction $f:x\mapsto f(x)$ quand il n'y a pas d'ambiguitée sur le domaine et codomaine.
+
+    \textbf{Produit cartésien.}
+    Soit $A$ un ensemble $f$ une fonctions le produit cartésien est
+    \begin{equation}
+        \bigtimes_{a\in A}f(a) = 
+        \left\{
+            g~|~D_g=A\wedge (\forall a\in A~g(a)\in f(a))
+        \right\}
+    \end{equation}
+
+    Si $A=\{i,j\}$ et $f(i)=B$ et $f(j)=C$ nous notons le produit cartésien : $B\times C$.
+    Si pour tout $a\in A~f(a)=B$ nous notons le produit cartésien $B^{A}$.
+\end{definition}
+
+
+
+
+    Nous dirons qu'une fonction $f:E\rightarrow F$ est injective si et seulement si $\forall (x,y)\in E^2(f(x)=f(y)\implies x=y$).
+    Nous dirons aussi que $f$ est surjective si et sulement si $\forall y\in F\exists x\in E~f(x)=y$.
+    Dans le cas où $f$ serait à la fois injective et surjective nous dirons qu'elle est bijective et que les ensembles $E$ et $F$ sont en bijection.
+
+    Pour une bijection $f$ de $E$ dans $F$ nous notons $f^{-1} : y\mapsto x~\text{tel que}~f(x)=y$.
+    Dans le cas où $f$ n'est pas bijective, nous définison cette notation de la manière suivant :
+    pour $B\subset F$,
+    $f^{-1}(B)=\{x\in E\mid f(x)\in B$.
+
+
+\paragraph{Axiome du choix}
+Cette axiome nous assure qui si tous les termers du produit cartérise sons non-vides alors le produits cartésien est non-vide.
+\begin{equation}
+    \forall a\in A f(a)\neq\emptyset \implies 
+        \bigtimes_{a\in A}f(a) \neq\emptyset
+\end{equation}
+
+\paragraph{Axiome de l'infini}
+\begin{equation}
+\exists A\forall a\in A~(\emptyset \in A \wedge a^+\in A)
+\end{equation}
+Où $a^+ = a\cup \{a\}$.
+Nous appelons un tel $A$, un ensemble récursif.
+
+\begin{definition}[Ensemble usuels]
+    \label{def:background-set-usu}
+
+    \textbf{Entiers.}
+Soit $C$ la classe des ensembles récursif.
+Soit $A$ un ensemble récursif.
+Nous appelons $\mathbb{N}$ l'ensemble des entier naturels que nous définissons comme suit :
+\begin{equation}
+\mathbb{N} = \{n\in A~|~\forall c\in C~n\in c\}
+\end{equation}
+$\mathbb{N}$ est bien en ensemble d'après l'axiome Aussonderung.
+    Cette construction permet de définir les opérations d'addition ($+$) et de multiplication ($\cdot$)~\cite{enderton1977elements}. 
+
+\textbf{Entiers relatifs.}
+La relation 
+\begin{equation}
+    R = 
+    \left\{ 
+    ((a,b),(c,d))\in{\mathbb{N}^2}^2~|~
+    a+d = b+c
+    \right\}
+\end{equation}
+est une relation d'équivalance sur $\mathbb{N}^2$.
+    Nous définissons alors l'ensemble des \emph{entiers relatifs} $\mathbb{Z}=\mathbb{N}^2/R$. 
+
+\textbf{Nombres rationels.}
+La relation 
+\begin{equation}
+    S = 
+    \left\{ 
+    ((a,b),(c,d))\in{\left(\mathbb{Z}\times\mathbb{Z}^*\right)}^2~|~
+    a\cdot d = b\cdot c
+    \right\}
+\end{equation}
+    est une relation d'équivalance sur $\mathbb{Z}\times\mathbb{Z}^*$.
+    Nous définissons alors l'ensemble des \emph{Nombres rationels} $\mathbb{Q}=\left(\mathbb{Z}\times\mathbb{Z}^*\right)/S$.
+
+\textbf{Nombres réels}
+    \begin{definition}[Suite de Cauchy]
+        Une \emph{suite} $u$ sur un ensemble de $A$ est une fonction de $\mathbb{N}$ dans $A$. On note $u(n) = u_n$ pour tout $n\in\mathbb{N}$.
+
+        Une \emph{suite de Cauchy} $u$ sur $\mathbb{Q}$ est elle que 
+        \begin{equation}
+            \forall \varepsilon\in\mathbb{Q}~
+            \exists N\in\mathbb{N}~
+            \forall (a,b) \in \mathbb{N}^2~
+            a\geq N\wedge b\geq N \implies
+            |u_a-u_b|\leq\varepsilon
+        \end{equation}
+
+        Soit $C$ l'ensemble des suite de Cauchy sur $\mathbb{Q}$.
+    \end{definition}
+
+La relation 
+\begin{equation}
+    T = 
+    \left\{ 
+    (u,v)\in C^2~|~
+    \forall\varepsilon~
+    \exists N\in\mathbb{N}~
+    \forall (a,b)\in\mathbb{N}^2~
+    a\geq N\wedge b\geq N \implies
+    |u_a-v_b|\leq\varepsilon
+    \right\}
+\end{equation}
+    est une relation d'équivalance sur $C^2$.
+    Nous définissons alors l'ensemble des \emph{Nombres réels} $\mathbb{R}=C/T$.
+
+\end{definition}
+
+\paragraph{Axiome de régularitée}
+Tout ensemble non-vide a un élément disjoint de cet ensemble.
+
+\paragraph{Axiome de remplacement}
+Soit $F(a,b)$ un formule qui ne dépend pas de $B$.
+\begin{equation}
+    \forall A\forall y\forall z
+    \left(
+    \forall (x\in A~F(x,y)\wedge F(x,z)\implies x=z)\implies
+    (\exists B~B=\{y~|~\exists x\in A~F(x,y)\})
+    \right)
+\end{equation}
+
+\subsubsection{Arithmétique}
+\label{sec:background-set-ari}
+Avec un niveau d'abstraction supplémentaire, nous considérons désormais que $\mathbb{N}\subset\mathbb{Z}\subset\mathbb{Q}\subset\mathbb{R}$.
+Cela est possible grace aux injéctions canoniques suivantes : 
+\begin{equation}
+    \left\{
+        \begin{matrix}
+            \mathbb{N}\rightarrow\mathbb{Z}\\
+            n\mapsto (n,0)
+        \end{matrix}
+    \right.
+\end{equation}
+
+\begin{equation}
+    \left\{
+        \begin{matrix}
+            \mathbb{Z}\rightarrow\mathbb{Q}\\
+            (a,b)\mapsto ((a,b),(1,1))
+        \end{matrix}
+    \right.
+\end{equation}
+
+\begin{equation}
+    \left\{
+        \begin{matrix}
+            \mathbb{Q}\rightarrow\mathbb{R}\\
+            (a,b)\mapsto 
+            \left[
+                \left\{
+                    \begin{matrix}
+                        \mathbb{N}\rightarrow \mathbb{Q}\\
+                        n\mapsto (a,b)
+                    \end{matrix}
+                \right.
+            \right]_T
+        \end{matrix}
+    \right.
+\end{equation}
+
+Nous identifions aussi $\mathbb{R}$ aux réprésentation en base 10 de ses éléments.
+Et nous utiliserons les opérations usuelles $+$, $\cdot$, $-$ et $/$ ainsi que la relation d'ordre $<$ sur ces représentation.
+En générale il est possible de construire ces opérations sans utiliser la représentation en base 10~\cite{enderton1977elements} mais une telle construction est hors de propos pour ce manuscrit.
+
+Outre les opératiosn usuelles, nous allons avoir aussi besoin de quelques fonction particulière :
+\begin{itemize}
+    \item La factorielle : pour $n\in\mathbb{N}~n!=n(n-1)\cdots1$.
+    \item La division euclidienne : pour 
+        $(a,b)\in\mathbb{N}\times\mathbb{N}^*~\exists (q,r)\in\left(\mathbb{N}^*\right)^2~
+        a=qb+r\wedge b(q+1)>a$.
+        $q$ est appellé quotient et $r$ reste de la division de $a$ par $b$.
+\end{itemize}
+
+\subsubsection{Intervalle}
+\label{sec:background-math-int}
+Pour $(a,b)\in\mathbb{R}^2$ avec $a\leq b$ nous définissone l'intervalle $[a,b]$ de la manière suivant : $\{x\in\mathbb{R}\mid a\leq x\wedge x\leq b\}$.
+Et aussi sa contrepartie entière : $[|a,b|] = [a,b]\cap\mathbb{N}$.
+
+\subsubsection{Cardinal}
+\label{sec:background-math-card}
+La notion de cardinal cherche à comparer la taille d'ensembles arbitraires.
+Nous n'allons pas ici considérer la théorie de ordinaux de Van Neumann qui compléte notre simplification.
+Le lecteur souhaitant aller plus loin et apprendre cette théorie peut se référer aux chapitres 6,7,8 et 9 de \textit{Elements of set thoery} de Herbert B. Enderton~\cite{enderton1977elements}.
+Notre simplification est ce suffit à elle même pour les dévelopement qui nous allons présenter dans ce manuscrit.
+
+Nous dirons donc que tout ensemble $A$ à un cardinal que nous noterons $\#A$.
+Si $A$ est en bijection avec  $n\in\mathbb{N}$ alors $\#A = n$.
+Nous dirons alors que $A$ est un ensemble fini.
+Dans le cas contraite nous dirons que $A$ est infini.
+Si $A$ est en bijection avec un sous ensemble de $\mathbb{N}$ nous dirons que $A$ est dénombrable et que sons cardinal est $\#A = \aleph_0$.
+Enfin nous dirons que deux ensemble arbitraires ont le même cardinal si et seulement si ils sont en bijection.