diff options
Diffstat (limited to 'background/set.tex')
| -rw-r--r-- | background/set.tex | 189 |
1 files changed, 100 insertions, 89 deletions
diff --git a/background/set.tex b/background/set.tex index 5aaffdd..ee5c2c1 100644 --- a/background/set.tex +++ b/background/set.tex @@ -1,46 +1,46 @@ -Commencons donc cette section préliminaire avec les définitions et quelques porpiété des ensemble et de fonctions. -Commencons par les ensembles. +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 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}. +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éroie ZF} +\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é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. +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 égaut si et seulement si ils ont les mêmes éléments. -\begin{equation} +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} +\end{equation*} -\paragraph{Axiome de l'Ensemble vide} -Il exite un ensemble qui ne contient aucun élément. +\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} +\begin{equation*} \forall A \forall B \exists \{A,B\}\forall c(c\in \{A,B\}\iff c=A\vee c=B) -\end{equation} +\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} +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} +\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} +\begin{equation*} \forall A \exists \mathcal{P}(A) ~ P\subset A \iff P\in \mathcal{P}(A) -\end{equation} +\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 +\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] @@ -63,23 +63,23 @@ $\forall b\in B (b\in A \wedge F)$ \textbf{Relation.} Nous appelons \emph{relation} un ensemble de 2-uplets. - L'\emph{ensemble de définision} d'une relation $R$ est + 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 symmetrique ($\forall x\forall y~(x,y)\in R \iff (y,x)\in R$), - reflexive ($\forall x~(x,x)\in R$) et + 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'é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$. + 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} + \begin{equation*} \forall x\in D_f\left((x,y)\in f\wedge (x,z)\in f\implies y=z\right) - \end{equation} + \end{equation*} Pour tout ensemble $E$ et $F$ tels que $D_f\subset E$ et $Img(f)\subset F$ nous notons - \begin{equation} + \begin{equation*} f: \left\{ \begin{matrix} @@ -87,9 +87,9 @@ $\forall b\in B (b\in A \wedge F)$ x\mapsto f(x) \end{matrix} \right. - \end{equation} + \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 + En particulier, la fonction identité est telle que \begin{equation*} id_E:\left\{ \begin{matrix} @@ -109,45 +109,42 @@ $\forall b\in B (b\in A \wedge F)$ \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. + 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} + \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} + \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$. + 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$. - Dans le cas où $f$ n'est pas bijective, nous définison cette notation de la manière suivant : + 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$. - + $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 termers du produit cartérise sons non-vides alors le produits cartésien est non-vide. -\begin{equation} +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} +\end{equation*} \paragraph{Axiome de l'infini} -\begin{equation} +\begin{equation*} \exists A\forall a\in A~(\emptyset \in A \wedge a^+\in A) -\end{equation} +\end{equation*} Où $a^+ = a\cup \{a\}$. Nous appelons un tel $A$, un ensemble récursif. @@ -158,54 +155,53 @@ Nous appelons un tel $A$, un ensemble récursif. 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} +\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}. +\end{equation*} +$\mathbb{N}$ est bien en ensemble d'après l'axiome de séparation. \textbf{Entiers relatifs.} La relation -\begin{equation} +\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$. +\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 rationels.} +\textbf{Nombres rationnels.} La relation -\begin{equation} +\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$. +\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 elle que - \begin{equation} + 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} + \end{equation*} Soit $C$ l'ensemble des suite de Cauchy sur $\mathbb{Q}$. \end{definition} La relation -\begin{equation} +\begin{equation*} T = \left\{ (u,v)\in C^2~|~ @@ -215,48 +211,48 @@ La relation 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$. +\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ée} +\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)$ un formule qui ne dépend pas de $B$. -\begin{equation} +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 x=z)\implies + \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} +\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} +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} +\end{equation*} -\begin{equation} +\begin{equation*} \left\{ \begin{matrix} \mathbb{Z}\rightarrow\mathbb{Q}\\ (a,b)\mapsto ((a,b),(1,1)) \end{matrix} \right. -\end{equation} +\end{equation*} -\begin{equation} +\begin{equation*} \left\{ \begin{matrix} \mathbb{Q}\rightarrow\mathbb{R}\\ @@ -271,36 +267,51 @@ Cela est possible grace aux injéctions canoniques suivantes : \right]_T \end{matrix} \right. -\end{equation} +\end{equation*} -Nous identifions aussi $\mathbb{R}$ aux réprésentation en base 10 de ses éléments. +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ératiosn usuelles, nous allons avoir aussi besoin de quelques fonction particulière : +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 appellé quotient et $r$ reste de la division de $a$ par $b$. + $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éfinissone l'intervalle $[a,b]$ de la manière suivant : $\{x\in\mathbb{R}\mid a\leq x\wedge x\leq b\}$. +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. +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. +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$ à un cardinal que nous noterons $\#A$. +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 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$. +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. |