# Introduction aux mathématiques/Relations binaires

Ici $E$ désigne un ensemble.

## Généralités

Voir aussi : Relation (mathématiques)/Définition.

### Définition, exemples

On appelle relation binaire sur E, toute partie de E × E.
Si ${\mathcal {R}}$ est une telle relation sur E et si $x,y\in E$, on note $x{\mathcal {R}}y$ plutôt que $(x,y)\in {\mathcal {R}}$.
Exemples :
* Pour $E=\mathbb {N}$, posons ${\mathcal {R}}=\{(0,1),(3,7),(3,4),(1,1)\}$. On a $0{\mathcal {R}}1$, $3{\mathcal {R}}7$, $3{\mathcal {R}}4$ mais pas $3{\mathcal {R}}5$.
* L'égalité ($=$) sur $E$ provient de $\Delta =\{(x,x),x\in E\}$. Ici on préfèrera $x=y$ à $x\Delta y$.
* L'inclusion sur ${\mathcal {P}}(E)$ : ${\mathcal {R}}=\{(X,Y)\in {\mathcal {P}}(E)^{2}/X\subset Y\}$.
* L'ordre sur $\mathbb {R}$ : ${\mathcal {R}}=\{(x,y)\in \mathbb {R} ^{2}/x\leq y\}$.

### Qualités d'une relation binaire

Soit ${\mathcal {R}}$ une relation binaire sur E. ${\mathcal {R}}$ est dite :
* réflexive ssi $\forall x\in E,x{\mathcal {R}}x$ (les exemples 2, 3, et 4 ci-dessus illustrent cette propriété) ;
* transitive ssi $\forall x,y,z\in E,(x{\mathcal {R}}z\,{\text{et}}\,z{\mathcal {R}}y)\Rightarrow x{\mathcal {R}}y$ (exemples 1, 2, 3, et 4) ;
* symétrique ssi $\forall x,y\in E,x{\mathcal {R}}y\Rightarrow y{\mathcal {R}}x$ (exemples 2 et 3 si E est vide) ;
* antisymétrique ssi $\forall x,y\in E,x{\mathcal {R}}y\,{\text{et}}\,y{\mathcal {R}}x\Rightarrow x=y$ (exemples 1, 2, 3, et 4).
* complète ssi $\forall x,y\in E,x{\mathcal {R}}y\,{\text{ou}}\,y{\mathcal {R}}x$

## Relations d'équivalence

On appelle relation d'équivalence sur E toute relation binaire ${\mathcal {R}}$ sur E à la fois réflexive, transitive et symétrique.
Pour tout $x\in E$ on appelle classe d'équivalence de x modulo ${\mathcal {R}}$ la partie de E notée ${\overline {x}}=\{y\in E\mid x{\mathcal {R}}y\}$.
L'ensemble de ces classes d'équivalence, qui est une partie de ${\mathcal {P}}(E)$ est appelé ensemble quotient de $E$ par ${\mathcal {R}}$, noté $E/{\mathcal {R}}$.
L’application $\pi :E\rightarrow E/{\mathcal {R}},x\mapsto {\overline {x}}$. C'est une surjection, appelée surjection (ou projection) canonique.
$\forall x,y\in E\quad \left(x{\mathcal {R}}y\Rightarrow {\overline {x}}={\overline {y}}\right)$.
Par définition des classes et transitivité de ${\mathcal {R}}$, on a $x{\mathcal {R}}y\Rightarrow {\overline {y}}\subset {\overline {x}}$. Par symétrie de ${\mathcal {R}}$, on en déduit : $y{\mathcal {R}}x\Rightarrow {\overline {y}}\subset {\overline {x}}$, donc $x{\mathcal {R}}y\Rightarrow {\overline {x}}\subset {\overline {y}}$.
Les classes d'équivalence forment une partition de E.
D'abord, ce sont des parties de E.
Par réflexivité de ${\mathcal {R}}$, $x\in {\overline {x}}$, donc les classes sont non vides et leur réunion est égale à E.
Enfin, deux classes non distinctes sont disjointes, car deux classes non disjointes sont égales. En effet, si $z\in {\overline {x}}\cap {\overline {y}}$, c'est-à-dire si $x{\mathcal {R}}z$ et $y{\mathcal {R}}z$ alors, d'après le lemme, ${\overline {x}}={\overline {z}}={\overline {y}}$.

