Archivo de la etiqueta: conjunto completo de representantes

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

Por Gabriela Hernández Aguilar

Deja un comentario

Introducción

En la sección anterior definimos a las relaciones de equivalencia por lo que ahora tenemos las bases para definir otros conceptos. Esta entrada estará dedicada a dos conjuntos nuevos a los que llamaremos clases de equivalencia y particiones. Dichos conjuntos nos permitirán por un lado agrupar a los elementos de un conjunto conforme estén relacionados con otros y así estudiar a un conjunto no solo como un total si no por partes.

Clases de equivalencia

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

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

Observación: Para cada $a\in A$, $[a]_R\not=\emptyset$ pues $aRa$ (por reflexividad de $R$). Así, $[a]_R$ tiene al menos un elemento, a saber $a$.

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 cuales 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$

Del ejemplo anterior podemos notar que es posible que dos clases de equivalencia sean iguales. En este caso tenemos que $[a]_{R}=[b]_{R}$, por lo que podemos considerar únicamente a un representante para estás clases, es decir, las clases de $R$ estarán dadas por $[a]_R$ y $[c]_R$, donde $[a]_R$ representará tanto a $[a]_R$ como a $[b]_R$. A partir de este último hecho podemos introducir la definición del conjunto completo de representantes.

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

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

Esta última definición nos permitirá tomar a un representante para aquellas clases de equivalencia que son iguales.

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$.

Por lo tanto, 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$ por la observación.

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

Dado que $[a]_R\cap [b]_R\not=\emptyset$, entonces 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 de $R$.

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 a la partición de un conjunto. Este concepto tendrá utilidad pues va a resultar que el conjunto completo de representantes de una relación de equivalencia corresponde a una partición del conjunto.

Definición: Sea $A$ un conjunto no vacío y sea $P=\set{A_i}_{i\in I}$ una familia de subconjuntos de $A$. Decimos que $P$ es una partición de $A$ si cumple las siguientes condiciones:

  1. $A_i\not=\emptyset$ para toda $i\in I$,
  2. $A_i\cap A_j=\emptyset$ si $i\not= j$ para toda $i, j\in I$,
  3. $\bigcup_{i\in I}A_i=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 $x\not=y$, $\set{x}\not=\set{y}$.
  3. Tenemos que:

$\bigcup_{x\in X} \set{x}=\set{1}\cup\set{2}\cup\set{3}\cup\set{4}=\set{1,2,3,4}=X$.

$\square$

Teorema: Sea $R$ una relación de equivalencia en $A$ un conjunto no vacío. Sea $S$ un conjunto completo de representantes de $A$. 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$ 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 sección estableceremos la conexión de relaciones de equivalencia con las particiones, lo haremos a través de definir a un nuevo conjunto llamado conjunto cociente.

Enlaces