Introducción

En esta entrada hablaremos acerca de órdenes totales. Retomaremos los conceptos de orden parcial y orden estricto y añadiremos el concepto de elementos comparables. Esto nos llevará a decir cuándo un orden es total. Además, definiremos el orden lexicográfico vertical y horizontal.

Comparabilidad y órdenes totales

En un conjunto parcial (o estrictamente) ordenado, hay algunas parejas de elementos que se pueden comparar y otras que no.

Definición. Sea $\leq$ un orden parcial en $A$ y sean $a, b\in A$. Decimos que $a$ y $b$ son $\leq$-comparables si:

$a\leq b$ o $b\leq a$.

Ejemplo.

Sea $A=\set{\emptyset, \set{\emptyset}, \set{\emptyset, \set{\emptyset}}}$ y sea $\subseteq_A$ la relación dada por el conjunto

$\subseteq_A=\set{(\emptyset, \emptyset), (\emptyset, \set{\emptyset}), (\emptyset, \set{\emptyset, \set{\emptyset}}), (\set{\emptyset},\set{\emptyset}), (\set{\emptyset}, \set{\emptyset, \set{\emptyset}}), (\set{\emptyset, \set{\emptyset}}, \set{\emptyset, \set{\emptyset}})}.$

Como vimos la entrada pasada, esta relación es un orden parcial.

Luego, dados $a,b\in A$ siempre sucede que $a\subseteq_A b$ o $b\subseteq_A a$. En efecto,

• Si $a=\emptyset$ y $b=\emptyset$, entonces $a\subseteq_A b$ y $b\subseteq_A a$.
• Si $a=\set{\emptyset}$ y $b=\set{\emptyset}$, entonces $a\subseteq_A b$ y $b\subseteq_A a$.
• Si $a= \set{\emptyset, \set{\emptyset}}$ y $b=\set{\emptyset,\set{\emptyset}}$, entonces $a\subseteq_A b$ y $b\subseteq_A a$.
• Si $a=\emptyset$ y $b=\set{\emptyset}$, entonces $a\subseteq_A b$.
• Si $a=\emptyset$ y $b=\set{\emptyset, \set{\emptyset}}$, entonces $a\subseteq_A b$.
• Si $a=\set{\emptyset}$ y $b=\set{\emptyset, \set{\emptyset}}$, entonces $a\subseteq_A b$.

$\square$

Definición. Sea $<$ un orden estricto en $A$ y sean $a,b\in A$. Decimos que $a$ y $b$ son $<$-comparables si:

$a<b$ o $a=b$ o $b<a$.

Ejemplo.

Sea $A=\set{\emptyset, \set{\emptyset}, \set{\emptyset, \set{\emptyset}}}$ y sea $R$ la relación definida como $R=\set{(\emptyset, \set{\emptyset}), (\emptyset, \set{\emptyset, \set{\emptyset}}), (\set{\emptyset}, \set{\emptyset, \set{\emptyset}})}$. Se puede verificar que $R$ es orden estricto.

Notemos que $aRb$ si y sólo si $a\in b$ para $a,b\in A$. Luego, dados $a,b\in A$ podemos decidir si $a\in b$, $a=b$ o $b\in a$. En efecto,

• Si $a=\emptyset$ y $b=\emptyset$, entonces $a=b$,
• Si $a=\set{\emptyset}$ y $b=\set{\emptyset}$, entonces $a=b$,
• Si $a= \set{\emptyset, \set{\emptyset}}$ y $b=\set{\emptyset,\set{\emptyset}}$, entonces $a=b$,
• Si $a=\emptyset$ y $b=\set{\emptyset}$, entonces $a\in b$ y así, $aRb$,
• Si $a=\emptyset$ y $b=\set{\emptyset, \set{\emptyset}}$, entonces $a\in b$ y así, $aRb$,
• Si $a=\set{\emptyset}$ y $b=\set{\emptyset, \set{\emptyset}}$, entonces $a\in b$ y así, $aRb$.

$\square$

Definición. Sea $A$ un conjunto y sea $\leq$ ($<$) un orden parcial (orden estricto) en $A$. Si cualesquiera $a, b\in A$ son $\leq(<)$-comparables, entonces $\leq(<)$ es un orden total (orden total estricto).

Ejemplo.

Sea $A=\set{\emptyset, \set{\emptyset}, \set{\emptyset, \set{\emptyset}}}$ y sea $R$ la relación dada por el conjunto

$R=\set{(\emptyset, \emptyset), (\emptyset, \set{\emptyset}), (\emptyset, \set{\emptyset, \set{\emptyset}}), (\set{\emptyset},\set{\emptyset}), (\set{\emptyset}, \set{\emptyset, \set{\emptyset}}), (\set{\emptyset, \set{\emptyset}}, \set{\emptyset, \set{\emptyset}})}$.

Ya vimos en la parte de arriba que todos los elementos de $A$ son $\leq$-comparables y por lo tanto $R$ es un orden total.

$\square$

Ejemplo.

Sea $A=\set{\emptyset, \set{\emptyset}, \set{\emptyset, \set{\emptyset}}}$ y sea $R$ la relación dada por el conjunto

