Introduction aux mathématiques/Relations binaires

Début de la boite de navigation du chapitre

Ici $E$ désigne un ensemble.

fin de la boite de navigation du chapitre

Généralités

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

Définition, exemples

Définition et notation : relations binaires

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 :

1. 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$.
2. L'égalité ($=$) sur $E$ provient de $\Delta =\{(x,x),x\in E\}$. Ici on préfèrera $x=y$ à $x\Delta y$.
3. L'inclusion sur ${\mathcal {P}}(E)$ : ${\mathcal {R}}=\{(X,Y)\in {\mathcal {P}}(E)^{2}/X\subset Y\}$.
4. 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

Définitions et notations : relation d'équivalence, classes d'équivalence, ensemble quotient, surjection canonique

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.

Début d'un lemme

Lemme

$\forall x,y\in E\quad \left(x{\mathcal {R}}y\Rightarrow {\overline {x}}={\overline {y}}\right)$.

Fin du lemme

Démonstration

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

 

Proposition

Les classes d'équivalence forment une partition de E.

Démonstration

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.

Définitions et notations : relations d'ordre, ensembles ordonnés, ordres totaux

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 )$ :

Proposition et définition : plus petit et plus grand éléments

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.

Définitions : majorants, minorants, bornes supérieure et inférieure

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 :

1. Étant donnée une application $f:E\rightarrow F$, la rendre canoniquement surjective. On note encore $f$ la surjection obtenue.
2. 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

Définition : application croissante ou décroissante

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 :

1. 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$.
2. 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 :

1. Considérer ${\mathcal {A}}:=\{A\subset E\mid \Phi (A)\subset A\}$ et $A_{0}:=\bigcap _{A\in {\mathcal {A}}}A$.
2. Faire un dessin et appliquer 1/, ou aller voir sur Wikipédia…