correction Algboole13

[cours-maths-dis.git] / ensembles / IntroAuxEnsembles.tex

\section{Rappels de théorie des ensembles}

\subsection{Notion première d'ensemble}

\begin{description}
 \item[Ensemble]\index{ensemble} Notion première qui ne se définit pas. C'est une collection d'objets réunis en vertu d'une propriété commune.

On peut définir un ensemble de deux manières :
\begin{itemize}
 \item \emph{en extension} : on donne la liste exhaustive des éléments qui y figurent,
 \item \emph{en compréhension} : en donnant la propriété que doivent posséder les éléments de l'ensemble.
\end{itemize}
\end{description}

\begin{Exo}
Définir les ensembles suivants en compréhension :
\begin{enumerate}
\item A = \{1,2,4,8,16,32,64\}
\item B = \{1,2,7,14\}
\item C = \{4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20 \}
\end{enumerate}
\end{Exo}

\textit{\underline{Réponse :}} 1) Les puissances de 2 inférieures ou égales à 64. 2) Les diviseurs de 14. 3) Les entiers inférieurs ou égaux à 20 qui ont au moins 3 diviseurs (les nombres non premiers entre 2 et 20).


\begin{Notation}
On note $\N_n$ l'ensemble des entiers inférieurs ou égaux à $n$.
\end{Notation}


\begin{Exo}
Définir les ensembles suivants en extension
\begin{enumerate}
\item $A = \{ x \in \R | x(x+5) = 14 \}$
\item $B = \{ x \in \N | x(2x+3) = 14 \}$
\item $C = \{ x \in \N_{10}^* | x^4 -1 \textrm{ est divisible par 5 } \}$
\end{enumerate}
\end{Exo}


\textit{\underline{Réponse :}} A = \{2, -7\}, B = \{2\}, et C = \{1, 2, 3, 4, 6, 7, 8, 9\} (factoriser $x^4-1$).

\subsection{Règles de fonctionnement}


 \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$.

\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.

\paragraph{Ensemble vide.}\index{ensemble!vide} Il existe un ensemble ne contenant aucun élément, appelé ensemble vide. Symbole : le cercle barré\footnote{La notation $\varnothing$ a été introduite par le mathématicien français André Weil du groupe Bourbaki. Unicode : U+00D8} $\varnothing$.

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. 


La notation $\{\varnothing \}$ n'a pas le même sens que $\varnothing$. La dernière notation décrit un ensemble qui ne contient rien alors que le premier décrit un ensemble contenant un élément : l'ensemble vide. On peut, afin de mieux comprendre, reprendre l'analogie du sac vide. Un tiroir contenant un sac vide - $\{ \varnothing \}$ - n'est pas vide - $\varnothing$ - et contient bien un objet.

D'ailleurs, l'ensemble $\{\varnothing \}$ contient un élément (qui est un ensemble), quand l'ensemble $\varnothing$ n'en contient aucun...

