Archivo de la etiqueta: teoría de conjuntos

Teoría de los Conjuntos I: Cotas inferiores e ínfimos

Por Gabriela Hernández Aguilar

Deja un comentario

Introducción

En esta entrada hablaremos acerca de cotas inferiores e ínfimos. Estos nuevos conceptos nos permitirán establecer intuitivamente qué quiere decir que un conjunto esté «limitado» una vez que hemos dado un orden.

Cotas inferiores

Para comenzar definiremos qué es una cota inferior. Notaremos que este concepto es muy parecido al de mínimo, sin embargo la cota inferior podría no ser elemento de $B$ un subconjunto de $A$. Veamos la definición.

Definición. Sea $(A, \leq)$ un orden parcial y sea $B\subseteq A$. Decimos que $a\in A$ es una cota inferior de $B$ si $a\leq x$ para toda $x\in B$. Si $B$ tiene por lo menos una cota inferior, diremos que $B$ está acotado inferiormente.

Ejemplo.

Sea $A=\set{\emptyset, \set{\emptyset}, \set{\emptyset, \set{\emptyset}}}$ y consideremos al conjunto parcialmente ordenado $(A, \subseteq)$. Sea $B= \set{\set{\emptyset}, \set{\emptyset, \set{\emptyset}}}\subseteq A$, tenemos que $\emptyset\in A$ es una cota inferior de $B$ pues $\emptyset\subseteq x$ para todo $x\in B$, como se muestra en el siguiente diagrama:

Sin embargo, podemos notar que $\emptyset\notin B$, por lo que para ser cota inferior no es necesario ser elemento de $B$, solo de $A$. Por otro lado, $\set{\emptyset}\in B$ también es una cota inferior de $B$ pues para cada $x\in B$, $\set{\emptyset}\subseteq x$. Más aún, $\set{\emptyset}$ es el elemento mínimo de $B$.

$\square$

El ejemplo anterior sugiere que la propiedad de ser mínimo implica ser cota inferior, pero no es válido el recíproco.

En este último ejemplo es posible notar que la cota inferior en un conjunto puede no ser única, y entonces podemos pensar en el conjunto que tenga a todas las cotas inferiores. Esta idea junto con el concepto de máximo motiva el concepto de ínfimo.

Ínfimos

Definición. Sea $(A, \leq)$ un orden parcial y sea $B\subseteq A$. Decimos que $a\in A$ es ínfimo de $B$ si es el elemento máximo del conjunto de todas las cotas inferiores de $B$. Lo denotaremos por $\inf(B)$.

Ejemplo.

Retomando el ejemplo anterior, si consideramos al conjunto de todas las cotas inferiores de $B$, es decir, $\set{\emptyset, \set{\emptyset}}$ tenemos que el ínfimo es $\set{\emptyset}$ pues respecto al orden de $A$, $\emptyset\subseteq \set{\emptyset}$ y por lo tanto, $\set{\emptyset}$ es el máximo de las cotas inferiores de $B$.

$\square$

Teorema. Sea $(A, \leq)$ un orden parcial y $B\subseteq A$ un conjunto no vacío. Si $B$ tiene ínfimo en el orden $\leq$, entonces es único.

Demostración.

Sea $(A,\leq)$ un orden parcial y $B\subseteq A$ no vacío. Supongamos que $B$ tiene ínfimo, es decir, que existe $a\in A$ de tal forma que $a\leq x$ para toda $x\in B$ y, si $b\in A$ es tal que $b\leq x$ para toda $x\in B$, entonces, $b\leq a$.

Supongamos que $a_1,a_2\in A$ son ínfimos de $B$. Veamos que $a_1=a_2$.

Como $a_1$ es ínfimo $B$, en particular se tiene que $a_1\leq x$ para toda $x\in B$. Luego, como $a_2$ es ínfimo de $B$ se sigue por definición que $a_1\leq a_2$. De manera análoga, como $a_2$ es ínfimo de $B$, en particular se tiene que $a_2\leq x$ para toda $x\in B$ y así, como $a_1$ es ínfimo de $B$ se sigue por definición que $a_2\leq a_1$.

Tenemos entonces que $a_1\leq a_2$ y $a_2\leq a_1$, de donde se sigue que $a_1=a_2$, lo cual demuestra la unicidad del ínfimo.

$\square$

Teorema. Sea $(A, \leq)$ un orden parcial y $B\subseteq A$ un conjunto no vacío. Si $B$ tiene un elemento mínimo $b$, entonces $b$ es el ínfimo de $B$.

Demostración.

Sea $(A, \leq)$ un orden parcial y $B\subseteq A$ un conjunto no vacío. Luego como $b\in B$ es el elemento mínimo de $B$, entonces para cualquier $x\in B$, $b\leq x$.

Sea $C$ el conjunto de todas las cotas inferiores de $B$. Veamos que $b\in C$ y que $b=\max(C)$. Dado que $b\leq x$ para todo $x\in B$, entonces $b$ es cota inferior de $B$ y, por tanto, $b\in C$. Luego, si $c\in C$ es cualquier elemento, entonces $c$ es cota inferior de $B$, es decir, $c\leq x$ para cualquier $x\in B$. En particular, como $b\in B$ se tiene que $c\leq b$. Esto muestra que $b=\max(C)$.

