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 $\le$ un orden parcial en $A$ y sean $a,b\in A$. Decimos que $a$ y $b$ son $\le$-comparables si:

$a\le b$ o $b\le a$.

Ejemplo.

Sea $A=\{\mathrm{\varnothing },\{\mathrm{\varnothing }\},\{\mathrm{\varnothing },\{\mathrm{\varnothing }\}\}\}$ y sea ${\subseteq }_A$ la relación dada por el conjunto

${\subseteq }_A=\{(\mathrm{\varnothing },\mathrm{\varnothing }),(\mathrm{\varnothing },\{\mathrm{\varnothing }\}),(\mathrm{\varnothing },\{\mathrm{\varnothing },\{\mathrm{\varnothing }\}\}),(\{\mathrm{\varnothing }\},\{\mathrm{\varnothing }\}),(\{\mathrm{\varnothing }\},\{\mathrm{\varnothing },\{\mathrm{\varnothing }\}\}),(\{\mathrm{\varnothing },\{\mathrm{\varnothing }\}\},\{\mathrm{\varnothing },\{\mathrm{\varnothing }\}\})\}.$

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=\mathrm{\varnothing }$ y $b=\mathrm{\varnothing }$, entonces $a{\subseteq }_{A}b$ y $b{\subseteq }_{A}a$.
• Si $a=\{\mathrm{\varnothing }\}$ y $b=\{\mathrm{\varnothing }\}$, entonces $a{\subseteq }_{A}b$ y $b{\subseteq }_{A}a$.
• Si $a=\{\mathrm{\varnothing },\{\mathrm{\varnothing }\}\}$ y $b=\{\mathrm{\varnothing },\{\mathrm{\varnothing }\}\}$, entonces $a{\subseteq }_{A}b$ y $b{\subseteq }_{A}a$.
• Si $a=\mathrm{\varnothing }$ y $b=\{\mathrm{\varnothing }\}$, entonces $a{\subseteq }_{A}b$.
• Si $a=\mathrm{\varnothing }$ y $b=\{\mathrm{\varnothing },\{\mathrm{\varnothing }\}\}$, entonces $a{\subseteq }_{A}b$.
• Si $a=\{\mathrm{\varnothing }\}$ y $b=\{\mathrm{\varnothing },\{\mathrm{\varnothing }\}\}$, entonces $a{\subseteq }_{A}b$.

$\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/14.0.0/svg/25fb.svg">}$

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=\{\mathrm{\varnothing },\{\mathrm{\varnothing }\},\{\mathrm{\varnothing },\{\mathrm{\varnothing }\}\}\}$ y sea $R$ la relación definida como $R=\{(\mathrm{\varnothing },\{\mathrm{\varnothing }\}),(\mathrm{\varnothing },\{\mathrm{\varnothing },\{\mathrm{\varnothing }\}\}),(\{\mathrm{\varnothing }\},\{\mathrm{\varnothing },\{\mathrm{\varnothing }\}\})\}$. 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=\mathrm{\varnothing }$ y $b=\mathrm{\varnothing }$, entonces $a=b$,
• Si $a=\{\mathrm{\varnothing }\}$ y $b=\{\mathrm{\varnothing }\}$, entonces $a=b$,
• Si $a=\{\mathrm{\varnothing },\{\mathrm{\varnothing }\}\}$ y $b=\{\mathrm{\varnothing },\{\mathrm{\varnothing }\}\}$, entonces $a=b$,
• Si $a=\mathrm{\varnothing }$ y $b=\{\mathrm{\varnothing }\}$, entonces $a\in b$ y así, $aRb$,
• Si $a=\mathrm{\varnothing }$ y $b=\{\mathrm{\varnothing },\{\mathrm{\varnothing }\}\}$, entonces $a\in b$ y así, $aRb$,
• Si $a=\{\mathrm{\varnothing }\}$ y $b=\{\mathrm{\varnothing },\{\mathrm{\varnothing }\}\}$, entonces $a\in b$ y así, $aRb$.