\paragraph{Dernière règle de fonctionnement des ensembles.} \textcolor{red}{Un ensemble ne peut pas s'appartenir à lui-même}.

Cette dernière règle de fonctionnement peut sembler obscure, pas naturelle.

Dans l'euphorie de la naissance de la théorie des ensembles, les mathématiciens ne voyaient pas d'objection à envisager un ensemble $\Omega$ dont les éléments seraient tous les ensembles (en particulier, $\Omega \in \Omega$) : l'ensemble des ensembles, à l'origine de tout !

Leur enthousiasme fut stoppé lorsque Russell leur opposa le paradoxe...


\begin{Exo}[Paradoxe de  Bertrand Russell (1872-1970)]
Soit $X$ l'ensemble de tous les éléments qui ne sont pas éléments d'eux-mêmes.

A-t-on $X \in X$? A-t-on $X \not \in X$ ?
\end{Exo}

\begin{Rem}
Dit autrement : le barbier qui rase tous les barbiers qui ne se rasent pas eux-mêmes...se rase-t-il lui-même ?
\end{Rem}

\begin{Rem}
On en déduit donc que l'on ne peut pas parler de l'ensemble de tous les ensembles (cet ensemble devrait s'appartenir lui-même). Il ne faut pas négliger l'impact d'une telle révélation. 
\end{Rem}


\subsection{Sous-ensembles, ensemble des parties}

\paragraph{Sous-ensemble.}\index{ensemble!sous-} Les sous-ensembles sont définis par la relation d'inclusion\index{inclusion}...

\begin{Def}
$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$.
\end{Def}


\begin{Th}
L'ensemble vide est inclus dans n'importe quel ensemble.
\end{Th}

\begin{Proof}
D'après la définition d'un sous-ensemble, cela veut dire que pour tout élément x de $\varnothing$, x appartient à A. Raisonnons a contrario : si l'ensemble vide n'est pas inclus dans A, alors il existe au moins un élément de l'ensemble vide qui n'appartient pas à A. Or, il n'y a aucun élément dans l'ensemble vide, donc plus particulièrement aucun élément de l'ensemble vide qui n'appartienne pas à A. On en conclut donc que tout élément de $\varnothing$ appartient à A, et donc que $\varnothing$ est un sous-ensemble de A. 
\end{Proof}

Plus généralement, toute proposition commençant par « pour tout élément de $\varnothing$» est vraie. On a de plus le résultat suivant :

\begin{Th}
Tout ensemble est inclus dans lui-même.
\end{Th}

\paragraph{Ensemble des parties.} \index{ensemble!des parties}

\begin{Def}
Soit $A$ un ensemble. L'ensemble des parties de $A$, noté $\mathcal{P}(A)$, est l'ensemble de tous les sous-ensembles de $A$.
\end{Def}

On sait déjà que $\varnothing$ et $A$ sont deux parties de $A$...

\begin{Th}
Pour tout ensemble $A$, on a $\varnothing, A \in \mathcal{P}(A)$.
\end{Th}


\begin{Ex}
 Si $A = \{ 1, 2, 3\}$, alors  $\mathcal{P}(A) = \{ \varnothing , \{1 \},\{2 \}, \{3 \},  \{1,2 \}, \{1,3 \}, \{2,3 \}, \{1,2,3 \} \}$
\end{Ex}



\begin{Ex}
  Si $A = \varnothing, \mathcal{P}(A) = \{ \varnothing \}, \mathcal{P} \left( \mathcal{P} (a) \right) = \{ \varnothing , \{ \varnothing \} \} $. Cela n'est pas qu'un jeu de l'esprit :
  \begin{itemize}
  \item On définit 0 comme étant $\varnothing$,
  \item 1 correspond alors à $\mathcal{P}(\varnothing)$,
  \item 2 est alors  $\mathcal{P}(\mathcal{P}(\varnothing))$,
  \item \emph{etc.}
  \end{itemize}
  D'autres définitions de l'ensemble des entiers naturels existent.
\end{Ex}

De manière plus générale, si $A$ possède $n$ éléments, $\mathcal{P}(A)$ en possède $2^n$.

\begin{Exo}
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$.
\end{Exo}


\begin{Exo}
On considère A = \{1,2\}. Dire quelles assertions sont exactes :
\begin{itemize}
\item $1 \in A$,
\item $1 \subset A$,
\item $\{1\} \in A$,
\item $\{1\} \subset A$,
\item $\varnothing \in A$,
\item $\varnothing \subset A$.
\end{itemize}
\end{Exo}

\begin{Exo}
Reprendre l'exercice précédent, avec $A = \{\{1\}, \{2\}\}$.
\end{Exo}

\subsection{Représentation graphique}

On peut représenter ensembles et sous-ensembles à l'aide d'un diagramme de Venn (les célèbres \og patates \fg{})...

\begin{Exo}[Diagramme de Venn]
A partir des affirmations
\begin{enumerate}
\item les poëtes sont des gens heureux, 
\item tous les docteurs sont riches et 
\item nul être heureux n'est riche, 
\end{enumerate}
déterminer la validité de chacune des conclusions suivantes
\begin{enumerate}
\item Aucun poëte n'est riche.
\item Les docteurs sont des gens heureux.
\item Nul ne peut être à la fois docteur et poëte.
\end{enumerate}
\end{Exo}


\subsection{Exercices}

\begin{Exo}
Est-ce que $\{a\} \in \{a,b,c\}$ ? Former la liste des parties de $\{a,b,c\}$.
\end{Exo}


\begin{Exo}
 Montrer que $\mathcal{P}(A) \subset \mathcal{P}(B)$ quand $A \subset B$.
\end{Exo}



\begin{Exo}
Soit $\mathbb{B} = \{0,1\}$.
\begin{enumerate}
 \item A-t-on $\mathbb{B} \in \mathbb{B}$ ?
\item Quels sont les éléments de $\mathcal{P}(\mathbb{B})$ ?
\item Quels sont les éléments de $\mathcal{P}(\mathcal{P}(\mathbb{B}))$ ?
\end{enumerate}
\end{Exo}



\section{Opérations sur les ensembles}

\subsection{\'Egalite de deux ensembles}

\begin{Def}
Deux ensembles sont \emph{égaux} si et seulement si ils ont les mêmes éléments.
\end{Def}



$A \subset B$ et $B \subset A \Longleftrightarrow A = B$. 

\begin{Exo}
Dans chacun des cas suivants, déterminer si les ensembles sont égaux :
\begin{enumerate}
 \item $A = \{ x \in \R | x > 0 \}$ et $ B = \{x \in \R | x \geqslant |x| \}$
\item $A = \{ x \in \R | x > 0 \}$ et $ B = \{x \in \R | x \leqslant |x| \}$
\item $A = \Z$ et $B = \{ x \in \Z | x^2-x \textrm{ pair } \}$
\item $A = \{x \in \mathbb{N}_{10} \mid x \textrm{ impair, non divisible par 3 }\}$ et $B =\{x \in \mathbb{N}_{10} \mid \textrm{ 24 divise } x^2 -1 \}$
\end{enumerate}
\end{Exo}

\textit{\underline{Réponse :}} Pour le 3, $x^2-x = x(x-1)$, et réfléchir sur la parité de ce produit.

\subsection{Réunion, intersection}

\paragraph{Réunion}\index{réunion} $A$ et $B$ sont deux ensembles, on considère la réunion de $A$ et de $B$, notée $A \cup B$, l'ensemble des éléments qui sont éléments de $A$ ou de $B$.\\
\begin{Ex}
 $A = \{1,2,3\}, B = \{1,4,5\}, \text{ alors } A \cup B = \{ 1,2,3,4,5\}$
\end{Ex}



\begin{Exo}
Faire la réunion des ensembles $A = \{x \in \R | 0 \leqslant x \leqslant 3 \}$, $B = \{ x \in \R | -2 < x \leqslant 1 \}$.
\end{Exo}



\begin{Th}[Propriétés de la réunion]
La réunion de deux ensembles possède certaines propriétés :
\begin{itemize}
 \item idempotence : $A \cup A = A$
 \item commutativité : $A \cup B = B \cup A$
 \item associativité : $A \cup (B \cup C) = (A \cup B) \cup C$
 \item élément neutre : $A \cup \varnothing = A$
\end{itemize}
\end{Th}

\begin{Exo}
Donner des exemples d'opérateurs idempotents, commutatifs, associatifs, et possédant un élément neutre, par exemple en arithmétique, ou en analyse.
\end{Exo}




\paragraph{Intersection}\index{intersection} L'intersection de deux ensembles $A$ et $B$ est l'ensemble, noté $A \cap B$ des éléments communs à $A$ et à $B$.



\begin{Exo}
 Dans chacun des cas suivants, faire l'intersection des ensembles $A$ et $B$.
\begin{enumerate}
 \item A = l'ensemble des rectangles, et B = l'ensemble des losanges.
\item  $A = \{x \in \R | 0 \leqslant x \leqslant 3 \}$, $B = \{ x \in \R | -2 < x \leqslant 1 \}$
\end{enumerate}
\end{Exo}

\begin{Th}[Propriétés de l'intersection]

L'intersection de deux ensembles possède certaines propriétés :
\begin{itemize}
 \item idempotence : $A \cap A = A$
 \item commutativité : $A \cap B = B \cap A$
 \item associativité : $A \cap (B \cap C) = (A \cap B) \cap C$
 \item élément neutre : si l'on se place dans un ensemble $E$ et que $A$ est une partie de $E$, alors $E$ est élément neutre pour l'intersection : $A \cap E = A$
\end{itemize}
\end{Th}

\paragraph{Propriétés mutuelles de ces deux opérations} Ces deux opérations ont des propriétés symétriques...

\begin{Th}[Distributivités de $\cup$ et $\cap$]
On a les distributivités :
\begin{itemize}
 \item de $\cup$ sur $\cap$ : $A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$
\item de $\cap$ sur $\cup$ : $A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$
\end{itemize}
\end{Th}






\begin{Exo}
 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.
\end{Exo}


\subsection{Complémentation}

\begin{Def}[Complémentation]
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$.
\end{Def}


\begin{Notation}
Il existe plusieurs manières de noter le complémentaire de A dans E : $E \setminus A$ (\og $E$ moins $A$ \fg{}), $\bar A$, ou encore $\mathcal{C}_E A$.
\end{Notation}


\begin{Rem}
Il faut donc se placer, pour la définition de la complémentation, dans $\mathcal{P}(E)$ (où $E$ est un ensemble fixé) : \emph{la complémentation se définit par rapport à un ensemble}.
\end{Rem}


\begin{Th}
La complémentation a plusieurs propriétés remarquables :
 \begin{itemize}
 \item involution\index{involution} : $\bar{\bar{A}} = A$,
 \item loi de De Morgan\index{loi de De Morgan}  : $\bar{A \cup B} = \bar{A} \cap \bar{B}$, et $\bar{A \cap B} = \bar{A} \cup \bar{B}$.
\end{itemize}
\end{Th}

\begin{Exo}
Connaissez-vous d'autres opérations involutives ?
\end{Exo}

\begin{Exo}
Illustrez, à l'aide d'un diagramme de Venn, les lois de De Morgan.
\end{Exo}

\begin{Exo}
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 } \}$.
\end{Exo}

\textit{\underline{Réponse :}} Rechercher à quoi correspond le complémentaire de la réunion de $A$ et $B$.



\subsection{Produit cartésien}

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)$, 
\begin{itemize}
\item $(a,b)$ n'est pas un ensemble et 
\item $(a,b)$ est distinct de $(b,a)$.
\end{itemize}



\begin{Exo}
Représenter graphiquement la réunion des ensembles $A = \{(x,y) \in \R^2 | x+y \leqslant 2 \}$, et $B = \{ (x,y) \in \R^2 | 2 < 3x -y \}$.
\end{Exo}



\begin{Exo}
Représenter graphiquement l'intersection des ensembles $A = \{(x,y) \in \R^2 | x+y \leqslant 2 \}$, et $B = \{ (x,y) \in \R^2 | 2 < 3x -y \}$. 
\end{Exo}



\section{Exercices}

\subsection{Ensembles de base}

\begin{Exo}
Rappelez la définition et la notation des ensembles fondamentaux suivants : entiers naturels, entiers relatifs, nombres rationnels, décimaux, réels et complexes.
\end{Exo}

\begin{Exo}
Connaissez-vous d'autres ensembles de nombres ? Quelle en est la définition ?
\end{Exo}

\begin{Exo}
Réalisez un diagramme de Venn des ensembles des deux précédents exercices.
\end{Exo}

\subsection{La différence symétrique}

\begin{Def}
Pour deux ensembles $A$ et $B$, on appelle différence symétrique, note $A\Delta B$, 
l'ensemble défini par 
\[
A \Delta B = (A \cup B) \setminus (A \cap B)
\]
c'est-à-dire que $A \Delta B$ est constitué des éléments qui appartiennent soit à $A$, soit à $B$, mais pas aux deux.
\end{Def}


\begin{Exo}
Soit 
$A=\{1,2,3,4,5,6\}$,
$B=\{1,3,5,7,9\}$,
$C=\{4,5,6,7,8,9\}$ et 
$D=\{2,3,5,7,8\}$.\\
Trouver 
$A\Delta B$, $C\Delta B$, $A\cap (B \Delta D)$,
$B\Delta C$, $A\Delta D$ et $(A\cap B)\Delta(A \cap D)$.
\end{Exo}

\begin{Exo}
Montrez que $A\Delta B = [A\inter(E\moins B)]\union[(E\moins A) \inter B]$
\end{Exo}

\begin{Exo}
Calculer $A \Delta A$, $A \Delta (E\moins A)$, $A \Delta E$ et $E\moins (A\triangle B)$.
\end{Exo}


\begin{Exo}
Montrer que, si $A\triangle B=C$, alors $A\triangle C=B$ et $B\triangle C=A$.
\end{Exo}

\begin{Exo}
Montrer que la différence ensembliste est commutative, 
et possède un élément neutre. %, est distributive, et associative.
\end{Exo}

\begin{Exo}
Montrer que si $A \Delta B = A \Delta C$ alors $B = C$.
\end{Exo}


\subsection{Généraux}

\begin{Exo}
Soit $E$ un ensemble.

Démontrer que, quelles que soient les parties $A$, $B$, $X$, $Y$ de $E$, l'implication suivante est vraie : 

\begin{center}
$(X\inter A=X\inter B)$ et $Y\sse X\Imp Y\inter A=Y\inter B$.
\end{center}
\end{Exo}


\begin{Exo}
On se place dans l'ensemble ${\cal P}(E)$ des parties d'un ensemble non vide $E$; $A$, $B$ et $C$ sont des parties de $E$.

Montrer que $(A\union C)\sse(A\union B)$ et $(A\inter C)\sse(A\inter B)$
implique que $C\sse B$.
\end{Exo}




\begin{Exo}
Soit $E$ un ensemble non vide et ${\cal P}(E)$ l'ensemble de ses parties.

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)$).
\begin{enumerate}
\item Montrer que, pour tout couple $(X,Y)$ de parties de $E$, on a: $f(X) \union
f(Y) \sse f(X \union Y)$

