Orden lexicográfico para Niños

En matemáticas, o más particularmente en Teoría del orden, el orden lexicográfico es una relación de orden definida sobre el producto cartesiano de conjuntos ordenados. Es conocido principalmente por su aplicación a cadenas de caracteres, por ejemplo en diccionarios o en la guía telefónica.

Definición matemática

Definición en el caso de un producto de dos conjuntos

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

\forall (a,b), (a',b') \in A \times B:

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

Si $\le_A$ y $\le_B$ son órdenes totales, $\le_{A,B}$ también es un orden total.

Productos cartesianos n-arios

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

\prod_{i=1}^{1} A_i := A_1

\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.

Cadenas de caracteres

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 $\epsilon$ , es decir:

\forall b \in \Sigma^* : \epsilon \leq b

Así, la definición recursiva queda:

\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])

Ejemplos y propiedades

El orden lexicográfico no es igual al orden numérico

Si a = [19] y b = [138] tenemos que b < a, porque el prefijo es a₁ = b₁ = 1 y b₂ = 3 < a₂ = 9.

Los diccionarios son el ejemplo más conocido de ordenamiento lexicográfico. En este caso, no se hace distinción entre mayúsculas y minúsculas, y se considera por lo tanto que a=A, b=B, c=C, etc.
El producto de dos grupos ordenados con el orden lexicográfico es un grupo ordenado.

Véase también

En inglés: Lexicographic order Facts for Kids

Problemas del orden lexicográfico en Wikipedia

Obtenido de «https://ninos.kiddle.co/index.php?title=Orden_lexicográfico&oldid=3797656»

Todo el contenido de los artículos de la Enciclopedia Kiddle (incluidas las imágenes) se puede utilizar libremente para fines personales y educativos bajo la licencia Atribución-CompartirIgual a menos que se indique lo contrario. Citar este artículo:

Orden lexicográfico para Niños. Enciclopedia Kiddle.

Orden lexicográfico para niños