Ordre lexicographique

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, si l'on veut, des suites finies de longueur fixée.

Définitions et propriétés

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.

Ordre lexicographique sur un produit cartésien

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 équivalent à l'ordre usuel sur les entiers strictement inférieurs à n.p.
• 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, mais qui n'est pas équivalent à ω, 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 équivalent à ω, l'ordre usuel sur N.
• N × N ordonné lexicographiquement est un bon ordre équivalent à 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), ....

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 ω³, qui n'est équivalent ni à ω ni à ω².

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 longueurs 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^*=, la réunion de tous les produits cartésiens finis construit 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^*,e t 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. Il suffit que l'ensemble ordonné initial possède au moins deux éléments. 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.

Voir aussi

• Ordre alphabétique

• Portail des mathématiques