\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
régulière dans $E$ et que, si $X$ est régulière, il en est de même de $f(X)$.

\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$.
\end{enumerate}
\end{Exo}




\begin{Exo}
Soit $E$ un ensemble et $A$, $B$, $C$ des parties de $E$. 

Démontrer la proposition suivante :

\begin{center}$[ A\sse (B\inter C) ]$ et $[ (B\union C)\sse A ]
\Imp[ A=B=C ]$.
\end{center}
\end{Exo}


\begin{Exo}
Sous les mêmes hypothèses, montrer que
$A \inter (A \union B)=A \union (A \inter B) = A$
\end{Exo}





\begin{Exo}
Montrer que $(A\union B)\inter(B\union C)\inter(C\union A)=(A\inter B)\union (B\inter C)\union(C\inter A)$.
\end{Exo}




\begin{Exo}[Archives]
Le jour où il ne faut pas, vous découvrez que
\begin{itemize}
\item vous avez besoin d'un fichier client $C$ et du fichier prospects $P$ qui contenait la liste des clients prospects, c.à.d. des clients actuels ou potentiels visités par les représentants au dernier semestre;
\item Le stagiaire les a effacé par mégarde, en répondant au hasard à une question du système qu'il ne comprenait pas.
\end{itemize}
Au cours d'une réunion de crise, vous apprenez cependant qu'il reste 
\begin{itemize}
\item le fichier $F$ des clients non prospects de ce dernier trimestre;
\item le fichier $G$ des prospects du dernier trimestre non encore client;
\item le fichier $H$ des clients et/ou propspects mélangés sans distinction.
\end{itemize}
En déduire comment reconstruire $P$ et $C$.
\end{Exo}




