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, de façon équivalente, les mots construits sur un ensemble ordonné). Sa définition est une généralisation de l'ordre du dictionnaire : l'ensemble ordonné est l'alphabet, les mots sont bien des suites finies de lettres de l'alphabet. La principale propriété de l'ordre lexicographique est de conserver la totalité 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.

Ordre lexicographique sur un produit cartésien

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.

Exemples

• L'ordre lexicographique sur {0, 1} × {0, 1} ordonnés usuellement donne (0, 0) < (0, 1) < (1, 0) < (1, 1).
• De façon générale l'ordre lexicographique sur {0, 1, … , n – 1} × {0, 1, … , p – 1} ordonnés usuellement est un ordre isomorphe à l'ordre usuel sur les entiers strictement inférieurs à np.
• 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 ω^2.

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), …

Propriétés

• Si chacune des relations d'ordre initiales (sur A et B) est un ordre total, alors la relation d'ordre lexicographique sur A × B est un ordre total.
• Si de plus chaque relation d'ordre initiale est un bon ordre, la relation d'ordre lexicographique sur A × B est également un bon ordre.

Généralisation aux produits cartésiens finis

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)

Exemples

Si on ordonne lexicographiquement N × N × N, chacun étant ordonné usuellement, on obtient un bon ordre dénombrable correspondant à l'ordinal ω^3, qui n'est égal ni à ω, ni à ω^2.

Propriétés

Les propriétés énoncées pour les produits cartésiens binaires se généralisent immédiatement par récurrence : l'ordre lexicographique défini sur un produit cartésien fini d'ensembles totalement ordonnés est un ordre total, l'ordre lexicographique défini sur un produit cartésien fini d'ensembles bien ordonnés est un bon ordre.

Ordre lexicographique sur des suites finies

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^0 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).

Propriétés

On montre facilement que, si l'ordre initial sur E est total, l'ordre lexicographique sur E*, l'ensemble des suites finies d'éléments de E, est également total.

Par contre la propriété de bon ordre n'est pas conservé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.

Définition en prenant en compte les longueurs des suites

Baader et Nipkow[1] 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.

Notes et références

1. Franz Baader et Tobias Nipkow, Term Rewriting and All That, Cambridge University Press, 1999, 18–19 p. (ISBN 978-0-521-77920-3, lire en ligne)

Voir aussi

• 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