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.)



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 .

  1. No comments yet.
  1. No trackbacks yet.