Archivo de la etiqueta: clases de equivalencia

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

Por Gabriela Hernández Aguilar

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

Álgebra Superior I: Relaciones de equivalencia y clases de equivalencia

Por Guillermo Oswaldo Cota Martínez

Introducción

Siguiendo la revisión de algunas relaciones de un conjunto en sí mismo, ahora vamos a hablar de un tipo especial de relaciones, que se llamarán de equivalencia. Este es un concepto que aparece frecuentemente en las matemáticas y es un tipo de relación que permite «agrupar» distintos elementos de un conjunto según alguna propiedad que tengan.

Relación de equivalencia

La relación que veremos en esta entrada es la de equivalencia. Para entender propiedades de este tipo de relaciones, consideremos al conjunto de todas las personas $X$ y la relación $\sim$ como:$$\sim = \{(x,y) \in X^2:x\text{ tiene el mismo cumpleaños que }y\}.$$ Y como es costumbre, escribiremos $x \sim y$ si $(x,y) \in \sim$. Esta relación será de equivalencia, y antes de definirla, vamos a hacer algunas observaciones de ella.

Observa que este tipo de relación nos permite «agrupar» a las personas según su cumpleaños, pues al haber $365$ días en el año, cada persona $x$ tendrá su cumpleaños en alguno de esos días. Nota que podríamos hablar de «el subconjunto» de $X$ formado de las personas las cuales cumplen años el $14$ de febrero, y esto lo haríamos con ayuda de la relación $\sim$, pues considerando alguna persona $x$ que cumpla años ese día, podríamos considerar a todas las personas $y$ tales que $x \sim y$. Y todas las personas que estén relacionadas con $x$, serán las que tienen su cumpleaños ese día. Retomaremos esta idea de las «agrupaciones» más adelante, lo importante ahora es que veas que este tipo de relaciones (aún no hemos dicho qué significa que sea de equivalencia o porqué esta es una relación de equivalencia) nos permiten «agrupar» elementos de un conjunto según los elementos que se relacionan entre sí.

Ahora, veamos algunas propiedades que tiene esta relación que la hará de equivalencia:

  • $\sim$ es reflexiva. Nota que toda persona $x$ cumple el mismo día años que la persona $x$. Esto es porque estamos hablando de la misma persona.
  • $\sim$ es simétrica. Considera dos personas $x,y$ relacionadas ($x \sim y$). Entonces es cierto que $x$ tiene el mismo cumpleaños que $y$. Pero también es cierto que $y$ tiene el mismo cumpleaños que $x$, de esta manera $y \sim x$.
  • $\sim$ es transitiva. Ahora supón que $x \sim y$ y que $y \sim z$. Entonces es cierto que $x$ y $y$ comparten cumpleaños, pero como $y \sim z$ entonces $z$ tiene el mismo cumpleaños que $y$ y esto solo puede significar que $x$ tiene el mismo cumpleaños que $z$, pues no puede suceder que $y$ tenga dos cumpleaños distintos.

Estas son las propiedades que decimos que cumple una relación de equivalencia.

Definición. Sea $X$ un conjuntos y $\sim$ una relación de $X$ en sí mismo. Diremos que $\sim$ es una relación de equivalencia si $\sim$ es reflexiva, simétrica y transitiva.

Este es un concepto que se aparecerá muchas veces en distintas áreas de las matemáticas, veamos a continuación algunos ejemplos de relaciones de equivalencia, no importa que ahora no sepas muy bien qué son estos conceptos, lo importante es que veas que aparecen en distintas áreas de las matemáticas:

  1. En $\mathbb{R}$, la relación $x \sim y \Leftrightarrow |x|=|y|$ es de equivalencia.
  2. Si $X=\{a,b,c\}$ y $\sim=\{(a,a),(b,b),(a,b),(b,a),(c,c)\}$, entonces $\sim$ es una relación de equivalencia.
  3. En el espacio de matrices reales $M_{2\times 2}(\mathbb{R})$, la siguiente es una relación de equivalencia: $A \sim B \Leftrightarrow \exists \lambda \in \mathbb{R}, \lambda \neq 0(A = \lambda B)$
  4. En espacios topológicos, la relación $X \sim Y \Leftrightarrow X \text{ es homeomorfo a } Y$ es una relación de equivalencia.
  5. La congruencia entre triángulos, es una relación de equivalencia.
  6. Diremos que un número entero $x$ es congruente con $y$ módulo $n$ si el residuo de dividir $x$ entre $n$ es el mismo que el residuo de dividir $y$ entre $n$ y lo escribiremos como $x \equiv_n y$. $\equiv_n$ es una relación de equivalencia.

