Ordre lexicographique

Bien que l'ordre du dictionnaire soit manipulé dès l'école primaire, on va commencer la formalisation par un cas simple, celui du produit cartésien binaire. C’est-à-dire que les mots de notre dictionnaire ne seront composés tout d'abord que de deux lettres.

Les ensembles (A, ≤) et (B, ≤) sont tous deux ordonnés, l'ordre étant noté de la même façon pour les deux ensembles, une liberté qui ne devrait troubler personne. L'ordre lexicographique sur A × B, que l'on note encore ≤, est défini de la façon suivante, pour (a,b) et (a’,b’) deux couples de A × B :

(a,b) ≤ (a’,b’) si et seulement si [a < a’ ou (a = a’ et b ≤ b’)]

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

(a,b) < (a’,b’) si et seulement si [a < a’ ou (a = a’ et b < b’)].

Il s'agit bien de l'ordre du dictionnaire, 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 l'on considère qu'un produit cartésien fini A₁ × … × A_k, est défini à l'aide du produit cartésien binaire par :

A₁ × A₂ × … × A_k = A₁ × (A₂ × ( … × A_k)…)

(ou si on l'a défini autrement, qu'il y a une bijection canonique entre ces deux ensembles), on généralise naturellement, par récurrence, l'ordre lexicographique aux produits finis d'ensembles ordonnés.

Supposons que nous ayons défini l'ordre lexicographique pour les produits cartésiens de k ensembles ordonnés. Alors pour définir l'ordre lexicographique pour le produit de k+1 ensembles ordonnés, soient A₁, A₂, … , A_k × A_k+1, on ordonne lexicographiquement le produit cartésien binaire de A₁, et du produit cartésien de k ensembles A₂ × … × A_k × A_k+1, ce dernier étant lui-même ordonné lexicographiquement. C’est-à-dire que l'ordre lexicographique sur le produit d'ensembles ordonnés A₁ × A₂ × … × A_k+1 est défini ainsi à partir de l'ordre lexicographique sur A₂ × … × A_k+1 (on définit l'ordre strict qui est noté < pour tous les ensembles en jeu) :

(a₁, … , a_k+1) < (b₁, … , b_k+1) si et seulement si :

a₁ < b₁ ou [ a₁ = b₁ et (a₂, … , a_k+1) < (b₂, … , b_k+1) ]

En décomposant le produit cartésien « en commençant par la fin », on obtient le même ordre, c’est-à-dire qu'en conservant les mêmes notations on a :

(a₁, … , a_k+1) < (b₁, … , b_k+1) si et seulement si :

(a₁, … , a_k) < (b₁, … , b_k) ou [ (a₁, … , a_k) = (b₁, … , b_k) et a_k+1 < b_k+1 ].

En « développant » la définition par récurrence de l’ordre lexicographique sur A₁ × A₂ × … × A_k, chacun de ces ensembles étant ordonné, on obtient :

(a₁, … , a_k) < (b₁, … , b_k) si et seulement si

a₁ < b₁ ou ( a₁ = b₁ et a₂ < b₂) ou ( a₁ = b₁ et a₂ = b₂ et a₃ < b₃) ou …… ou ( a₁ = b₁ et a₂ = b₂ et … et a_k-1 = b_k-1 et a_k < b_k)

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" < "m". Cependant « maison » a 6 lettres et « maman » 5. Ces mots ne peuvent être considérés comme éléments d'un même produit cartésien fini, à moins d'ajouter une lettre à l'alphabet, par laquelle on complète arbitrairement le mot le plus court. Ce n'est pas complètement inenvisageable pour le dictionnaire, puisque les mots d'une langue ont, en pratique, une longueur maximale (tout du moins ceux qui apparaissent dans le dictionnaire …), mais serait très artificiel. Il est donc naturel de définir l'ordre lexicographique sur des suites finies de longueur arbitraire.

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

(a₁, … , a_m) < (b₁, … , b_m) (pour l'ordre lexicographique sur E^m)

ou (a₁, … , a_m) = (b₁, … , b_m) et m < q (c’est-à-dire p < q).

• 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