Por lo tanto, $b=\inf(B)$.

$\square$

Aún cuando ser mínimo implica ser ínfimo, no siempre va a ocurrir que el ínfimo de un conjunto sea mínimo, como ocurre en el siguiente ejemplo.

Ejemplo.

Sea $A=\set{\emptyset, \set{\emptyset}, \set{\set{\emptyset}}, \set{\emptyset, \set{\emptyset}}}$ y consideremos al conjunto parcialmente ordenado $(A, \subseteq)$. Sea $B= \set{\set{\emptyset}, \set{\set{\emptyset}}, \set{\emptyset, \set{\emptyset}}}\subseteq A$. Tenemos que $\emptyset \in A$ es una cota inferior de $B$ pues $\emptyset\leq x$ para todo $x\in B$, como se muestra en el siguiente diagrama:

Sin embargo, $B$ no tiene mínimo pues no existe $x\in B$ tal que $x\leq y$ para todo $y\in B$. En efecto, si existiera tal $x$ tendría que ser simultáneamente subconjunto de $\set{\emptyset}$ y de $\set{\set{\emptyset}}$. Pero el único subconjunto que comparten estos conjuntos es $\emptyset$, que no está en $B$.

$\square$

Tarea moral

La siguiente lista de ejercicios te ayudará a reforzar el contenido de esta entrada y de la entrada anterior.

  1. Sean $(A, \leq)$ un orden parcial y $B\subseteq A$ un conjunto no vacío. Demuestra que si $b$ es ínfimo y $b\in B$, entonces $b$ es mínimo de $B$.
  2. Sean $(A, \leq)$ un orden parcial y $B,C\subseteq A$ no vacíos. Si $B$ y $C$ tienen ínfimo y $C\subseteq B$, demuestra que $inf (B)\leq inf (C)$.
  3. Exhibe un conjunto que esté acotado inferiormente pero que no tenga ínfimo.
  4. Da un ejemplo de un conjunto parcialmente ordenado $(A,\leq)$ en el cual se cumpla que el conjunto $\emptyset$ tiene ínfimo.
  5. Escribe las definiciones de cota inferior e ínfimo para un orden parcial estricto.

Más adelante…

La siguiente entrada estará dedicada a cotas superiores y supremos. Con esto concluiremos la sección de acotar conjuntos ordenados.

Entradas relacionadas

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»

Teoría de los Conjuntos I: Mínimos, máximos, minimales y maximales

Por Gabriela Hernández Aguilar

Deja un comentario

Introducción

Una vez que se le ha dado un orden a los elementos de un conjunto, podemos decir más acerca de ellos. En esta entrada hablaremos de aquellos elementos con características especiales, según sean éstas los llamaremos mínimos, máximos, minimales o maximales.

Mínimos y máximos

Comenzaremos definiendo a los mínimos y máximos en un conjunto parcialmente ordenado.

Definición. Sea $\leq$ un orden parcial en $A$ y sea $B\subseteq A$. Decimos que $b\in B$ es elemento mínimo de $B$ en el orden $\leq$ si para cualquier $x\in B$, se tiene que $b\leq x$.

Ejemplo.

Consideremos $A= \set{\emptyset, \set{\emptyset}, \set{\emptyset, \set{\emptyset}}}$ y sea $\subseteq_A$ la relación de contención en $A$. Si consideramos $A\subseteq A$, tenemos que $\emptyset$ es elemento mínimo pues para cada elemento de $A$, se tiene que $\emptyset$ está por debajo o es igual. Más explícitamente, $\emptyset\subseteq \emptyset$, $\emptyset\subseteq \set{\emptyset}$ y $\emptyset\subseteq \set{\emptyset, \set{\emptyset}}$, como se muestra en el siguiente diagrama:

4$\square$

Definición. Sea $\leq$ un orden parcial en $A$ y sea $B\subseteq A$. Decimos que $b\in B$ es elemento máximo de $B$ en el orden $\leq$ si para cualquier $x\in B$, se tiene que $x\leq b$.

Ejemplo.

Consideremos $A= \set{\emptyset, \set{\emptyset}, \set{\emptyset, \set{\emptyset}}}$ y sea $\subseteq_A$ la relación de contención en $A$. Si consideramos $A\subseteq A$, tenemos que $\set{\emptyset, \set{\emptyset}}$ es elemento máximo pues para cada elemento de $A$, se tiene que $\set{\emptyset, \set{\emptyset}}$ esta por encima o es igual a ellos. Más explícitamente, $\emptyset\subseteq \set{\emptyset, \set{\emptyset}}$, $\set{\emptyset}\subseteq \set{\emptyset, \set{\emptyset}}$ y $\set{\emptyset, \set{\emptyset}}\subseteq \set{\emptyset, \set{\emptyset}}$ como se muestra en el siguiente diagrama:

$\square$

Minimales y maximales

Definición. Sea $\leq$ un orden parcial en $A$ y sea $B\subseteq A$. Decimos que $b\in B$ es elemento minimal de $B$ en el orden $\leq$ si no existe $x\in B$ tal que $x\leq b$ y $x\not=b$.

Ejemplo.

