Relaciones de equivalencia y particiones

Relaciones de equivalencia

En la sección de relaciones vimos la definición de que una relación \(R\) sobre un conjunto \(A\) sea una relación de equivalencia. En esta sección veremos ejemplos y propiedades de estas relaciones.

Ejemplos

En este momento ya hemos visto algunos ejemplos de relaciones de equivalencia. Durante el resto de la carrera se verán muchos otros ejemplos. Por el momento sólo citaremos aquellos que ya vimos.

El ejemplo al cual estamos más acostumbrados es la igualdad. La igualdad es una relación reflexiva, simétrica y transitiva. Otro ejemplo es “ser biyectables”, en la sección de cardinalidad que ser biyectables, o bien, tener la misma cardinalidad es una relación de equivalencia. La equivalencia lógica es otro ejemplo de relación de equivalencia.

Propiedades

Si consideramos la equivalencia lógica y dos fórmulas equivalentes, por ejemplo \(\alpha\land\beta\) y \(\beta\land\alpha\), podemos ver que estas fórmulas son intercambiables cuando estamos haciendo una demostración. Así fue que se demostró que la intersección es conmutativa en la sección de operaciones con conjuntos. Esto significa que podemos pensar que son iguales, aunque como fórmulas no lo sean. Lo que está pasando es que la equivalencia lógica es una igualdad en el significado de las fórmulas, no como sucesiones de símbolos.

De la misma manera que el caso de la equivalencia lógica, las relaciones de equivalencia son relaciones que nos dicen que dos objetos son iguales en algún sentido, diferente al sentido estricto de \(=\).

Lo primero que haremos es reconocer, de forma general, qué es lo que está igualando una relación de equivalencia. Así, de ahora en adelante tomaremos \(R\) una relación de equivalencia sobre un conjunto \(A\).

Definición

Dado un elemento \(a\in A\), la clase de equivalencia de \(a\) es el conjunto

\[[a] = \{x\in A\mid (a,x)\in R\}.\]

El elemento \(a\) es llamado representante de la clase de equivalencia.

Una observación es que, por la reflexividad de \(R\), tenemos que \(a\in[a]\).

Con sólo la definición de clase de equivalencia podemos ver en qué sentido es una “igualdad” la relación \(R\).

Proposición

Si \(a,b\in A\), entonces \([a]=[b]\) si y sólo si \((a,b)\in R\).

Demostración

Si \([a]=[b]\), entonces \(a\in[a]=[b]\), es decir, \((a,b)\in R\). Recíprocamente, si \((a,b)\in R\) y queremos ver \([a]=[b]\), entonces hacemos doble contención.

\[\begin{align*} x\in[a] & \iff (x,a)\in R && \text{por definición de }[a] \\ & \iff (x,b)\in R && \text{hipótesis y } R\text{ es de equivalencia} \\ & \iff x\in[b] && \text{por definición de }[b]. \end{align*}\]

Lo siguiente es formar al conjunto en el cual \(R\) es la relación de “igualdad”.

Definición

El cociente de \(A\) módulo \(R\) es el conjunto

\[A/R = \{[a]\mid a\in A\}.\]

El proceso hasta ahora ha sido que empezamos con un conjunto y noción de “igualdad” (relación de equivalencia) que no es la igualdad de verdad. Luego hemos modificado al conjunto original para forzar a que nuestra noción sea la igualdad de verdad.

Podemos pensar en el ejemplo de las proposiciones con la relación de equivalencia lógica. En este caso, el conjunto \(A\) es el conjunto de todas las fórmulas proposicionales y el cociente “pega” todas las fórmulas equivalentes en una sola clase de equivalencia. Por ejemplo, todas las tautologías son pegadas al un elemento que se suele denotar por \(\top\) o \(1\). Las contradicciones se pegan a \(\bot\) o \(0\).

Paréntesis acerca de proposiciones

Cuando hacemos el cociente \(L=\mathsf{Prop}/\mathord{\equiv}\) podemos definir operaciones sobre este conjunto. Por ejemplo, definimos la suma \([\alpha]+[\beta]\) como \([\alpha\lor\beta]\). Esto es una operación bien definida, es decir, no depende de representantes.

Si recordamos que \(1\) es la clase de las tautologías y que la disyunción de tautologías es una tautología, entonces obtenemos que \(1+1=1\). Mostrando que sí es posible tener una estructura donde se vale esa igualdad, como mencionamos en la sección de proposiciones.

Una vez que hemos formado el cociente, podemos relacionar al conjunto original \(A\) con el cociente \(A/R\) mediante una función.

\[q\colon A\to A/R,\quad a\mapsto[a].\]

Esta función se llama función cociente y es suprayectiva. En efecto, si tomamos un elemento \([a]\in A/R\), entonces \(q(a)=[a]\).

Para terminar este resumen de relaciones de equivalencia, veremos algunas propiedades que nos serán útiles acerca de clases de equivalencia.

Proposición

1. Para toda \(a\in A\) se cumple \([a]\ne\emptyset\).
2. Si \(a,b\in A\), entonces \([a]\ne[b]\) implica \([a]\cap[b]=\emptyset\).
3. \(\bigcup_{a\in A}[a]=A\).

Demostración

El primer punto se sigue del comentario que hicimos antes, que \(a\in[a]\).
Para el segundo punto, supongamos que \([a]\ne[b]\), es decir, \((a,b)\notin R\). Si \(x\in[a]\cap[b]\), entonces \((x,a)\in R\) y \((x,b)\in R\). Como \(R\) es simétrica y transitiva, tenemos que \((a,b)\in R\). Lo cual es una contradicción.
Para el tercer punto, si \(x\in A\), entonces \(x\in[x]\in\bigcup_{a\in A}[a]\). La otra contención se sigue de que para cada \(a\in A\) se tiene \([a]\subseteq A\).

