Orden lexicográfico

sean ${\displaystyle (A,\leq _{A})}$ y ${\displaystyle (B,\leq _{B})}$ dos conjuntos parcialmente ordenados por las relaciones ${\displaystyle \leq _{A}}$ y ${\displaystyle \leq _{B}}$, respectivamente, entonces un orden lexicográfico es una relación de orden parcial ${\displaystyle \leq _{A,B}}$ definida como sigue:

${\displaystyle \forall (a,b),(a',b')\in A\times B:}$

${\displaystyle (a,b)\leq _{A,B}(a',b')\ \Leftrightarrow \ a<a'\vee (a=a'\wedge b\leq b')}$

Si ${\displaystyle \leq _{A}}$ y ${\displaystyle \leq _{B}}$ son órdenes totales, ${\displaystyle \leq _{A,B}}$ también es un orden total.

La definición arriba mencionada, que solo define una relación de orden en productos cartesianos de dos conjuntos ordenados, se puede extender a productos cartesianos n-arios, sacando provecho de la definición recursiva de ellos

${\displaystyle \prod _{i=1}^{1}A_{i}:=A_{1}}$

${\displaystyle \prod _{i=1}^{n+1}A_{i}:=\left(\prod _{i=1}^{n}A_{i}\right)\times A_{n+1},n\geq 1}$

que solo basa en la aplicación múltiple del producto cartesiano binario.

Una aplicación más general del orden lexicográfico es al comparar cadenas de caracteres. Distinto al caso para los productos cartesianos n-arios mencionados arriba, las cadenas de caracteres no poseen longitud fija. Usando la misma idea de definición recursiva que para el caso anterior, ahora debemos considerar el que una secuencia puede ser más larga que la otra, y que por lo tanto termine de recorrerse mientras que todavía quedan caracteres en la otra.

La secuencia más corta a considerar será la cadena vacía ${\displaystyle \epsilon }$, es decir:

${\displaystyle \forall b\in \Sigma ^{*}:\epsilon \leq b}$

Así, la definición recursiva queda:

${\displaystyle \forall [a_{1}\dots a_{m}],[b_{1}\dots b_{n}]\in \Sigma ^{*}\backslash \{\epsilon \}:[a_{1}\dots a_{m}]\leq [b_{1}\dots b_{n}]\Leftrightarrow a_{1}<b_{1}\vee (a_{1}=b_{1}\wedge [a_{2}\dots a_{m}]\leq [b_{2}\dots b_{n}])}$