$\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/14.0.0/svg/25fb.svg">}$

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

Ejemplo.

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

$R=\{(\mathrm{\varnothing },\mathrm{\varnothing }),(\mathrm{\varnothing },\{\mathrm{\varnothing }\}),(\mathrm{\varnothing },\{\mathrm{\varnothing },\{\mathrm{\varnothing }\}\}),(\{\mathrm{\varnothing }\},\{\mathrm{\varnothing }\}),(\{\mathrm{\varnothing }\},\{\mathrm{\varnothing },\{\mathrm{\varnothing }\}\}),(\{\mathrm{\varnothing },\{\mathrm{\varnothing }\}\},\{\mathrm{\varnothing },\{\mathrm{\varnothing }\}\})\}$.

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

$\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/14.0.0/svg/25fb.svg">}$

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

Ejemplo.

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

$R=\{(\mathrm{\varnothing },\{\mathrm{\varnothing }\}),(\mathrm{\varnothing },\{\mathrm{\varnothing },\{\mathrm{\varnothing }\}\}),(\{\mathrm{\varnothing }\},\{\mathrm{\varnothing },\{\mathrm{\varnothing }\}\})\}$.

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

$\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/14.0.0/svg/25fb.svg">}$

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,{\le }_A)$ es un conjunto parcialmente ordenado y tenemos dos elementos $a,b\in A$ tales que $a{\le }_{A}b$ pero $a\ne b$, entonces escribiremos simplemente $a{<}_{A}b$.

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

$(a,b){\ll }_v(a^{\prime },b^{\prime })$ si y sólo si ($a{<}_A{a}^{\prime }$) o ($a=a^{\prime }$ y $b{\le }_B{b}^{\prime }$).

