EJERCICIOS: RELACIONES DE EQUIVALENCIA

1. Sea $R$ una relación sobre $X$, tal que $Dom(R) = X$ y $R$ es simétrica y transitiva. Muestre que $R$ es una relación de equivalencia.

2. Sea $f: X \longrightarrow Y$ una función sobreyectiva, con $X$ un conjunto no vacío. Defina la relación $E_{f}$ sobre $X$ así: $aEb$ si y sólo si $f(a) = f(b)$.
   1. Muestre que $E_{f}$ es una relación de equivalencia.

   2. Dé una biyección entre $X/E$ y $Y$. [De este modo, la relación $E$ transforma al conjunto $X$ en un conjunto $X/E$ con el mismo tamaño del conjunto $Y$ ].

3. Sea $R$ la siguiente relación sobre $\mathbb{R}$: $rRs$ si y sólo si $r - s \in \mathbb{Z}$.
   1. Muestre que $R$ es una relación de equivalencia.
   2. Describa $[0]$ y $[\pi]$.
   3. Muestre que para $r, s \in \mathbb{R}$: $([r], <) \cong ([s], <)$.
   4. Encuentre un conjunto de representantes para $R$.
   5. Concluya que $\mathbb{R}$ es la unión disyunta de copias de $\mathbb{Z}$ (más precisamente, $\mathbb{R}$ es la unión disyunta de conjuntos isomorfos con el orden a los enteros).

4. Sea $E$ la siguiente relación sobre $\mathbb{R}$: $\theta \; E \; \beta$ si y sólo si existe un entero $k$ tal que $\theta - \beta = 2 \pi k$.
   1. Muestre que $E$ es una relación de equivalencia.
   2. Encuentre 4 distintos conjuntos de representantes para $E$.
   3. Encuentre una biyección entre $\mathbb{R}/E$ y el círculo sin un punto $C* = \{ (x, y) : x^2 + y^2 = 1, \} \smallsetminus \{ (1, 0) \}$.

5. Sea $L$ el conjunto de todas las rectas de $\mathbb{R}^2$. Dé un ejemplo de una relación de equivalencia sobre $L$, distinta de la relación igualdad.

6. El espacio proyectivo: Sea $X = \mathbb{R} \smallsetminus \{ (0, 0)\}$, y defina la relación $\sim$ sobre $X$ así: $(a, a') \sim (b, b')$ si y sólo si $(a, a')$ y $(b, b')$ están ambos sobre una misma recta que pasa por el origen.

7. Sea $R_{0}$ una relación reflexiva y simétrica, y para $n \in \mathbb{N}$, sea $R_{n + 1}$ una relación reflexiva y simétrica tal que $R_{n + 1} \circ R_{n + 1} \subseteq R_{n}$. Muestre que $R = \cap_{ n \in \mathbb{N} } R_{n}$ es una relación de equivalencia.
   1. Muestre que $\sim$ es una relación de equivalencia.

   2. Encuentre un conjunto de representantes para $\sim$, y dibújelo. [$X/\sim$ es llamado el espacio proyectivo].

8. Dado $X$ un conjunto no vacío, muestre que existe una única relación de equivalencia $R$ sobre $X$ tal que $X/R$ sea un singleton.

9. El siguiente ejercicio es informal, pero ilustrativo: Sea $E$ el conjunto de puntos de una ciudad donde una persona puede pararse, esto es, el espacio libre de la ciudad (por comodidad, podemos ver a $X$ como un subconjunto de $R^2$). Defina la relación $\sim$ sobre $E$ así: $pEq$ si y sólo si es posible transladarse a pie del punto $p$ hacia el punto $q$.
   1. Muestre que $\sim$ es una relación de equivalencia.
   2. Describa a $[p]$, la clase de un punto $p$ cualquiera.
   3. Interprete al valor $n$ = tamaño del conjunto $E/\sim$.

10. Sea $n$ un natural positivo. Dé un ejemplo de una relación de equivalencia $R$ sobre $\mathbb{Z}$ tal que $\mathbb{Z}/R$ sea un conjunto de $n$ elementos.

11. Sea $I = [0, 1] \subseteq \mathbb{R}$. $I^2$ es, entonces, un cuadrado de lado $1$, con borde $B = I^{2} \smallsetminus (0, 1)^2$. Defina la relación $\sim$ sobre $I^2$ así: $(a, b) \sim (c, d)$ si y sólo si [ $(a, b), (c, d) \in B$ ó ( $(a, b) \not\in B$ y (a, b) = (c, d))].
    1. Muestre que $\sim$ es una relación de equivalencia.

    2. ¿Quiénes son las clases de $\sim$?

    3. Encuentre un conjunto de representantes para $\sim$.

    4. $\star$ Así como $I^2$ es un cuadrado, ¿cómo puede verse, espacialmente hablando, $I^2 / \sim$?

