Teoría de conjuntos 6 – Relación de equivalencia

Existen varios tipos de relaciones entre conjuntos, en Aplicaciones y Funciones vimos los aspectos generales de la relaciones entre conjuntos.

En este post vamos a ver una relación muy importante y que se usa tanto en teoría de conjuntos, álgebra o matemática discreta es la relación de equivalencia.

Definición:

Sea la relación $R$ una relación entre los conjuntos $A$ y $B$ , se dice que es de equivalencia cuando cumple las siguientes propiedades:

Reflexividad:
Simetria
Transitividad

Una relación es reflexiva cuando $\forall x \quad xRx$

Es simétrica cuando $\forall x,y \quad xRy \Rightarrow yRx$

Y es transitiva cuando $\forall x,y,z \quad xRy \land yRz \Rightarrow xRz$

Cuando $aRb$ es una relación de equivalencia entre $a$ y $b$ la denotamos como $a \sim b$

Ejemplo:

Sea $A$ un conjunto y $R= \{ x,y \in A / x = y \}$ es una relación de equivalencia. En efecto.

Para todo $x \in A$ , se cumple que $x\sim x \to$ Reflexiva
Si $x\sim x$ implica $y\sim x \to$ Simétrica
Si $x\sim y$ e $y\sim z \to x\sim z \to$ Transitiva

Ejemplo 2:

Si $E$ es el conjunto de rectas del plano, la relación $a\sim b \iff a \| b$ es una relación de equivalencia en $E$ . En efecto

Toda recta el paralela a si misma.
Si $a \| b \to b \| a$
Si $a \| b \land b \| c \to a \| c$

En cambio la relación $a \perp b$ NO es una relación de equivalencia por que $a \not \perp a$ y por lo tanto no es una relación reflexiva. Con esto ya alcanza para decir que no es una relación de equivalencia, pero es interesante verificar las otras propiedades.

Si $a \perp b \to b \perp a$ se cumple la propiedad de simetría

Si $a \perp b \land b \perp c \to a \not \perp c$ sino que $a \quad y \quad c$ son paralelas, entonces no se cumple la propiedad transitiva.

Ejemplo 3:

Sea los vectores $\mathbf{v} , \mathbf{u} \in \mathbb{R}^n$ la relación $\mathbf{v} \| \mathbf{u}$ es una relación de equivalencia. En efecto:

Todo vector es paralelo a si mismo.
Si $\mathbf{v} \| \mathbf{u} \to \mathbf{u} \| \mathbf{v}$
Si $\mathbf{v} \| \mathbf{u} \land \mathbf{u} \| \mathbf{w} \to \mathbf{v} \| \mathbf{w}$

Ejemplo 4:

Se dice que el conjunto $A$ es coordinable con el conjunto $B$ si existe una biyección entre $A$ y $B$ .

Sea $E$ un conjunto , la relación $X \sim Y$ si y solo si $X$ es coordinable con $Y$ , es una relación de equivalencia en $\mathcal{P}(E)$ . En efecto:

Para todo $X \subset E \$ la función idéntica* de $X$ es una biyección de $X \to$ Reflexiva.
Si $X$ es coordinable con $Y$ , existe una biyección f de $X$ en $Y$ y por lo tanto existe la función inversa $f ^{-1}$ que es una biyección de $Y$ en $X \to$ Simétrica.
Si $X$ es coordinable con $Y$ y $Y$ es coordinable con $Z$ , existen biyecciones f y g de $X$ en $Y$ y de $Y$ en $Z$ respectivamente la composición gof es una biyección de $X$ en $Z \to$ Transitiva.

* Se $A$ un conjunto , se llama “diagonal de $A \times A$ ” y se denota como $\Delta A$ , al conjunto

$\Delta A = \{ (x,x): x \in A \}$

La correspondencia $\Delta A \to A$ se llama “función idéntica de A” y para todo $x \in A \quad I_d(x) = x$

