Orden Lexicografico
Jeison Aleixer Tellez Pineda 1360530
Jesus Miguel Sandoval Duran 1360531
Teoria de conjuntos
Maestra: Sonia Maritza Mendoza Lizcano
Universidad Francisco de Paula Santander
Licenciatura en Matematicas
Cucuta
2023
Introduccion
El ordenamiento es un concepto fundamental en diversas disciplinas y contextos, que nos
permite organizar y clasificar elementos de acuerdo a criterios específicos. Entre los diferentes
métodos de ordenamiento, uno de los más ampliamente utilizados es el orden lexicográfico.
El orden lexicográfico se basa en el principio de ordenar elementos en función de su posición en
un diccionario o en un sistema alfabético. Este enfoque de ordenamiento se aplica tanto en
lenguajes naturales como en campos científicos y tecnológicos, y su relevancia se extiende a
áreas tan diversas como las ciencias de la computación, la matemática discreta, la lingüística y la
estadística.
En este trabajo, exploraremos en profundidad el concepto de orden lexicográfico y analizaremos
sus fundamentos teóricos y aplicaciones prácticas. Examindaremos cómo se establece el orden
lexicográfico entre elementos que pueden ser letras, números, palabras o cualquier otro tipo de
símbolo, y cómo este orden puede variar según el contexto y las reglas específicas.
Orden Lexicografico
“El orden lexicográfico ≼ en A1 x A2 se define especificando que un par es menor que un
segundo par si la primera componente del primer par es menor (en A1) que la primera
componente del segundo par o si las primeras componentes son iguales, pero la segunda
componente del primer par es menor (en A2) que la segunda componente del segundo par. En
otras palabras. (a 1 , a2 ¿es menor que (b 1 , b2 ¿, esto es,
( a 1 , a 2) ≼ ( b1 , b2 ) , si biena 1 ≺1 b1 o bien a1=b 1 y a2 ≼ 2 b 2”
Demostracion:
Veamos que esta relación es, en efecto, una relación de orden
Reflexiva: Sea ( a , b ) cualquiera de A × B . Entonces, a ∈ A y b ∈ B y como ≼2 es reflexiva,
a=a ∧ b ≼2 b ⇒a ≺ 1 a ∨(a=a ∧b ≼2 b) ⟺(a , b) ≼( a , b)
Antisimetrica: a. Sean (a, b) y (a`, b`) dos elementos cualesquiera de A × B. Pues bien,
Transitiva: Sean (a, b), (a’, b’) y (a’’, b’’) tres elementos cualesquiera de A × B. Entonces,
Este ordenamiento se llama lexicográfico u orden de diccionario. Domina el orden de los
elementos de la primera coordenada, exceptuando el caso de “empate”, en el que la atenci´on
pasa a la segunda coordenada
Ejemplos:
1. Determina si es cierto o no que (3,5)≺(4,8), que (3,8)≺(4,5) y que (4,9)≺(4,11) en el
conjunto parcialmente ordenado de los números enteros (ℤ𝑥ℤ, ≼)donde el ≼ es el orden
lexicográfico construido a partir de la relación usual ≤ en ℤ
Solución:
3≺4
(3,5)≺(4,8)
(3,8)≺(4,5)
4=4∧9≺11
(4,9)≺(4,11)
2. Sea A={ a , b , c , … , z } el alfabeto, ordenado totalmente por el orden usual, es decir,
a ≤ b , b ≤ c , … , y ≤ z . El producto cartesiano An puede considerarse como el conjunto de
las palabras de longitud n
El orden lexicográfico en An tiene la propiedad de que si p1 ≼ p2 ( p1 , p2 ∈ An ), entonces la
palabra p1 deberá preceder a la p2en una lista de diccionario. Este hecho justifica el
nombre dado al ordenamiento
Leñera ≼leñero
Amigo ≼ azar
Pájaro ≼ zumbido
Nota: El ordenamiento lexicográfico puede extenderse fácilmente al producto cartesiano
A1 × A2 ×… × A n en la forma:
3. Sea Σ= { a ,b , c , … , z }. Entonces, Σ ¿es el conjunto de todas las palabras posibles de
cualquier longitud, independiente de que tengan o no significado
ama ≼amando
¿
en Σ ya que
ama ≼ama
en Σ 3 .
amando ≼amante
¿
en Σ ya que
amando ≼amante
en Σ 6 .
ama ≼amando
ama ≼amante
Esto prueba que este orden incluye el “orden de los prefijos”; esto es, cualquier palabra es
mayor que cualquiera de sus prefijos. También es esta la forma en que las palabras están
colocadas en el diccionario. Tenemos, pues, nuevamente un ordenamiento de diccionario,
en este caso de palabras de cualquier longitud finita.
Nota: si Σ es un alfabeto ordenado, el orden lexicográfico puede extenderse al conjunto Σ ¿ de todas las
palabras de longitud finita construidas con símbolos de Σ , en la forma siguiente
Si x=a 1 , a 2 … , an e y =b1 , b2 … , bk
están en Σ ¿ con n ≼ k , entonces
x ≼ y ⟺(a1 , a2 , … , an ) ≼(b 1 , b2 , … , bn )
bajo el orden lexicográfico Σ n
