7.3: Clases de equivalencia

Si nos interesan los nombres de pila (como en Ejemplo\(7.2.2(1)\)), entonces también nos puede interesar el conjunto de todas las personas que tienen el mismo nombre que tú. Esto se llama tu “clase de equivalencia”.

Definición\(7.3.1\).

Supongamos que\(\sim\) es una relación de equivalencia en un conjunto\(A\). Para cada uno\(a \in A\), la clase de equivalencia de\(a\) es el siguiente subconjunto de\(A\):\[[a]=\left\{a^{\prime} \in A \mid a^{\prime} \sim a\right\} .\]

Ejemplo\(7.3.2\).

Para la relación de equivalencia\(N\) descrita en Ejemplo\(7.2.2(1)\), tenemos\ [[\ text {Justin Timberlake}] =\ {x\ in\ text {People}\ mid\ text {firstName} (x) =\ text {firstName} (\ text {Justin Timberlake})\}.\)

En otras palabras,\(\text { [Justin Timberlake] }\) es el conjunto de todas las personas cuyo primer nombre es Justin.

ADVERTENCIA.

La notación\([a]\) no nos dice qué relación de equivalencia se está utilizando. Esto puede resultar confuso si se está considerando más de una relación de equivalencia.

Ejemplo\(7.3.3\).

Supongamos\(A=\{1,2,3,4,5\}\) y\ [R=\ izquierda\ {\ comenzar {array} {c}
(1,1), (1,3), (1,4), (2,2), (2,5), (3,1), (3,3),\\
(3,4), (4,1), (4,3), (4,4), (5,2), (5,5)
\ end {array}\ derecha\}.\]

Se puede verificar que\(R\) es una relación de equivalencia en\(A\). Las clases de equivalencia son:

Solución

\ [\ begin {reunió}
{[1] =\ {1,3,4\},\ quad [2] =\ {2,5\},\ quad [3] =\ {1,3,4\}}\\
{[4] =\ {1,3,4\},\ quad [5] =\ {2,5\}}.
\ end {reunido}\]

Ejercicio\(7.3.4\).

No es necesario que muestres tu trabajo.

1. Let\(B=\{1,2,3,4,5\}\) y\ [S=\ left\ {\ begin {array} {c}
   (1,1), (1,4), (2,2), (2,3), (3,2)\\
   (3,3), (4,1), (4,4), (5,5)
   \ end {array}\ right\}.\]
   Encuentra la clase de equivalencia de cada elemento de\(B\). (Puede asumir sin pruebas que\(S\) es una relación de equivalencia sobre\(B\).)
2. Dejar\(C = \{1,2,3,4,5\}\) y definir\(T\) por\[x T y \text { iff } x+y \text { is even. }\]
   Encuentra la clase de equivalencia de cada elemento de\(C\). (Puede asumir sin pruebas que\(T\) es una relación de equivalencia sobre\(C\).)

El siguiente teorema presenta algunas propiedades muy importantes de las clases de equivalencia:

Teorema\(\PageIndex{1}\)

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

1. Para todos\(a \in A\), tenemos\(a \in [a]\).
2. Para todos\(a \in A\), tenemos\([a] \neq \varnothing\).
3. La unión de las clases de equivalencia es todo de\(A\). Es decir, tenemos\(A=\bigcup_{a \in A}[a]\), donde\[\bigcup_{a \in A}[a]=\{x \mid \exists a \in A,(x \in[a])\} .\]
4. Para cualquiera\(a_{1}, a_{2} \in A\), tal que\(a_{1} \sim a_{2}\), tenemos\([a_{1}] = [a_{2}]\).
5. Para cualquiera\(a_{1}, a_{2} \in A\), tal que\(a_{1} \nsim a_{2}\), tenemos\(\left[a_{1}\right] \cap\left[a_{2}\right]=\varnothing\).

Ejercicio\(7.3.6\).

Demostrar teorema\(7.3.5\).
[Pista: Utilizar el hecho de que\(\sim\) es reflexivo, simétrico y transitivo.]

Obrar\(7.3.7\).

Supongamos que\(\sim\) es una relación de equivalencia en un conjunto\(A\). El teorema anterior implica que dos clases de equivalencia cualesquiera son iguales o disjuntas; es decir, o bien tienen exactamente los mismos elementos, o no tienen elementos en común.

Prueba

Dadas dos clases de equivalencia\([a_{1}]\) y\([a_{2}]\) que no son disjuntas, deseamos mostrar\([a_{1}] = [a_{2}]\). Dado que las clases de equivalencia no son disjuntas, su intersección no está vacía, por lo tanto, hay algunas\(a \in\left[a_{1}\right] \cap\left[a_{2}\right]\). De ahí,\(a \in [a_{1}]\) y\(a \in [a_{2}]\). Por definición de las clases de equivalencia, esto significa\(a \sim a_{1}\) y\(a \sim a_{2}\). De ahí, Teorema nos\(7.3.5(4)\) dice que\([a] = [a_{1}]\) y\([a] = [a_{2}]\). Por lo tanto\([a_{1}] = [a] = [a_{2}]\), como se desee