CommeUnJeu · L1 MPSI

Relations binaires

⌚ ~51 min ▢ 6 blocs ✓ 18 exercices ➣ Prérequis : Ensembles

Une relation binaire sur un ensemble $E$ est la manière la plus générale d'exprimer un lien entre deux éléments de $E$ : une règle qui décide, pour tout couple $(x, y) \in E \times E$, si $x$ est « en relation avec » $y$ ou non. L'ordre $\le$ sur $\mathbb{R}$, l'égalité $=$ sur tout ensemble, l'inclusion $\subset$ sur $\mathcal{P}(E)$, la divisibilité $\mid$ sur $\mathbb{N}$, et la relation « avoir la même parité » sur $\mathbb{Z}$ sont des relations binaires.

Une telle relation peut combiner quatre propriétés structurelles : réflexivité, symétrie, anti\-symétrie et transitivité. Deux combinaisons précises donnent les grandes familles qui structurent le reste du chapitre :

Les relations d'équivalence (réflexive + symétrique + transitive). Elles regroupent les éléments « identiques à un critère près » --- parité, signe, congruence, même image par une application. Les classes d'équivalence forment une partition de l'ensemble sous-jacent, et ce théorème de partition est la pierre angulaire du chapitre.
Les relations d'ordre (réflexive + antisymétrique + transitive). Elles hiérarchisent les éléments et permettent de parler de « plus petit » et « plus grand ». Elles généralisent $\le$ sur $\mathbb{R}$ et admettent deux variantes : total (deux éléments quelconques sont comparables) et partiel (certains éléments sont incomparables). Les diagrammes de Hasse visualisent les ordres partiels avec netteté.

Le chapitre se ferme sur l'exemple arithmétique standard d'équivalence : les congruences dans $\mathbb{Z}$ (base de l'arithmétique modulaire) et dans $\mathbb{R}$ (qui formalise « les angles modulo $2\pi$ »).

I Relations binaires et leurs propriétés

Définition — Relation binaire

Une relation binaire $\mathcal{R}$ sur un ensemble $E$ est une partie quelconque de $E \times E$. On écrit $x \, \mathcal{R} \, y$ pour signifier $(x, y) \in \mathcal{R}$, lu « $x$ est en relation avec $y$ ». Une relation peut combiner les propriétés suivantes :

réflexive : $\forall x \in E, \ x \, \mathcal{R} \, x$ ;
symétrique : $\forall (x, y) \in E^2, \ x \, \mathcal{R} \, y \implies y \, \mathcal{R} \, x$ ;
antisymétrique : $\forall (x, y) \in E^2, \ (x \, \mathcal{R} \, y \text{ et } y \, \mathcal{R} \, x) \implies x = y$ ;
transitive : $\forall (x, y, z) \in E^3, \ (x \, \mathcal{R} \, y \text{ et } y \, \mathcal{R} \, z) \implies x \, \mathcal{R} \, z$.

Exemple

L'égalité $=$ sur n'importe quel ensemble $E$ est réflexive, symétrique, antisymétrique, transitive.
L'ordre $\le$ sur $\mathbb{R}$ est réflexif, antisymétrique, transitif (pas symétrique : $1 \le 2$ mais $2 \not\le 1$).
L'ordre strict $<$ sur $\mathbb{R}$ est antisymétrique et transitif mais pas réflexif ($1 \not< 1$).
La divisibilité $\mid$ sur $\mathbb{N}$ est réflexive, transitive, antisymétrique. Sur $\mathbb{Z}$, elle n'est plus antisymétrique : $2 \mid -2$ et $-2 \mid 2$ mais $2 \ne -2$.
« Avoir la même parité que » sur $\mathbb{N}$ est réflexive, symétrique, transitive (pas antisymétrique : $2$ et $4$ sont en relation, mais $2 \ne 4$).

Compétences à pratiquer

Tester les quatre propriétés fondamentales

II Relations d'équivalence

Les relations d'équivalence sont la « plus faible identification raisonnable » : elles permettent de dire « $x$ et $y$ sont identiques au critère choisi près » sans imposer aucune structure. Les trois axiomes (réflexive, symétrique, transitive) capturent exactement les trois propriétés attendues d'une « identification » : tout $x$ est identifié à lui-même, l'identification est à double sens, et les chaînes d'identifications se contractent. Le théorème de partition en est la récompense : les classes d'équivalence découpent $E$ en morceaux disjoints.

Définition — Relation d'équivalence

Une relation binaire $\mathcal{R}$ sur $E$ est une relation d'équivalence si elle est réflexive, symétrique et transitive. On note souvent les relations d'équivalence par des symboles comme $\sim$, $\equiv$, $\approx$.

Méthode — Démontrer que $\sim$ est une relation d'équivalence

Vérifier les trois axiomes successivement, chacun sur son propre bullet :

Réflexivité. Pour tout $x \in E$, $x \sim x$.
Symétrie. Pour tous $x, y \in E$, si $x \sim y$ alors $y \sim x$.
Transitivité. Pour tous $x, y, z \in E$, si $x \sim y$ et $y \sim z$, alors $x \sim z$.

Sauter l'un des trois axiomes laisse une relation au comportement très différent (un ordre est réflexif + transitif mais pas symétrique ; l'ordre strict $<$ est transitif seulement ; etc.).

