7.2: Definición y Propiedades Básicas de las Relaciones de Equivalencia

La gente a menudo necesita clasificar una colección de objetos, juntando objetos similares en un grupo.

Ejemplo\(7.2.1\).

Al hacer un inventario de los animales en un zoológico, es posible que deseemos contar el número de antílopes, el número de babuinos, el número de guepardos, etc. En este caso, todos los animales de la misma especie podrían agruparse.

Solución

Matemáticamente hablando, definiríamos una relación binaria\(S\) sobre el conjunto de animales en el zoológico por\[x S y \quad \text { iff } \quad x \text { and } y \text { are in the same species. }\]

Cuando\(x\) y se\(y\) colocan en el mismo grupo (es decir, cuando\(x S y\) en el ejemplo anterior), podemos decir que\(x\) es “equivalente” a\(y\). Esto significa que\(x\) y\(y\) son los mismos en todos los aspectos que nos interesan. (En el ejemplo anterior, nos interesa únicamente la especie de un animal, no su peso, ni su edad, ni cualquier otra cosa). Llamamos a la relación binaria correspondiente una “relación de equivalencia”. Así, la relación binaria\(S\) en el ejemplo anterior es una relación de equivalencia.

Ejemplo\(7.2.2\).

Aquí hay ejemplos adicionales:

1. Si solo nos interesan los nombres, podríamos definir una relación de equivalencia\(N\) en el conjunto de todas las personas mediante\[x N y \text { iff } x \text { has the same first name as } y \text {. }\]
2. Supongamos que una tienda de dulces tiene contenedores para diferentes tipos de dulces que venden. Para un empleado que reabastecen los contenedores, todas las piezas de dulces que van a la misma papelera son iguales, por lo que está lidiando con una relación de equivalencia en el juego de dulces.
3. En geometría, a menudo uno solo se interesa por la forma de un triángulo, no su ubicación (o su color, o cualquier otra cosa). Por lo tanto, los matemáticos definen una relación de equivalencia\(\cong\) en el conjunto de todos los triángulos por\[T_{1} \cong T_{2} \text { iff } T_{1} \text { is congruent to } T_{2} .\]

OBSERVACIÓN\(7.2.3\).

Supongamos que\(\sim\) es una relación de equivalencia. (Es decir, tenemos\(x \sim y\) iff\(x\) y\(y\) somos los mismos en todos los aspectos que nos interesan.) Entonces esperaríamos:

1. \(\sim\)es reflexivo (\(x\)es lo mismo que\(x\)),
2. \(\sim\)es simétrico (si\(x\) es lo mismo que\(y\), entonces\(y\) es lo mismo que\(x\)), y
3. \(\sim\)es transitivo (si\(x\) es lo mismo que\(y\), y\(y\) es lo mismo que\(z\), entonces\(x\) es lo mismo que\(z\)).

Esto motiva la siguiente definición:

Definición\(7.2.4\).

Una relación de equivalencia en un conjunto\(A\) es una relación binaria en A que es reflexiva, simétrica y transitiva.

OBSERVACIÓN\(7.2.5\).

En lugar de representar una relación de equivalencia por una letra, es tradicional usar el símbolo\(\sim\) (o a veces\(\equiv\) o\(\cong\)).

Ejemplo\(7.2.6\).

Para cualquiera\(n \in \mathbb{Z}\), sabemos que el módulo de congruencia\(n\) es reflexivo, simétrico y transitivo (ver Ejercicio\(5.1.18\)). Por lo tanto, el módulo de congruencia\(n\) es una relación de equivalencia.

Ejemplo\(7.2.7\).

Definir una relación binaria\(\sim\) on\(\mathbb{R}\) por\(x \sim y\) iff\(x^{2} = y^{2}\). Entonces\(\sim\) es una relación de equivalencia.

Solución

Deseamos mostrar que\(\sim\) es reflexivo, simétrico y transitivo.

(reflexivo) Dado\(x \in \mathbb{R}\), tenemos\(x^{2} = x^{2}\), entonces\(x \sim x\).
(simétrico) Dado\(x, y \in \mathbb{R}\), tal que\(x \sim y\), tenemos\(x^{2} = y^{2}\). Dado que la igualdad es simétrica, esto implica\(y^{2} = x^{2}\), así\(y \sim x\).
(transitivo) Dado\(x, y, z \in \mathbb{R}\), tal que\(x \sim y\) y\(y \sim z\), tenemos\(x^{2} = y^{2}\) y\(y^{2} = z^{2}\). Por lo tanto\(x^{2} = y^{2} = z^{2}\), así\(x^{2} = z^{2}\). De ahí\(x \sim z\).

Ejemplo\(7.2.8\).

Definir una relación binaria\(\sim\) on\(\mathbb{N} \times \mathbb{N}\) by\((a_{1}, b_{1}\))\ sim (a_ {2}, b_ {2})\) iff\(a_{1}+b_{2} = a_{2}+b_{1}\). Entonces\(\sim\) es una relación de equivalencia.

