CommeUnJeu · L1 PCSI

Relations binaires

⌚ ~35 min ▢ 4 blocs ✓ 13 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)$ et la divisibilité $\mid$ sur $\mathbb{N}$ sont des relations binaires.

Une telle relation peut posséder quatre propriétés structurelles : réflexivité, symétrie, anti\-symétrie et transitivité. Ces quatre mots forment le vocabulaire nécessaire pour dégager l'objet central de ce 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 », généralisant $\le$ sur $\mathbb{R}$. Un ordre peut être total (deux éléments quelconques se comparent, comme $\le$ sur $\mathbb{R}$) ou partiel (certains éléments sont incomparables, comme $\subset$ sur $\mathcal{P}(E)$ ou la divisibilité sur $\mathbb{N}$), et les diagrammes de Hasse visualisent les ordres partiels avec netteté. En chemin on rencontre une autre relation utile : la congruence modulo $\alpha$ sur $\mathbb{R}$, dont le cas $\alpha = 2\pi$ formalise « les angles modulo un tour ».

I Relations binaires et leurs propriétés

Définition — Relation binaire et ses propriétés

Une relation binaire $\mathcal{R}$ sur un ensemble $E$ associe, à chaque couple $(x, y) \in E \times E$, la réponse « oui » ou « non » à la question « $x$ est-il en relation avec $y$ ? ». On écrit $x \, \mathcal{R} \, y$ lorsque la réponse est oui. Formellement, $\mathcal{R}$ est donnée par son graphe, la partie $\{(x, y) \in E \times E \mid x \, \mathcal{R} \, y\}$ de $E \times E$. Une telle relation peut posséder 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$.

Ces quatre propriétés constituent le vocabulaire qui sert ci-dessous à définir les relations d'ordre.

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 Congruences dans $\mathbb{R}$ et $\mathbb{Z}$

La relation de congruence est une manière familière d'identifier deux nombres qui « coïncident à un pas fixé près ». Sur $\mathbb{R}$, la congruence modulo $\alpha$ relie deux 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 », constamment utilisée en trigonométrie. La même idée sur $\mathbb{Z}$ donne la congruence modulo $n$, qui relie les entiers ayant le même reste dans la division par $n$.

Définition — Congruence modulo

Pour $\alpha \in \mathbb{R}_+^*$, la congruence modulo $\alpha$ sur $\mathbb{R}$ est définie par $$ x \equiv y \pmod \alpha \iff \exists k \in \mathbb{Z}, \ x - y = k \alpha. $$ Le cas le plus utilisé est $\alpha = 2\pi$, noté $x \equiv y \, [2\pi]$.
Pour $n \in \mathbb{N}^*$, la congruence modulo $n$ sur $\mathbb{Z}$ est définie par $$ x \equiv y \pmod n \iff \exists k \in \mathbb{Z}, \ x - y = k n. $$

Dans les deux cas la relation est réflexive, symétrique et transitive : elle se comporte comme une « égalité à un multiple de $\alpha$ (resp. $n$) près ».

Exemple

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}$. Par exemple $\dfrac{\pi}{3} \equiv \dfrac{7\pi}{3} \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}$.
Dans $\mathbb{Z}$ modulo $5$ : $7 \equiv 2 \pmod 5$, $-3 \equiv 2 \pmod 5$ et $0 \equiv 5 \equiv 10 \pmod 5$, car les différences ($5$, $-5$, $5$, $10$) sont toutes multiples de $5$.

Compétences à pratiquer

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

III 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