Archivo de la etiqueta: comparables

Teoría de los Conjuntos I: Sucesor

Por Gabriela Hernández Aguilar

Deja un comentario

Introducción

En esta nueva sección hablaremos acerca del sucesor de un número natural. Este nuevo concepto nos permitirá definir a los conjuntos inductivos e iniciar a descubrir el concepto del infinito desde la perspectiva de la teoría de conjuntos.

Concepto

Definición: Sea $x$ un conjunto, definimos al sucesor de $x$ como $s(x)=x\cup \set{x}$.

Ejemplos:

  • El sucesor de $\emptyset$ es $s(\emptyset)=\emptyset\cup \set{\emptyset}=\set{\emptyset}$.
  • El sucesor de $\set{\emptyset}$ es $s(\set{\emptyset})=\set{\emptyset}\cup \set{\set{\emptyset}}=\set{\emptyset, \set{\emptyset}}$.
  • Luego, el sucesor de $\set{\emptyset, \set{\emptyset}}$ es $s(\set{\emptyset, \set{\emptyset}})=\set{\emptyset,\set{\emptyset}}\cup \set{\set{\emptyset, \set{\emptyset}}}=\set{\emptyset, \set{\emptyset}, \set{\emptyset, \set{\emptyset}}}$.
  • El sucesor de $\set{\set{\emptyset}}$ es $s(\set{\set{\emptyset}})=\set{\set{\emptyset}}\cup \set{\set{\set{\emptyset}}}= \set{\set{\emptyset}, \set{\set{\emptyset}}}$.

$\square$

Aunque podemos definir al sucesor para cualquier conjunto, dado que en esta unidad únicamente estaremos trabajando con números naturales, usaremos la definición de sucesor de un conjunto para conjuntos que son números naturales.

Bajo este hecho va a resultar que si $x$ es un número natural, entonces $s(x)$ es un número natural, vamos a demostrar esto, pero antes demostraremos algunos lemas que nos serán de utilidad.

Resultados previos

Lema 1: Para cualquier número natural $n$, no es posible que $n\in n$.

Demostración:

Sea $n$ un número natural, entonces $n$ es un orden total con la $\in$ y así, los elementos de $n$, son $\in$-comparables, es decir, para cualesquiera $w,z\in n$ se tiene que $w\in z$ o $z\in w$ o $z=w$.

Dado que $n=n$, no ocurre que $n\in n$.

$\square$

Lema 2: Si $n$, $m$ son números naturales, entonces no es posible que $n\in m$ y $m\in n$ al mismo tiempo.

Demostración:

Sean $n$ y $m$ números naturales. Si $n\in m$ y $m\in n$, entonces $n\in n$ por transitividad de $\in$ en $n$, lo cual contradice el lema anterior.

Por lo tanto, no es posible que $n\in m$ y $m\in n$ al mismo tiempo.

$\square$

El sucesor de un natural

Ahora que demostramos los lemas anteriores probaremos que el sucesor de un número natural es un número natural.

Teorema:

  1. $\emptyset$ es un número natural.
  2. Si $x$ es un número natural, entonces $s(x)$ es un número natural.

Demostración:

En la entrada anterior probamos que $\emptyset$ es un número natural, lo que prueba el punto uno del teorema.

Ahora, sea $x$ un número natural. Veamos que $s(x)$ es un número natural, para ello vamos a probar que $x\cup\set{x}$ es un conjunto transitivo, ordenado totalmente con $\in$ y que para cada subconjunto $b$ no vacío se cumple que $b$ tiene mínimo y máximo con la pertenencia en $b$.

Sea $y\in x\cup\set{x}$. Si $y\in x$ dado que $x$ es un número natural, entonces $x$ es un conjunto transitivo y por lo tanto, $y\subseteq x$. Así, $y\subseteq x\cup\set{x}$.

Si $y\in \set{x}$, entonces $y=x$ y en particular, $y\subseteq x$ y así, $y\subseteq x\cup\set{x}$.

Por lo tanto, $s(x)$ es un conjunto transitivo.

Ahora, queremos ver que $s(x)$ es un orden total con la $\in_{s(x)}$, para ello debemos probar que $\in_{s(x)}$ es una relación asimétrica y transitiva, además de que sus elementos son $\in_{s(x)}$ comparables.

Sean $y,z\in s(x)$ tales que $y\in_{s(x)} z$. Veamos que no es posible que $z\in_{s(x)} y$.

Dado que $y,z\in s(x)=x\cup \set{x}$, tenemos los siguientes casos:

Caso 1: Si $y\in x$ y $z\in x$, entonces por ser $\in_x$ una relación asimétrica en $x$ y $y\in z$, se tiene que no es posible que $z\in y$.

Caso 2: Si $y\in x$ y $z\in \set{x}$, entonces $z=x$. Dado que $y\in z$, si ocurriera que $z\in y$, entonces $x\in y$ y así, $x\in y$ y $y\in x$, lo cual probamos en el lema 2 que no ocurre, por lo tanto, $z\notin y$.

El caso $y\in \set{x}$ y $z\in x$, entonces $y=x$. Dado que $y\in z$, entonces $x\in z$, lo cual no puede ocurrir pues de ser así, $x\in z$ y $z\in x$ al mismo tiempo, lo que contradice al lema 2.

El caso en el que $y\in \set{x}$ y $z\in \set{x}$ no puede ocurrir pues de ser así, $y=x$ y $z=x$, en particular $y=z$ y por el primer lema de esta entrada vimos que no ocurre que $y\in y$.

