7.2: Relaciones de equivalencia

Como hemos visto en el apartado anterior, las nociones de reflexiva, simétrica y transitiva son independientes entre sí. Es decir, una relación puede tener alguna combinación de estas propiedades, posiblemente ninguna de ellas y posiblemente todas ellas. Sin embargo, tenemos un nombre especial para cuando una relación satisface las tres propiedades.

Definición 7.35. Que\(\sim\) sea una relación en un set\(A\). Entonces\(\sim\) se llama relación de equivalencia sobre\(A\) si\(\sim\) es reflexiva, simétrica y transitiva.

El símbolo “\(\sim\)" suele pronunciarse como “twiddle” o “tilde” y la frase “\(a\sim b\)" podría leerse como “\(a\)está relacionado con\(b\)" o “\(a\)twiddles\(b\)”.

Problema 7.36. Deje\(A=\{1,2,3,4,5,6\}\) y defina\[R=\{(1,1),(1,6),(2,2),(2,3),(2,4),(3,3),(3,2),(3,4),(4,4),(4,2),(4,3),(5,5),(6,6),(6,1)\}.\] Usando\(R\), complete cada uno de los siguientes.

1. Dibuja el dígrafo para\(R\).
2. Determinar si\(R\) es una relación de equivalencia en\(A\).
3. Encuentra\(Rel(R)\) determinando\(rel(x)\) para cada uno\(x\in A\).

Problema 7.37. Vamos\(A=\{a,b,c,d,e\}\).

1. Informar una relación de equivalencia\(\sim\) sobre\(A\) dibujando un dígrafo tal que no\(a\) esté relacionado con\(b\) y no\(c\) esté relacionado con\(b\).
2. Usando tu dígrafo, encuentra\(Rel(\sim)\) determinando\(rel(x)\) para cada uno\(x\in A\).

Problema 7.38. Dado un conjunto finito\(A\) y una relación de equivalencia\(\sim\) sobre\(A\), describa cómo tendría que ser la dígrafa correspondiente.

Problema 7.39. Determinar qué relaciones dadas en Problema 7.34 son relaciones de equivalencia.

Problema 7.40. Dejar\(\mathcal{T}\) ser el conjunto de todos los triángulos y definir\(\sim\) en\(\mathcal{T}\) via\(T_1\sim T_2\) si\(T_1\) es similar a\(T_2\). Determinar si\(\sim\) es una relación de equivalencia en\(\mathcal{T}\).

Problema 7.41. Si es posible, construya una relación de equivalencia en el conjunto vacío. Si esto no es posible, explique por qué.

Teorema 7.42. Supongamos que\(\sim\) es una relación de equivalencia en un conjunto\(A\) y let\(a,b\in A\). Entonces\(rel(a)=rel(b)\) si y sólo si\(a\sim b\).

Teorema 7.43. Supongamos que\(\sim\) es una relación de equivalencia en un conjunto\(A\). Entonces

1. \(\displaystyle \bigcup_{a\in A}\ rel(a)=A\), y
2. [thm:equiv produce partición b] Para todos\(a,b\in A\), ya sea\(rel(a)=rel(b)\) o\(rel(a)\cap rel(b)=\emptyset\).

A la luz del Teorema 7.43, tenemos la siguiente definición.

Definición 7.44. Si\(\sim\) es una relación de equivalencia en un conjunto\(A\), entonces para cada uno\(a\in A\), nos referimos\(rel(a)\) como la clase de equivalencia de\(a\).

Cuando\(\sim\) es una relación de equivalencia en un conjunto\(A\), es común escribir cada clase de equivalencia\(rel(a)\) como\([a]\) (o a veces\(\overline{a}\)). El elemento\(a\) dentro de los corchetes se llama el representante de la clase de equivalencia\([a]\). El teorema 7.42 implica que una clase de equivalencia puede ser representada por cualquier elemento de la clase de equivalencia. Por ejemplo, en Problema 7.36, tenemos\([1]=[6]\) desde 1 y 6 están en la misma clase de equivalencia. La colección de clases de equivalencia a menudo\(Rel(\sim)\) se denota por\(A/\mathord\sim\), que se lee como “\(A\)módulo\(\sim\)" o “\(A\)mod\(\sim\)”. A la colección\(A/\mathord\sim\) se le hace referencia a veces como el cociente de\(A\) by\(\sim\).

Ejemplo 7.45. Dejar\(P\) denotar a los residentes de un pueblo en particular y definir\(\sim\) en\(P\) vía\(a\sim b\) si\(a\) y\(b\) tienen el mismo apellido. Se ve fácilmente que esta relación es reflexiva, simétrica y transitiva, y por lo tanto\(\sim\) es una relación de equivalencia sobre\(P\). Las clases de equivalencia corresponden a colecciones de individuos con el mismo apellido. Por ejemplo, María García, Anthony García y Ariana García pertenecen todos a la misma clase de equivalencia. Cualquier García puede ser utilizado como representante para la clase de equivalencia correspondiente, por lo que podemos denotarlo como\([\text{Maria Garcia}]\), por ejemplo. La colección\(P/\mathord\sim\) consta de los diversos conjuntos de personas con el mismo apellido. En particular,\([\text{Maria Garcia}]\in P/\mathord\sim\).

Ejemplo 7.46. Los cinco conjuntos distintos de familiares que identificaste en Problema 7.22 son las clases de equivalencia para\(\equiv_5\) on\(\mathbb{Z}\). Estas clases de equivalencia a menudo se denominan clases de congruencia módulo 5.

El resultado del Teorema 7.43 es que dada una relación de equivalencia, cada elemento vive exactamente en una clase de equivalencia. En la siguiente sección, veremos que podemos ejecutar esto a la inversa. Es decir, si separamos los elementos de un conjunto para que cada elemento sea un elemento de exactamente un subconjunto, entonces esto determina una relación de equivalencia.

Problema 7.47. Si\(\sim\) es una relación de equivalencia sobre un conjunto finito\(A\), describa\(A/\mathord\sim\) en términos del dígrafo correspondiente a\(\sim\).

Problema 7.48. Para cada una de las relaciones de equivalencia que identificó en el Problema 7.39, describa sucintamente las clases de equivalencia correspondientes.

Problema 7.49. Supongamos\(R\) y\(S\) son ambas relaciones de equivalencia en un conjunto\(A\). ¿Está\(R\cap S\) encendida una relación de equivalencia\(A\)? Si es así, demuéstralo. De lo contrario, proporcione un contraejemplo.

Problema 7.50. Supongamos\(R\) y\(S\) son ambas relaciones de equivalencia en un conjunto\(A\). ¿Está\(R\cup S\) encendida una relación de equivalencia\(A\)? Si es así, demuéstralo. De lo contrario, proporcione un contraejemplo.