Consideremos $A= \set{\emptyset, \set{\emptyset}, \set{\emptyset, \set{\emptyset}}}$ y sea $\subseteq_A$ la relación de contención en $A$. Si consideramos $A\subseteq A$, tenemos que $\emptyset$ es elemento minimal pues no existe $x\in B$ tal que $x\subseteq \emptyset$ y $x\not=\emptyset$.

$\square$

Definición. Sea $\leq$ un orden parcial en $A$ y sea $B\subseteq A$. Decimos que $b\in B$ es elemento maximal de $B$ en el orden $\leq$ si no existe $x\in B$ tal que $b\leq x$ y $x\not=b$.

Ejemplo.

Consideremos $A=\set{\emptyset, \set{\emptyset}, \set{\emptyset, \set{\emptyset}}}$ y sea $\subseteq_A$ la relación de contención en $A$. Si consideramos $A\subseteq A$, tenemos que $\set{\emptyset, \set{\emptyset}}$ es elemento maximal pues no existe $x\in B$ tal que $\set{\emptyset, \set{\emptyset}}\subseteq x$ y $x\not=\set{\emptyset, \set{\emptyset}}$.

$\square$

Diferencias entre las definiciones

Podemos preguntarnos si la definición de minimal es equivalente a la de mínimo o si la de maximal es equivalente a la de máximo. Sin embargo, va a resultar que las definiciones de minimal y maximal son más débiles que las de mínimo y máximo, respectivamente. Veamos el siguiente ejemplo que muestra que pueden existir elementos minimales sin que haya un elemento mínimo.

Ejemplo.

Consideremos el conjunto parcialmente ordenado $(\set{\set{\emptyset}, \set{\set{\emptyset}}, \set{\emptyset, \set{\emptyset}}}, \subseteq)$. Veamos el siguiente diagrama:

En la imagen anterior podemos notar que $\set{\emptyset}\subseteq \set{\emptyset, \set{\emptyset}}$ y $\set{\set{\emptyset}}\subseteq \set{\emptyset, \set{\emptyset}}$ y que éstas son las únicas relaciones posibles por la definición de contención. Luego, $\set{\emptyset}$ y $\set{\set{\emptyset}}$ son minimales pues no existe $x\in \set{\set{\emptyset}, \set{\set{\emptyset}}, \set{\emptyset, \set{\emptyset}}}$ tal que $x\subseteq \set{\emptyset}$ y $x\not=\set{\emptyset}$ ni $x\subseteq \set{\set{\emptyset}}$ y $x\not=\set{\set{\emptyset}}$.

Además, $\set{\set{\emptyset}, \set{\set{\emptyset}}, \set{\emptyset, \set{\emptyset}}}$ no tiene elemento mínimo pues de existir $x\in \set{\set{\emptyset}, \set{\set{\emptyset}}, \set{\emptyset, \set{\emptyset}}}$ tal que $x\subseteq y$ para todo $y\in \set{\set{\emptyset}, \set{\set{\emptyset}}, \set{\emptyset, \set{\emptyset}}}$, en particular, se tendría que $x\subseteq \set{\emptyset}$. Luego, el único elemento $x$ con esta propiedad en el conjunto $\set{\set{\emptyset},\set{\set{\emptyset}},\set{\emptyset,\set{\emptyset}}}$ es $\set{\emptyset}$ y en consecuencia, $x=\set{\emptyset}$. Por otro lado, por ser $x$ mínimo se tendría que $x\subseteq \set{\set{\emptyset}}$, y así $\set{\emptyset}\subseteq \set{\set{\emptyset}}$, es decir, $\set{\emptyset}\subseteq\set{\set{\emptyset}}$, lo cual no es verdad. Por lo tanto, no existe un mínimo en el conjunto $ \set{\set{\emptyset},\set{\set{\emptyset}},\set{\emptyset,\set{\emptyset}}} $.

$\square$

De este ejemplo podemos concluir que aunque un conjunto tenga minimal no necesariamente tendrá mínimo. Esto se debe a que en un conjunto puede existir más de un elemento minimal y en cambio, si un conjunto tiene mínimo, entonces éste resulta ser único, como demostraremos a continuación.

Proposición. Sea $(A, \leq)$ un orden parcial. Si $b\in A$ es mínimo, entonces es único.

Demostración.

Sea $b\in A$ un elemento mínimo, entonces $b\leq a$ para cualquier $a\in A$. Supongamos que $c\in A$ también es elemento mínimo, así, $c\leq a$ para cualquier $a\in A$. Como $b\in A$, entonces $c\leq b$ y de manera similar, $b\leq c$, pues $c\in A$. Por lo tanto, $b=c$ por la antisimetría de $\leq$ en $A$.

$\square$

Dado que el elemento mínimo de un orden parcial $(A,\leq)$ es único, le podemos asignar una notación y lo vamos a denotar como $\min(A)$.

Ahora, veamos el siguiente ejemplo que muestra que pueden existir elementos maximales sin que haya un elemento máximo.

Ejemplo.

Consideremos el conjunto parcialmente ordenado $(\set{\emptyset, \set{\emptyset}, \set{\set{\emptyset}}}, \subseteq)$. Veamos el siguiente diagrama:

En la imagen anterior podemos notar que $\emptyset\subseteq \set{\emptyset}$ y $\emptyset\subseteq \set{\set{\emptyset}}$ y que estás son las únicas relaciones posibles por la definición de contención. Luego, $\set{\emptyset}$ y $\set{\set{\emptyset}}$ son maximales pues no existe $x\in \set{\emptyset, \set{\emptyset}, \set{\set{\emptyset}}}$ tal que $\set{\emptyset}\subseteq x$ y $x\not=\set{\emptyset}$ y $\set{\set{\emptyset}}\subseteq x$ y $x\not=\set{\set{\emptyset}}$, respectivamente.

Notemos también que $\set{\emptyset, \set{\emptyset}, \set{\set{\emptyset}}}$ no tiene elemento máximo pues de existir $x\in \set{\emptyset, \set{\emptyset}, \set{\set{\emptyset}}} $ tal que $y\subseteq x$ para todo $y\in \set{\emptyset, \set{\emptyset}, \set{\set{\emptyset}}}$, se tendría en particular que $\set{\emptyset}\subseteq x$, de donde se sigue que $x=\set{\emptyset}$, pues este es el único elemento con tal propiedad en el conjunto $\set{\emptyset,\set{\emptyset},\set{\set{\emptyset}}}$. Luego, como $x=\set{\emptyset}$ es máximo se sigue que $\set{\set{\emptyset}}\subseteq\set{\emptyset}$, es decir, $\set{\set{\emptyset}}\subseteq\set{\emptyset}$, lo cual no es verdad. Por lo tanto, el conjunto $\set{\emptyset,\set{\emptyset},\set{\set{\emptyset}}}$ no tiene elemento máximo.

$\square$

De este ejemplo podemos concluir que aunque un conjunto tenga elementos maximales no necesariamente tendrá máximo. Esto se debe a que puede existir más de un elemento maximal y, si un conjunto tiene máximo, éste resulta ser único.

Proposición: Sea $(A, \leq)$ un orden parcial. Si $b\in A$ es máximo, entonces es único.

Demostración.

Sea $b\in A$ un elemento máximo, entonces $a\leq b$ para cualquier $a\in A$. Supongamos que $c\in A$ también es elemento máximo, así, $a\leq c$ para cualquier $a\in A$. Como $b\in A$, entonces $b\leq c$ y de manera similar, $c\leq b$, pues $c\in A$. Por lo tanto, $b=c$ por la antisimetría de $\leq$ en $A$.

$\square$

Dado que el elemento máximo de un orden parcial $(A,\leq)$ es único, le podemos asignar una notación y lo vamos a denotar como $\max(A)$

Máximo y maximal en un orden total

Ya vimos que los conceptos de elemento máximo y maximal en un orden parcial no coinciden en general, sin embargo, podríamos preguntarnos si esto mismo sucede en un orden total. En el siguiente lema veremos que en un orden total de hecho sí coinciden.

Lema: Sea $(A, \leq)$ un orden total. Entonces, $b$ es elemento maximal de $A$ si y sólo si $b$ es elemento máximo de $A$.

Demostración.

Sea $(A,\leq)$ un orden total. Supongamos que $b\in A$ es un elemento maximal. Sea $a\in A$. Luego, por ser $(A,\leq)$ un orden total, $a\leq b$ o $b\leq a$. Si $b\leq a$, entonces, $a=b$ por ser $b$ elemento maximal, de modo que las condiciones $a\leq b$ o $b\leq a$ pueden ser escritas como $a\leq b$ o $a=b$, es decir, $a\leq b$. Por lo tanto, para cada $a\in A$, $a\leq b$ y, en consecuencia, $b=max(A)$.

Si ahora suponemos que $b\in A$ es elemento máximo, entonces, no existe $a\in A$ con $b\leq a$ y $b\not=a$, de lo contrario $b$ no sería máximo. Por lo tanto, $b$ es elemento maximal. Por lo tanto, $b$ es maximal si y sólo si $b$ es máximo.

$\square$

Definiciones para órdenes estrictos

Definición. Sea $<$ un orden estricto en $A$ y sea $B\subseteq A$. Decimos que $b\in B$ es elemento mínimo de $B$ en el orden $<$ si para cualquier $x\in B\setminus\set{b}$, $b<x$.

Definición. Sea $<$ un orden estricto en $A$ y sea $B\subseteq A$. Decimos que $b\in B$ es elemento máximo de $B$ en el orden $<$ si para cualquier $x\in B\setminus\set{b}$, $x<b$.

Definición. Sea $<$ un orden estricto en $A$ y sea $B\subseteq A$. Decimos que $b\in B$ es elemento minimal de $B$ en el orden $<$ si no existe $x\in B$ tal que $x< b$.

Definición. Sea $<$ un orden en $A$ y sea $B\subseteq A$. Decimos que $b\in B$ es elemento maximal de $B$ en el orden $<$ si no existe $x\in B$ tal que $b< x$.

Tarea moral

La siguiente lista de ejercicios te permitirá reforzar el tema de esta sección:

Sea $(A, \leq)$ un conjunto parcialmente ordenado. Demuestra que si $A$ tiene máximo, entonces tiene maximal.