Así, en cualquiera de los casos se satisface que $\in_{s(x)}$ es una relación asimétrica.

Ahora, veamos que $\in_{s(x)}$ es una relación transitiva. Para ello tomemos $w,y,z\in s(x)$ arbritarios tales que $w\in_{s(x)} y$ y $y\in_{s(x)} z$ y veamos que $w\in_{s(x)} z$.

Del hecho, $w\in_{s(x)} y$ y $y\in_{s(x)} z$ se derivan los siguientes casos:

Caso 1: Si $w\in x$, $y\in x$ y $z\in x$. Dado que $w\in y$ y $y\in z$, como $\in$ es una relación transitiva en $x$ se tiene que $w\in z$.

Caso 2: Si $w\in x$, $y\in x$ y $z\in \set{x}$, entonces $z=x$, por lo que $w\in z=x$.

El caso $w\in x$, $y\in \set{x}$ y $z\in \set{x}$, entonces $y=x=z$. Dado que $w\in y$ y $y\in z$, se tendría que $w\in y$ y $y\in y$, lo cual contradice al lema 1.

El caso $w,y,z\in\set{x}$ no es posible, pues de lo contrario $w=y=z=x$ y así $w\in w$, lo cual contradice al lema 1.

Por lo tanto, $\in_{s(x)}$ es una relación transitiva.

Finalmente, los elementos de $s(x)$ son $\in_{s(x)}$-comparables. En efecto, sean $y,z\in s(x)$.

Caso 1: Si $y\in x$ y $z\in x$, entonces como los elementos de $x$ son $\in$-comparables, debe ocurrir que $y\in z$ o $z\in y$ o $z=y$.

Caso 2: Si $y\in x$ y $z\in \set{x}$, entonces $z=x$. Por lo tanto, $y\in z$.

Caso 3: Si $y\in \set{x}$ y $z\in x$, entonces $y=x$. Por lo tanto, $z\in y$.

Caso 4: Si $y\in \set{x}$ y $z\in \set{x}$, entonces $y=x$ y $z=x$. Por lo tanto, $z=y$.

Por lo tanto, los elementos de $s(x)$ son $\in_{s(x)}$-comparables.

Así, $(s(x), \in)$ es un orden total.

Ahora, supongamos que $B$ conjunto no vacío es subconjunto de $s(x)$ y veamos que $B$ tiene máximo y mínimo.

Caso 1: Si $B\cap x=\emptyset$, entonces $B\subseteq \set{x}$ y como $B\not=\emptyset$ entonces $B=\set{x}$.

Luego, $x=\min (B)$ pues se satisface que para cualquier $y\in B\setminus \set{x}=\emptyset$, $x\in y$ por vacuidad.

Finalmente, $x=\max (B)$ pues se satisface que para cualquier $y\in B\setminus \set{x}=\emptyset$, $y\in x$ por vacuidad.

Caso 2: Si $B\cap x\not= \emptyset$, entonces $B\cap x$ es un subconjunto no vacío de $x$. Así, dado que $x$ es un natural, se satisface que $B\cap x$ tiene elemento mínimo y máximo con respecto a la $\in$ en $x$. Sea $b=\min (B\cap x)$ con respecto a la pertenencia en $x$ y $a=\max (B\cap x)$ con respecto a la pertenencia en $x$.

Veamos que $b=min(B)$ con respecto a $\in$ en $s(x)$. Sea $z\in B\setminus \set{b}$ arbitrario, vamos a probar que $b\in z$.

Caso 1: Si $z\in x$, entonces $z\in B\cap x$, entonces $b\in z$ pues $b=\min(B\cap x)$.

Caso 2: Si $z\notin x$, dado que $z\in s(x)=x\cup\set{x}$ entonces $z=x$. Como $b\in B\cap x$, entonces $b\in x$ y así, $b\in z$.

Así, $b=\min(B)$ para $B\subseteq s(x)$.

En la tarea moral será tu turno de probar que cualquier subconjunto no vacío de $s(x)$ tiene elemento máximo con respecto a la pertenencia en $s(x)$.

Por lo tanto, cualquier subconjunto de $s(x)$ tiene elemento mínimo y máximo con respecto a la $\in$ en $s(x)$.

Por lo tanto, $s(x)$ es un natural.

$\square$

Tarea moral

  • Describe al sucesor del natural $\set{\emptyset, \set{\emptyset}, \set{\emptyset, \set{\emptyset}}, \set{\emptyset, \set{\emptyset},\set{\emptyset, \set{\emptyset}}}}$.
  • Demuestra que si $s(n)=s(m)$, entonces $n=m$.
  • Prueba que $\bigcup s(x)=x$.
  • Demuestra que si $B$ es un subconjunto no vacío de $s(x)$, entonces $B$ tiene elemento máximo con respecto a la pertenencia en $s(x)$.

Más adelante

En la siguiente sección definiremos a los conjuntos inductivos, tales conjuntos nos darán la base para definir al conjunto de los naturales. Además hablaremos de un nuevo axioma: el axioma del infinito.

Enlaces

En el siguiente enlace podrás repasar el contenido acerca de números naturales. así mismo podrás ver más contenido acerca del tema:

Nota 16. Los números naturales.

Teoría de los Conjuntos I: Orden total

Por Gabriela Hernández Aguilar

Deja un comentario

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