$R=\set{(\emptyset, \set{\emptyset}), (\emptyset, \set{\emptyset, \set{\emptyset}}), (\set{\emptyset}, \set{\emptyset, \set{\emptyset}})}$.

Ya vimos que todos los elementos de $A$ son $<$-comparables y por lo tanto $R$ es un orden total.

$\square$

Orden lexicográfico vertical

Ahora, vamos a dar un orden parcial al producto cartesiano de dos conjuntos parcialmente ordenados. Para ello conviene hacer mención de lo siguiente: si $(A,\leq_A)$ es un conjunto parcialmente ordenado y tenemos dos elementos $a,b\in A$ tales que $a\leq_Ab$ pero $a\not=b$, entonces escribiremos simplemente $a<_Ab$. De esta manera, en un conjunto parcialmente ordenado $(A,\leq_A)$, si $a,b\in A$, el símbolo $a<_Ab$ significará $a\leq_Ab$ y $a\not=b$.

Definición. Sean $(A, \leq_A)$ y $(B, \leq_B)$ conjuntos parcialmente ordenados. Definimos al orden lexicográfico vertical en $A\times B$ como sigue:

$(a,b)\ll_v (a’, b’)$ si y sólo si ($a<_A a’$) o ($a=a’$ y $b\leq_B b’$).

Proposición. Sean $(A, \leq_A)$ y $(B, \leq_B)$ conjuntos totalmente ordenados. El orden lexicográfico vertical es un orden total en $A\times B$.

Demostración.

• Reflexividad:
  Sea $(a,b)\in A\times B$. Dado que $b\in B$ y $\leq_B$ es un orden parcial en $B$, entonces $\leq_B$ es una relación reflexiva y así $b\leq_B b$. En consecuencia, la conjunción $a=a$ y $b\leq_B b$ es verdadera, y por tanto $(a,b)\ll_v (a,b)$. De esta manera, $\ll_v$ es reflexivo.
• Antisimetría:
  Sean $(a,b), (c,d)\in A\times B$ tales que $(a,b)\ll_v (c,d)$ y $(c,d)\ll_v (a,b)$. Veamos que $(a,b)=(c,d)$, es decir, $a=c$ y $b=d$.
  Como $(a,b)\ll_v (c,d)$ entonces, ($a<_A c$) o ($a=c$ y $b\leq_B d$).
  Como $(c,d)\ll_v (a,b)$ entonces, ($c<_A a$) o ($c=a$ y $d\leq_B b$).
  Probemos que $a=c$ y $b\leq_Bd$. Para probarlo supongamos que esto no ocurre buscando generar una contradicción. Dado que la conjunción $a=c$ y $b\leq_Bd$ no es verdadera, entonces, necesariamente debe ser cierto que $a<_Ac$. Ahora, no puede ocurrir que $c<_Aa$, pues de ser así tendríamos que $c<_Aa$ y $a<_Ac$ son verdaderas al mismo tiempo, y por ende se tendría que $c\leq_A a$ pero $c\not=a$ y que $a\leq_Ac$ pero $a\not=c$. Así, en particular obtenemos que $c\leq_Aa$ y $a\leq_Ac$, pero esto implica que $a=c$ pues $\leq_A$ es una relación antisimétrica. Este último hecho contradice que $a\not=c$. Por tanto, no puede ocurrir que $c<_Aa$. Como consecuencia debe ser cierto que $c=a$ y $d\leq_Bb$, pero esto nuevamente contradice el hecho de que $a<_Ac$, es decir, que $a\leq_Ac$ y $a\not=c$. Como la contradicción viene de suponer que $a<_Ac$, entonces, debe ser cierto que $a=c$ y $b\leq_Bd$. Ya tenemos entonces que $a=c$ por lo que resta ver que $b=d$. Como $a=c$ entonces no puede ocurrir que $c<_Aa$ y, por tanto, debe ocurrir que $c=a$ y $d\leq_Bb$ es verdadero. De esta manera tenemos que $b\leq_Bd$ y $d\leq_Bb$, de donde $d=b$ pues $\leq_B$ es una relación antisimétrica.
  Por lo tanto, $(a,b)=(c,d)$ lo que demuestra que $\ll_v$ es una relación antisimétrica.