Proposición. Sean $(A,{\le }_A)$ y $(B,{\le }_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 ${\le }_B$ es un orden parcial en $B$, entonces ${\le }_B$ es una relación reflexiva y así $b{\le }_{B}b$. En consecuencia, la conjunción $a=a$ y $b{\le }_{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{\le }_{B}d$).
  Como $(c,d){\ll }_v(a,b)$ entonces, ($c{<}_{A}a$) o ($c=a$ y $d{\le }_{B}b$).
  Probemos que $a=c$ y $b{\le }_{B}d$. Para probarlo supongamos que esto no ocurre buscando generar una contradicción. Dado que la conjunción $a=c$ y $b{\le }_{B}d$ no es verdadera, entonces, necesariamente debe ser cierto que $a{<}_{A}c$. Ahora, no puede ocurrir que $c{<}_{A}a$, pues de ser así tendríamos que $c{<}_{A}a$ y $a{<}_{A}c$ son verdaderas al mismo tiempo, y por ende se tendría que $c{\le }_{A}a$ pero $c\ne a$ y que $a{\le }_{A}c$ pero $a\ne c$. Así, en particular obtenemos que $c{\le }_{A}a$ y $a{\le }_{A}c$, pero esto implica que $a=c$ pues ${\le }_A$ es una relación antisimétrica. Este último hecho contradice que $a\ne c$. Por tanto, no puede ocurrir que $c{<}_{A}a$. Como consecuencia debe ser cierto que $c=a$ y $d{\le }_{B}b$, pero esto nuevamente contradice el hecho de que $a{<}_{A}c$, es decir, que $a{\le }_{A}c$ y $a\ne c$. Como la contradicción viene de suponer que $a{<}_{A}c$, entonces, debe ser cierto que $a=c$ y $b{\le }_{B}d$. Ya tenemos entonces que $a=c$ por lo que resta ver que $b=d$. Como $a=c$ entonces no puede ocurrir que $c{<}_{A}a$ y, por tanto, debe ocurrir que $c=a$ y $d{\le }_{B}b$ es verdadero. De esta manera tenemos que $b{\le }_{B}d$ y $d{\le }_{B}b$, de donde $d=b$ pues ${\le }_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{\le }_{B}d$).
  Como $(c,d){\ll }_v(e,f)$ entonces, ($c{<}_{A}e$) o ($c=e$ y $d{\le }_{B}f$).
  Caso 1: Si $a{<}_{A}c$ 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{\le }_{B}f$) es verdadero y así, $(a,b){\ll }_v(e,f)$.
  Caso 2: Si $a{<}_{A}c$ y $c=e$ y $d{\le }_{B}f$, entonces $a{<}_{A}e=c$. Por lo tanto, ($a{<}_{A}e$) o ($a=e$ y $b{\le }_{B}f$) es verdadero y así, $(a,b){\ll }_v(e,f)$.
  Caso 3: Si $a=c$ y $b{\le }_{B}d$ y $c{<}_{A}e$, entonces $a=c{<}_{A}e$. Por lo tanto, ($a{<}_{A}e$) o ($a=e$ y $b{\le }_{B}f$) es verdadero y así, $(a,b){\ll }_v(e,f)$.
  Caso 4: Si $a=c$ y $b{\le }_{B}d$ y $c=e$ y $d{\le }_{B}f$, entonces $a=e$ y $b{\le }_{B}f$ por transitividad de ${\le }_B$. Por lo tanto, ($a{<}_{A}e$) o ($a=e$ y $a{\le }_{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 ${\le }_A$ y ${\le }_B$ son órdenes totales en $A$ y $B$ respectivamente, tenemos que sus elementos son comparables, es decir, ($a{\le }_{A}c$ o $c{\le }_{A}a$) y ($b{\le }_{B}d$ o $d{\le }_{B}b$).

Caso 1: Si $a{\le }_{A}c$ y $b{\le }_{B}d$, hay dos posibles casos. Si $a{<}_{A}c$ y $b{\le }_{B}d$ se tiene que $(a,b){\ll }_v(c,d)$. Ahora, si $a=c$ y $b{\le }_{B}d$ entonces $(a,b){\ll }_v(c,d)$.

Caso 2: Si $a{\le }_{A}c$ y $d{\le }_{B}b$, hay dos posibles casos. Si $a{<}_{A}c$, entonces $(a,b){\ll }_v(c,d)$. Ahora, si $a=c$ y $d{\le }_{B}b$ entonces $(c,d){\ll }_v(a,b)$.

Caso 3: Si $c{\le }_{A}a$ y $b{\le }_{B}d$, hay dos posibles casos. Si $c{<}_{A}a$, entonces $(c,d){\ll }_v(a,b)$. Ahora, si $a=c$ y $b{\le }_{B}d$ entonces $(a,b){\ll }_v(c,d)$.

Caso 4: Si $c{\le }_{A}a$ y $d{\le }_{B}b$, hay dos posibles casos. Si $c{<}_{A}a$, entonces $(c,d){\ll }_v(a,b)$. Ahora, si $c=a$ y $d{\le }_{B}b$, entonces $(c,d){\ll }_v(a,b)$.

Esto muestra que el orden es total.

$\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/14.0.0/svg/25fb.svg">}$

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,{\le }_A)$ y $(B,{\le }_B)$ conjuntos parcialmente ordenados. Definimos al orden lexicográfico horizontal en $A\times B$ como sigue:

$(a,b){\ll }_h(a^{\prime },b^{\prime })$ si y sólo si ($b{<}_B{b}^{\prime }$) o ($b=b^{\prime }$ y $a{\le }_A{a}^{\prime }$).

Tarea moral

• Demuestra que el orden lexicográfico horizontal es un orden total.
• Consideremos $(\mathcal{P}(\{\{\mathrm{\varnothing }\},\{\mathrm{\varnothing },\{\mathrm{\varnothing }\}\},\{\mathrm{\varnothing },\{\mathrm{\varnothing }\},\{\mathrm{\varnothing },\{\mathrm{\varnothing }\}\}\}\},\subseteq )$. Da dos elementos que no sean comparables.
• Si consideramos $(A,{\le }_A)$ y $(B,{\le }_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{\le }_{A}c$ y $b{\le }_{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»