ajout en vrac de tous les partiels

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

Dans tout ce chapitre, on se donne deux ensembles $E$ et $F$. 

\section{Relations}


\begin{Def}[Relation binaire]
On définit une \emph{relation binaire} \index{relation binaire} entre
les deux ensembles $E$ et $F$ lorsqu'on construit une partie $G$
de l'ensemble produit $E\times F$ 
($G\sse E\times F$).
Si $x$ dans $E$ et $y$ dans $F$ sont tels que $(x,y)\in G$, on dit 
que $x$ est \emph{en Relation avec} $y$. On note cela $x{\mathcal{R}}y$.
\end{Def}

\begin{Exo}
\begin{enumerate}
\item Définir la relation \og a pour mention au Bac \fg{} comme une 
  relation entre deux ensembles.
\item Définir l'index d'un livre comme une relation entre deux ensembles.
\item Définir le fait d'avoir un compte dans une banque comme une relation entre deux ensembles.
\end{enumerate}
\end{Exo}




\begin{Rem}
Lorsque $E=F$, on parle de relation binaire définie dans l'ensemble $E$.
Son graphe est une partie de $E^2$.
Dans ce cas, il est possible que $x \mathcal{R} y$ sans que $y \mathcal{R} x$.
(Penser à la relation \og est plus âgé que \fg{}).
\end{Rem}



% \begin{Exo}
% Sur l'ensemble $\Z$ des entiers relatifs, on définit deux relations $\Sigma$ et $\Delta$:
% \begin{itemize}
%  \item $x \Sigma y$ quand la somme $x+y$ est paire
% \item  $x \Delta y$ quand la différence $x-y$ est paire
% \end{itemize}
% Sont-elles égales ?
% \end{Exo}


