Relation d'ordre, ordre total, ordre partiel : définition (MPSI)
Relation d'ordre, ordre total, ordre partiel
Une relation d'ordre sur $E$ est une relation binaire réflexive, antisymétrique et transitive. On la note souvent $\preccurlyeq$ et on dit que $(E, \preccurlyeq)$ est un ensemble ordonné.
Deux éléments $x, y$ sont comparables si $x \preccurlyeq y$ ou $y \preccurlyeq x$. L'ordre est total si deux éléments quelconques de $E$ sont toujours comparables ; sinon il est partiel.
Exemples de référence
- $\leq$ sur $\mathbb{R}$ (ou $\mathbb{N}, \mathbb{Z}, \mathbb{Q}$) est un ordre total.
- L'inclusion $\subset$ sur $\mathcal{P}(E)$ est une relation d'ordre : réflexive ($A \subset A$), antisymétrique (c'est la double inclusion), transitive. Si $E$ contient deux éléments distincts $a$ et $b$, l'ordre est partiel : ni $\{a\} \subset \{b\}$, ni $\{b\} \subset \{a\}$.
- La divisibilité $|$ sur $\mathbb{N}$ est un ordre partiel : $2$ et $3$ ne sont pas comparables.
Démonstration : Relation d'ordre, ordre total, ordre partiel
La divisibilité est une relation d'ordre sur $\mathbb{N}$
Rappel : $a \mid b$ s'il existe $k \in \mathbb{Z}$ tel que $b = ka$.
- Réflexivité : $a = 1 \cdot a$.
- Transitivité : si $b = ka$ et $c = \ell b$, alors $c = (\ell k) a$.
- Antisymétrie : soit $a, b \in \mathbb{N}$ avec $b = ka$ et $a = k'b$, où $k, k' \in \mathbb{Z}$. Si $a = 0$, alors $b = k \cdot 0 = 0 = a$. Sinon $a > 0$, et $a = k'b$ impose $b \neq 0$, donc $b > 0$. Alors $a = k'ka$ donne $kk' = 1$. Comme $a, b > 0$, la relation $b = ka$ impose $k > 0$, et de même $k' > 0$. Deux entiers strictement positifs de produit $1$ valent $1$, donc $k = 1$ et $b = a$.
Antisymétrique ne veut pas dire non symétrique
Sur $\mathbb{Z}$, la divisibilité n'est pas antisymétrique : $2 \mid -2$ et $-2 \mid 2$, mais $2 \neq -2$. Ce n'est donc pas une relation d'ordre sur $\mathbb{Z}$.
L'antisymétrie n'est pas la négation de la symétrie : l'égalité sur $E$ est à la fois symétrique et antisymétrique. De même, la relation stricte $<$ n'est pas une relation d'ordre au sens du programme, car elle n'est pas réflexive.
S’entraîner
- Une relation d'équivalence sur $\mathbb{R}$
- L'ordre produit sur $\mathbb{R}^2$
- Applications idempotentes et applications vérifiant $f \circ f \circ f = f$ (type Mines-Ponts)
Dans le cours
Ensembles et applications : Relation d'ordre, ordre total, ordre partiel