Définition — Classe d'équivalence

Soient $\sim$ une relation d'équivalence sur $E$ et $x \in E$. La classe d'équivalence de $x$ pour $\sim$ est l'ensemble $$ \operatorname{cl}(x) = \{ y \in E \ \mid \ x \sim y \}. $$ Autres notations : $[x]$, $\bar{x}$, $\dot{x}$. Par réflexivité, $x \in \operatorname{cl}(x)$, donc la classe est non vide. Deux éléments équivalents ont la même classe : $x \sim y \iff \operatorname{cl}(x) = \operatorname{cl}(y)$.

Définition — Partition

Une partition de $E$ est un ensemble $\mathcal{U}$ de parties de $E$ tel que :

tout $A \in \mathcal{U}$ est non vide ;
les éléments de $\mathcal{U}$ sont deux à deux disjoints : pour $A, B \in \mathcal{U}$ avec $A \ne B$, $A \cap B = \emptyset$ ;
leur réunion vaut $E$ : $\bigcup_{A \in \mathcal{U}} A = E$.

Tout $x \in E$ appartient à exactement un élément de $\mathcal{U}$.

Méthode — Vérifier qu'$\mathcal{U}$ est une partition de $E$

Trois vérifications, dans l'ordre :

Non-vacuité. Tout $A \in \mathcal{U}$ contient au moins un élément.
Disjonction deux à deux. Pour $A, B \in \mathcal{U}$ avec $A \ne B$, $A \cap B = \emptyset$.
Recouvrement. Tout $x \in E$ appartient à un certain $A \in \mathcal{U}$.

Une partition peut s'exprimer de manière équivalente par une règle qui, à chaque $x \in E$, associe l'unique morceau le contenant. Les deux points de vue --- « liste des morceaux » et « règle d'affectation » --- sont interchangeables.

Theorem — Les classes forment une partition

Soit $\sim$ une relation d'équivalence sur $E$. L'ensemble des classes d'équivalence $$ \{ \operatorname{cl}(x) \ \mid \ x \in E \} $$ est une partition de $E$.

Preuve

Trois conditions à vérifier.

Non-vacuité. Pour tout $x \in E$, par réflexivité $x \sim x$, donc $x \in \operatorname{cl}(x)$, donc $\operatorname{cl}(x) \ne \emptyset$.
Disjonction deux à deux. Soient $\operatorname{cl}(x), \operatorname{cl}(y)$ deux classes avec $\operatorname{cl}(x) \cap \operatorname{cl}(y) \ne \emptyset$. Choisissons $z$ dans l'intersection : $x \sim z$ et $y \sim z$. Par symétrie, $z \sim y$ ; par transitivité depuis $x \sim z$ et $z \sim y$, $x \sim y$. Donc $\operatorname{cl}(x) = \operatorname{cl}(y)$. Par contraposée, deux classes distinctes sont disjointes.
Recouvrement. Pour tout $x \in E$, $x \in \operatorname{cl}(x)$, donc $E \subset \bigcup_{x \in E} \operatorname{cl}(x)$. L'inclusion inverse est triviale car chaque $\operatorname{cl}(x) \subset E$.

Exemple

