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

\section{Relations}
On se donne deux ensembles $E$ et $F$.

\begin{Def}[Relation binaire, graphe]
On dit que:
 \begin{itemize}
\item l'on a défini une \emph{relation binaire} \index{relation binaire} ${\mathcal{R}}$ entre ces deux ensembles lorsque l'on s'est donné une partie $G$ de l'ensemble produit $E\times F$ ($G\sse E\times F$).
\item Cette partie est appelée \emph{graphe} \index{graphe} de la relation binaire.
\item Si $x (\in E)$ et $y (\in F)$ sont tels que $(x,y)\in G$, on dit que $x$ est \emph{en relation avec} $y$ par la relation ${\mathcal{R}}$.
 \end{itemize}
\end{Def}


Pour formaliser cette proposition, on utilise la notation 
$x {\mathcal{R}} y$ comme suit:

\begin{Notation}
$$x {\mathcal{R}} y \Ssi \quad\hbox{[\og x est en relation avec y\fg{}  ]}\Ssi
(x,y)\in G\quad\hbox{[$G$: graphe de la relation ${\mathcal{R}}$]}.$$
\end{Notation}

\begin{Exo}
On se place dans l'ensemble $E = \{1,2,3,\hdots,20\}$.

Représenter, dans le plan rapporté à deux axes de coordonnées rectangulaires, les graphes des relations binaires sur $E$ dont les définitions suivent:
\begin{itemize}
\item $x \mathcal{R} y \Longleftrightarrow x \leqslant y$.
\item $x \mathcal{R} y \Longleftrightarrow x | y$: $x$ divise $y$.
\item $x \mathcal{R} y \Longleftrightarrow x \equiv y[3]$: $x$ est congru à $y$ modulo 3.
\item $x \mathcal{R} y \Longleftrightarrow y = x^2$.
\end{itemize}
\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$.
\end{Rem}

\begin{Rem}
Il est possible que $x \mathcal{R} y$ sans que $y \mathcal{R} x$.
\end{Rem}


\begin{Exo}
A-t-on $y \mathcal{R} x$ quand $x \mathcal{R} y$, dans les relations binaires définies dans l'exercice précédent ?
\end{Exo}

\begin{Exo}
Sur l'ensemble des mots de la langue française, on définit la relation: \og le mot M est lié au mot N s'ils coïncident quand on écrit M à l'envers \fg{}.

Déterminer quelques couples de mots en relation, ainsi que des mots en relation avec eux-mêmes. Comment appelle-t-on de tels mots ?
\end{Exo}


\begin{Exoc}
Sur l'ensemble $\Z$ des entiers relatifs, on définit deux relations, notées respectivement $\Sigma$ et $\Delta$, de la façon suivante:
\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 ?

\noindent\textit{\underline{Réponse: }} $x \Sigma y \Leftrightarrow \exists k \in \Z, x+y = 2k \Leftrightarrow \exists k \in \Z, x+y-2y = 2k-2y = 2(k-y).$

Donc $x \Sigma y \Leftrightarrow \exists k' \in \Z,  x-y =  2k' \Leftrightarrow x \Delta y.$
\end{Exoc}

\section{Application d'un ensemble dans un autre}

\subsection{Application et relation fonctionnelle}


\begin{Def}[Application]
Une \emph{application}\index{application} de l'ensemble $E$ dans l'ensemble $F$ est une relation binaire particulière ${\mathcal{R}}$ entre $E$ et $F$, dont le graphe $G$ doit posséder les propriétés suivantes:

\begin{itemize}
 \item pour tout élément $x$ de $E$, il doit exister un élément $y$ de $F$ tel que $(x,y)$ soit élément de $G$;
 \item cet élément $y$ doit être unique.
\end{itemize}
\end{Def}



\noindent Voici la formalisation (partielle) de ces propositions:

\begin{itemize}
\item $\qqs x\in E,\ \exi y\in F,\ (x,y)\in G$
\item $\qqs x\in E,\ \qqs y\in F,\ \qqs y'\in F, [(x,y)\in G\ {\rm et}\ (x,y')\in G \Longrightarrow y=y']$.
\end{itemize}

\medskip

Il existe un intermédiaire entre relation et application \ldots

\begin{Def}[Relation fonctionnelle]
On parle de \emph{relation fonctionnelle}\index{relation!fonctionnelle} quand tout élément de l'ensemble de départ possède au plus une image.
\end{Def}

\begin{Rem}
Une application est donc une relation fonctionnelle particulière : tout élément de l'ensemble de départ possède exactement une image.
\end{Rem}


\begin{Exo}
Parmi les relations suivantes de $\mathbb{R}$ vers $\mathbb{R}$, repérez les relations fonctionnelles, repérez les applications:
\begin{enumerate}
\item $\mathcal{R} = \{ (x,y) \in \mathbb{R}^2, |y| = \sqrt{x} \}$
\item $\mathcal{R} = \{ (x,y) \in \mathbb{R}^2, xy = 1 \}$
\item $\mathcal{R} = \{ (x,y) \in \mathbb{R}^2, y-x+2 = 0 \}$
\end{enumerate}
\end{Exo}

