Archivo de la etiqueta: conjunto completo de representantes

Teoría de los Conjuntos I: Clases de equivalencia y particiones

Por Gabriela Hernández Aguilar

Introducción

En la entrada anterior definimos a las relaciones de equivalencia, con lo cual ahora tenemos las bases para definir otros conceptos. Esta entrada estará dedicada a dos nociones nuevas a las que llamaremos clases de equivalencia y particiones. Dichos conjuntos nos permitirán agrupar a los elementos de un conjunto.

Clases de equivalencia

En la entrada anterior hemos usado la notación de pares para referirnos a los elementos de una relación. En esta entrada será más conveniente cambiar a la notación en la que ponemos a la relación entre dos elementos. Como recordatorio, esto quiere decir que para un conjunto $A$ y una relación $R$ en $A$, en vez de escribir $(a,b)\in R$, simplemente escribiremos $aRb$. Una versión abreviada de las propiedades de relación de equivalencia en esta notación es la siguiente:

  1. Para todo $a\in A$ se tiene $aRa$.
  2. Para $a,b\in X$ si $aRb$, entonces $bRa$.
  3. Para $a,b,c\in A$ si $aRb$ y $bRc$, entonces $aRc$.

La primera noción nueva que estudiaremos es la siguiente.

Definición. Sea $R$ una relación de equivalencia en $A$. Dado $a\in A$, definimos la clase de equivalencia de $a$ con respecto a $R$, como:

$[a]_R=\set{x\in A: aRx}$.

Observación. Si $A$ es un conjunto no vacío, entonces, para cada $a\in A$ se tiene $[a]_R\not=\emptyset$ pues $aRa$ (por reflexividad de $R$).

Ejemplo.

Consideremos al conjunto $A=\set{a,b,c}$ y $R$ la relación de equivalencia en $A$ dada por $R=\set{(a,a), (b,b),(c,c), (a,b), (b,a)}$. Veamos cuáles son las clases de equivalencia de cada uno de los elementos de $A$.

Tenemos que:

\begin{align*}
[a]_R&= \set{x\in A: aRx}\\
&= \set{x\in \set{a,b,c}: aRx}\\
&=\set{a,b}.
\end{align*}

\begin{align*}
[b]_R&= \set{x\in A: bRx}\\
&= \set{x\in \set{a,b,c}: bRx}\\
&=\set{a,b}.
\end{align*}

\begin{align*}
[c]_R&= \set{x\in A: cRx}\\
&= \set{x\in \set{a,b,c}: cRx}\\
&=\set{c}.
\end{align*}

$\square$

Conjuntos completos de representantes

Del ejemplo anterior podemos notar que es posible que dos clases de equivalencia sean iguales. En ese ejemplo, tenemos que $[a]_{R}=[b]_{R}$, por lo que podemos considerar únicamente a un representante para estás clases, es decir, las clases distintas de $R$ estarán dadas por $[a]_R$ y $[c]_R$, pues $[a]_R$ representa tanto a $[a]_R$ como a $[b]_R$. Para formalizar estas ideas, podemos introducir la siguiente definición.

Definición. Sea $R$ una relación de equivalencia en $A$. Decimos que $S\subseteq A$ es un conjunto completo de representantes con respecto a $R$, si se satisfacen las siguientes condiciones:

  1. Para cualesquiera $a,b\in S$, se tiene que $[a]_R\cap [b]_R=\emptyset$ si $a\not=b$,
  2. $\bigcup_{a\in S}[a]_R=A$.

Ejemplo.

Sea $X=\set{1,2}$. Consideremos las relaciones $R_1=\set{(1,1),(2,2)}$ y $R_2=\set{(1,1),(2,2),(1,2),(2,1)}$ en $X$. Las relaciones $R_1$ y $R_2$ son relaciones de equivalencia en $X$. Luego, un conjunto completo de representantes con respecto a $R_1$ es $S_1=\set{1,2}$ y un conjunto completo de representantes con respecto a $R_2$ es $S_2=\set{1}$.

Ejemplo.

Sea $X$ un conjunto no vacío y consideremos la relación $R=\set{(x,x):x\in X}$. Ciertamente $R$ es una relación de equivalencia en $X$, y un conjunto completo de representantes respecto a $R$ es $S=X$.

¿Será que para cualquier relación de equivalencia podremos encontar un conjunto completo de representantes? La respuesta es que sí, pero todavía no podemos demostrarlo. Se logrará hasta que introduzcamos el axioma de elección. Para seguir desarrollando tu intuición de por qué, piensa en qué sucedería si el conjunto $A$ en donde está la relación de equivalencia $R$ es infinito, y se tiene que todas las clases de equivalencia tienen dos elementos (digamos). Nuevamente, tenemos que elegir una infinidad de veces uno de los dos elementos. Para hacer estas elecciones infinitas es que se necesita el axioma de elección.

Teorema. Sea $R$ una relación de equivalencia en $A$ y sean $a,b\in A$. Las siguientes propiedades son equivalentes:

  1. $aRb$,
  2. $[a]_R=[b]_R$,
  3. $[a]_R\cap[b]_R\not=\emptyset$.

Demostración.

$1)\rightarrow 2)$ Supongamos que $aRb$. Veamos que $[a]_R=[b]_R$.

