path: root/background/set.tex

Commençons donc cette section préliminaire avec les définitions et quelques propriétés des ensembles et de fonctions.
Commençons par les ensembles.
Nous utilisons ici la théorie des ensembles Zermelo–Fraenkel (ZF).
Si nous avons, dans ce manuscrit, besoin d'objet plus grands que les ensembles, nous les appellerons 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 succincte, juste suffisante pour réaliser les calculs du Chapitre~\ref{sec:fini}.
Si le.la lecteur.rice souhaite plus de détails sur ces théories il.elle peut consulter \textit{Elements of set thoery} de Herbert B. Enderton~\cite{enderton1977elements}.

\subsubsection{Axiomes de la théorie 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éveloppements mathématiques que nous ferons dans ce manuscrit.
Pour un.e lecteur.rice qui ne serai pas familier.ère 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 égaux 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 existe un ensemble qui ne contienne 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 ensemble $A$, il existe 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 de séparation}\footnote{\textit{Aussonderung}}
Pour toute formule $F$ (au sens du calcul des prédicats et du vocabulaire $\in$, $=$) qui ne dépend 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éfinition} 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 symétrique ($\forall x\forall y~(x,y)\in R \iff (y,x)\in R$), 
    réflexive ($\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'équivalence}.
    Pour tout $a$, nous notons $[a]_R = \{b~|~(a,b)\in R\}$ la \emph{classes d'équivalence} de $a$.
    Nous notons $A/R$ l'ensemble des classes d'équivalence 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é 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 pertinent nous noterons $f(\square)$ la fonction $f:x\mapsto f(x)$ quand il n'y a pas d'ambiguïté 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 seulement 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$, c'est la fonction inverse de $f$.
    Dans le cas où $f$ n'est pas bijective, nous définissons cette notation de la manière suivant :
    pour $B\subset F$,
    $f^{-1}(B)=\{x\in E\mid f(x)\in B\}$,
    c'est l'image réciproque de $f$.

\paragraph{Axiome du choix}
Cette axiome nous assure qui si tous les termes du produit cartésien sons non-vides alors le produit 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 de séparation.

\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'équivalence sur $\mathbb{N}^2$.
    Nous définissons alors l'ensemble des \emph{entiers relatifs} $\mathbb{Z}=\mathbb{N}^2/R$. 

\textbf{Nombres rationnels.}
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'équivalence sur $\mathbb{Z}\times\mathbb{Z}^*$.
    Nous définissons alors l'ensemble des \emph{Nombres rationnels} $\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 telle 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'équivalence 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é}
Tout ensemble non-vide a un élément disjoint de cet ensemble.

\paragraph{Axiome de remplacement}
Soit $F(a,b)$ une 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 y=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 grâce aux injections 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 représentations 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érations usuelles, nous allons avoir aussi besoin de quelques fonction particulière :
\begin{itemize}
    \item L'indicatrice de $A\subset E$ est 
        \begin{equation*}
            1_A:\left\{
                \begin{matrix}
                    E\rightarrow\{0,1\}\\
                    x\mapsto\left\{
                        \begin{matrix}
                            1~\text{si}~x\in A\\
                            0~\text{sinon}
                        \end{matrix}
                    \right.
                \end{matrix}
            \right.
        \end{equation*}
    \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 appelé 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éfinissons 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 se suffit à elle même pour les développements qui nous allons présenter dans ce manuscrit.

Nous dirons donc que tout ensemble $A$ 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 contraire 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.
Si $A$ est en bijection avec $\mathbb{N}$ nous notons $\#A = \aleph_0$.
Enfin nous dirons que deux ensemble arbitraires ont le même cardinal si et seulement si ils sont en bijection.