Sea $(A, \leq)$ un conjunto parcialmente ordenado. Demuestra que si $A$ tiene mínimo, entonces tiene minimal.

Muestra que si $(A,\leq)$ es un conjunto totalmente ordenado y $A$ tiene un elemento minimal, entonces es único.

Más adelante…

En la siguiente entrada seguiremos hablando de elementos con características especiales en un conjunto según estén ordenados. Hablaremos acerca de las cotas superiores e inferiores, así como de supremos e ínfimos.

Entradas relacionadas

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»

Teoría de los Conjuntos I: Ordenes totales

Por Gabriela Hernández Aguilar

Deja un comentario

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

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»

Teoría de los Conjuntos: Órdenes parciales y órdenes estrictos

Por Gabriela Hernández Aguilar

2 respuestas

Introducción

La sensación que quizás te quedó tras discutir las relaciones de equivalencia es que una relación de equivalencia establece cuándo elementos de un conjunto son «iguales» o «similares». Ahora introduciremos otros tipos de relaciones que nos harán pensar cuándo para dos elementos de un conjunto uno es «mayor» o «mejor» que otro bajo cierto criterio de comparación.

Antisimetría y orden parcial

Definición. Sea $R$ una relación sobre un conjunto $A$. Decimos que $R$ es una relación antisimétrica si y sólo si para cualesquiera $a,b\in A$ tales que $(a,b)\in R$ y $(b,a)\in R$ se tiene que $a=b$.

Veamos algunos ejemplos.

Ejemplo.

Sea $A$ un conjunto y sea $R$ la relación en $A$ definida como:

$aRb\ \text{si y sólo si} \ a\subseteq b$.

Veamos que $R$ es antisimétrica. En efecto, sean $a, b\in A$ tales que $(a,b)\in R$ y $(b,a)\in R$, entonces por definición de $R$ tenemos que $a\subseteq b$ y $b\subseteq a$. Por lo tanto, $a=b$.

$\square$

Ejemplo.

Sea $A$ un conjunto. Tenemos que $Id_A$ es una relación antisimétrica pues, si $(a,b)\in Id_A$ y $(b,a)\in Id_A$, entonces, $a=b$ por definición de $Id_A$.

$\square$

Para la siguiente definición es necesario recordar el concepto de relación reflexiva y transitiva que puedes encontrar en el la entrada de relaciones de equivalencia.

Definición. Sea $R$ una relación en $A$. Si $R$ es una relación reflexiva, antisimétrica y transitiva, entonces decimos que $R$ es un orden parcial en $A$. Para abreviar, diremos que $(A, R)$ es un orden parcial.

Ejemplo.

Si $A=\emptyset$, entonces la relación $\emptyset$ es un orden parcial en $A$. En efecto, se cumplen las tres propiedades que necesitamos:

  1. Como no hay $a\in A$, entonces $a\in A$ implica $(a,a)\in \emptyset$ por vacuidad. Por lo tanto, $\emptyset$ es una relación reflexiva.
  2. Como no hay elementos en $\emptyset$, entonces por vacuidad si $(a,b)\in \emptyset$ y $(b,a)\in \emptyset$, entonces $a=b$. Por lo tanto, $\emptyset$ es una relación antisimétrica.
  3. Como no hay elementos en $\emptyset$, entonces por vacuidad si $a,b,c\in A$ tales que $(a,b)\in \emptyset$ y $(b,c)\in \emptyset$, entonces $(a,c)\in \emptyset$. Por lo tanto, $\emptyset$ es una relación transitiva.

$\square$

Ejemplo.

Si $A$ es un conjunto y $R$ es la relación en $A$ definida como sigue:

$aRb\ \text{si y sólo si} \ a\subseteq b$,

entonces $R$ es un orden parcial. En efecto, se cumplen las tres propiedades que necesitamos:

  1. Sea $a\in A$, entonces $(a, a)\in R$ pues $a\subseteq a$ para cualquier conjunto $a$. Por lo tanto, $R$ es una relación reflexiva.
  2. Sean $a,b\in A$ tales que $(a,b)\in R$ y $(b,a)\in R$. Ya probamos que esto implica $a=b$. Por lo tanto, $R$ es una relación antisimétrica.
  3. Sean $a,b,c\in A$ tales que $(a,b)\in R$ y $(b,c)\in R$, entonces $a\subseteq b$ y $b\subseteq c$ respectivamente. Luego, $a\subseteq b$ y $b\subseteq c$ implican que $a\subseteq c$. Por lo tanto, $(a,c)\in R$ y así, $R$ es una relación transitiva.

Por lo tanto, $R$ es un orden parcial.

$\square$

Cuando una relación $R$ es un orden parcial, entonces la expresión $aRb$ se comporta como el símbolo $\leq$. Por ello, usualmente nos referiremos a los órdenes parciales usando este símbolo e intuitivamente pensaremos que una relación parcial nos permite decir cuando un elemento es menor o igual que otro.

Orden estricto

Si los órdenes parciales «se comportan como $\leq$», ¿qué tipo de relaciones «se comportan como $\lt$? Esto es lo que discutiremos a continuación. Primero necesitamos introducir dos nociones.