Algunos ejemplos de relaciones que no son de equivalencia:

  1. La relación «ser menor o igual» en números enteros $\leq$ no es de equivalencia.
  2. La relación «ser padre/madre de» no es una relación de equivalencia.
  3. Si $X=\{a,b,c\}$ y $\sim=\{(a,a),(a,b),(b,a),(c,c)\}$, entonces $\sim$ no es de equivalencia.

Clases de equivalencia

Volvamos al ejemplo de la relación $\sim$ «tener el mismo cumpleaños». Ahora veremos porqué desde el principio hemos dicho que las relaciones de equivalencias nos ayudan a «agrupar» elementos de un conjunto de acuerdo a los elementos que se relacionan con él. Considera de nuevo el ejemplo de las personas que cumplen años el $14$ de febrero. La relación $\sim$ nos ayuda a encontrar a todas las personas que cumplen años ese día. Pues solo tendríamos que considerar una persona que cumpla años ese día y enseguida encontrar todas las personas que se relacionan con esta persona. Claramente este grupo, será distinto al grupo de personas que cumple años el $17$ de Junio, y a su vez estos do serán distintos al grupo de personas que cumplen el $10$ de Enero. En total podríamos «partir» el conjunto de personas $X$ en $365$ grupos de acuerdo al día en que cumplen años.

Si partimos de una persona $x$, entonces podemos considerar el conjunto $$[x]_{\sim}=\{y \in X: x \sim y\}.$$ Este conjunto representa a todas las personas que tienen el mismo cumpleaños que $x$, y recordando lo que dijimos en el párrafo anterior, si $x$ cumple el $14$ de febrero, entonces $[x]_{\sim}$ es el conjunto de personas que cumplen años ese día. Pues con esto en mente, hemos llegado al siguiente concepto: clase de equivalencia.

Definición. Sea $\sim$ una relación de equivalencia en $X$ y $x \in X$. La clase de equivalencia de $x$ es: $$[x]_{\sim}=\{y \in X: x \sim y\}.$$

Algunas veces cuando estemos hablando de una relación de equivalencia $\sim$ y no haya ambigüedad en qué relación de equivalencia estemos hablando, es común únicamente escribir $[x]$ para la clase de equivalencia del elemento $x$ en lugar de escribir $[x]_\sim$.

Veamos a continuación algunas propiedades que tienen estas clases de equivalencia que nos permiten asegurar que «parten» un conjunto agrupando sus elementos en distintos subconjuntos.

Proposición. Sea $\sim$ una relación de equivalencia en $X$ y $x,y \in X$. Son equivalentes:

  1. $x \sim y$
  2. $[x]=[y]$
  3. $[x] \cap [y] \neq \emptyset$

Demostración.

$(1) \Rightarrow (2)$ Para demostrar la igualdad entre conjuntos, demostraremos que cada clase equivalencia está contenida en la otra.

$\subset )$ Sea $w \in [x]$. Por definición del conjunto, $w \sim x$ y por hipótesis, $x \sim y$. Ahora, como $\sim$ es de equivalencia, entonces $w \sim y$. De esta forma, $w \in [y]$.

$\supset )$ De manera análoga a la contención anterior, si $w \in [y]$ entonces $w \sim y \land w \sim x$ de manera que $w \in [x]$.

$(2) \Rightarrow (3)$. Notemos que si $[x]=[y]$ entonces $[x] \cap [y]=[x]$ y $x \in [x]$, de esta manera, la intersección no es vacía.

$(3) \Rightarrow (1)$. Como $[x] \cap [y] \neq \emptyset$ entonces existe un elemento $w \in [x] \cap [y]$. De esta forma $x \sim w \land y \sim w$. Como $\sim$ es una relación de equivalencia, entonces $x \sim y$.

$\square$

Corolario. Sea $\sim$ una relación de equivalencia en $X$ y $x,y \in X$. Entonces $[x]=[y] \lor [x] \cap [y] = \emptyset.$

Demostración. Sean $x,y$ dos elementos de $X$. Entonces tenemos dos casos para $x,y$.

Caso 1) $x \sim y$. En este caso, por la proposición anterior, $[x]=[y]$.

Caso 2) $x \not \sim y$. Notemos que en este caso $[x]\cap [y]= \emptyset$, pues si no fuera cierto, la intersección no sería vacía y por la proposición anterior, esto significaría que $x \sim y$, contradiciendo la hipótesis de este caso.

