Ordre lexicographique : Définition

Qu’est-ce que l’ordre lexicographique ? Découvrez la notion assez simple qui se cache derrière ce mot complexe !
Dictionnaire

L’ordre lexicographique est quelque chose que l’on connait tous, que l’on fasse des maths ou nous. Il s’agit en fait de l’ordre du dictionnaire. Découvrez dans cet article sa définition mathématique.

Prérequis

Définition de l’ordre lexicographique

Soient (A, \leq ) et (B, \leq ) deux ensembles ordonnés. L’ordre lexicographique, défini sur le produit A \times B avec pour a,a' \in A, b,b' \in B :

(a,b) \leq (a',b') \iff [ a \leq a' \text{ ou } (a=a' \text{ et } b \leq b')]

Avec une relation d’ordre strict :

(a,b) <(a',b') \iff [ a< a' \text{ ou } (a=a' \text{ et } b < b')]

Cela correspond bien à l’ordre du dictionnaire. En effet,

  • le < un car l < u
  • la < le car l = l et a < e

Généralisation

On peut généraliser cette définition à un produit cartésien fini par récurrence ce qui nous donne :

Soient (A_1, \leq ), \ldots, (A_n, \leq ) n ensembles ordonnés. L’ordre lexicographique, défini sur le produit A_1 \times \ldots \times A_n avec pour a_1,a_1' \in A_1, a_n,a_n' \in A_n

\begin{array}{c}
(a_1,\ldots,a_n) \leq (a_1',\ldots,a_n') \\
\iff \\
\left[ a_1 \leq a_1' \text{ ou } (a_1=a_1' \text{ et } (a_2, \ldots,a_n) \leq (a_1',\ldots,a_n'))\right]
\end{array}
Total
0
Shares

Laisser un commentaire

Articles similaires