%Exercice 3 
% Diagramme de Venn
\begin{Exo}
Soit les affirmations~:
\begin{itemize}
\item J'ai planté tous mes arbres onéreux l'an passé.
\item Tous mes arbres fruitiers sont dans mon verger.
\item Aucun des arbres fruitiers n'a été planté l'an passé.
\item J'ai un orme, qui est un arbre onéreux, mais pas dans mon verger.
\end{itemize}
Dire si les affirmations suivantes sont justes ou fausses ou impossibles à répondre.
\begin{enumerate}
\item Aucun de mes arbres fruitiers n'est onéreux.
\item Tous mes arbres plantés l'an passé l'ont été dans le verger.
\item J'ai planté au moins un arbre l'an passé.
\end{enumerate}
\end{Exo}






\begin{Exo}[Fonction caractéristique des parties d'un ensemble]
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
\begin{itemize}
\item $\qqs x\in A,\ f_A(x) = 1$,
\item $\qqs x \in E\moins A,\ f_A(x) = 0$.
\end{itemize}

On pose de plus  $\qqs x\in E, f_{\vide}(x) = 0$ et $f_E(x)=1$.

Étudier les fonctions caractéristiques d'une réunion, d'une intersection de deux parties, ainsi que celle du
complémentaire d'une partie.
\end{Exo}


\begin{Exo}
On définit, dans $\{0,1\}$, trois lois de composition, de manière que,  $\qqs x \in E$, on ait $f_A(x) \cdot f_B(x)=f_{A\inter B}(x)$, $f_A(x)+f_B(x)=f_{A\union B}(x)$ et $\overline{f_A(x)} = f_{E\moins A}(x)$.

Montrer que $(\{0,1\},+, \cdot , \overline{\mathstrut\enskip})$ est une algèbre de Boole binaire.
\end{Exo}



\gsaut
\centerline{\x{Fin du Chapitre}}