Ordre lexicographique

En mathématiques, un ordre lexicographique est un ordre que l'on définit sur les suites finies d'éléments d'un ensemble ordonné (ou mots construits sur un tel ensemble). Sa définition reprend le concept de classement des mots dans un dictionnaire, d'où son nom. La principale propriété de l'ordre lexicographique est de conserver le caractère total de l'ordre initial. On peut définir de façon analogue un ordre lexicographique sur des produits cartésiens d'ensembles ordonnés, dont les éléments sont donc des n-uplets, c’est-à-dire, en d'autres termes, des suites finies de longueur fixée.

On se donne deux ensembles ordonnés ${\displaystyle (A,\leqslant )}$ et ${\displaystyle (B,\leqslant )}$ , l'ordre étant noté de la même façon pour les deux ensembles, et l'ordre strict associé noté ${\displaystyle <}$.

L'ordre lexicographique sur ${\displaystyle A\times B}$, que l'on note encore ${\displaystyle \leqslant }$, est défini de la façon suivante : pour ${\displaystyle (a,b)}$ et ${\displaystyle (a',b')}$ deux couples de ${\displaystyle A\times B}$,

${\displaystyle (a,b)\leqslant (a',b')}$  si et seulement si ${\displaystyle [a<a'{\text{ ou }}(a=a'{\text{ et }}b\leqslant b')]}$,

et on en déduit facilement la propriété analogue pour l'ordre lexicographique strict :

${\displaystyle (a,b)<(a',b')}$  si et seulement si  ${\displaystyle [a<a'{\text{ ou }}(a=a'{\text{ et }}b<b')]}$.

Il s'agit bien de l'ordre du dictionnaire, les lettres étant ordonnées par l'ordre alphabétique ; par exemple :

lu < ne car l < n (on ne regarde que la première lettre)

le < lu car e < u (les premières lettres sont identiques, on regarde la seconde).

Le choix de la première composante pour commencer la comparaison est purement arbitraire, mais, comme illustré par l'exemple alphabétique qui précède, si l'on commence la comparaison par la seconde composante, on obtient un ordre différent.

• Si chacune des relations d'ordre initiales (sur ${\displaystyle A}$ et ${\displaystyle B}$) est un ordre total, alors la relation d'ordre lexicographique sur ${\displaystyle A\times B}$ est un ordre total.

• L'ordre lexicographique sur ${\displaystyle \{0,1\}\times \{0,1,2\}}$ ordonnés usuellement donne ${\displaystyle (0,0)<(0,1)<(0,2)<(1,0)<(1,1)<(1,2)}$.
• Plus généralement, ranger par l'ordre lexicographique croissant les éléments de ${\displaystyle A\times B}$ où ${\displaystyle (A,\leqslant )}$ et ${\displaystyle (B,\leqslant )}$ sont finis et totalement ordonnés fournit une permutation des éléments de ${\displaystyle A\times B}$ débutant par ${\displaystyle (\min(A),\min(B))}$ et se terminant par ${\displaystyle (\max(A),\max(B))}$.
• Le plan ${\displaystyle \mathbb {R} ^{2}=\mathbb {R} \times \mathbb {R} }$ est totalement ordonné par l'ordre lexicographique, mais ne possède plus la propriété de la borne supérieure. En effet, la droite ${\displaystyle \{0\}\times \mathbb {R} }$ est majorée par ${\displaystyle (1,0)}$ mais ne possède pas de borne supérieure.

Étant donné ${\displaystyle n}$ ensembles ordonnés ${\displaystyle (A_{1},\leqslant ),\dots ,(A_{n},\leqslant )}$, on définit l'ordre lexicographique (en commençant par la gauche) sur le produit cartésien ${\displaystyle A_{1}\times \cdots \times A_{n}}$ de la façon suivante : pour deux n-uplets ${\displaystyle a=(a_{1},\dots ,a_{n}),b=(b_{1},\dots ,b_{n})}$,

on a ${\displaystyle a\leqslant b}$ si et seulement si^[1],[2]:

- ou bien ${\displaystyle a_{1}<b_{1}}$

- ou bien il existe un indice ${\displaystyle k,1\leqslant k<n}$, tel que ${\displaystyle a_{1}=b_{1},\dots ,a_{k}=b_{k}}$ et ${\displaystyle a_{k+1}<b_{k+1}}$

- ou bien ${\displaystyle a=b}$.

Cet ordre est celui obtenu en considérant les ordres lexicographiques obtenus successivement sur ${\displaystyle A_{1}\times A_{2};(A_{1}\times A_{2})\times A_{3}=A_{1}\times A_{2}\times A_{3};\dots ;(A_{1}\times \cdots A_{n-1})\times A_{n}=A_{1}\times \cdots A_{n-1}\times A_{n}}$.

En commençant par la droite, on a ${\displaystyle a\leqslant b}$ si et seulement si :

- ou bien ${\displaystyle a_{n}<b_{n}}$

- ou bien il existe un indice ${\displaystyle k,1<k\leqslant n}$, tel que ${\displaystyle a_{n}=b_{n},\dots ,a_{k}=b_{k}}$ et ${\displaystyle a_{k-1}<b_{k-1}}$

- ou bien ${\displaystyle a=b}$.

• Si les ${\displaystyle (A_{i},\leqslant )}$ sont des ensembles totalement ordonnés, ${\displaystyle (\prod _{i=1}^{n}A_{i},\leqslant )}$ l'est également.

• L'ordre usuel des entiers naturels s'obtient par l'ordre lexicographique sur les chiffres (en base 10 ou en base quelconque). Par exemple, ${\displaystyle 4570>975>974}$ car ${\displaystyle (4,5,7,0)>(0,9,7,5)>(0,9,7,4)}$ dans ${\displaystyle \{0,1,\dots ,9\}^{4}}$ muni de l'ordre lexicographique.
• On range en général les monômes des polynômes en plusieurs indéterminées dans l'ordre lexicographique décroissants des exposants. Par exemple, ${\displaystyle 3X^{2}YZ+6XY^{4}-5Z}$ est écrit ainsi car ${\displaystyle (2,1,1)>(1,4,0)>(0,0,1)}$ dans ${\displaystyle \mathbb {N} ^{3}}$ muni de l'ordre lexicographique.
• Les 6 permutations de ${\displaystyle (1,2,3)}$ rangées dans l'ordre lexicographique croissant sont ${\displaystyle (1,2,3),(1,3,2),(2,1,3),(2,3,1),(3,1,2),(3,2,1)}$.
• Dans  A096907, A096908, A096909, A096910, les quadruplets pythagoriciens ont été rangés par ordre lexicographique croissant, en commençant par la droite. Par exemple, ${\displaystyle (6,6,7,11)}$ se trouve avant ${\displaystyle (2,6,9,11)}$.
• Dans la définition de la représentation d'un entier naturel dans le système de numération de base une suite d'entiers intervient la notion d'ordre lexicographique^[3].

On peut généraliser la notion d'ordre lexicographique à une famille ${\displaystyle (A_{i},\leqslant )_{i\in I}}$ d'ensembles ordonnés, où ${\displaystyle I}$ est muni d'une relation ${\displaystyle R}$ de bon ordre^[4].

Pour ${\displaystyle a=(a_{i}),b=(b_{i})}$ éléments distincts de ${\displaystyle \prod _{i\in I}{A_{i}}}$, soit ${\displaystyle i_{0}}$ le plus petit des ${\displaystyle i\in I}$ tel que ${\displaystyle a_{i}\neq b_{i}}$ (qui existe car ${\displaystyle R}$ est un bon ordre); alors ${\displaystyle a<b\Leftrightarrow a_{i_{0}}<b_{i_{0}}}$.

L'ordre usuel des réels dans ${\displaystyle [0,1[}$ s'obtient par l'ordre lexicographique sur les développements décimaux (ou en base ${\displaystyle b}$), le développement décimal propre de ${\displaystyle x=\sum _{k=1}^{\infty }{\frac {a_{k}}{10^{k}}}}$ étant la suite ${\displaystyle (a_{k})_{k\geqslant 1}}$ appartenant à ${\displaystyle \{0,\dots ,9\}^{\mathbb {N} ^{*}}}$ ne se terminant pas par des 9. Par exemple, ${\displaystyle \pi -3=0,14159\dots }$ et ${\displaystyle 22/7-3=0,14285\dots }$ permet d'affirmer que ${\displaystyle \pi <22/7}$.

C'est celui qui a pour cas particulier l'ordre employé pour les dictionnaires. Contrairement aux cas précédents on veut pouvoir comparer des suites finies de longueur arbitraire. Par exemple, dans le cas du dictionnaire « maison » est avant « maman » car "ma" = "ma" et "i"

Soit donc ${\displaystyle (E,\leqslant )}$un ensemble ordonné. On pose ${\displaystyle E^{*}=\bigcup _{k=0}^{\infty }E^{k}}$, la réunion de tous les produits cartésiens finis construits sur ${\displaystyle E}$ (${\displaystyle E^{0}}$ contient uniquement la suite vide). On définit l'ordre lexicographique sur ${\displaystyle E^{*}}$ de la façon suivante. Soient ${\displaystyle a=(a_{1},\dots ,a_{p}),b=(b_{1},\dots ,b_{q})}$ deux éléments quelconques de ${\displaystyle E^{*}}$, et soit ${\displaystyle m}$ le plus petit des deux entiers ${\displaystyle p}$ et ${\displaystyle q}$. Alors ${\displaystyle a<b}$ si et seulement si :

${\displaystyle (a_{1},\dots ,a_{m})<(b_{1},\dots ,b_{m})}$ (pour l'ordre lexicographique sur ${\displaystyle E^{m}}$)

ou ${\displaystyle (a_{1},\dots ,a_{m})=(b_{1},\dots ,b_{m})}$ et ${\displaystyle m<q}$ (c’est-à-dire ${\displaystyle p<q}$).

• On montre que, si l'ordre initial sur ${\displaystyle E}$ est total, l'ordre lexicographique sur ${\displaystyle E^{*}}$, l'ensemble des suites finies d'éléments de ${\displaystyle E}$, est également total.

• Si chaque relation d'ordre initiale est un bon ordre, la relation d'ordre lexicographique sur A × B est également un bon ordre. Exemples :
  • Si (A, ≤) est un ensemble ordonné, l'ordre lexicographique sur {0,1} × A revient à « mettre bout à bout » deux copies de A (la première associée à la première composante 0, la seconde à la première composante 1). Ainsi si N est l'ensemble des entiers naturels, ordonné usuellement — on l'appelle alors ω — {0,1} × N ordonné lexicographiquement est un bon ordre, qui n'est pas isomorphe à ω mais à l'ordinal ω + ω = ω2. On aura :

(0, 0) < (0, 1) < (0, 2) < … < (1, 0) < (1, 1) < (1, 2) < ...

• • N × {0,1} ordonné lexicographiquement est un bon ordre isomorphe à 2ω = ω, l'ordre usuel sur N.
  • N × N ordonné lexicographiquement est un bon ordre isomorphe à l'ordinal ω².

    Ainsi (0, 0) est le plus petit élément, le suivant est (0, 1) puis (0, 2), (0, 3), …, (0, n), … , (1, 0), … , (2, 0), … Si on ordonne lexicographiquement N × N × N, chacun étant ordonné usuellement, on obtient un bon ordre dénombrable correspondant à l'ordinal ω³, qui n'est égal ni à ω, ni à ω².

• Par contre la propriété de bon ordre n'est pas conservée sur ${\displaystyle E^{*}}$ (sauf bien sûr si E est un singleton). Par exemple {0, 1} est bien ordonné, mais {0, 1}* ne l'est pas, comme le montre la suite infinie décroissante :

(1) > (0, 1) > (0, 0, 1) > (0, 0, 0, 1) > …

Il faut donc envisager d'autres méthodes pour bien ordonner les suites finies d'un ensemble bien ordonné, par exemple comparer d'abord les longueurs des suites.

Baader et Nipkow^[5] définissent l'ordre lexicographique comme suit. Si (E, >) est un ordre strict, alors l'ordre lexicographique >^*_lex sur E* est défini par :

u >^*_lex v si, et seulement si (|u| > |v| ou (|u| = |v| et u >^|u| _lex v))

où |w| est la longueur du mot w, et >^|u|_lex est l'ordre lexicographique sur E^|u|.

Si > est un ordre strict, alors >^*_lex est aussi un ordre strict. Si > termine, alors >^*_lex termine.

• Définition plus générale de l'ordre lexicographique, sur le produit d'une famille d'ensembles ordonnés indexée par un ensemble bien ordonné
• Ordre alphabétique

• Portail des mathématiques