## 1.3 Exercise 2

This problem is interesting because it shows that restrictions of equivalence relations are also equivalence relations.

"Let  $C$ be a relation on a set $A$.  If  $A_0 \subset A$, define the restriction of  $C$ to  $A_0$ to be the relation  $C \cap (A_0 \times A_0)$. Show that the restriction of an equivalence relation is an equivalence relation."

(Taken from Topology by James R. Munkres, Second Edition, Prentice Hall, NJ, 2000. Page 28.)

----------

SOLUTION

Reflexivity: Notice that  $A_0 \times A_0$ will naturally contain those reflexive elements that belong to it (pick a fixed element $a \in A_0$, then $(a, a) \in A_0 \times A_0$).  By hypothesis of reflexivity of  $C$, such are included in  $C$ too, because  $C$ contains all reflexive elements in  $A \times A$. It follows that such a point is also in the restriction.

Symmetry:  We want to show that, picking any point in the restriction, its symmetric point is also in the restriction.  First, notice that for any (fixed) element  $(a, b) \in A_0 \times A_0$, its symmetric partner  $(b, a) \in A_0 \times A_0$ because of the set's square-symmetry.  Now pick  $(x, y) \in C \cap A_0 \times A_0$.  Of course, such  $(x, y) \in A_0 \times A_0$, and also  $(x, y) \in C$ by the definition of intersection.  Since  $(x, y) \in C$, there exists a point  $(y, x) \in C$ by hypothesis of its symmetry in  $A \times A$.   $(y, x)$ is also a point in  $A_0 \times A_0$ by its square-symmetry.  Therefore  $(y, x) \in C \cap A_0 \times A_0$ and the restriction is symmetric.

Transitivity:  First, notice that transitivity holds in  $A_0 \times A_0$, because it contains all elements that belong to  $A_0$ in combination with themselves.  Thus, having chosen any three (fixed) elements  $a, b, c \in A_0$, specifically these elements  $(a, b), (b, c), (a, c)$ are in  $A_0 \times A_0$.  Now pick two elements  $(x, y), (y, z) \in C \cap A_0 \times A_0$.  There is an element  $(x, z) \in C$ by hypothesis of its transitivity in  $A \times A$.  Such exists in  $A_0 \times A_0$ as well by our aforementioned observation.  Since the element is in both  $C$ and  $A_0 \times A_0$, it is in their intersection and therefore in the restriction of  $C$.

Categories: