Logo AND Algorithmique Numérique Distribuée

Private GIT Repository
ajout relbin13
[cours-maths-dis.git] / ensembles / IntroAuxEnsembles13.tex
1 \section{Rappels de théorie des ensembles}
2
3 \subsection{Notion première d'ensemble}
4
5 \begin{description}
6  \item[Ensemble]\index{ensemble} Un ensemble est une collection
7    d'objets distincts réunis en vertu d'une propriété commune.
8
9 On peut définir un ensemble de deux manières :
10 \begin{itemize}
11  \item \emph{en extension} : on donne la liste exhaustive des éléments qui y figurent,
12  \item \emph{en compréhension} : en donnant la propriété que doivent posséder les éléments de l'ensemble.
13 \end{itemize}
14 \end{description}
15
16 \begin{Notation}
17 On note $\N_n$ l'ensemble des entiers inférieurs ou égaux à $n$.
18 \end{Notation}
19
20 \begin{Exo}
21 \begin{enumerate}
22 \item Définir les ensembles suivants en compréhension:
23 \begin{enumerate}
24 \item A = \{1,2,4,8,16,32,64\};
25 \item B = \{1,2,7,14\}.
26 \end{enumerate}
27 \item Définir les ensembles suivants en extension:
28 \begin{enumerate}
29 \item $A = \{ x \in \R | x(x+5) = 14 \}$;
30 \item $C = \{ x \in \N_{10}^* | x^4 -1 \textrm{ est divisible par 5 } \}$.
31 \end{enumerate}
32 \end{enumerate}
33 \end{Exo}
34
35
36 \subsection{Règles de fonctionnement}
37
38
39  \paragraph{Relation d'appartenance.} \index{appartenance} On admet être capable de décider si un objet est ou non élément d'un ensemble. Le fait que l'élément $x$ appartienne à l'ensemble $X$ se note : $x \in X$.
40
41 \paragraph{Objets distincts.} On admet aussi être capable de distinguer entre eux les éléments d'un ensemble. En particulier, un ensemble ne peut pas contenir deux fois le même objet.
42
43 \paragraph{Ensemble vide.}\index{ensemble!vide} Il existe un ensemble ne contenant aucun élément, appelé ensemble vide: $\varnothing$.
44 L'ensemble vide ne correspond pas à rien ; c'est en fait un ensemble qui ne contient rien, mais en tant qu'ensemble il n'est pas rien : un sac vide est vide, mais le sac en lui même existe. 
45
46
47 \paragraph{Dernière règle de fonctionnement des ensembles.} \textcolor{red}{Un ensemble ne peut pas s'appartenir à lui-même}.
48
49
50
51 \subsection{Sous-ensembles, ensemble des parties}
52
53 Les sous-ensembles sont définis par la relation d'inclusion\index{inclusion}...
54
55 \begin{Def}
56 $A$ est un sous-ensemble de $B$ ($A \subset B$)\fg{} si et seulement si tout élément de $A$ appartient à $B$. On dit aussi que $A$ est une partie de $B$.
57 \end{Def}
58
59
60 \begin{Th}
61 L'ensemble vide est inclus dans n'importe quel ensemble.
62 \end{Th}
63
64 \begin{Proof}
65 Raisonnons par l'absurde: 
66 si l'ensemble vide n'est pas inclus dans $A$, 
67 alors il existe au moins un élément de l'ensemble vide qui n'appartient pas à $A$.
68 Ceci est absurde puisque l'ensemble vide est vide.
69 \end{Proof}
70
71
72 \begin{Th}
73 Tout ensemble est inclus dans lui-même.
74 \end{Th}
75
76
77 \begin{Def}
78 Soit $A$ un ensemble. L'ensemble des parties de $A$, noté $\mathcal{P}(A)$, est l'ensemble de tous les sous-ensembles de $A$.
79 \end{Def}
80
81
82
83 \begin{Th}
84 Pour tout ensemble $A$, on a $\varnothing, A \in \mathcal{P}(A)$.
85 \end{Th}
86
87
88 \begin{Ex}
89  Si $A = \{ 1, 2, 3\}$, alors  $\mathcal{P}(A) = \{ \varnothing , \{1 \},\{2 \}, \{3 \},  \{1,2 \}, \{1,3 \}, \{2,3 \}, \{1,2,3 \} \}$.
90 \end{Ex}
91
92
93 \begin{Exo}
94 Justifier le fait que le nombre d'éléments de $\mathcal{P}(A)$ est égal à $2^n$, où $n$ représente le nombre d'éléments de $A$.
95 \end{Exo}
96
97
98 \begin{Exo}
99 On considère A = \{1,2\}. Dire quelles assertions sont exactes :
100 \begin{enumerate}
101 \item $1 \in A$,
102 \item $1 \subset A$,
103 \item $\{1\} \in A$,
104 \item $\{1\} \subset A$,
105 \item $\varnothing \in A$,
106 \item $\varnothing \subset A$.
107 \end{enumerate}
108 \end{Exo}
109
110 \begin{Exo}
111 Reprendre l'exercice précédent, avec $A = \{\{1\}, \{2\}\}$.
112 \end{Exo}
113
114
115
116
117 \begin{Exo}
118 Est-ce que $\{a\} \in \{a,b,c\}$ ? Former la liste des parties de $\{a,b,c\}$.
119 \end{Exo}
120
121
122 \begin{Exo}
123  Montrer que $\mathcal{P}(A) \subset \mathcal{P}(B)$ quand $A \subset B$.
124 \end{Exo}
125
126
127 \section{Opérations sur les ensembles}
128
129 \subsection{\'Egalite de deux ensembles}
130
131 \begin{Def}
132 Deux ensembles sont \emph{égaux} si et seulement si ils ont les mêmes éléments.
133 \end{Def}
134
135
136
137 $A \subset B$ et $B \subset A \Longleftrightarrow A = B$. 
138
139 \begin{Exo}
140 Dans chacun des cas suivants, déterminer si les ensembles sont égaux :
141 \begin{enumerate}
142  \item $A = \{ x \in \R | x > 0 \}$ et $ B = \{x \in \R | x \geqslant |x| \}$;
143 \item $A = \{ x \in \R | x > 0 \}$ et $ B = \{x \in \R | x \leqslant |x| \}$;
144 \item $A = \Z$ et $B = \{ x \in \Z | x(x-1) \textrm{ pair } \}$;
145 on pourra réfléchir sur la parité de $x(x-1)$.
146 \end{enumerate}
147 \end{Exo}
148
149 \subsection{Réunion, intersection}
150
151 \begin{Def}[Reunion]\index{réunion} 
152 La \emph{réunion} des deux ensembles $A$ et  $B$, notée $A \cup B$ est
153 l'ensemble des éléments qui sont éléments de $A$ ou de $B$.
154 \end{Def}
155 \begin{Ex}
156  $A = \{1,2,3\}, B = \{1,4,5\}, \text{ alors } A \cup B = \{ 1,2,3,4,5\}$
157 \end{Ex}
158
159
160 \begin{Def}[Intersection]\index{réunion} 
161 L'\emph{intersection} des deux ensembles $A$ et  $B$, notée $A \cap B$, 
162 est l'ensemble des éléments communs à $A$ et à $B$.
163 \end{Def}
164
165
166
167
168
169
170
171 \begin{Th}[Propriétés de la réunion et de l'intersection]
172 La réunion de deux ensembles possède certaines propriétés :
173 \begin{itemize}
174  \item idempotence : $A \cup A = A$ et $A \cap A = A$;
175  \item commutativité : $A \cup B = B \cup A $ et $A \cap B = B \cap A$;
176  \item associativité : $A \cup (B \cup C) = (A \cup B) \cup C$ et $A \cap (B \cap C) = (A \cap B) \cap C$;
177  \item éléments neutres : $A \cup \varnothing = A$ et $A \cap \Omega = A$.
178 \end{itemize}
179 \end{Th}
180
181 \begin{Exo}
182 \item Construire la réunion puis l'intersection des ensembles $A = \{x \in \R | 0 \leqslant x \leqslant 3 \}$, $B = \{ x \in \R | -2 < x \leqslant 1 \}$.
183 \end{Exo}
184
185 \begin{Exo}
186 Faire la réunion des ensembles $A$ et $B$, quand $A = \{x \in \N | x \textrm{ impair } \}$, et $B = \{ x \in \N | x \textrm{  pas divisible par 3 } \}$.
187 \end{Exo}
188
189
190 \begin{Th}[Distributivités de $\cup$ et $\cap$]
191 On a les distributivités :
192 \begin{itemize}
193  \item de $\cup$ sur $\cap$ : $A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$
194 \item de $\cap$ sur $\cup$ : $A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$
195 \end{itemize}
196 \end{Th}
197
198 \begin{Exo}
199  On se donne trois ensembles $A, B, C$ tels que $A \cap B \cap C = \varnothing $. Sont-ils nécessairement disjoints deux à deux ? Donner des exemples.
200 \end{Exo}
201
202
203 \subsection{Complémentation}
204
205 \begin{Def}[Complémentation]
206 Pour $A \subset E$, on définit le \emph{complémentaire}\index{ensemble!complémentaire}\index{complémentation} de $A$ par rapport à $E$ comme l'ensemble des éléments de $E$ qui ne sont pas éléments de $A$. On note le complémentaire de $A$ dans $E$ : $E \setminus A$ (\og $E$ moins $A$ \fg{}) ou $\bar A$ quand ce n'est pas ambiguë.
207 \end{Def}
208
209
210
211 \begin{Th}
212 La complémentation a plusieurs propriétés remarquables :
213  \begin{itemize}
214  \item involution\index{involution} : $\bar{\bar{A}} = A$,
215  \item loi de De Morgan\index{loi de De Morgan}  : $\overline{A \cup B} = \overline{A} \cap \overline{B}$, et $\overline{A \cap B} = \overline{A} \cup \overline{B}$.
216 \end{itemize}
217 \end{Th}
218
219
220
221 \begin{Exo}
222 Pour deux ensembles $A$ et $B$, 
223 on appelle différence symétrique, note $A\Delta B$, 
224 l'ensemble défini par 
225 $A \Delta B = (A \cup B) \setminus (A \cap B)$ 
226 c'est-à-dire que $A \Delta B$ est constitué des éléments qui appartiennent soit à $A$, soit à $B$, mais pas aux deux.
227 \begin{enumerate}
228 \item Montrez que $A\Delta B = [A\inter(E\moins B)]\union[(E\moins A) \inter B]$.
229 \item Simplifier les expressions $A \Delta A$, $A \Delta (E\moins A)$, $A \Delta E$ et $E\moins (A\triangle B)$.
230 \item Montrer que, si $A\triangle B=C$, alors $A\triangle C=B$ et $B\triangle C=A$.
231 \item Montrer que si $A \Delta B = A \Delta C$ alors $B = C$.
232 \end{enumerate}
233 \end{Exo}
234
235
236 \subsection{Produit cartésien}
237
238 Le produit cartésien des ensembles $A$ et $B$ (dans cet ordre) est l'ensemble, que l'on note $A \times B$ (\og $A$ croix $B$ \fg{}) des couples ordonnés $(a,b)$ où $a \in A$ et $b \in B$. Dans le couple $(a,b)$:
239 \begin{itemize}
240 \item $(a,b)$ n'est pas un ensemble et 
241 \item $(a,b)$ est distinct de $(b,a)$.
242 \end{itemize}
243
244
245
246
247 \begin{Exo}
248 Énumérez les éléments de $\{a,b,c\}\times\{1,2\}$ . 
249 Combien y en a-t-il?
250 \end{Exo}
251
252
253
254
255 \section{Exercices supplémentaires}
256
257 \begin{Exo}
258 Soit $E$ un ensemble non vide et $A$, $B$, $C$, $X$, $Y$ des parties de $E$.
259 \begin{enumerate}
260 \item Montrer que si on a $(X\inter A=X\inter B)$ et $Y\sse X$ sont 
261 alors on a $ Y\inter A=Y\inter B$.
262  \item  Montrer que si on a 
263    $(A\union C)\sse(A\union B)$ et $(A\inter C)\sse(A\inter B)$ 
264    alors  on a  $C\sse B$.
265
266 \item  Montrer que si on a  
267 $ A\sse (B\inter C) $ et $(B\union C)\sse A $ 
268 alors on a 
269 $ A=B=C$.
270
271  \end{enumerate}
272 \end{Exo}
273
274
275
276
277 \begin{Exo}
278 Soit $E$ un ensemble non vide et ${\cal P}(E)$ l'ensemble de ses parties.
279
280 Soit $f$ une application croissante, pour l'inclusion, de ${\cal P}(E)$ dans lui-même (c'est-à-dire : si $X$ et $Y$ sont deux parties de $E$ et si $X \sse Y$, alors $f(X) \sse f(Y)$).
281 \begin{enumerate}
282 \item Montrer que, pour tout couple $(X,Y)$ de parties de $E$, on a: $f(X) \union
283 f(Y) \sse f(X \union Y)$.
284
285 \item On dit qu'une partie $X$ de $E$ est régulière si et seulement si $f(X) \sse X$. Montrer qu'il existe au moins une partie
286 régulière dans $E$ et que, si $X$ est régulière, il en est de même de $f(X)$.
287
288 \item Soit $A$ l'intersection de toutes les parties régulières de $E$. Montrer que $A$ est régulière et que $f(A) = A$.
289 \end{enumerate}
290 \end{Exo}
291
292
293
294
295
296
297
298
299
300 \begin{Exo}[Fonction caractéristique des parties d'un ensemble]
301 On appelle fonction caractéristique de la partie $A$ de l'ensemble $E$ $(E\neq\vide$, $A\neq\vide$, $A\sse E$) l'application $f_A:E\imp\{0,1\}$, définie par:
302 \begin{itemize}
303 \item $\qqs x\in A,\ f_A(x) = 1$;
304 \item $\qqs x \in E\moins A,\ f_A(x) = 0$.
305 \end{itemize}
306
307 On pose de plus  $\qqs x\in E, f_{\vide}(x) = 0$ et $f_E(x)=1$.
308
309 Étudier les fonctions caractéristiques d'une réunion, d'une intersection de deux parties, ainsi que celle du
310 complémentaire d'une partie.
311 \end{Exo}
312
313
314
315
316 \gsaut
317 \centerline{\x{Fin du Chapitre}}
318