1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
|
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}
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}[Fonctions]
\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$.
\textbf{Produit cartésien.}
Soit $A$ un ensemble $f$ une fonctions
\begin{equation}
\bigtimes_{a\in A}f(a) =
\left\{
g~|~D_g=A\wedge (\forall a\in A~g(i)\in f(i))
\right\}
\end{equation}
\end{definition}
\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]
\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}
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.
\subsubsection{Cardinal}
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.
|