Particiones

Las particiones son algo muy similar a un rompecabezas, donde tomamos una imagen y la dividimos en piezas ajenas cuyo pegado nos da la imagen orinal. Además, no tiene sentido hablar de una pieza vacía en un rompecabezas. Tratemos de formalizar esta idea en lo que será la definición de partición.

Definición

Una partición de un conjunto \(A\) es una colección de subconjuntos \(\{A_i\subset A\mid i\in I\}\) tal que

1. \(A_i\ne\emptyset\) para toda \(i\in I\),
2. \(A_i\cap A_j=\emptyset\) si \(i\ne j\), y
3. \(\bigcup_{i\in I}A_i=A\).

Por ejemplo, \(\{\:\{n\}\mid n\in\mathbb{N}\:\}\) es una partición de \(\mathbb{N}\). Otro ejemplo, es que la proposición anterior muestra que toda relación de equivalencia \(R\) induce una partición de \(A\), por medio de las clases de equivalencia. Un ejemplo más de partición consiste en tomar una función suprayectiva \(f\colon A\to I\) y definir \(A_i=f^{-1}(i)\), entonces \(\{A_i\mid i\in I\}\) es una partición de \(A\).

Ahora, ya tenemos que toda relación de equivalencia induce una partición. Lo que sigue es ver que toda partición induce una relación de equivalencia. Sea \(\{A_i\mid i\in I\}\) una partición de \(A\). Definimos la relación \(P\) como

\[(a,b)\in P \iff \exists i\in I(a,b\in A_i).\]

Una observación es que, como los \(A_i\) son disjuntos, entonces de existir \(i\) tal que \(a,b\in A_i\), entonces esa \(i\) es única.

No es difícil ver que la relación \(P\) es de equivalencia. La reflexividad se sigue de \(\bigcup_{i\in I}A_i=A\). La simetría es fácil ya que si \(a,b\in A_i\) entonces \(b,a\in A_i\). La transitividad se sigue de \(A_i\cap A_j=\emptyset\) si \(i\ne j\).

Denotemos con \(\mathsf{Part}(A)\) al conjunto de todas las particiones de \(A\) y con \(\mathsf{Eq}(A)\) al conjunto de todas las relaciones de equivalencia en \(A\). Entonces, lo que hemos hecho hasta ahora es definir dos funciones

\[\begin{align*} & \varphi\colon\mathsf{Eq}(A)\to\mathsf{Part}(A), \quad R\mapsto\{[a]\mid a\in A\}, \\ & \psi\colon\mathsf{Part}(A)\to\mathsf{Eq}(A), \quad \{A_i\mid i\in I\}\mapsto\{(a,b)\mid\exists i\in I(a,b\in A_i)\}. \end{align*}\]

Lo que falta ver es que estas funciones son inversas.

Empecemos con una relación de equivalencia \(R\). Luego, tomemos la partición asociada, \(A/R=\{[a]\mid a\in A\}\). Finalmente, tomemos la relación de equivalencia \(P\) inducida por esta partición. Entonces,

\[\begin{align*} (a,b)\in P & \iff \exists x\in A,\; a,b\in[x] \\ & \iff \exists x\in A,\; (a,x)\in R\text{ y }(b,x)\in R \\ & \iff (a,b)\in R. \end{align*}\]

La dirección de arriba hacia abajo, del último paso, se sigue de que \(R\) es de equivalencia. Para la dirección de abajo hacia arriba del mismo paso, la \(x\in A\) puede ser tomada como \(a\), ya que \((a,a)\in R\) y \((b,a)\in R\).

Lo que acabamos de hacer muestra que \(\psi\circ\varphi=\mathsf{id}_{\mathsf{Eq}(A)}\). Veamos que la otra composición también es la identidad.

Sea \(\{A_i\mid i\in I\}\) una partición de \(A\). Luego, tomemos la relación de equivalencia generada, \(P\). Finalmente, tomemos la partición asociada a \(P\), es decir, \(A/P=\{[a]\mid a\in A\}\). Veamos que la partición inicial es igual a la final, por doble contención.

Sea \(i\in I\) y veamos que \(A_i\in A/P\), es decir, que existe \(a\in A\) tal que \(A_i=[a]\). Como \(A_i\ne\emptyset\), tomamos \(a\in A_i\). Luego, sea \(b\in A_i\), entonces \(a,b\in A_i\), lo cual implica \((a,b)\in P\) y así \(b\in [a]\). Por otro lado, si \(b\in[a]\), entonces \((a,b)\in P\). Esto implica que existe \(j\in I\) tal que \(a,b\in A_j\), pero como \(a\in A_i\) y los \(A_i\) son ajenos, entonces \(i=j\) y \(b\in A_i\). Así, \(A_i=[a]\).

Ahora tomamos \(a\in A\) y veamos que \([a]\in\{A_i\mid i\in I\}\), es decir, que existe \(i\in I\) tal que \([a]=A_i\). Sabemos que existe \(i\in I\) tal que \(a\in A_i\). Luego, si \(b\in[a]\), entonces \((a,b)\in P\), lo cual implica que existe \(j\in I\) tal que \(a,b\in A_j\). Pero como \(a\in A_i\) y los \(A_i\) son ajenos, entonces \(i=j\) y \(b\in A_i\). Finalmente, si \(b\in A_i\), entonces \((a,b)\in P\) y así \(b\in[a]\).

Todo lo anterior se puede escribir en el siguiente resultado.

Teorema

Hay una biyección entre el conjunto de relaciones de equivalencia en un conjunto \(A\) y el conjunto de particiones de \(A\).