• Transitividad:
  Sean $(a,b), (c,d), (e,f)\in A\times B$ tales que $(a,b)\ll_v (c,d)$ y $(c,d)\ll_v (e,f)$. Veamos que $(a,b)\ll_v(e,f)$.
  Como $(a,b)\ll_v (c,d)$ entonces, ($a<_A c$) o ($a=c$ y $b\leq_B d$).
  Como $(c,d)\ll_v (e,f)$ entonces, ($c<_A e$) o ($c=e$ y $d\leq_B f$).
  Caso 1: Si $a<_Ac$ y $c<_A e$. Por transitividad de $<_A$ se tiene que $a<_A e$. Por lo tanto, ($a<_A e$) o ($a=e$ y $b\leq_B f$) es verdadero y así, $(a,b)\ll_v (e,f)$.
  Caso 2: Si $a<_Ac$ y $c=e$ y $d\leq_B f$, entonces $a<_A e=c$. Por lo tanto, ($a<_A e$) o ($a=e$ y $b\leq_B f$) es verdadero y así, $(a,b)\ll_v (e,f)$.
  Caso 3: Si $a=c$ y $b\leq_B d$ y $c<_A e$, entonces $a=c<_A e$. Por lo tanto, ($a<_A e$) o ($a=e$ y $b\leq_B f$) es verdadero y así, $(a,b)\ll_v (e,f)$.
  Caso 4: Si $a=c$ y $b\leq_B d$ y $c= e$ y $d\leq_B f$, entonces $a=e$ y $b\leq_B f$ por transitividad de $\leq_B$. Por lo tanto, ($a<_A e$) o ($a=e$ y $a\leq_B e$) es verdadero y así, $(a,b)\ll_v (e,f)$.
  Por lo tanto, $\ll_v$ es transitivo.
  Por lo tanto, $\ll_v$ es un orden parcial en $A\times B$.

Para ver que $\ll_v$ es un orden total en $A\times B$ debemos ver que todos sus elementos son $\ll_v$ comparables.

Sean $(a,b), (c,d)\in A\times B$, veamos que $(a,b)\ll_v (c,d)$ o $(c,d)\ll_v(a,b)$.

Dado que $(a,b), (c,d)\in A\times B$, entonces $a,c\in A$ y $b,d\in B$. Luego, como $\leq_A$ y $\leq_B$ son órdenes totales en $A$ y $B$ respectivamente, tenemos que sus elementos son comparables, es decir, ($a\leq_A c$ o $c\leq_A a$) y ($b\leq_B d$ o $d\leq_B b$).

Caso 1: Si $a\leq_A c$ y $b\leq_B d$, hay dos posibles casos. Si $a<_A c$ y $b\leq_B d$ se tiene que $(a,b)\ll_v (c,d)$. Ahora, si $a=c$ y $b\leq_B d$ entonces $(a,b)\ll_v (c,d)$.

Caso 2: Si $a\leq_A c$ y $d\leq_B b$, hay dos posibles casos. Si $a<_A c$, entonces $(a,b)\ll_v (c,d)$. Ahora, si $a=c$ y $d\leq_B b$ entonces $(c,d)\ll_v (a,b)$.

Caso 3: Si $c\leq_A a$ y $b\leq_B d$, hay dos posibles casos. Si $c<_A a$, entonces $(c,d)\ll_v (a,b)$. Ahora, si $a=c$ y $b\leq_B b$ entonces $(a,b)\ll_v (c,d)$.

Caso 4: Si $c\leq_A a$ y $d\leq_B b$, hay dos posibles casos. Si $c<_A a$, entonces $(c,d)\ll_v(a,b)$. Ahora, si $c=a$ y $d\leq_B b$, entonces $(c,d)\ll_v (a,b)$.

Esto muestra que el orden es total.

$\square$

Orden lexicográfico horizontal

A continuación definiremos al orden lexicográfico horizontal. Este orden también será un orden total cuando sus compontentes lo sean. La demostración forma parte de la tarea moral.

Definición. Sean $(A, \leq_A)$ y $(B, \leq_B)$ conjuntos parcialmente ordenados. Definimos al orden lexicográfico horizontal en $A\times B$ como sigue:

$(a,b)\ll_h (a’, b’)$ si y sólo si ($b<_B b’$) o ($b=b’$ y $a\leq_A a’$).

Tarea moral

• Demuestra que el orden lexicográfico horizontal es un orden total.
• Consideremos $(\mathcal{P}(\set{\set{\emptyset}, \set{\emptyset, \set{\emptyset}}, \set{\emptyset, \set{\emptyset}, \set{\emptyset, \set{\emptyset}}}}, \subseteq)$. Da dos elementos que no sean comparables.
• Si consideramos $(A, \leq_A)$ y $(B, \leq_B)$ conjuntos parcialmente ordenados, podemos definir una relación en el producto $A\times B$ como:
  $(a,b)\ll_{A\times B} (c,d)$ si y sólo si $a\leq_A c$ y $b\leq_B d$.
  Demuestra que $\ll_{A\times B}$ no necesariamente es un orden total. ¿Es un orden parcial?

Más adelante…

En la siguiente entrada hablaremos acerca de elementos mínimos y máximos en un conjunto ordenado. Además hablaremos acerca de cotas superiores e inferiores, así como de otros conceptos que nos permitirán acotar a un conjunto.

Entradas relacionadas

• Entrada relacionada: Álgebra Superior I: Órdenes parciales y totales
• Ir a Teoría de los Conjuntos I
• Entrada anterior: Teoría de los Conjuntos: Órdenes parciales y órdenes parciales estrictos
• Siguiente entrada: Teoría de los Conjuntos I: Mínimos, máximos, minimales y maximales

Agradecimientos

Trabajo realizado con el apoyo del Programa UNAM-DGAPA-PAPIME PE109323 «Hacia una modalidad a distancia de la Licenciatura en Matemáticas de la FC-UNAM – Etapa 3»