Definición. Sea $R$ una relación sobre un conjunto $A$. Decimos que $R$ es una relación asimétrica si y sólo si para cualesquiera $a,b\in A$ tales que $(a,b)\in R$ entonces no es cierto que $(b,a)\in R$.

Ejemplo.

Sean $A=\set{1,2,3}$ y $R=\set{(1,2), (1,3)}$. Se tiene que $R$ es una relación asimétrica. En efecto, $(1,2)\in R$ pero $(2,1)\notin R$ y $(1,3)\in R$ pero $(3,1)\notin R$.

$\square$

Definición. Sea $R$ una relación sobre un conjunto $A$. Decimos que $R$ es una relación irreflexiva si y sólo si para cualquier $a\in A$ se tiene que $(a,a)\notin R$.

Ejemplo.

Sean $A=\set{1,2,3}$ y $R=\set{(1,2), (1,3)}$. Se tiene que $R$ es una relación irreflexiva. En efecto, pues para cualquier elemento en $A$ en este caso $1, 2$ y $3$ se cumple que $(1,1)\notin R$, $(2,2)\notin R$ y $(3,3)\notin R$.

$\square$

Del ejemplo anterior podemos inferir que si $R$ es una relación asimétrica, entonces $R$ es irreflexiva. Vamos a demostrar esto último en la siguiente proposición.

Proposición. Sea $A$ un conjunto y $R$ una relación en $A$. Si $R$ es asimétrica, entonces $R$ es irreflexiva.

Demostración.

Vamos a probar que si $R$ no es irreflexiva, entonces no es asimétrica. Si $a\in A$ cumple que $(a,a)\in A$, entonces no es posible tener simultáneamente $(a,a)\in A$ y $(a,a)\notin A$, es decir, $R$ no es asimétrica.

$\square$

Definición. Sea $R$ una relación en $A$. Si $R$ es una relación asimétrica y transitiva decimos que $R$ es un orden estricto en $A$. Para abreviar, diremos $(A, R)$ es un orden estricto.

Ejemplo.

Sea $A$ un conjunto cualquiera (no necesariamente vacío). Veamos que la relación $\emptyset$ es un orden estricto.

Si $A=\emptyset$, se cumple por vacuidad que $\emptyset$ es una relación asimétrica y transitiva. Por lo tanto, $\emptyset$ es un orden estricto.

Supongamos ahora que $A\not=\emptyset$, verifiquemos las propiedades de asimetría y transitividad.

  1. Sean $a,b\in A$ tales que $(a,b)\in \emptyset$ entonces $(b,a)\notin \emptyset$ se satisface por vacuidad. Por lo tanto, $\emptyset$ es una relación asimétrica.
  2. Sean $a,b,c\in A$ tales que $(a,b)\in \emptyset$ y $(b,c)\in \emptyset$. Como esto nunca sucede, por vacuidad implica que $(a,c)\in \emptyset$. Por lo tanto, $\emptyset$ es una relación transitiva.

$\square$

Dado que estamos ordenando elementos de un conjunto, usualmente usaremos $<$ para denotar a una relación de orden estricto, ya que esta es irreflexiva.

Tarea moral

La siguiente lista de ejercicios te permitirá fortalecer tu entendimiento del tema de ordenes parciales y el de órdenes parciales estrictos.

  1. Si $A \not=\emptyset$, prueba que la pareja $(A,\emptyset)$ no es un orden parcial.
  2. Demuestra que si $A$ es un conjunto y $R$ es la relación $\subset$ en $A$, entonces $(A, R)$ es un orden parcial estricto.
  3. Argumenta por qué el concepto de no reflexividad es distinto al de irreflexividad. Además, encuentra un ejemplo de una relación que no sea ni reflexiva ni irreflexiva.
  4. Para cada una de las siguientes proposiciones, demuéstrala o da un contraejemplo.
    • Si $R$ es una relación asimétrica, entonces es antisimétrica.
    • Si $R$ es una relación antisimétrica, entonces es asimétrica.
  5. Sea $<$ un orden parcial estricto en un conjunto $A$. Muestra que $<\cup \{(a,a): a\in A\}$ es un orden parcial en $A$.

Más adelante…

En la siguiente entrada estudiaremos a los órdenes totales. Para hablar de tales órdenes retomaremos a los órdenes parciales y a los órdenes parciales estrictos. Además platicaremos del orden lexicográfico horizontal y vertical, los cuales se definen en el producto cartesiano de dos conjuntos ordenados.

Entradas relacionadas

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»

Teoría de los Conjuntos I: Conjunto cociente

Por Gabriela Hernández Aguilar

2 respuestas

Introducción

En esta entrada partimos de una relación de equivalencia y con ella definimos al conjunto cociente. Dicho conjunto tendrá como elementos a las clases de equivalencia de una relación. Además probaremos que toda relación de equivalencia induce una partición y viceversa.

Conjunto cociente

A continuación definimos un nuevo conjunto. Como parte de los ejercicios de la tarea moral, se incluye verificar que en efecto esta definición da un conjunto a partir de los axiomas.

Definición. Sea $R$ una relación de equivalencia en $A$. Definimos al conjunto cociente por la relación $R$ como el conjunto:

$A/R=\set{[a]_R: a\in A}$.

Veamos algunos ejemplos.

Ejemplo.

