path: root/background/set.tex

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.