Orden lexicográfico

Definimos el concepto de orden lexicográfico.

  1. Teorema. Sean $(A,\le_A)$ y $(B,\le_B)$ dos conjuntos ordenados. Definimos en $A\times B$ la relación $$(a,b) \le (a’,b’) \ \Leftrightarrow \ a <_A a' \vee (a = a' \wedge b \leq_B b').$$ Entonces,
    1) $\le$ es relación de orden en $A\times B$ (se le llama orden lexicográfico).
    2) Si $\le_A$ y $\le_B$ son de orden total. también $\le$ es de orden total.

    Demostración. 1) (a) Reflexiva. Para todo $(a,b)\in A\times B$ se verifica $a=a$ y $b\leq_B b,$ lo cual implica $(a,b)\le (a,b).$
    (b) Antisimétrica. Sean $(a,b)$ y $(a^\prime,b^\prime),$ elementos de $A\times B$ con $(a,b)\le (a^\prime,b^\prime)$ y $(a^\prime,b^\prime)\le (a,b).$ Si $a=a^\prime,$ entonces $b\leq_B b^\prime$ y $b^\prime\leq_B b.$ Es decir, $a=a^\prime$ y $b=b^\prime,$ luego $(a,b)=(a^\prime,b^\prime).$ No puede ocurrir $a\neq a^\prime$ pues si así fuera, $a <_A a^\prime$ y $a^\prime <_A a$ (absurdo).
    (c) Transitiva. Sean $(a_1,b_1)$, $(a_2,b_2)$ y $(a_3,b_3)$ elementos de $A\times B$ tales que $(a_1,b_1)\le (a_2,b_2)$ y $(a_2,b_2)\le (a_3,b_3).$ Tenemos, $$a_1=a_2\Rightarrow b_1\leq_B b_2\Rightarrow\left \{ \begin{matrix} a_2=a_3\Rightarrow b_2\leq_B b_3\\a_2\neq a_3\Rightarrow a_2 <_A a_3\end{matrix}\right.$$ $$\Rightarrow \left \{ \begin{matrix} a_1=a_3\wedge b_1\leq_B b_3\\a_1\neq a_3\wedge a_1 <_A a_3\end{matrix}\right.\Rightarrow \left \{ \begin{matrix} (a_1,b_1)\le (a_3,b_3)\\(a_1,b_1)\le (a_3,b_3).\end{matrix}\right.$$ Es decir, si $a_1=a_2,$ en cualquier caso ocurre $(a_1,b_1)\le (a_3,b_3).$ Analicemos ahora el caso $a_1\neq a_2.$ $$a_1\neq a_2\Rightarrow a_1 <_A a_2 \Rightarrow\left \{ \begin{matrix} a_2=a_3\Rightarrow a_1 <_A a_3\\a_2\neq a_3\Rightarrow a_2 <_A a_3\end{matrix}\right.$$ $$\Rightarrow \left \{ \begin{matrix} a_1 <_A a_3\\a_1 <_A a_3\end{matrix}\right.\Rightarrow \left \{ \begin{matrix} (a_1,b_1)\le (a_3,b_3)\\(a_1,b_1)\le (a_3,b_3).\end{matrix}\right.$$ Es decir, si $a_1\neq a_2,$ en cualquier caso ocurre $(a_1,b_1)\le (a_3,b_3).$ Concluimos pues que $\le$ es relación de orden en $A\times B.$

    2) Sean $(a_1,b_1)$, $(a_2,b_2)$ elementos de $A\times B.$ Puede ocurrir $a_1=a_2$ o $a_1\neq a_2.$ Si $a_1=a_2,$ o bien $b_1\leq_B b_2$ o bien $b_2\leq_B b_1,$ lo cual implica que o bien $(a_1,b_1)\le$ $(a_2,b_2),$ o bien $(a_2,b_2)\le (a_1,b_1).$ Si $a_1\neq a_2,$ o bien $a_1 <_A a_2$ o bien $a_2 <_A a_1,$ lo cual implica que o bien $(a_1,b_1)\le (a_2,b_2),$ o bien $(a_2,b_2)\le (a_1,b_1).$ Hemos demostrado que $\le$ es relación de orden total en $A\times B.$ $\quad \square$

  2. Generalizazión. Habiendo definido el orden lexicográfico para el producto cartesiano de dos conjuntos, podemos extender la definición para el producto de $n > 2$ conjuntos por recursión mediante la identificación $\prod_{k=1}^{n} A_k := \left( \prod_{k=1}^{n-1} A_k \right) \times A_{n}.$

  3. Ejemplo. Sea $A=\{a,b,c,d,\ldots, w, x, y, z\}$ el conjunto de las letras del abecedario español y consideremos el orden del diccionario $a < b,c < d < \ldots < w < x < y < z.$ Denotemos por $P=\prod_{k=1}^{5} A_k$ con $A_i=A$ para todo $k$ y denotemos abreviadamente a $(a_1,a_2,a_3,a_4,a_5)$ por $a_1a_2a_3a_4a_5.$ Tendríamos (por ejemplo) en $P$ y según el orden lexicográfico,

            ábaco < abadí < gabán < gacha < ocaso < vacas < vacío < vacuo < yaces.

Esta entrada fue publicada en Álgebra. Guarda el enlace permanente.