### Exercice

    Étant donnée une partition de $E$, définir une relation d'équivalence canoniquement associée à la partition. Quelles en sont les classes d'équivalence ?

## Relations d'ordre

Voir aussi : Relation (mathématiques)/Relation d'ordre.
On appelle relation d'ordre sur E toute relation binaire ${\mathcal {R}}$ sur E à la fois réflexive, transitive et antisymétrique.
On appelle ensemble ordonné un tel couple $(E,{\mathcal {R}})$.
On note plus volontiers $\leq$ une telle relation.
L'ordre est dit total si pour tous éléments $x,y\in E\quad \left(x\leq y\,{\text{ ou }}\,y\leq x\right)$. C'est le cas de l’ordre usuel sur $\mathbb {R}$ mais pas de l'inclusion sur ${\mathcal {P}}(E)$ dès que $E$ a au moins deux éléments.
Éléments remarquables d'un ensemble ordonné $(E,\leq )$ :
Soit $A\subset E$.
Alors il existe au plus un élément $m\in A$ tel que $\forall x\in A\quad x\leq m$.
Un tel élément est appelé plus grand élément de $A$, noté $\max A$. On définit de même un éventuel plus petit élément.
Une partie $A\subset E$ est dite majorée (resp : minorée) ssi $\exists m\in E/\forall x\in A,x\leq m$.
Un tel élément s’appelle un majorant (resp : minorant). $\max A$ s'il existe en est un.
Si l’ensemble des majorants (resp : minorants) de A admet un plus petit élément (resp : plus grand élément), celui-ci unique, s’appelle la borne supérieure (resp : inférieure) de A.

### Exercice

    Soit $\leq$ un ordre sur $E$. On définit $\geq$, par $\forall x,y\in E,\,x\geq y\Leftrightarrow y\leq x$. Montrer que c’est un ordre. Quels en sont les éléments remarquables ?

## Liens avec les applications

On s'intéresse ici à la compatibilité des applications avec les relations d'équivalence ou d'ordre.

### Avec l'équivalence

Soit $f:E\rightarrow F$ une application et $\sim$ une relation d'équivalence sur $E$. On dit que $f$ est compatible avec $\sim$ si $\forall x,y\in E\quad \left(x\sim y\Rightarrow f(x)=f(y)\right)$. Alors, l'application $f$ passe au quotient, c'est-à-dire qu'on peut définir une nouvelle application ${\tilde {f}}:E/\sim \to F,\ {\overline {x}}\mapsto f(x)$.
Exercices :
* Étant donnée une application $f:E\rightarrow F$, la rendre canoniquement surjective. On note encore $f$ la surjection obtenue.
* On considère la relation binaire sur $E$ définie par $\forall x,x'\in E\quad \left(x\sim x'\Leftrightarrow f(x)=f(x')\right)$. Montrer qu’il s'agit d'une relation d'équivalence. Que dire de l’application obtenue en passant au quotient ?

### Avec l’ordre

Soit $f:E\rightarrow F$ une application et $<,\leq$ deux ordres sur $E$ et $F$ respectivement. On dit que $f$ est croissante (resp. : décroissante) si :
$\forall x,x'\in E\quad \left(x<x'\Rightarrow f(x)\leq f(x')\right)$
(resp. : $\forall x,x'\in E\quad \left(x'<x\Rightarrow f(x)\leq f(x')\right)$).
Exemple : ${\mathcal {P}}(E)\to {\mathcal {P}}(E),\ A\mapsto A^{c}$ est décroissante pour l'inclusion.
Exercices :
* Soit $\Phi :{\mathcal {P}}(E)\rightarrow {\mathcal {P}}(E)$ croissante pour l'inclusion. Montrer que $\Phi$ admet un point fixe, c'est-à-dire une partie $A\subset E$ telle que $\Phi (A)=A$.
* Soit $f:E\rightarrow F$ et $g:F\rightarrow E$ deux injections. Montrer le théorème de Cantor-Bernstein : « Il existe une bijection de $E$ sur $F$. »
Indications :
* Considérer ${\mathcal {A}}:=\{A\subset E\mid \Phi (A)\subset A\}$ et $A_{0}:=\bigcap _{A\in {\mathcal {A}}}A$.
* Faire un dessin et appliquer 1/, ou aller voir sur Wikipédia…
| Applications | Entiers naturels |