Archivo de la etiqueta: comparables

Teoría de los Conjuntos I: Orden total

Introducción

En esta sección hablaremos acerca de ordenes totales, retomaremos el concepto de orden parcial y orden parcial estricto y añadiremos el concepto de ser comparable. Además hablaremos acerca del orden lexicográfico vertical y horizontal.

Concepto

Definición: Sea $\leq$($<$) una relación de orden en $A$ y sean $a, b\in A$. Decimos que $a$ y $b$ son $\leq$-comparables($<$-comparables) en el orden $\leq$ ($<$) si:

$a\leq b$ o $b\leq a$
($a<b$, o $a=b$, o $b<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}})}$

una relación de orden parcial.

Luego, dados $a,b\in A$ podemos decidir si $a\subseteq b$ o $b\subseteq 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_R b$ y $b\subseteq_R a$.
  • Si $a=\emptyset$ y $b=\set{\emptyset}$, entonces $a\subseteq_R 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$

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}})}$ una relación de orden parcial 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$ ($<$) orden parcial (estricto) en $A$. Si para cualesquiera $a, b\in A$ son $\leq(<)$-comparables, entonces $\leq(<)$ es un orden total.

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 al producto cartesiano de dos conjuntos 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 totalmente 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: El orden lexicográfico vertical es un orden total.

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$).
    Luego, tiene que ocurrir 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, pues estamos suponiendo que no ocurre, 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)$.

$\square$

Orden lexicográfico horizontal

A continuación definiremos al orden lexicográfico horizontal, este orden también será un orden total. (Probar que $(A\times B, \ll_h)$ es un orden total será parte de tu tarea moral).

Definición: Sean $(A, \leq_A)$ y $(B, \leq_B)$ conjuntos totalmente 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 y definimos la relación producto en $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 es un orden total.

Más adelante

En la siguiente sección 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 permitan acotar a un conjunto.

Enlaces

Aquí puedes consultar más contenido acerca de órdenes totales:

Álgebra Superior I: Órdenes parciales y totales