%\noindent\textit{\underline{Réponse:}} Les deux dernières sont des relations fonctionnelles, et la dernière est la seule application. 

\subsection{Image et antécédent d'un élément}


On suppose dorénavant que $\mathcal{R}$ est une application. Pour un $x$ donné de $E$, il lui correspond un et un seul $y$ de $F$ qui est en relation avec lui par ${\mathcal{R}}$.

\begin{Def}
Cet unique $y$ est alors appelé \emph{image}\index{image} de $x$ par l'application définie par ${\mathcal{R}}$.
\end{Def}

\begin{Notation}
Si l'on désigne par $f$ cette application, l'expression \og $y$ est l'image de $x$ par $f$\fg{} est formalisée par $y=f(x)$.
De plus,  on formalise la proposition \og $f$ est une application de $E$ dans $F$\fg{} par $f: E\vers F$. La proposition \og $y$ est l'image de $x$ par $f$\fg{}   peut aussi être traduite par: $f: x \fc y$.
\end{Notation}



\begin{Exo}
 Interpréter chacune des situations suivantes au moyen d'une application. Pour cela, on définira deux ensembles $A$ et $B$ ainsi que $f: A\vers B$. Préciser dans chaque cas pourquoi il s'agit bien d'une application.

\begin{enumerate}
\item Le registre d'un hôtel qui possède 55 chambres.
\item Le numéro d'INSEE.
\item La parité d'un entier naturel.
\end{enumerate}

\end{Exo}

 
Réciproquement, soit $f$ une application\ldots

\begin{Def}[Antécédent]
Si $y$ est l'image de $x$ par $f$, alors $x$ est appelé un \emph{antécédent} \index{antécédent} de $y$ par $f$.
\end{Def}

Un quelconque élément $y$ de $F$ ne possède pas forcément d'antécédant par une application $f : E \longrightarrow F$. Et il n'y a pas forcément unicité quand il en possède : un $y$ de $F$ peut avoir plusieurs antécédants par une application $f$.

Les cas particuliers où tout $y$ de $F$ possède au plus un antécédant, et au moins un antécédant, sont étudiés dans les deux sections suivantes.

\subsection{Applications injectives}



\begin{Def}[Injectivité]
L'application $f:E \longrightarrow F$ est dite \emph{injective} \index{application!injective} quand tout $y \in F$ possède au plus un antécédant par $f$.
\end{Def}


\begin{Rem}
Le terme injection\index{injection} est synonyme d'\og application injective\fg{}.
\end{Rem}
 
L'injectivité d'une application peut se caractériser de la manière suivante.

\begin{Th}[Caractérisation des fonctions injectives]
$$\hbox{\og $f:E \longrightarrow F$ est une application injective\fg{}  } \Longleftrightarrow [ \forall x,x' \in E, f(x)=f(x') \Imp x=x' ]$$
\end{Th}

\begin{Exo}
Prouver, en utilisant la caractérisation ci-dessus, que les applications suivantes sont injectives :
\begin{enumerate}
\item $f : \R \longrightarrow \R, x \fc 2x+3$.
\item $f : \mathbb{R}^+ \longrightarrow \R, x \fc 3 x^2 +1$.
\end{enumerate}
\end{Exo}


\begin{Exo}
Prouver, en utilisant la caractérisation ci-dessus, que les applications suivantes ne sont pas injectives :
\begin{enumerate}
\item $f : \R \longrightarrow \R, x \fc |x|$.
\item $f : \R \longrightarrow \R, x \fc x^2$.
\end{enumerate}
\end{Exo}


\begin{Exo}
Tracez le graphe d'une application qui est injective, et d'une application qui ne l'est pas. Trouver une caractérisation de l'injectivité d'une application $f :E \longrightarrow F$, à partir du nombre d'intersections entre la courbe $\mathcal{C}_f$ et les droites verticales $y=b, b\in F$.
\end{Exo}


\begin{Exo}
Soit $f:E \longrightarrow F$ une application injective. Peut-elle perdre ce caractère injectif si on réduit l'ensemble d'arrivée ? Et si l'on réduit l'ensemble de départ ?

Que se passe-t-il si l'on change «réduit» en «augmente» dans les précédentes questions ?
\end{Exo}


\begin{Exo}
On suppose $g o f$ injective. Montrer que $f$ est injective. Est-ce que $g$ est obligatoirement injective ?
\end{Exo}


\subsection{Applications surjectives}

La définition d'une application $f$ exige seulement que chaque élément $x$ de $E$ admette une image (unique) $y$ dans $F$, mais pas que tout élément $y$ de $F$ admette un antécédent dans $E$.
S'il en est néanmoins ainsi, l'application est dite \emph{surjective}:
\begin{Def}
 Une application \emph{surjective}\index{application!surjective} $f: E\vers F$ est une application telle que tout $y$ de $F$ admette un antécédent dans $E$.
\end{Def}

\begin{Rem}
\emph{Surjection} est synonyme d'\og application surjective\fg{}. \index{surjection}
\end{Rem}


\begin{Exo}
Tracez le graphe d'une application qui est surjective, et d'une application qui ne l'est pas.
\end{Exo}

\begin{Exo}
Donnez des exemples (sous forme analytique) de fonctions surjectives, et de fonction qui ne le sont pas.
\end{Exo}

\subsection{Image d'un ensemble par une application}

D'une manière générale, on peut considérer l'ensemble des images des éléments de $E$ par une application $f$ de $E$ dans $F$ (ils en ont tous une, et une seule).

\begin{Def}[Image d'un ensemble par une application]
Cet ensemble, qui est évidemment une partie de $F$, est noté $f<E>$, et est appelé \emph{image de $E$ par $f$}: $$f<E>=\{f(x)\in F \mid x\in E\}$$
\end{Def}


\begin{Rem}
Si tous les éléments de $F$ ont un antécédent dans $E$ ($f$ est surjective), cela signifie que tout élément de $F$ est élément de $f<E>$, donc que $F\sse f<E>$. Comme on a remarqué par ailleurs que $f<E>\sse F$, on a, dans ce cas, $f<E>=F$.
\end{Rem}



Cette dernière remarque permet la formalisation suivante: 

\begin{Th}[Caractérisation de la surjectivité]
$$\hbox{\og $f$ est (une application) surjective\fg{}  } \Ssi f<E>=F$$
\end{Th}


\begin{Ex}
Soit l'application \og élévation au carré \fg{} $f: x \longmapsto x^2$ de $\R$ dans $\R$. Elle est:
\begin{itemize}
\item non surjective: $f < \R > = \R^+$,
\item non injective: $f(-2) = f(2) = 4$.
\end{itemize}
\end{Ex}

\begin{Exo}
On suppose $g o f$ surjective. Montrer que $g$ est surjective. Est-ce que $f$ est obligatoirement surjective ?
\end{Exo}

\subsection{Applications bijectives}


\begin{Def}[Applications bijectives]
Une application qui est à la fois injective et surjective est dite \emph{bijective} \index{application!bijective}. 
\end{Def}


\begin{Rem}
Synonyme d'\og application bijective\fg{}: bijection\index{bijection}.
\end{Rem}

\begin{Exo}
Dans chaque cas, dire si l'application $f:A \vers B$ est injective, surjective ou bijective.

\begin{enumerate}
\item $A = \R, B = \R, f(x) = x+7$
\item $A = \R, B = \R, f(x) = x^2+2x-3$
\item $A = \{ x \in \R | 4 \leqslant x \leqslant 9 \}, B = \{ x \in \R | 21 \leqslant x \leqslant 96 \}, f(x) = x^2+2x-3$
\item $A = \R, B = \R, f(x) = 3x-2|x|$
\item $A = \R, B = \R, f(x) = e^x+1$
\item $A = \N, B = \N, f(x) = x(x+1)$
\end{enumerate}
\end{Exo}


\begin{Th}
Dans le cas d'une bijection, à chaque élément $x$ de $E$ correspond un et un seul élément $y$ de $F$ (définition d'une application) et, réciproquement, à chaque (surjectivité) élément $y$ de $F$ correspond un et un seul (injectivité) élément $x$ de $E$.
\end{Th}


Cette dernière proposition est précisément l'affirmation de l'existence d'une application $g$ de $F$ dans $E$, telle que $x = g(y) \Longleftrightarrow f(x) = y $.




\begin{Def}[Application inverse]
Cette application est appelée \emph{application inverse}\index{application!inverse} de l'application $f$.
\end{Def}

\begin{Notation}
 On la note $f^{-1}$
\end{Notation}

\begin{Exo}
Reprendre l'exercice précédent, en trouvant l'application réciproque des applications bijectives.
\end{Exo}


% \begin{Rem}
% On peut démontrer que la bijectivité est une condition nécessaire et suffisante pour qu'une application admette une inverse.
% \end{Rem}

\begin{Ex}
Soit l'application \og multiplication par 2 \fg{} $f: x \longmapsto 2 x$ de $\R$ dans $\R$. Elle est surjective et injective.
Elle admet donc une application inverse: $f^{-1}: x \longmapsto \dfrac{x}{2}$.
\end{Ex}

\begin{Exo}
Soit $f: \Z \vers \Z$ définie par $f(n) = n + (-1)^n$.
\begin{enumerate}
 \item Montrer que $n$ et $f(n)$ sont toujours de parité différente.
\item Montrer que $f$ est bijective.
\item Calculer $f(f(n))$. En déduire une expression de $f^{-1}$ et résoudre l'équation $347 = n+(-1)^n$.
\end{enumerate}

\end{Exo}


\section{Cardinal et puissance d'un ensemble}

Il s'agit ici de proposer une réflexion sur la notion intuitive de \og nombre d'éléments d'un ensemble\fg{}, nécessaire pour pouvoir aborder ultérieurement les notions de dénombrabilité et de calculabilité, fondamentaux en informatique.


\subsection{Cas des ensembles finis}


On commence par prendre deux ensembles $E=\{a,b,c,d\}$ et $F=\{1,2,3\}$ et à remarquer que:
\begin{itemize}
 \item il est possible de définir une injection de $F$ dans $E$, mais pas une surjection,
 \item de définir une surjection de $E$ sur $F$, mais pas d'injection,
\end{itemize}
\ldots tout simplement parce qu'il n'y a \og pas assez\fg{} d'éléments dans $F$ (ou \og trop\fg{}  dans $E$).


Si l'on  veut pouvoir définir une bijection entre deux ensembles, il semble nécessaire et suffisant qu'ils aient le même \og nombre d'éléments\fg{} (on se limite ici au domaine fini).
Cette notion intuitive, résultat immédiat d'une simple opération de comptage, est reliée à la notion mathématique de mise en bijection avec une partie de $\Net$ de la forme $\{1\vir 2\vir\ldots\vir n\}$. 
 Ainsi, pour $n\in\Net$ donné, les ensembles à $n$ éléments sont tous ceux qui peuvent être mis en bijection avec $\{1\vir 2\vir\ldots\vir n\}$ (et, par convention, $\varnothing$ a 0 élément).


\begin{Def}[Cardinal d'un ensemble fini]
L'élément maximum $n$ de la partie finie $P=\{1\vir 2\vir\ldots\vir n\}$ de $\Net$ est un représentant du \emph{cardinal} \index{ensemble!cardinal}\index{cardinal} de tout ensemble en bijection avec $P$.
\end{Def}



Pas de problème donc lorsque l'on s'en tient aux ensembles finis, dont la définition mathématique est:


\begin{Def}[Ensemble fini]
Un ensemble est dit fini\index{ensemble!fini} s'il ne peut pas être mis en bijection avec une partie stricte de lui-même.
\end{Def}


\subsection{Cas des ensembles infinis}



Lorsque l'on se pose la question du \og nombre d'éléments\fg{}  d'un ensemble infini, on peut être tenté, dans un premier temps, de répondre par \og une infinité\fg{}, ce qui n'est pas satisfaisant pour au moins deux raisons: 

\begin{itemize}
 \item jusqu'à présent, le \og nombre d'éléments\fg{}  était un entier, et l'infini n'est pas un nombre entier,
 \item cela laisserait supposer que tous les ensemble infinis ont le même \og nombre d'éléments\fg{}
\end{itemize}



Une réflexion plus appronfondie apparaît comme nécessaire. On décide donc de se calquer sur le domaine fini\ldots 


\begin{Def}[Puissance d'un ensemble infini]
Deux ensembles ont \emph{même puissance}\index{ensemble!puissance}\index{puissance!d'un ensemble} (\og même nombre d'éléments\fg{}) si l'on peut les mettre en bijection.
\end{Def}



\begin{Ex}
Il existe des bijections entre $\N$ et l'ensemble des entiers pairs ($2\N$) ou impairs ($2\N+1$), qui conduisent à des formulations du style \og il y a autant d'entiers que d'entiers pairs \fg{}.
\end{Ex}
 

\begin{Rem}
$(2\N) \cup (2\N+1) = \N$, bien que ces trois ensembles \og on le même nombre d'éléments \fg{}, les deux premiers étants disjoints \ldots \'A rapprocher de $\infty\plinf=\infty$.
\end{Rem}


\begin{Rem}
Pour ce genre de raisons, on a tendance à abandonner ce vocabulaire (sur les nombres d'individus) pour dire simplement que ces ensembles ont même puissance.
\end{Rem}



\subsection{Puissance d'un ensemble infini}


Si $E$ est un ensemble infini, le résultat fondamental est:

\begin{Th}
Il est impossible de définir une surjection de $E$ sur $\mathcal{P}(E)$.
\end{Th}

\begin{Pre}
 Admis
\end{Pre}

Ce résultat montre que, même si $E$ est un ensemble infini, il ne peut être mis en bijection avec ${\cal P}(E)$, qui a donc \og strictement plus d'éléments\fg{}  que $E$.
Conséquemment, $\N$ et ses parties infinies, $\Z$, et même $\Q$ ont tous la même puissance, dite \emph{puissance du dénombrable} \index{puissance!du dénombrable}. Mais\ldots 


\begin{Def}[Puissance du continu]
${\cal P}(\N)$ n'est pas dénombrable, et est de puissance strictement supérieure, dite \emph{puissance du continu}\index{puissance!du continu}, dite 
 \emph{puissance de $\R$}.
\end{Def}


\noindent De même, ${\cal P}(\R)$ est de puissance strictement supérieure à $\R$, et ainsi de suite\ldots 

\begin{Th}
$\R$ est indénombrable. 
\end{Th}

\begin{Pre}[Démonstration de Cantor]
Supposons que $\mathbb{R}$ soit dénombrable.
On pourrait alors écrire la liste de TOUS les réels,
à partir du premier, en écriture décimale $r_1$, $r_2$, $r_3$, etc.

On choisit pour les nombres décimaux l'écriture qui ne comporte que des zéros à partir d'un certain rang, s'il y a ambiguïté.
Ainsi, l'on préférera l'écriture 1 à 0,9999999\ldots \ldots  (ces nombres sont égaux ; c'est-à-dire que l'on a affaire ici à deux représentations décimales d'un même nombre).


 Construisons alors le nombre $S$ de la manière suivante:
 \begin{enumerate}
 \item sa partie entière est 0,
 \item et pour sa partie décimale,
   \begin{itemize}
   \item le premier chiffre est différent du premier chiffre après la virgule de $r_1$,
   \item le deuxième chiffre est différent du deuxième chiffre après la virgule de $r_2$,
   \item \emph{etc.}
   \end{itemize}
 \end{enumerate}

Le nombre $S$ ne fait alors pas partie de la liste des réels, ce qui est contradictoire: l'hypothèse $\mathbb{R}$ dénombrable (on peut numéroter tous les réels avec $\mathbb{N}$) est erronée.
\end{Pre}
\section{Relations d'ordre}
Dans ce paragraphe, on se place dans le cas où $E=F$.
Soit ${\mathcal{R}}$ une relation binaire définie dans un ensemble $E$, de graphe $G$.

\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,x)\in G$$
\end{Def}


\begin{Rem}
 C'est-à-dire $\qqs x\in E,\ x {\mathcal{R}} x$, ou encore: la diagonale de $E^2$ est incluse dans $G$.
\end{Rem}



\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\in E,\ \qqs y\in E,\ (x,y)\in G ~{\rm et}\ (y,x)\in G\ \Imp x=y$$
\end{Def}


\begin{Rem}
 C'est-à-dire $\qqs(x,y)\in E^2,\ x {\mathcal{R}} y\ {\rm et}\ y {\mathcal{R}} x\Imp\ x=y$.
\end{Rem}



\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,y)\in G\ {\rm et}\ (y,z)\in G
\Imp (x,z)\in G$$
\end{Def}


\begin{Rem}
C'est-à-dire: $\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$. 
\end{Rem}


\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 un ensemble à $n$ éléments, combien y a-t-il de relations\ldots 
\begin{enumerate}
\item réflexives~? 
\item symétriques~?
\end{enumerate} 
\end{Exo}



\begin{Exo}
Déterminer quand une relation $\mathcal{R}$ dans un ensemble $A$ est 
\begin{enumerate}
\item non réflexive,
\item non symétrique,
\item non transitive,
\item non antisymétrique.
\end{enumerate}
\end{Exo}


\begin{Exo}
Donner des exemples de relation $\mathcal{R}$ dans $\{1,2,3\}$ ayant les propriétés suivantes:
\begin{enumerate}
\item $\mathcal{R}$ est symétrique,
\item $\mathcal{R}$ n'est ni symétrique ni antisymétrique,
\item $\mathcal{R}$ est transitive mais $\mathcal{R} \cup \mathcal{R}^{-1}$ n'est pas transitive.
\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} lorsqu'elle est réflexive, antisymétrique et transitive.
\end{Def}


\begin{Ex}[Exemples de relations d'ordre]
Quelques relations d'ordre: 
\begin{itemize}
\item $(\R,\leqslant)$
\item $({\cal P}(E),\sse)$
\end{itemize}
\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[reflexive:] $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é}.



\subsection{Ordre partiel, ordre total}

Une relation d'ordre définie dans un ensemble $E$ peut posséder une propriété supplémentaire, celle selon laquelle tous les éléments de $E$ sont comparables entre eux.
On formalise comme suit:


\begin{Def}[Relation d'ordre totale]
Une relation d'ordre qui possède cette dernière propriété est dite relation d'\emph{ordre total}\index{relation!d'ordre!totale}, et la structure algébrique correspondante est celle d'\emph{ensemble totalement ordonné}\index{ensemble!totalement ordonné}.
\end{Def}


\begin{Rem}
Cette propriété est aussi équivalente à: $$\qqs x\in E,\ \qqs y\in E,\ x\ {\mathcal{R}}\ y\ {\rm ou}\ y {\mathcal{R}} x$$
\noindent ou encore: \og si $x$ n'est pas en relation avec $y$, alors $y$ est en relation avec $x$ \fg{}.
\end{Rem}


\begin{Def}[Relation d'ordre partiel]
Dans le cas contraire, il existe des éléments qui ne sont pas comparables: on parle alors d'\emph{ordre partiel} \index{relation!d'ordre!partiel}.
\end{Def}


\begin{Ex}
$\leqslant$ est une relation d'ordre totale dans $\R$.
\end{Ex}

\begin{Ex}
$\subset$ dans $\mathcal{P}(E)$, et $|$ dans $\N$ sont des relations d'ordre partiels.
\end{Ex}



\begin{Exo}
Parmi les relations suivantes sur l'ensemble $E$, repérez les relations d'ordre, les relations d'ordre total:
\begin{enumerate}
\item $E = \mathbb{Z}$, $x \mathcal{R} y \Leftrightarrow \exists k \in \mathbb{N}: x = y^k$.
\item $E = \mathbb{N}$, $x \mathcal{R} y \Leftrightarrow x<y$.
\item $E = \mathbb{R}$, $x \mathcal{R} y \Leftrightarrow x^2 = y^2$.
\item $E = \mathbb{R}^2$, $(x_1,x_2) \mathcal{R} (y_1,y_2) \Leftrightarrow (x_1 \leqslant y_2) \et (x_2 \leqslant y_1)$.
\end{enumerate}
\end{Exo}



\begin{Exo}
Tenter de caractériser par son graphe une relation d'ordre (partiel, total).
\end{Exo}


\begin{Exo}
Définir, par leurs graphes, les relations d'ordre dans E qui comportent respectivement le moins et le plus possible de points; que peut-on dire de ces relations? 
\end{Exo}







\subsection{\'Eléments maximaux}

Soit $(E,{\mathcal{R}})$ un ensemble ordonné et $A$ une partie de $E$. Quelques définitions\ldots 


\begin{Def}[Majorant]
On appelle \emph{majorant} \index{majorant} de $A$ tout élément $M$ de $E$ tel que, quel que soit $a\in A$, $a{\mathcal{R}}M$.
\end{Def}


\begin{Def}[Partie majorée]
La partie $A$ de $E$ est dite \emph{majorée}\index{partie majorée} s'il existe un majorant de $A$.
\end{Def}

\begin{Exo}
Trouvez des exemples de majorants et de parties majorées sur 
$\N$ et 
$\R$.
\end{Exo}


\begin{Rem}
Il existe des parties non majorées ($\mathcal{R}^+$ pour $\leqslant$ dans $\R$)
\end{Rem}

\begin{Rem}
Il peut exister une infinité de majorants pour une partie majorée.
\end{Rem}


\begin{Def}[Minorant]
On appelle \emph{minorant} \index{minorant} de $A$ tout élément $m$ de $E$ tel que, quel que soit $a\in A$, $m{\mathcal{R}}a$.

On parle aussi de partie minorée.
\end{Def}

\begin{Exo}
Trouvez des exemples de minorants et de parties minorées sur 
$\mathbb{Z}$ et 
$\mathbb{Q}$.
\end{Exo}



\begin{Def}[Élément maximum]
On appelle \emph{élément maximum} \index{maximum} de $A$ un élément de $A$ qui est majorant de $A$.
\end{Def}
 
\begin{Exo}
Trouvez des exemples d'élément maximum sur $\mathbb{N}$ et 
$\R$.
\end{Exo}

\begin{Notation}
 $\max A$.
\end{Notation}

\begin{Rem}
 Si $A$ est non majorée, il est exclu qu'elle admette un élément maximum.
 Cet élément maximum n'existe pas toujours, même pour une partie majorée. Ainsi, l'intervalle réel ]2,3[ est majoré, mais n'a pas d'élément maximum.
Cependant, s'il existe, cet élément est unique.
\end{Rem}



\begin{Def}[Élément minimum]
 On appelle \emph{élément minimum} \index{minimum} de $A$ un élément de $A$ qui est minorant de $A$.
\end{Def}
 

\begin{Notation}
 $\min A$.
\end{Notation}

\begin{Exo}Etant donné 
$B=\{1,2,3,4,5\}$ 
ordonné selon la relation 
$4 < 2$,
$5<2$,
$5<3$,
$2<1$,
$3<1$.
Trouver $\min A$ et $\max A$. 
\end{Exo}



\begin{Def}[Borne supérieure]
On appelle \emph{borne supérieure}\index{borne!supérieure} de $A$ l'élément minimum, s'il existe, de l'ensemble des majorants de $A$.
\end{Def}
 

\begin{Notation}
 $\sup A$.
\end{Notation}


\begin{Def}[Borne inférieure]
 On appelle \emph{borne inférieure}\index{borne!inférieure} de $A$ l'élément maximum de l'ensemble des minorants de $A$.
\end{Def}
 

\begin{Notation}
 $\inf A$.
\end{Notation}



\begin{Exo}
Trouvez des exemples de bornes sup et de bornes inf sur $\R$.
\end{Exo}

\begin{Exo}[Relations d'ordre en Algèbre de Boole]
Soit $\cal A$ une algèbre de Boole.

On considère la relation binaire, de symbole $<$, définie par $$a<b \Ssi a+b=b.$$
\begin{enumerate}
\item Montrer qu'il s'agit d'une relation d'ordre.
\item Montrer que $a<b\ \Ssi\ a\cdot b=a$.
\item Montrer que, $\forall (a,b,c)\in {\cal A}^3,\ b\cdot c<a\cdot b+{\sur a}\cdot c$.
\item On définit la relation binaire $\sse$ par: $a\sse b$ si et seulement si 
$a\cdot{\sur b}=0$; montrer que c'est une relation d'ordre. 
\item Comparer $<$ et $\sse$.
\item En utilisant l'une ou l'autre des définitions ci-dessus pour la relation d'ordre, trouver,
lorsqu'ils existent, les éléments $\sup \{a,b\}$ et $\inf \{a,b\}$. 
Trouver $\max {\cal A}$ et
$\min {\cal A}$.
\end{enumerate}
\end{Exo}




% \begin{Exo}[Une relation d'ordre]
% On considère l'ensemble des points d'un plan affine euclidien, et on y définit une relation binaire (symbole $\leqslant $) par $P_1\leqslant P_2 \Ssi (x_1\leqslant x_2\  {\rm et}\ y_1\leqslant y_2)$.

% \begin{enumerate}
%  \item Définir, lorsqu'ils existent, les points $\sup\{P_1,P_2\}$ et $\inf\{P_1,P_2\}$.
%  \item Existent-ils toujours, quels que soient les points $P_1$ et $P_2$ ?
% \end{enumerate}
% \end{Exo}


\begin{Th}
Il est clair que:
\begin{itemize}

\item dans certains cas, les éléments définis ici n'existent pas,

\item que l'élément maximum est aussi borne supérieure.
\end{itemize}

\noindent Et finalement, pour une partie $A$ d'un ensemble ordonné $E$:

\begin{itemize}
 \item $A$ peut ne pas être majorée.
\item Si $A$ est majorée, elle peut ne pas admettre de borne supérieure.
\item Si $Sup A$ existe ($A$ est majorée), $A$ peut ne pas admettre d'élément maximum.
\item Si $Max A$ existe, alors $Sup A = Max A$.
\end{itemize}

\noindent\ldots et on a les mêmes résultats pour les parties minorées.
\end{Th}




\begin{Ex}
 Cas de $E=\{x\in\Q\mid x\leqslant 32\}$.
\begin{itemize}
\item ensemble majoré de nombres réels
\item 56, 32 sont majorants
\item ensemble $E'$ des majorants: $E'=\{y\in\Q\mid y\geqslant 32\}$
\item $\max E=32$
\item $\min E'=32$, donc $\sup E=32$.
\end{itemize}
\end{Ex}

\begin{Ex}
Cas de $E=\{x\in\Q\mid x<32\}$.
\begin{itemize}
\item ensemble majoré de nombres réels
\item 56, 32 sont majorants
\item ensemble $E'$ des majorants: $E'=\{y\in\Q\mid y\geqslant 32\}$
\item $E$ n'a pas d'élément maximum
\item $\min E'=32$, donc $\sup E=32$.
\end{itemize}
\end{Ex}

\begin{Exo}
Etant donné $A=\{1,2,3,4,\ldots\}= \N \setminus\{1\}$ ordonné par 
\og $x$ divise $y$ \fg{}.
\begin{enumerate}
\item Trouver tous les éléments minimaux;
\item Trouver tous les éléments maximaux.
\end{enumerate}
\end{Exo}

\begin{Exo}
Soit  $W=\{1,2,3,4,\ldots,8\}$ ordonné comme à la figure~\ref{fig:ordre:10.6} et
le sous-ensemble $V=\{4,5,6\}$ de $W$.
\begin{enumerate}
\item Trouver l'ensemble des majorants de $V$;
\item Trouver l'ensemble des minorants de $V$;
\item $\sup(V)$ et $\inf(V)$ existent-ils ?
\end{enumerate}
\end{Exo}
\begin{figure}[h]
\begin{center}
\includegraphics[width=3cm]{ensembles/relExo.eps}
\end{center}
\caption{Relation d'ordre particulière\label{fig:ordre:10.6}}
\end{figure}




\subsection{Treillis}

%\subsubsection{Cas des ensembles totalement ordonnés}

Dans un ensemble totalement ordonné, si l'on choisit une paire d'éléments quelconques $(x,y)$ il est possible de décider lequel est le plus petit et lequel est le plus grand.
Ainsi, l'ensemble $\{x\vir y\}$ admet un élément minimum et un élément maximum;
ces deux éléments sont aussi (respectivement) borne inférieure et supérieure, on peut écrire $\inf\{x\vir y\}=x$ et $\sup\{x\vir y\}=y$.
L'existence de ces deux éléments est assurée, ce qui n'est pas le cas dans un ensemble qui n'est que partiellement ordonné.



%\subsubsection{
Dans des ensembles partiellement ordonnés,
il existe cependant des paires d'éléments $(x,y)$ qui ne sont pas comparables.
Pour une telle paire, les éléments $\min\{x\vir y\}$ et $\max\{x\vir y\}$ ne sont pas définis.
Néanmoins, il se peut que les éléments $\inf\{x\vir y\}$ et
$\sup\{x\vir y\}$ soient eux définis.



Si cette propriété est vérifiée pour tous les couples d'éléments $(x,y)$, alors l'ensemble est un treillis:


\begin{Def}[Treillis]
Un ensemble ordonné est un \emph{treillis} \index{treillis} lorsque toute partie finie admet une borne sup et une borne inf.
\end{Def}

\begin{Rem}
 Il suffit que la propriété soit vraie pour deux éléments distincts (\emph{i.e.} une partie à deux éléments) pour qu'elle soit vrai pour toutes les parties finies. (On l'admettra).
\end{Rem}

% \begin{Exo}
% Démontrez l'assertion de la remarque précédente.
% \end{Exo}


\begin{Def}[Treillis complet]
 Si la propriété est vrai pour toute partie, alors le treillis est dit \emph{complet}\index{treillis!complet}.
\end{Def}


\begin{Ex}
Un ensemble totalement ordonné est toujours un treillis. 
\end{Ex}


\begin{Rem}
 Cette notion n'offre un intérêt que dans le cas d'un ensemble partiellement ordonné, car l'existence d'une borne inférieure et d'une borne supérieure pour tout couple (et donc pour toute partie finie) permet de les comparer aux autres par l'intermédiaire de ces bornes, même si on ne peut pas les comparer entre eux.


En effet, on a toujours $\inf\{x\vir y\}\leqslant x\leqslant \sup\{x\vir
y\}$ et $\inf\{x\vir y\}\leqslant y\leqslant \sup\{x\vir y\}$ (on reprend les exemples vus plus haut).
\end{Rem}




\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). Montrer que cette relation est une relation d'ordre. $E$ est-il totalement ordonné par cette relation ?
Est-il un treillis ?

\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,y)\in G \Imp (y,x)\in G$$
\end{Def}



\begin{Rem}
 Ou encore: $\qqs x\in E, \qqs y\in E,\ x {\mathcal{R}} y \Imp y {\mathcal{R}} x$.
\end{Rem}


\begin{Exo}
 Est-ce qu'une relation sur un ensemble A dont le graphe est constitué uniquement de couples (x,x) est symétrique ? transitive ?
\end{Exo}




\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{itemize}
\item réflexivité: $x\equiv x [n]$: en effet, $x-x=0\cdot n$, et
$0\in\Z$.
\item symétrie: 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 transitivité: 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
aditionnant 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{itemize}
C'est bien une relation d'équivalence. 
\end{Ex}



\begin{Exo}
Sur $\mathbb{Z}$, on écrit \og $x \mathcal{R} y$ quand $x+y$ est pair. \fg{}

Montrez que $\mathcal{R}$ est une relation d'équivalence.
\end{Exo}

\begin{Exo}
Sur $\mathbb{R}$, on définit la relation \og $x \mathcal{R} y$ quand 
$\cos(2x)=\cos(2y)$\fg{}.

Montrez que $\mathcal{R}$ est une relation d'équivalence.
\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}
Trouvez les classes d'équivalences des deux exercices précédents.
\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.
\end{Th}

\begin{Rem}
 On dit aussi que les classes sont deux à deux disjointes.
\end{Rem}


\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}[Une relation d'équivalence]
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:
$$P_1 {\mathcal{R}} P_2 \Ssi x_1y_1=x_2y_2$$
\begin{itemize}
\item S'agit-il d'une relation d'équivalence? Si oui, étudier
les classes d'équivalence.
\item Mêmes questions pour la relation ${\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{itemize}
\end{Exo}





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


\begin{Exo}
Définir, par leurs graphes, les relations d'équivalence dans $E$ qui comportent respectivement le moins et le plus possible de points.
Que peut-on dire de ces relations? 
\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}



\section{Compatibilité entre une opération et une relation binaire}

\begin{Def}
La relation binaire (dans $E$) de symbole ${\mathcal{R}}$ est dite
\emph{compatible avec l'opération} (définie dans $E$) de symbole $\circ$ lorsque, quels que soient les éléments $x$, $x'$, $y$ et $y'$ de $E$: si $x{\mathcal{R}}x'$ et si $y{\mathcal{R}}y'$, alors $(x\circ y){\mathcal{R}}(x'\circ y')$
\end{Def}


Autrement dit, l'opération conserve la relation.


\begin{Ex}
On considère la relation classique d'inégalité dans $\R$: si on a $x\leqslant x'$ et $y\leqslant y'$, on peut écrire $x+x'\leqslant y+y'$.

Ce résultat est bien connu: on a le droit \og d'additionner des inégalités membre à membre\fg{}. En d'autres termes, l'addition des réels est compatible avec l'inégalité.


Mais, de $-2\leqslant 1$ et de $-3\leqslant -1$, on ne peut pas déduire que $6\leqslant -1$\ldots  On n'a pas le droit de \og multiplier des inégalités membre à membre\fg{}.

La multiplication des réels, quant a elle, n'est donc pas compatible avec l'inégalité. 
\end{Ex}



\begin{Exo}[Congruences modulo $n$]
Montrer que la relation de congruence modulo $n$ dans $\Z$ définie en cours est compatible avec addition et multiplication.

Établir les tables des opérations que l'on peut alors définir dans les ensembles $\Z/5\Z$, $\Z/6\Z$.
\end{Exo}

Lorsqu'une relation d'équivalence est compatible avec une opération, on peut définir dans {l'ensemble-quotient} une opération, dite \emph{induite} de celle qui existe dans l'ensemble d'origine.






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