Qu'est-ce que « Relation d’ordre » ?

Exemple 1.34

$(\R, \leq)$ est totalement ordonné. $(\mathcal{P}(E), \subseteq)$ est partiellement ordonné dès que $E$ a deux éléments : $\{a\}$ et $\{b\}$ ne sont pas comparables. La partie $A = \{\{a\}, \{b\}\}$ de $\mathcal{P}(\{a,b\})$ n’a pas de plus grand élément, et pourtant elle admet le majorant $\{a, b\}$ : la distinction entre plus grand élément et majorant reviendra, pour $\R$, au Chapitre 10.

Exemple 1.35 (Deux ordres sur la grille $\N^2$)

Sur les couples d’entiers naturels, comparons composante par composante : $(a, b) \preceq (a', b')$ lorsque $a \leq a'$ et $b \leq b'$ (l’ordre produit). C’est bien un ordre — chaque axiome est hérité coordonnée par coordonnée — mais un ordre partiel : $(1, 3)$ et $(2, 0)$ sont incomparables. Comparons maintenant comme un dictionnaire : $(a, b) \preceq_{\mathrm{lex}} (a', b')$ lorsque $a < a'$, ou bien $a = a'$ et $b \leq b'$ (l’ordre lexicographique). La transitivité demande une vérification en deux cas mais elle est vraie, et deux couples quelconques sont désormais comparables : l’ordre est total. Les deux ordres classent le même ensemble différemment — $(0, 100) \preceq_{\mathrm{lex}} (1, 0)$ alors que l’ordre produit ne dit rien — ce qui rappelle qu’un ordre est une structure que l’on choisit, et non une propriété de l’ensemble. La comparaison lexicographique est aussi l’astuce standard pour transformer plusieurs critères de tri en un seul.

Exemple 1.7 (Ordre des quantificateurs)

L’ordre de deux quantificateurs différents compte :

Dans la première assertion, $y$ peut dépendre de $x$ ; dans la seconde, un seul et même $y$ doit convenir pour tous les $x$. Deux quantificateurs identiques, en revanche, commutent toujours.