Sea $A=\set{1,2,3,4}$ y $R$ la relación identidad en $A$. Sabemos que $R$ es de equivalencia en $A$. Luego, siguiendo la definición de conjunto cociente tenemos que $A\diagup R=\set{[1]_R, [2]_R, [3]_R, [4]_R}$, donde $[1]_R=\set{1}$, $[2]_R=\set{2}$, $[3]_R=\set{3}$, $[4]_R=\set{4}$.

$\square$

Ejemplo.

Sean $A=\set{1,2,3,4}$ y $R=\set{(1,1), (2,2), (3,3), (4,4), (1,4), (4,1)}$. Se tiene que $R$ es una relación de equivalencia en $A$. Luego, tenemos que

$A\diagup R=\set{[1]_R, [2]_R, [3]_R, [4]_R}$,

donde

  • $[1]_R=\set{1,4}$,
  • $[2]_R=\set{2}$,
  • $[3]_R=\set{3}$,
  • $[4]_R=\set{4,1}$, pero este conjunto es igual a $[1]_R$.

Por lo tanto, $A\diagup R=\set{[1]_R, [2]_R, [3]_R}$.

$\square$

Cada relación de equivalencia induce una partición

Teorema. Sea $R$ una relación de equivalencia en $A$. El conjunto cociente $A\diagup R$ es una partición de $A$.

Demostración.

Supongamos que $R$ es una relación de equivalencia en $A$. Veamos que $A\diagup R$ es una partición de $A$.

  1. Sea $a\in A$, vimos en la entrada de particiones que $[a]_R\not=\emptyset$.
  2. Sean $[a]_R,[b]_R\in A\diagup R$ tales que $[a]_R\not=[b]_R$ y veamos que $[a]_R\cap [b]_R=\emptyset$. En la entrada anterior probamos que $aRb$ si y sólo si $[a]_R=[b]_R$ lo cual ocurre si y sólo si $[a]_R\cap[b]_R=\emptyset$. De este modo, si $[a]_R\not=[b]_R$, $[a]_R\cap[b]_R=\emptyset$.
  3. Por último, $\bigcup_{a\in A} [a]_R= A$ pues para cada $a\in A$, $a\in [a]_R$.

$\square$

Este último teorema demuestra que toda relación de equivalencia induce una partición.

Las particiones inducen una relación de equivalencia

El teorema anterior nos permitió probar que cada relación de equivalencia induce una partición y de hecho, esta partición será el conjunto cociente, Podemos preguntarnos si el resultado se cumple «de regreso», en el sentido de si dada una partición podemos inducir una relación de equivalencia. Veamos el siguiente ejemplo.

Ejemplo.

Este ejemplo es todavía algo informal, pues no hemos introducido formalmente a los números naturales, a los pares y los impares. Haremos esto más adelante. Por el momento, puedes usar lo que ya sabes de los números naturales y de su paridad.

Sea $A=\set{0,1,2, 3, \cdots}$ y sean $A_1=\set{0,2,4,\cdots}$ y $A_2=\set{1,3, 5,\cdots}$. Resulta que $\mathcal{P}$ es una partición de $A$ pues tanto $A_1$ y $A_2$ son conjuntos no vacíos, además $A_1\cap A_2=\emptyset$ y $A_1\cup A_2=A$.

Queremos ver si existe la manera de relacionar a los elementos de $A$ tal que la relación que resulte sea de equivalencia. Consideremos la relación definida como sigue:

$R_\mathcal{P}=\set{(a,b)\in A\times A: a,b\in A_1\vee a,b\in A_2}$.

Notemos que la relación $R_\mathcal{P}$ es una relación en $A$ y además relaciona a los elementos si pertenecen a un mismo conjunto de la partición.

Veamos que $R_\mathcal{P}$ es una relación de equivalencia, para ello verifiquemos si es una relación reflexiva, simétrica y transitiva.

  1. Sea $a\in A$. Si $a$ es un número par (existe $k$ tal que $a= 2k$), entonces $a\in A_1$ y por lo tanto $(a,a)\in R_\mathcal{P}$.
    Si $a$ es un número impar (existe $k$ tal que $a= 2k+1$), entonces $a\in A_2$ y por lo tanto $(a,a)\in R_\mathcal{P}$.
    Por lo tanto, $R_\mathcal{P}$ es una relación reflexiva.
  2. Supongamos que $(a,b)\in R_\mathcal{P}$ y veamos que $(b,a)\in R_\mathcal{P}$.
    Como $(a,b)\in R_\mathcal{P}$ entonces $a,b\in A_1$ o $a,b\in A_2$, lo que es equivalente a decir que $b,a\in A_1$ o $b,a\in A_2$, es decir, $(b,a)\in R_\mathcal{P}$.
    Por lo tanto, $R_\mathcal{P}$ es una relación simétrica.
  3. Supongamos que $(a,b)\in R_\mathcal{P}$ y $(b,c)\in R_\mathcal{P}$.
    Como $(a,b)\in R_\mathcal{P}$ entonces $a,b\in A_1$ o $a,b\in A_2$. Luego, como $(b,c)\in R_\mathcal{P}$ entonces $b,c\in A_1$ o $b,c\in A_2$. Si $a,b\in A_1$, entonces $b,c\in A_1$, pues de lo contrario $b,c\in A_2$ y, por tanto, $b\in A_1$ al mismo tiempo que $b\in A_2$ y así, $b$ es par e impar, lo cuál no puede ocurrir. Por lo tanto, $b,c\in A_1$, de modo que $a,c\in A_1$ y así, $(a,c)\in R_\mathcal{P}$. Análogamente, si $a,b\in A_2$, entonces, $b,c\in A_2$ y, por tanto, $a,c\in A_2$ y $(a,c)\in R_{\mathcal{P}}$. Por lo tanto $R_\mathcal{P}$ es una relación transitiva.