Sur $\mathbb{Z}$ avec la relation « avoir la même parité », il y a exactement deux classes : les pairs $2\mathbb{Z}$ et les impairs $2\mathbb{Z}+1$. Elles sont non vides, disjointes, et leur réunion est $\mathbb{Z}$ --- une partition de $\mathbb{Z}$ en deux morceaux. Sur $\mathbb{R}$ avec la congruence modulo $2\pi$, les classes sont les « angles modulo un tour », une pour chaque $\theta \in [0, 2\pi[$ --- une infinité de classes, toujours deux à deux disjointes et recouvrant $\mathbb{R}$.

Compétences à pratiquer

Vérifier qu'une relation est une équivalence
Calculer des classes d'équivalence

III Congruences dans $\mathbb{R}$ et $\mathbb{Z}$

Les congruences sont les relations d'équivalence les plus familières. Dans $\mathbb{Z}$, la congruence modulo $n$ identifie les entiers ayant le même reste dans la division par $n$ --- c'est la base de l'arithmétique modulaire, dont les applications vont de la cryptographie aux codes correcteurs d'erreurs. Dans $\mathbb{R}$, la congruence modulo $\alpha$ identifie les réels dont la différence est un multiple entier de $\alpha$ --- le cas $\alpha = 2\pi$ est la formalisation standard des « angles modulo un tour ».

Définition — Congruence modulo

Pour $n \in \mathbb{N}^*$, la relation définie sur $\mathbb{Z}$ par $$ x \equiv y \pmod n \iff \exists k \in \mathbb{Z}, \ x - y = k n $$ est une relation d'équivalence sur $\mathbb{Z}$, appelée congruence modulo $n$.
Pour $\alpha \in \mathbb{R}_+^*$, la relation définie sur $\mathbb{R}$ par $$ x \equiv y \pmod \alpha \iff \exists k \in \mathbb{Z}, \ x - y = k \alpha $$ est une relation d'équivalence sur $\mathbb{R}$, appelée congruence modulo $\alpha$.

Exemple

Dans $\mathbb{Z}$ modulo $5$ : $7 \equiv 2 \pmod 5$, $-3 \equiv 2 \pmod 5$, $0 \equiv 5 \equiv 10 \pmod 5$. Il y a $5$ classes d'équivalence, les résidus $\{0, 1, 2, 3, 4\}$ modulo $5$.
Dans $\mathbb{R}$ modulo $2\pi$, la congruence est l'identité trigonométrique « même angle modulo un tour ». Pour tous réels $x, y$, $\cos x = \cos y$ et $\sin x = \sin y$ si et seulement si $x \equiv y \pmod {2\pi}$.
La congruence modulo $1$ sur $\mathbb{R}$ est « avoir la même partie fractionnaire » : $x \equiv y \pmod 1 \iff x - y \in \mathbb{Z}$.

Compétences à pratiquer

Calculer dans $\mathbb{Z}/n\mathbb{Z}$

IV Relations d'ordre

L'autre grande famille est celle des relations d'ordre. Où l'équivalence capture « l'identification », l'ordre capture la hiérarchie : plus petit, plus grand, avant, après. Les trois axiomes (réflexive, antisymétrique, transitive) découpent la combinaison juste : tout $x$ se compare à lui-même ; si $x \preccurlyeq y$ et $y \preccurlyeq x$ alors $x = y$ (pas d'égalités entre éléments distincts) ; les chaînes de comparaison se composent. Deux variantes coexistent --- total (deux éléments quelconques se comparent, comme $\le$ sur $\mathbb{R}$) et partiel (certains éléments sont incomparables, comme $\subset$ sur $\mathcal{P}(E)$ ou la divisibilité sur $\mathbb{N}$). Les diagrammes de Hasse sont la visualisation canonique des ordres partiels.

Définition — Relation d'ordre

Une relation binaire $\preccurlyeq$ sur $E$ est une relation d'ordre (ou ordre) si elle est réflexive, antisymétrique et transitive. Le couple $(E, \preccurlyeq)$ est alors appelé ensemble ordonné. Les relations d'ordre sont notées typiquement $\le$, $\preccurlyeq$, $\sqsubseteq$.

Définition — Ordre total$\virgule$ ordre partiel

Soit $(E, \preccurlyeq)$ un ensemble ordonné. Deux éléments $x, y \in E$ sont comparables si $x \preccurlyeq y$ ou $y \preccurlyeq x$. L'ordre $\preccurlyeq$ est :

total si deux éléments quelconques de $E$ sont comparables : $\forall (x, y) \in E^2, \ x \preccurlyeq y \text{ ou } y \preccurlyeq x$ ;
partiel dans le cas contraire (il existe des éléments incomparables).

Exemple

$(\mathbb{R}, \le)$, $(\mathbb{Q}, \le)$, $(\mathbb{Z}, \le)$, $(\mathbb{N}, \le)$ sont totalement ordonnés : la droite réelle est une unique ligne, aucun réel n'est incomparable à un autre.
$(\mathcal{P}(E), \subset)$ est partiellement ordonné dès que $|E| \ge 2$ : pour $a \ne b$ dans $E$, $\{a\}$ et $\{b\}$ sont incomparables (aucun n'est inclus dans l'autre).
$(\mathbb{N}, \mid)$ (divisibilité) est partiellement ordonné : $2$ et $3$ sont incomparables.

Un ordre partiel se visualise par un diagramme de Hasse : les n\oe{}uds sont les éléments, les arêtes vont vers le haut de $x$ à $y$ lorsque $x \preccurlyeq y$ sans élément strictement entre eux.

Le diagramme de Hasse de $(\mathcal{P}(\{1, 2, 3\}), \subset)$. Les paires $\{1\}, \{2\}, \{3\}$ sont deux à deux incomparables : c'est la nature « partielle » de l'ordre.

Exemple

Un autre ordre partiel : la divisibilité sur les diviseurs de $12$. L'ensemble $D_{12} = \{1, 2, 3, 4, 6, 12\}$ muni de $\mid$ a le diagramme de Hasse ci-dessous.

Lecture du diagramme : $2 \mid 4$ et $2 \mid 6$, mais $4$ et $6$ sont incomparables (aucun ne divise l'autre). Le plus petit élément est $1$, le plus grand est $12$.

Définition — Plus grand$\virgule$ plus petit élément

Soient $(E, \preccurlyeq)$ un ensemble ordonné, $A \subset E$ et $a \in A$.

$a$ est le plus grand élément de $A$ si $\forall x \in A, \ x \preccurlyeq a$. Lorsqu'il existe, il est unique et noté $\max(A)$.
$a$ est le plus petit élément de $A$ si $\forall x \in A, \ a \preccurlyeq x$. Lorsqu'il existe, il est unique et noté $\min(A)$.

L'existence n'est pas garantie : $\mathopen{]}0, 1[$ n'a ni plus grand ni plus petit élément dans $(\mathbb{R}, \le)$. L'unicité découle de l'antisymétrie : si $a, b$ sont tous deux plus grands éléments, alors $a \preccurlyeq b$ et $b \preccurlyeq a$, donc $a = b$.

Définition — Majorant$\virgule$ minorant

Soient $(E, \preccurlyeq)$ un ensemble ordonné et $A \subset E$. Un élément $m \in E$ est :

un majorant de $A$ si $\forall x \in A, \ x \preccurlyeq m$ ;
un minorant de $A$ si $\forall x \in A, \ m \preccurlyeq x$.

$A$ est majoré s'il admet au moins un majorant, minoré s'il admet au moins un minorant, borné si les deux. Le plus grand élément de $A$, lorsqu'il existe, est l'unique majorant de $A$ qui appartient à $A$.

Exemple

Dans $(\mathbb{R}, \le)$ :

$A = [0, 1]$. Majorants : $[1, +\infty[$. Minorants : $\mathopen{]}-\infty, 0]$. Plus grand élément : $1$. Plus petit élément : $0$.
$A = \mathopen{]}0, 1\mathclose{[}$. Majorants : $[1, +\infty[$. Minorants : $\mathopen{]}-\infty, 0]$. Aucun plus grand élément, aucun plus petit élément (les bornes $0, 1$ ne sont pas dans $A$).
$A = \mathbb{N}$. Minorants : $\mathopen{]}-\infty, 0]$. Aucun majorant (tout réel est dépassé par un entier).

Dans $(\mathcal{P}(\{1,2,3\}), \subset)$, l'ensemble entier $\{1,2,3\}$ est le plus grand élément et $\emptyset$ le plus petit.

Compétences à pratiquer

Reconnaître ordres partiels et totaux
Déterminer max$\virgule$ min$\virgule$ bornes