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}
