Archive for February 2nd, 2009

1.3 Exercise 5

February 2nd, 2009 2 comments

This problem was fun but a bit long.  In it we see how we can construct a couple uncommon equivalence relations on the real line.  Having done this, one should have the grasp to create monsters of any kind.

"Let  S and  S' be the following subsets of the plane:

 S = \{(x, y)\verb| | \vert \verb| | y = x+1 and  0<x<2 \}

 S' = \{(x, y)\verb| | \vert \verb| | y - x is an integer \}

(a) Show that  S' is an equivalence relation on the real line and  S' \supset S .  Describe the equivalence classes of  S' .

(b) Show that given any collection of equivalence relations on a set  A , their intersection is an equivalence relation on  A .

(c) Describe the equivalence relation  T on the real line that is the intersection of all equivalence relations on the real line that contain  S .  Describe the equivalence classes of  T ."

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




First, notice that the equivalence relation is on  \mathbb{R} , this is the set we've been calling  A in previous problems.  And so an equivalence relation lives in  \mathbb{R} \times \mathbb{R} , as can be seen from the definition of  S' .

Reflexivity is established by the fact that  S' \supset \{(x, y) \verb| | \vert \verb| | y - x = 0 \} , and so  \forall x \verb| | (x, x) \in C simply means  x - x = 0 is true for all  x .  Recognizing this as a real number axiom, we take for granted its veracity.

Symmetry: by definition,  S' \supset \{(x, y) \verb| | \vert \verb| | y - x = K \} with  K \in \mathbb{Z} .  We wish to show that  (y, x) \in S' , and this would mean  x - y = K .  Rearranging this in turn suggests that  -(y - x) = K , or  y - x = -K .  Now  -K is also an integer by closure of the ring operation "addition" ( -K + K = 0 \verb| | \vert \verb| | K, 0 \in \mathbb{Z} \Rightarrow -K \in \mathbb{Z} ), and so  S' \supset \{(x, y) \verb| | \vert \verb| | y - x = -K \} .  Thus,  (x, y) and  (y, x) are in  S' .

Transitivity.  Picking elements  (x, y), (y, z) \in S' , we want to show  (x, z) \in S' .  Again we will resort  to the definitions.  That the first point is in  S' suggests  y - x = K_1 with  K_1 \in \mathbb{Z} , and the second that  z - y = K_2 \Rightarrow y = z - K_2 with  K_2 \in \mathbb{Z} . Substituting we get  z - K_2 - x = K_1 \Rightarrow z - x = K_1 + K_2 = K_3 , with  K_3 \in \mathbb{Z} by closure of the ring structure of integers.  Thus,  (x, z) \in S' .

To show the inclusion  S' \supset S , recast  S as  \{(x, y) \verb| | \vert \verb| | y - x = 1 and  0 < x < 2\} .  Obviously  S' \supset \{(x, y) \verb| | \vert \verb| | y - x = 1\} , and  S' also includes any subset of  \{(x, y) \verb| | \vert \verb| | y - x = 1\} , too.

Having picked an  i \in [0, 1) , the equivalence classes can be described by  E_i = \{e \verb| | \vert \verb| | e = i + z, z \in \mathbb{Z}\} .  The set of integers is an equivalence class, e.g.


Reflexivity is established by the fact that the reflexive elements belong to all equivalence relations on  A , or, in other words,  \forall x \in A, (x, x) \in C_i if we index by  i .  Thus,  \forall x \in A, (x, x) \in \cap C_i .

Symmetry.  First, notice that any particular equivalence relation of  A is symmetric. So now pick any element in the intersection of equivalence relations,  (x, y) \in \cap C_i .  Such a point belongs to all equivalence relations because it is in the intersection.  Its symmetric point  (y, x) is also in all equivalence relations, and therefore it is in the intersection. We can conclude  (y, x) \in \cap C_i , or  \cap C_i is symmetric.

Transitivity. First notice that each and all equivalence relations are transitive.  So now pick points  (x, y), (y, z) \in \cap C_i .  These points are in all equivalence relations because they are in the intersection.  But then the point  (x, z) is in all equivalence relations as well.  Therefore it will find its way in the intersection  (x, z) \in \cap C_i , and  \cap C_i is transitive.


The set  T is an equivalence relation, by (b) above.   T contains  S because the elements of  S are in all equivalence relations  by the definition of intersection.  Also,  T contains the set  \{(x, y) \verb| | \vert \verb| | y-x = 0\} by reflexivity.  Then by symmetry,  T contains  \{(x, y) \verb| | \vert \verb| | y = x -1, 1 < x < 3\} .  There are additional elements that are included by transitivity: pick two points  (x, x+1), (x+1, x+2) \in S with  0 < x+1 < 2 .  This last statement suggests  -1 < x < 1 , but  x must be greater than zero because of the restriction of  S , so  0 < x < 1 .  These elements obtained by transitivity indicate that points of the set  S^* = \{(x, y) \verb| | \vert \verb| | y = x+2, 0<x<1\} are in  T .  By symmetry again,  \{(x, y) \verb| | \vert \verb| | y = x-2, 2<x<3\} \in T .  We should try applying transitivity on  S^* , to make sure we're not missing any elements of  T .  Pick another two points  (x, x+2), (x+2, x+4) \in S^* , with  0<x+2<2 \Rightarrow -2<x<-1 .  These elements cannot be in  T because they lie outside  0 < x < 1 .  One checks this covers all transitivity possibilities.

Summarizing:  T = \{(x, y) \verb| | \vert \verb| | y - x = 0\} \cup \{(x, y) \verb| | \vert \verb| | y = x + 1, 0 < x < 2\} \cup \{(x, y) \verb| | \vert \verb| | y = x - 1, 1 < x < 3\} \cup \{(x, y) \verb| | \vert \verb| | y = x + 2, 0 < x < 1\} \cup \{(x, y) \verb| | \vert \verb| | y = x - 2, 2 < x < 3\} .

The equivalence classes: for  -\infty < x \leq 0 and  3 \leq x < \infty , each equivalence class has  x as its single element.  \{1, 2\} belong to an equivalence class. Elements  0 < x < 1 belong to a 3-member equivalence class,  \{x, x+1, x+2\} .