Bases mathématiques-Opérations entre ensembles-Ensembles ordonnés-Relation d’ordre-MPSI
Mathématiques MPSI
Bases mathématiques,Opérations entre ensembles,Ensembles ordonnés,Relation d’ordre,Mathématiques MPSI
Ensembles ordonnés
Relation d’ordre
Définition
Une relation d’ordre sur un ensemble $E$ non vide est une relation binaire $\prec$ qui vérifie les trois propriétés suivantes
– $\prec$ est réflexive
$$
\forall x \in E, \quad x \prec x .
$$
– est antisymétrique
– est transitive
$$
\forall x, y \in E, \quad x \prec y \text { et } y \prec x \quad \Rightarrow \quad x=y \text {. }
$$
$$
\forall x, y, z \in E, \quad x \prec y \text { et } y \prec z \quad \Rightarrow \quad x \prec z .
$$
Le couple $(E, \prec)$ est alors appelé ensemble ordonné.
Voici quelques exemples de relations d’ordre usuelles.
Exemple
La relation de comparaison «inférieur ou égal» $\leq$ est une relation d’ordre sur $\mathbb{N}, \mathbb{Z}, \mathbb{Q}, \mathbb{R},[a, b]$ En revanche, la relation «inférieur strictement» $<$ ne l’est pas puisqu’il lui manque la réflexivité.
Exemple
L’inclusion $\subset$ est une relation d’ordre sur $\mathscr{P}(E)$ avec $E$ non vide (l’antisymétrie correspond à la définition de l’égalité entre parties via la double-inclusion).
Exemple
La divisibilité définit une relation d’ordre sur $\mathbb{N} \backslash\{0\}$.
Exemple
Ordre lexicographique
L’ordre lexicographique (ou ordre du dictionnaire) est une relation d’ordre sur $\mathbb{N}^p$. Rappelons que cet ordre consiste à comparer les $p$-uplets en comparant les premières composantes puis en cas d’égalité en passant à la suivante comme on le fait pour classer les mots dans un dictionnaire; ainsi $(1,7,8,9)$ est plus petit pour cet ordre que $(1,7,9,3)$ : les deux premières coordonnées sont égales dans les deux 4-uplet donc on considère la troisième : on conclut en remarquant que 8 est plus petit que 9 .
Parmi ces relations d’ordre, toutes n’ont pas les mêmes propriétés.
Définition
Une relation d’ordre $\prec$ sur $E$ est totale si l’on peut comparer tous les éléments de $E$
$$
\forall x, y \in E, \quad x \prec y \text { ou } y \prec x .
$$
Une relation d’ordre qui n’est pas totale est partielle.
Parmi les exemples précédents, l’inclusion et la divisibilité sont des relations d’ordre partielles.
Exemple
Si $(E, \prec)$ est un ensemble ordonné et $F$ une partie de $E$, alors $\prec$ définit une relation d’ordre sur $F$, appelée relation d’ordre induite.
Si la relation $\prec$ sur $E$ est totale, alors la relation induite sur une partie $F$ est elle aussi totale (en revanche, la réciproque est fausse).