Solución

Deseamos mostrar que\(\sim\) es reflexivo, simétrico y transitivo.

(reflexivo) Dado\((a, b) \in \mathbb{N} \times \mathbb{N}\), tenemos\(a + b = a + b\), entonces\((a, b) \sim (a, b)\).
(simétrico) Dado\((a_{1}, b_{1}),(a_{2}, b_{2}) \in \mathbb{N} \times \mathbb{N}\), tal que\((a_{1}, b_{1}) \sim (a_{2}, b_{2})\), la definición de nos\(\sim\) dice eso\(a_{1} + b_{2} = a_{2} + b_{1}\). Dado que la igualdad es simétrica, esto implica\(a_{2} + b_{1} = a_{1} + b_{2}\), así\((a_{2}, b_{2}) \sim (a_{1}, b_{1})\).
(transitivo) Dado\((a_{1}, b_{1}),(a_{2}, b_{2}),(a_{3}, b_{3}) \in \mathbb{N} \times \mathbb{N}\), tal que\[(a_{1}, b_{1}) \sim (a_{2}, b_{2}) \text { and } (a_{2}, b_{2}) \sim (a_{3}, b_{3}) ,\]

tenemos\[a_{1}+b_{2}=a_{2}+b_{1} \text { and } a_{2}+b_{3}=a_{3}+b_{2} .\]
Por lo tanto\ [\ begin {alineado}
\ left (a_ {1} +b_ {3}\ right) +\ left (a_ {2} +b_ {2}\ right) &=\ left (a_ {1} +b_ {2}\ right) +\ left (a_ {2} +b_ {3}\ right)\\
&=\ left (a_ {2} +b_ {1}\ derecha) +\ izquierda (a_ {3} +b_ {2}\ derecha)\\
&=\ izquierda (a_ {3} +b_ {1}\ derecha) +\ izquierda (a _ {2} +b_ {2}\ derecha)
\ end {alineado}\]
Restando\(a_{2} + b_{2}\) de ambos lados de la ecuación, concluimos que\(a_{1} + b_{3} = a_{3} + b_{1}\), así\((a_{1}, b_{1}) \sim (a_{3}, b_{3})\).

Ejercicio\(7.2.10\).

Demostrar que cada una de estas relaciones binarias es una relación de equivalencia.

1. Una relación binaria\(\sim\)\(\mathbb{R}\) encendida se define por\(x \sim y \text { iff } x^{2}-3 x=y^{2}-3 y\)
2. Una relación binaria\(\sim\) on\(\mathbb{R}\) se define por\(x \sim y \text { iff } x-y \in \mathbb{Z} \text {. }\)
   [Pista: Puede asumir (sin pruebas) que el negativo de cualquier entero es un entero, y que la suma de dos enteros cualesquiera es un entero. Para la transitividad, fíjese en eso\(x-z=(x-y)+(y-z)\).]
3. Una relación binaria\(\sim\) on\(\mathbb{N}^{+} \times \mathbb{N}^{+}\) se define por\(\left(a_{1}, b_{1}\right) \sim\left(a_{2}, b_{2}\right) \text { iff } a_{1} b_{2}=a_{2} b_{1}\).
   [Pista: Similar a la prueba en Ejemplo\(7.2.8\), pero con multiplicación en lugar de suma.]

Cada vez que tengamos una función, podemos usarla para hacer una relación de equivalencia en el dominio de la función:

Ejemplo\(7.2.11\).

1. Cada animal tiene una sola especie, por lo que\(\text { Species }\) es una función que se define en el conjunto de todos los animales. La relación\(S\) de equivalencia del Ejemplo se\(7.2.1\) puede caracterizar por\[x S y \quad \text { iff } \quad \text { Species }(x)=\operatorname{Species}(y) .\]
2. Si asumimos que cada persona tiene un nombre de pila, entonces\(\text { FirstName }\) es una función en el conjunto de todas las personas. La relación\(N\) de equivalencia del Ejemplo se\(7.2.2(1)\) puede caracterizar por\[x N y \quad \text { iff } \quad \text { FirstName }(x)=\text { FirstName }(y) .\]

El siguiente resultado generaliza esta idea a todas las funciones.

Ejercicio\(7.2.12\).

Supongamos\(f : A \rightarrow B\). Si definimos una relación binaria\(\sim\) on\(A\) by\[a_{1} \sim a_{2} \quad \text { iff } \quad f\left(a_{1}\right)=f\left(a_{2}\right) ,\]

entonces\(\sim\) es una relación de equivalencia.

Ejercicio\(7.2.13\).

Demostrar que si\(\sim\) es una relación de equivalencia sobre\(\mathbb{R}\), entonces existe\(a, b \in \mathbb{R}\), tal que\(a \sim b\) y\(a + b = 6\).