$\subseteq]$ Sea $x\in [a]_R$, entonces $aRx$. Luego, como $aRb$ y $R$ es una relación simétrica entonces $bRa$. Así, $bRa$ y $aRx$ y por la transitividad de $R$ se tiene que $bRx$ y así, $x\in [b]_R$.

Por lo tanto, $[a]_R\subseteq [b]_R$.

$\supseteq]$ Sea $x\in [b]_R$, entonces $bRx$. Luego, como $aRb$ y $bRx$ se tiene por transitividad de $R$ que $aRx$ y así, $x\in [a]_R$.

Por lo tanto, $[b]_R\subseteq [a]_R$. Concluimos entonces que si $aRb$ entonces $[a]_R=[b]_R$.

$2)\rightarrow 3)$ Supongamos que $[a]_R=[b]_R$ entonces $[a]_R\cap[b]_R=[a]_R\not=\emptyset$ pues por la observación, $a\in [a]_R$.

$3)\rightarrow 1)$ Supongamos que $[a]_R\cap[b]_R\not=\emptyset$. Veamos que $aRb$.

Dado que $[a]_R\cap [b]_R\not=\emptyset$, existe $x\in [a]_R\cap[b]_R$, es decir existe $x$ tal que $x\in[a]_R$ y $x\in [b]_R$. Entonces $aRx$ y $bRx$. Por lo tanto, $aRx$ y $xRb$ por la propiedad simétrica. Luego, $aRb$ por transitividad.

Por lo tanto, si $[a]_R\cap[b]_R\not=\emptyset$ entonces $aRb$.

Por lo tanto, $1)$, $2)$ y $3)$ son enunciados equivalentes.

$\square$

Particiones

A continuación definiremos qué es una partición de un conjunto. A grandes rasgos, se refiere a «fragmentar» un conjunto. Este concepto estará muy relacionado con el de las clases de equivancia de un conjunto completo de representantes.

Definición. Sean $A$ un conjunto no vacío y $P\subseteq \mathcal{P}(A)$. Decimos que $P$ es una partición de $A$ si cumple las siguientes condiciones:

  1. $B\not=\emptyset$ para todo $B\in P$,
  2. $B\cap C=\emptyset$ para cualesquiera $B,C\in P$ si $B\not=C$,
  3. $\bigcup P=A$.

Ejemplo.

Sea $X=\set{1,2,3,4}$. Consideremos a la siguiente colección de subconjuntos de $X$, $P=\set{\set{x}:x\in X}$.

Veamos que $P$ es una partición de $X$:

  1. Dado que para todo $x\in X$ se cumple que $x\in \set{x}$ tenemos que $\set{x}\not=\emptyset$.
  2. Ahora, como $P=\set{\set{x}:x\in X}=\set{\set{1},\set{2}, \set{3}, \set{4}}$ se cumple que para cualquier $x,y\in X$ tales que $\set{x}\not=\set{y}$, $\set{x}\cap\set{y}=\emptyset$.
  3. Tenemos que:

$\bigcup P=\set{1}\cup\set{2}\cup\set{3}\cup\set{4}=\set{1,2,3,4}=X$.

$\square$

A continuación se muestra el primero de varios resultados que vinculan a las relaciones de equivalencia con las particiones.

Teorema. Sea $R$ una relación de equivalencia en $A$ un conjunto no vacío. Si $S$ es un conjunto completo de representantes respecto a la relación $R$, entonces $\set{[a]_R: a\in S}$ es una partición de $A$.

Demostración.

Veamos que $\set{[a]_R:a\in S}$ es una partición de $A$. En efecto,

  1. Sea $a\in S\subseteq A$, entonces $aRa$ por reflexividad de $R$ y por lo tanto $a\in [a]_R$. De este modo, para cualquier $a\in S$ se cumple que $[a]_R\not=\emptyset$.
  2. Ahora, sean $a,b\in S$ tales que $a\not=b$. Por definición de conjunto completo de representantes se sigue que $[a]_R\cap [b]_R=\emptyset$.
  3. Finalmente, tenemos por definición que $\bigcup_{a\in S}[a]_R=A$.

Por lo tanto, $\set{[a]_R:a\in S}$ es una partición de $A$.

$\square$

Tarea moral

  1. Sea $A=\set{1,2,3,4}$. Da una partición del conjunto $A$ y verifica que en efecto es una partición.
  2. Sea $A=\set{1,2,3,4,5}$ y sea $R$ una relación de equivalencia en $A$ dada por $R=\set{(1,1), (2,2), (3,3), (4,4), (5,5)}$. Escribe las clases de equivalencia de $A$ con respecto a $R$.
  3. Sea $A=\set{1,2,3}$ y sea $R$ una relación de equivalencia en $A$ dada por $R=\set{(1,1), (2,2), (3,3), (1,2), (2,1)}$. Encuentra a un conjunto completo de representantes.
  4. Sean $R$ y $S$ relaciones de equivalencia en $X$. Demuestra que para cada $x\in X$ se tiene que $[x]_{R\cap S}=[x]_R\cap [x]_S$.

Más adelante…

En la siguiente entrada estableceremos otras conexiones de relaciones de equivalencia con particiones. Lo haremos a través de definir a una nueva noción llamada conjunto cociente.

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»