$\square$

Particiones

El siguiente concepto nos permite hablar de «partir» un conjunto en distintos subconjuntos. En términos simples, una partición será una forma de dividir un conjunto en subconjuntos que no comparten elementos en común entre sí. Por ejemplo, considera a los números enteros. Podemos dividir el conjunto en dos particiones: el de los número pares y el de los impares. Denotemos al conjunto de los números pares como $P$ y al de los impares como $I$ entonces:

  • $P \cap I=\emptyset$
  • $P \cup I = \mathbb{Z}$

Entonces podemos observar algunos puntos para definir qué es una partición:

  • Cada uno de los subconjuntos que forman la partición son no vacíos. Nota que tanto $P$ como $I$ tienen al menos un elemento.
  • La intersección entre cada una de los subconjuntos de la partición es vacía. Esto significa que las particiones no comparten elementos, en el ejemplo, es claro que ningún número par es impar y viceversa.
  • La unión de los subconjuntos de la partición forman de nuevo el conjunto. Esto significa que todo elemento del conjunto pertenece a una única partición, en nuestro ejemplo esto significa que cualquier número entero es impar o es par, no ambos al mismo tiempo.

Estas son las tres propiedades que pediremos para definir una partición.

Definición. Sea $X$ un conjunto y $F = \{X_i\}_{i \in \mathcal{F}}$ una colección de subconjuntos, entonces diremos que $F$ es una partición de $X$ si:

  • Para cada $X_i \in F, X_i \neq \emptyset$.
  • Para $X_i,X_j \in F$ dos subconjuntos distintos, $X_i \cap X_j = \emptyset$.
  • $\bigcup F = X$

Resulta que esta definición no es al azar, pues cada relación de equivalencia induce una partición.

Proposición. Sea $\sim$ una relación de equivalencia sobre un conjunto $X$. Entonces las distintas clases de equivalencia forman una partición.

Demostración. Denotemos a $P$ como el conjunto de todas las clases de equivalencia de $X$, es decir $$P = \{[x]: x \in X\}$$. Ahora demostraremos que $P$ es una partición. Para ello, notemos que:

  1. Cada elemento de la partición $P$ es distinta al vacío. Observemos que si $[x] \in P$ entonces existe al menos un elemento en esa clase de equivalencia, de manera explícita, $x \in [x]$.
  2. Si $[x], [y] \in P$ son dos clases distintas, entonces $[x] \cap [y]$ es vacía. Este punto sale directamente del corolario demostrado anteriormente, pues $[x]=[y]$ o $[x] \cap [y]=\emptyset$.
  3. $\bigcup P = X$. De manera clara sucede que $\bigcup P \subset X$, pues cada elemento de $P$ es un subconjunto de $X$, y la unión de subconjuntos de un conjunto siempre está contenida en el conjunto. Para demostrar que $X \subset \bigcup P$, notemos que si $x \in X$, entonces $x \in [x]$ y $[x] \in P$, de esta manera, $x \in \bigcup P$.

De esta manera, $P$ es una partición.

$\square$

Este concepto de relaciones de equivalencia aparece muy seguido en distintas ramas de las matemáticas, será importante conforme avances en tu carrera del área matemática, pues muchas veces será útil ver que algunas relaciones son de equivalencias de manera en que sabremos que son particiones y podremos ver el conjunto en sus distintas partes de acuerdo a la relación.

Tarea moral

A continuación hay algunos ejercicios para que practiques los conceptos vistos en esta entrada. Te será de mucha utilidad intentarlos para entender más la teoría vista.

  1. Demuestra que la relación «ser igual a» $=$ en $\mathbb{Z}^2$ es una relación de equivalencia.
  2. Demuestre que la relación «ser menor o igual» en números enteros no es una relación de equivalencia.
  3. Demuestra que cualquier orden parcial no es una relación de equivalencia.
  4. Demuestra que si $x \in [y]_{\sim} \Leftrightarrow [x]_{\sim}=[y]_{\sim}$.

Más adelante…

En la siguiente entrada volveremos a hablar de relaciones entre conjuntos que en un inicio, no deben ser el mismo. Y el siguiente tipo de relación será fundamental, pues es el concepto de función entre dos conjuntos. No solo aparecerá aquí, sino que es una base para hablar en otras materias como en cálculo, geometría, entre otras.

Entradas relacionadas