12. Un grafo no dirigido y sin lazos $G = (V, E)$ consiste en un conjunto $V$ de vértices junto con una relación binaria $E \subseteq V^{2}$ irreflexiva y simétrica, llamada el conjunto de aristas. A los grafos los dibujamos como puntos (vértices) unidos por líneas (aristas). Por ejemplo, si $V = \{ 1, 2, 3, 4\}$ y $E = \{ (1, 4), (4, 1), (1, 3), (3, 1), (1, 2), (2, 1)\}$, entonces $G = (V, E)$ es un grafo, que dibujaremos de la siguiente manera:
    
    
    

    Dados dos grafos $G = (V, E)$ y $G' = (V', E')$, diremos que son isomorfos (y lo notamos: $G \cong G'$) si y sólo si existe una biyección $f: V \longrightarrow V'$ tal que para $u, v \in V$, $(u, v) \in E$ si y sólo si $(f(u), f(v)) \in E'$.

    1. Encuentre un grafo isomorfo al grafo del ejemplo de arriba (que sea distinto!).

    2. Sea $X$ el conjunto de todos los grafos $G = (V, E)$ no dirigidos sin lazos tales que $V = \{ 1, 2, 3, 4\}$, y defina en $X$ la siguiente relación: $G = (V, E) \sim G' = (V, E')$ si y sólo si $G \cong G'$.
       1. Muestre que $\sim$ es una relación de equivalencia.

       2. Exhiba un conjunto de representantes para $\sim$ (dibújelos).

       3. ¿Cuántos elementos tiene $X/\sim$? [Si $n = X / \sim$, diremos que existen $n$ grafos distintos de cuatro vértices, módulo isomorfismo].

13. Sea $R \subseteq X^{2}$. Demuestre que las propiedades de reflexividad, simetría y transitividad pueden enunciarse, conjuntistamente, de la siguiente manera:
    1. $R$ es reflexiva si y sólo si $Id_{X} \subseteq R$.

    2. $R$ es simétrica si y sólo si $R^{-1} = R$.

    3. $R$ es transitiva si y sólo si $R \circ R \subseteq R$.

14. Dados dos números reales $a, b$ con $a \leq b$, sea $(a, b) = \{ x \in \mathbb{R} : a < x < b \}$ (por ejemplo, $(a, a) = \varnothing$). Llamaremos básico a un conjunto de la forma $(a,b)$. Sea $B$ el conjunto de todos los básicos, esto es:
    $$B = \{ (a, b) : a, b \in \mathbb{R}, a \leq b \}$$

    Dado $r$ un número real cualquiera, sea $\sim_{r}$ la siguiente relación de equivalencia sobre $B$: $(a, b) \sim_{r} (c, d)$ si y sólo si existe $(y, z) \in B$ tal que $r \in (y, z)$ y $(a, b) \cap (y, z) = (c, d) \cap (y, z)$.

    1. Muestre que $\sim_{r}$ es una relación de equivalencia.
    2. Muestre que si $r \in (a, b), (c, d)$, entonces $[(a, b)]_{ \sim_{r} } = [(c, d)]_{ \sim_{r} }$.
    3. Dé un ejemplo de dos básicos $(a,b)$, $(c, d)$ tales que $r \not\in (a, b), (c, d)$, pero $[(a, b)]_{ \sim_{r} } \not= [(c, d)]_{ \sim_{r} }$.
    4. ¿Cuántos elementos tiene $B / \sim_{r}$?

15. Sea $E_{1}$ una relación de equivalencia sobre $\mathcal{P}( X )$, y defina la relación $E_{2}$ sobre $\mathcal{P}( X )$ así: $A E_{2} B$ si y sólo si $A^{c} E_{1} B^{c}$. Demuestre que $E_{2}$ es una relación de equivalencia. ¿Cuál es la relación entre $E_{1}$? y $E_{2}$?

16. Dado $X$ un conjunto y $S \subseteq X$, sea $E_{S} = \{ (A, B) \in \mathcal{P} ( X ) : A \bigtriangleup B \subseteq S \}$.
    1. Demuestre que $E_{S}$ es una relación de equivalencia.
    2. Para $S, T \subseteq X$, ¿cómo se comparan los conjuntos $E_{S} \cap E_{T}$ y $E_{S \cap T}$?
    3. Para $S, T \subseteq X$, ¿cómo se comparan los conjuntos $E_{S} \cup E_{T}$ y $E_{S \cup T}$?
    4. Para $S, T \subseteq X$, ¿cómo se comparan los conjuntos $E_{S} \bigtriangleup E_{T}$ y $E_{S \bigtriangleup T}$?

17. (Una bella caracterización de las relaciones de equivalencia) Sea $E$ una relación sobre $X$. Muestre que $E$ es una relación de equivalencia sobre $X$ si y sólo si se cumple la siguiente propiedad:
    $$\forall x, y \in X : x E y \leftrightarrow (\forall z \in X: x E z \leftrightarrow y E z)$$

    (Para más información, véase la siguiente página web: http://wwwpa.win.tue.nl/wstomv/publications/equivalence.pdf).