Por lo tanto, $R_\mathcal{P}$ es una relación de equivalencia.

$\square$

Podemos demostrar que esto ocurre para cualquier conjunto y cualquier partición. Veamos el siguiente teorema.

Teorema. Toda partición induce una relación de equivalencia.

Demostración.

Sea $A$ un conjunto y $\mathcal{P}$ una partición de $A$. Defimos a $R_\mathcal{P}$ como el siguiente conjunto:

$R_\mathcal{P}=\set{(a,b)\in A\times A: \exists p\in \mathcal{P}\ \text{tal que}\ a,b\in p}$.

Notemos que $R_\mathcal{P}$ es una relación en $A$ pues es un subconjunto de $A\times A$. Veamos que $R$ es de equivalencia, es decir, $R$ es reflexiva, simétrica y transitiva.

  1. Sea $a\in A$. Dado que $\mathcal{P}$ es una partición de $A$, entonces $A=\bigcup\mathcal{P}$. Entonces existe $p\in \mathcal{P}$ tal que $a\in p$, de donde $(a,a)\in R_\mathcal{P}$. Por lo tanto, $R_\mathcal{P}$ es una relación reflexiva.
  2. Supongamos que $(a,b)\in R_\mathcal{P}$ y veamos que $(b,a)\in R_\mathcal{P}$.
    Como $(a,b)\in R_\mathcal{P}$, existe $p\in \mathcal{P}$ tal que $a, b\in p$. Lo que es equivalente a decir que existe $p\in \mathcal{P}$ tal que $b,a\in p$, es decir, $(b,a)\in R_\mathcal{P}$. Por lo tanto, $R_\mathcal{P}$ es una relación simétrica.
  3. Supongamos que $(a,b)\in R_\mathcal{P}$ y $(b,c)\in R_\mathcal{P}$.
    Como $(a,b)\in R_\mathcal{P}$, existe $p\in \mathcal{P}$ tal que $a, b\in p$. Luego, como $(b,c)\in R_\mathcal{P}$, existe $q\in \mathcal{P}$ tal que $b,c\in q$. Además $p=q$ pues de lo contrario, $p\not= q$ y $b\in p$ al mismo tiempo que $b\in q$ y así, $b\in p\cap q$ lo cual es una contradicción a la definición de partición. Por lo tanto, $p=q$ y así $a,c\in p$, por lo que $(a,c)\in R_\mathcal{P}$. Por lo tanto, $R_\mathcal{P}$ es una relación transitiva.

Por lo tanto, $R_\mathcal{P}$ es una relación de equivalencia en $A$.

$\square$

Con este último teorema hemos probado que en efecto, así como cada relación de equivalencia induce una partición, se cumple que cada partición induce una relación de equivalencia. Además, estas correspondencias son en cierto sentido «una la inversa de la otra» como explorarás en los ejercicios a continuación.

Tarea moral

La siguiente lista de ejercicios te ayudará a reforzar el contenido de esta entrada:

  1. Demuestra mediante los axiomas que si $A$ es un conjunto y $R$ es una relación de equivalencia en $A$, entonces $A\diagup R$ es un conjunto.
  2. Sea $A=\set{1,2,3,4,5,6}$ y $R=\set{(1,1), (2,2), (3,3), (4,4), (5,5), (6,6), (5,6), (6,5), (4,6), (6,4), (4,5), (5,4)}$ relación de equivalencia en $A$. Determina al conjunto cociente de $A$ con respecto a $R$.
  3. Demuestra mediante los axiomas que $R_{\mathcal{P}}$ del último teorema en efecto es un conjunto.
  4. Demuestra lo siguiente, en términos de la notación usada en esta entrada:
    • Si $A$ es conjunto y $R$ es relación de equivalencia en $A$, entonces $R_{A\diagup R}=R$.
    • Si $A$ es conjunto $\mathcal{P}$ es partición de $A$, entonces $A\diagup R_{\mathcal{P}}=\mathcal{P}$.
  5. Si $R_1$ y $R_2$ son relaciones de equivalencia en $A$, ya demostramos que $R_1\cap R_2$ también lo es. ¿Cómo es $A\diagup (R_1\cap R_2)$ con respecto a $A\diagup R_1$ y $A\diagup R_2$?

Más adelante…

En la siguiente entrada introduciremos el concepto de orden parcial y de orden total. Estos son otro tipo especial de relaciones. Volveremos a usar las propiedades de reflexividad y transitividad. Sin embargo, tendremos que introducir otras como la asimetría, la antisimetría y la irreflexibilidad.

Entradas relacionadas

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»