\section{Relations d'ordre}
On se place dans le cas où $E=F$.
Soit ${\mathcal{R}}$ une relation binaire définie
dans un ensemble $E$.

\subsection{Réflexivité, antisymétrie, transitivité}


\begin{Def}[Réflexivité]
 ${\mathcal{R}}$ est dite \emph{réflexive} \index{relation!réflexive} quand tout élément de $E$ est en relation avec lui-même : $\qqs x\in E,\ x {\mathcal{R}} x$. 
%  ou encore 
% $\qqs x\in E,\ (x,x)\in G$.
\end{Def}


\begin{Def}[Antisymétrie]
 ${\mathcal{R}}$ est dite \emph{antisymétrique} \index{relation!antisymétrique} si, lorsque  $x$ est en relation avec $y$, alors $y$ ne peut pas être en relation avec $x$ (sauf si $x=y$): 
 $\qqs(x,y)\in E^2,\ x {\mathcal{R}} y\ {\rm et}\ y {\mathcal{R}} x\Imp\ x=y$.
% ou encore
% $\qqs x\in E,\ \qqs y\in E,\ (x,y)\in G ~{\rm et}\ (y,x)\in G\ \Imp x=y$
% %
\end{Def}



\begin{Def}[Transitivité]
 ${\mathcal{R}}$ est dite \emph{transitive} \index{relation!transitive} lorsque, si $x$ est en relation avec $y$, et si $y$ l'est avec $z$, alors $x$ est en relation avec $z$:
$\qqs x\in E,\ \qqs y\in E,\qqs z \in E,\ x {\mathcal{R}} y\ {\rm et}\ y {\mathcal{R}} z \Imp x {\mathcal{R}} z$. 
% $$\qqs x\in E,\qqs y\in E,\ \qqs z\in E,\ (x,y)\in G\ {\rm et}\ (y,z)\in G
% \Imp (x,z)\in G$$
\end{Def}




\begin{Exo}
Les relations suivantes sont-elles réflexives, antisymétriques ou transitives ?
\begin{enumerate}
\item $A = \mathbb{R}$ et $x \mathcal{R} y$ si $|x| = |y|$.
\item $A = \mathbb{R}$ et $x \mathcal{R} y$ si $\sin^2 x + \cos^2 y = 1 $.
\item $A = \mathbb{N}$ et $x \mathcal{R} y$ s'il existe $p$ et $q$ entiers tels que $y = p x^q$.
% \item $A$ est l'ensemble des points du plan, et $x \mathcal{R} y$ si la distance de $x$ à $y$ est inférieure à 52,7 km.
\end{enumerate}
\end{Exo}



\begin{Exo}
Sur $\N^*$ on définit la relation
$a \mathcal{R} b$ si et seulement si $a^b \leq b ^a$.
\begin{enumerate}
\item Vérifier que cette relation est réflexive et transitive.
\item Comparer 2 et 4. La relation est-elle antisymétrique?
\end{enumerate}
\end{Exo}



% \begin{Exo}
% Soit $\mathcal{R}$ et $\mathcal{S}$ deux relations dans $A$.
% \begin{enumerate}
% \item Montrer que si $\mathcal{R}$ et $\mathcal{S}$ sont transitives alors $\mathcal{R} \cap \mathcal{S}$ est transitive.
% \item Si $\mathcal{R}$ est antisymétrique alors $\mathcal{R} \cap \mathcal{S}$ est antisymétrique.
% \end{enumerate}
% \end{Exo}


\subsection{Relation d'ordre}

\begin{Def}[Relation d'ordre]
${\mathcal{R}}$ est une \emph{relation d'ordre}\index{relation!d'ordre} si elle est réflexive, antisymétrique et transitive.
\end{Def}


\begin{Ex}
Quelques relations d'ordre: $(\R,\leqslant)$, $({\cal P}(E),\sse)$
\end{Ex}

\begin{Ex}[Relation de divisibilité]
On note $a|b$ si et seulement si $b$ est un multiple de $a$ ($\exists k \in \Net, b=ka$).
C'est une relation d'ordre définie dans $\Net$. En effet, elle est

\begin{description}
\item[réflexive:] $a=1a$, donc $a|a$ est vrai,
\item[antisymétrique:] si $a|b$ et $b|a$, alors $\exists k,k' \in \Net, a=kb$ et $b=k'a$. Donc $a = kk' a$. Comme $a \neq 0$, $kk'=1$. Mais $k,k' \in \Net$, donc $k = k' = 1$, et $a = b$.
\item[transitive:] si $a|b$ et $b|c$, alors alors $\exists k,k' \in \Net, a=kb$ et $b=k'c$. Donc $a = k k' c$: il existe $k'' \in \Net$ ($k''=k k'$) tel que $a = k''c$: $a|c$.
\end{description}

\end{Ex}


% La structure algébrique constituée par l'ensemble $E$, muni de la
% relation d'ordre ${\mathcal{R}}$, 
% (c'est-à-dire: le couple $(E,{\mathcal{R}})$) est
% celle d'\emph{ensemble ordonné}\index{ensemble!ordonné}.




\begin{Exo}
On définit une relation binaire $\mathcal{R}$ sur $\R\times \R^+$ par 
$(x,y) \mathcal{R} (x',y')$ ssi 
$x^2+y^2 < x'^2+y'^2$ ou 
($x^2+y^2 = x'^2+y'^2$ et  $x \leq  x'$).
Montrer qu'il s'agit d'une relation d'ordre.
\end{Exo}




\begin{Exo}[Diagrammes de transitivité]
On considère\ldots 
\begin{enumerate}
\item $E=\{1\vir 2\vir 3\vir 4\vir 5\vir 6\vir 7\vir 8\vir 9\}$ et on
définit la relation binaire $\mathcal{R}$ dans $E$ par son graphe
$G=\{$(1,1), (1,2), (1,3), (1,4), (1,5), (1,6), (1,7), (1,8), (1,9), (2,2), (2,3), (2,4), (2,6), (2,8), (2,9), (3,3), (4,3), (4,4), (4,6), (4,8), (4,9), (5,3), (5,4), (5,5), (5,6), (5,7), (5,8), 
(5,9), (6,6), (6,8), (6,9), (7,7), (7,8), (7,9), (8,8), (9,9)$\}$
(c'est-à-dire: $1{\mathcal{R}}1$, etc\ldots). 
Justifier que cette relation est une relation d'ordre.

\item Mêmes questions pour $E'=\{1\vir 2\vir 3\vir 4\vir 5\vir 6\}$ et
$G'=\{$(1,1), (1,2), (1,3), (1,4), (1,5), (1,6), 
(2,2), (2,4), (2,5), (2,6), (3,3), (3,4), (3,6), (4,4), (4,6), (5,5), (5,6), 
(6,6)$\}$.
\end{enumerate}
\end{Exo}







\section{Relations d'équivalence}


On se place encore dans ce paragraphe dans le cas où $E=F$.
Soit ${\mathcal{R}}$ une relation binaire définie dans un ensemble (non vide) $E$, de graphe $G$.

\begin{Def}[Relation symétrique]
${\mathcal{R}}$ est dite \emph{symétrique} \index{relation!symétrique} si, dès que $x$ est en relation avec $y$, alors $y$ est en relation avec $x$:
$\qqs x\in E, \qqs y\in E,\ x {\mathcal{R}} y \Imp y {\mathcal{R}} x$.
\end{Def}




\begin{Def}[Relation d'équivalence]
${\mathcal{R}}$ est une relation d'équivalence lorsqu'elle est 
réflexive, symétrique et transitive.
\end{Def}


\begin{Ex}
 L'égalité est une relation d'équivalence.
\end{Ex}



\begin{Ex}[Relation de congruence modulo $n$ dans $\Z$]
Par définition: $$x\equiv y\ [n]
\hbox{(lire: \og $x$ est congru à $y$ modulo $n$\fg{} )} \Ssi
\exi k\in\Z,\ x-y=k\cdot n.$$
\begin{description}
\item[réflexive:] $x\equiv x [n]$: en effet, $x-x=0\cdot n$, et
$0\in\Z$.
\item[symétrique:] si $x\equiv y\ [n]$, $\exists k\in\Z$, $x-y=k\cdot n$;
alors $y-x=(-k)\cdot n$; or, si $k\in\Z$, $(-k)\in\Z$, donc $y\equiv x\
[n]$.
\item[transitive:] si $x\equiv y\ [n]$ et $y\equiv z\ [n]$, $\exi
k\in\Z$, $x-y=k\cdot n$ et $\exi l\in\Z$, $y-z=l\cdot n$. En
additionnant membre à membre ces deux égalités, on obtient
$x-z=(k+l)\cdot n$, or $(k,l)\in\Z^2$, donc $k+l \in\Z$, donc
$x\equiv z\ [n]$.
\end{description}
\end{Ex}



\begin{Exo}
Montrer que les relations suivantes sont des relations d'équivalence:
\begin{itemize}
\item Sur $\mathbb{Z}$, on écrit  $x \mathcal{R} y$ quand $x+y$ est pair.
\item Sur $\mathbb{R}$, on écrit $x \mathcal{R} y$ quand 
$\cos(2x)=\cos(2y)$.
\end{itemize}
\end{Exo}




\subsection{Classes d'équivalence}


\begin{Def}[Classe d'équivalence]
Soit $x$ un élément de $E$, et $\mathcal{R}$ une relation d'équivalence sur $E$.
On appelle \emph{classe d'équivalence} \index{classe d'équivalence} 
de cet élément l'ensemble des éléments de $E$ qui
 sont en relation avec $x$ (on dit encore: \og qui sont équivalents à $x$ \fg{}).
\end{Def}




\begin{Notation}
On note $\dot x$ la classe de l'élément
$x$: $\dot x=\{y\in E \mid y {\mathcal{R}} x\}$.
\end{Notation}

\begin{Exo}
Dans $\R$, on considère la relation binaire $\mathcal{R}$ définie par:
$x\mathcal{R}y$ ssi   $x^2 - y^2 = x- y$.
\begin{enumerate}
\item Vérifier que $\mathcal{R}$ est une relation d'équivalence.
\item Pour tout réel $x$, déterminer $\dot x$.
\end{enumerate}
\end{Exo}

\begin{Exo}
Dans $\R$, on considère la relation binaire $\mathcal{R}$ définie par:
$x\mathcal{R}y$ ssi   $x.e^{y}= y.e^{x}$.
\begin{enumerate}
\item Vérifier que $\mathcal{R}$ est une relation d'équivalence.
\item Pour tout réel $x$, déterminer le nombre d'éléments de $\dot x$.
\end{enumerate}
\end{Exo}



% \begin{Exo}
% On définit une relation sur l'ensemble des mots de la langue française de la façon suivante: \og le mot $M$ est lié au mot $N$ si $N$ est une anagramme\index{anagramme}\footnote{Mot obtenu par transposition des lettres d'un autre mot. Une anagramme intéressante: aimer - Marie. Le pseudonyme de Alcofribas Nasier est, à peu près, l'anagramme de François Rabelais.} de $M$.\fg{}
% Quelle est la classe d'équivalence du mot chien?
% \end{Exo}





% \begin{Th}
% Une classe d'équivalence n'est jamais vide. 
% \end{Th}

% \begin{Pre}
% En effet, la classe de $x$ contient toujours au moins l'élément $x$ lui-même, par réflexivité.
% \end{Pre}



\begin{Th}
L'intersection de deux classes d'équivalence distinctes est vide.
On dit aussi que les classes sont deux à deux disjointes.
\end{Th}


\begin{Pre}
On considère deux classes, $\dot x$ et $\dot y$, soit $z\in\dot x\inter\dot y$; $\qqs t\in\dot x$, on a $(t,x)\in G$; mais
$z\in\dot x$, donc $(z,x)\in G$, donc (symétrie) $(x,z)\in G$, donc
(transitivité) $(t,z)\in G$; mais $z\in\dot y$, donc $(z,y)\in G$, donc
(transitivité) $(t,y)\in G$, donc (finalement) $t\in\dot y$, et donc
$\dot x\sse\dot y$; raisonnement analogue pour tout $t\in\dot y$, qui
aboutit à $\dot y\sse\dot x$, et enfin (par double inclusion)
$\dot x=\dot y$; si deux classes ont un élément commun, elles sont
confondues; donc deux classes distinctes sont disjointes). 
\end{Pre}

\begin{Def}[Partition d'un ensemble]
Une \emph{partition}\index{partition} d'un ensemble $E$ est une famille
de sous-ensembles de $E$, 2 à 2 disjoints, et dont la réunion est égale à $E$.
\end{Def}



\begin{Th}
Les classes d'équivalence réalisent une partition de $E$.
\end{Th}

\begin{Pre}
Comme les classes sont des parties de $E$, leur réunion est une partie de
$E$.
Réciproquement, tout élément de $E$ appartient à une classe (\og tout élément est classé\fg{}). Donc $E$ est une partie de la réunion des classes; et $E$ est égal à la réunion des classes.
\end{Pre}

\begin{Ex}
On reprend la congruence modulo $n$, par exemple pour $n = 4$.On a:

$\dot 0=\{\ldots,-12,-8,-4,0,4,8,12,\ldots\}$

$\dot 1=\{\ldots,-11,-7,-3,1,5,9,13,\ldots\}$

$\dot 2=\{\ldots,-10,-6,-2,2,6,10,14,\ldots\}$

$\dot 3=\{\ldots,-9,-5,-1,3,7,11,15,\ldots\}$
 
\end{Ex}



\begin{Exo}
Soit $\mathcal{R}$ la relation d'équivalence suivante dans l'ensemble 
$A=\{1,2,3,4,5,6\}$:
$
\mathcal{R} = \{(1,1), (1,5), (2,2), (2,3), (2,6), (3,2), (3,3), (3,6), (4,4), (5,1), (5,5), (6,2), (6,3), (6,6)\}.
$
Trouver la partition de $A$ induite par $\mathcal{R}$, c'est-à-dire trouver les classes d'équivalence de $\mathcal{R}$.
\end{Exo}




\begin{Exo}
On considère l'ensemble des points du plan rapporté à
deux axes de coordonnées rectangulaires et deux points $P_1$ et
$P_2$ de coordonnées respectives $(x_1,y_1)$ et $(x_2,y_2)$; on
définit dans cet ensemble la relation binaire ${\mathcal{R}}$ par:
\begin{enumerate}
\item $P_1 {\mathcal{R}} P_2 \Ssi x_1y_1=x_2y_2$.
  Est-ce une relation d'équivalence? Si oui, étudier
ses classes.
\item Mêmes questions pour ${\mathcal{R}}$, définie par
$P_1 {\mathcal{R}} P_2 \Ssi x_1y_1=x_2y_2\ {\rm et}\ x_1x_2\geqslant 0$
\end{enumerate}
\end{Exo}





% \begin{Exo}
% Tenter de caractériser par son graphe une relation d'équivalence.
% \end{Exo}




% \subsection{Ensemble-quotient}

% \begin{Def}[Ensemble-quotient]
% Il s'agit de l'ensemble des classes d'équivalence de tous les éléments de $E$.
% \end{Def}


% \begin{Notation}
% $E/{\mathcal{R}}$.
% \end{Notation}


% Pour parler aisément d'une classe, on choisit un de ses éléments, 
% et cet élément, surmonté d'un point, sert à représenter la classe en question.
% Une fois que ce choix est fait, il est définitif, et il n'est plus question d'évoquer les autres éléments de cette classe, il faut
% se tenir, sous peine d'incohérence, au choix qui a été fait.



% \begin{Ex}[Congruence modulo 4]
% On choisit pour représentants les entiers $<4$, donc 0, 1, 2 et 3.
% L'ensemble-quotient est $\Z/4\Z=\{\dot 0,\dot 1,\dot 2,\dot 3\}$.
% \end{Ex}



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