Ordre lexicographique

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.

Sommaire

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 bb’)]

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 ω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 A1 × … × Ak, est défini à l'aide du produit cartésien binaire par :

A1 × A2 × … × Ak = A1 × (A2 × ( … × Ak)…)

(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 A1, A2, … , Ak × Ak+1, on ordonne lexicographiquement le produit cartésien binaire de A1, et du produit cartésien de k ensembles A2 × … × Ak × Ak+1, ce dernier étant lui-même ordonné lexicographiquement. C’est-à-dire que l'ordre lexicographique sur le produit d'ensembles ordonnés A1 × A2 × … × Ak+1 est défini ainsi à partir de l'ordre lexicographique sur A2 × … × Ak+1 (on définit l'ordre strict qui est noté < pour tous les ensembles en jeu) :

(a1, … , ak+1) < (b1, … , bk+1) si et seulement si :
a1 < b1 ou [ a1 = b1 et (a2, … , ak+1) < (b2, … , bk+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 :

(a1, … , ak+1) < (b1, … , bk+1) si et seulement si :
(a1, … , ak) < (b1, … , bk) ou [ (a1, … , ak) = (b1, … , bk) et ak+1 < bk+1 ].

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

(a1, … , ak) < (b1, … , bk) si et seulement si
a1 < b1 ou ( a1 = b1 et a2 < b2) ou ( a1 = b1 et a2 = b2 et a3 < b3) ou …… ou ( a1 = b1 et a2 = b2 et … et ak-1 = bk-1 et ak < bk)

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 équivalent 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 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*=\bigcup_{k=0}^\infty E^k, la réunion de tous les produits cartésiens finis construit sur E (E0 contient uniquement la suite vide). On définit l'ordre lexicographique sur E* de la façon suivante. Soient a=(a1, … , ap) et b=(b1, … , bq) 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 :

(a1, … , am) < (b1, … , bm) (pour l'ordre lexicographique sur Em)
ou (a1, … , am) = (b1, … , bm) 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


Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Ordre lexicographique de Wikipédia en français (auteurs)

Игры ⚽ Нужно решить контрольную?

Regardez d'autres dictionnaires:

  • Ordre lexicographique sur un ensemble ordonné E — ● Ordre lexicographique sur un ensemble ordonné E relation d ordre total définie sur l ensemble E × E telle que (x0, y0) et (x1, y1) étant deux couples de E × E, si x0 ≠ x1, les couples sont rangés dans le même ordre que x0 et …   Encyclopédie Universelle

  • lexicographique — [ lɛksikɔgrafik ] adj. • 1801; de lexicographie ♦ Ling. Relatif à la lexicographie. ⇒ dictionnairique. Définition lexicographique. ● lexicographique adjectif Qui concerne la lexicographie. ● lexicographique (expressions) …   Encyclopédie Universelle

  • ordre — [ ɔrdr ] n. m. • 1080 sens II; lat. ordo, ordinis I ♦ (1155) Relation intelligible entre une pluralité de termes. ⇒ organisation, structure; économie. « L idée de la forme se confond avec l idée de l ordre » (A. Cournot). 1 ♦ Didact. Disposition …   Encyclopédie Universelle

  • Ordre total — On appelle relation d ordre total sur un ensemble E toute relation d ordre ≤ telle que tout élément de E soit comparable avec tout autre élément de E, c est à dire que pour tout x et y éléments de E, x ≤ y ou y ≤ x ; l ensemble E est dit… …   Wikipédia en Français

  • Relation d'ordre — Une relation d’ordre dans un ensemble est une relation binaire dans cet ensemble qui permet de comparer ses éléments entre eux de manière cohérente. Un ensemble muni d’une relation d’ordre est un ensemble ordonné ou tout simplement un ordre.… …   Wikipédia en Français

  • Arbre de Galton-Watson — Pour les articles homonymes, voir Arbre (homonymie). Simulation d un arbre de Galton Watson avec une loi de Poisson de paramètre 1 pour loi de rep …   Wikipédia en Français

  • Monoïde de traces — En mathématiques et en informatique, une trace est un ensemble de mots, où certaines lettres peuvent commuter, et d autres non. Le monoïde des traces ou monoïde partiellement commutatif libre est le monoïde quotient du monoïde libre par une… …   Wikipédia en Français

  • ORDONNÉS (ENSEMBLES) — Les relations d’ordre interviennent de manière naturelle dans des questions comme l’étude des liens de parenté et celle des liens de subordination, comme les problèmes de classification, etc. C’est de là, et de la relation 諒 entre nombres, que… …   Encyclopédie Universelle

  • String.h — Demande de traduction string.h → …   Wikipédia en Français

  • string.h — <string.h> est l en tête de la bibliothèque standard de C, du langage C, qui contient les définitions des macros, des constantes et les déclarations de fonctions et de types utilisées non seulement pour la manipulation de chaînes de… …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”