Ejemplo 4:

Sea $a,b \in \mathbb{N} \land a < b$ si $\forall a | b$ se dice que $b$ divide a $a$ o $b$ es múltiplo de $a$ . En ese caso el conjunto de los números $a_{i}$ forman una clase de equivalencia : “Divisores de $b$ “

Se dice que $a$ es congruente con $b$ módulo $m$ cuando el resto de $a/m$ es $b$ donde $a = mk + b$ con $k,m,b \in \mathbb{N}$ . Si $b = 0$ $a$ es divisible por $b$ , es decir $a | b$ módulo $m$ .

Sea $a$ el representante de la clase “divisible por $b$ ” se denota por $[a]$ .

La relación de congruencia se denota con el símbolo $\equiv$ y es una relación de equivalencia.

En efecto:

Para todo número entero $a$ $a-a=0$ y como $0$ es múltiplo de $m$ resulta $a \equiv a \pmod{m} \to$ Reflexiva.

Si $a \equiv b \pmod{m}$ se tiene $a-b$ es múltiplo de $m$ es decir existe un entero $k$ tal que $a-b = mk$ pero entonces $b-a = (-k)m$ de donde $b-a$ es múltiplo de $m$ , por lo tanto $a \equiv b \pmod{m} \to$ Simétrica.
Si $a \equiv b \pmod{m}$ y $b \equiv c \pmod{m}$ se tiene que $a-b$ y $b-c$ son múltiplos de $m$ . Es decir existen dos números enteros $k \land k'$ tales que $a-b = mk$ y $b-c=mk'$ , sumando miembro a miembro las anteriores igualdades tenemos $a-c = (k+k')m$ o sea $a-c$ es múltiplo de $m$ y por lo tanto $a \equiv c \pmod{m} \to$ Transitiva.

Ejemplo 5:

Sean p, q, r , s enteros, con $q \land s \neq 0$ . Definimos $p/q \sim r/s$ si $ps=qr$ . Claramente $\sim$ es refleja y simétrica. Para mostrar que también es transitiva, supongamos que $p/q \sim r/s \land r/s \sim t/u$ , con q, s, u todos distintos de cero. Entonces $ps=qr \land ru=st$ .

Por lo tanto, $psu=qru=qst$ .

Como $s \neq 0 \quad pu=qt$ . Así, $p/q \sim t/u$ .

Relación de equivalencia y conjunto cociente:

Definición: Sea $E$ un conjunto y $R$ una relación de equivalencia en $E$ se llama clase de equivalencia módulo $R$ (o según $R$ ) a la imagen de $R$ por $\{x\}$ , donde $\{x\}$ es un elemento de la relación de equivalencia y se denomina “representante de la clase” .

Es decir $R(x)= \{ y / y \in E \land x \sim y\}$

Definición: Sea $E$ un conjunto y $R$ una relación de equivalencia en $E$ por $R$ . Se llama conjunto cociente de $E$ por $R$ al conjunto de las clases de equivalencia módulo $R$ en $E$ . Al conjunto cociente se denota como $E/R$ .

Lema: Si $R$ es una relación de equivalencia en un conjunto $E$ , entonces para todo para $(x,y)$ perteneciente a $E \times E$ se tiene que $x \sim y \iff R(x) = R(y)$ .

Teorema: Sea $E$ un conjunto y $R$ una relación de equivalencia en $E$ . El conjunto cociente de $E$ es una partición de $E$

Demostración: $\forall x \in E \quad x \in R(x)$ , los elementos de $E/R$ son subconjuntos no vacíos de $E$ y sea $R(x)$ y $R(y)$ dos elementos de $E/R$ y sea $z \in R(x) \cap R(y) \Rightarrow x \sim y \quad y \sim z \Rightarrow x \sim y$ entonces por el lema anterior $R(x) = R(y)$ . Propiedad simétrica y transitiva.