1.3 Exercise 4

This problem was very interesting to me because it demonstrates the nifty idea that you can create an injective function out of any surjective function (hence a bijective function) by grouping members of the domain into equivalence classes -- or, in other words, by "partitioning" the domain appropriately.  Or, from a more poetical point-of-view, by "collecting-doubled-up-string," "string" being the function.  Perhaps what I mean will be clearer by working out the problem.  

"Let  f : A \rightarrow B be a surjective function.  Let us define a relation on  A by setting  a_0 \sim a_1 if

 f(a_0) = f(a_1) .

(a) Show that this is an equivalence relation. 

(b) Let  A^* be the set of equivalence classes.  Show there is a bijective correspondence of  A^* with  B ."

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




Reflexivity, symmetry, and transitivity of the equivalence relation in this case follow from the reflexive, symmetric, and transitive properties of equality.

Reflexivity:  Pick any  a \in A , and apply  f .  By the reflexive property of equality,  f(a) = f(a) .  So  a \sim a  \forall a \in A .

Symmetry: Pick  (a_0, a_1) \in A \times A so that  f(a_0) = f(a_1) , or  a_0 \sim a_1 .  By the symmetric property of equality,  f(a_1) = f(a_0) , or  a_1 \sim a_0 .

Transitivity:  Pick  (a_0, a_1), (a_1, a_2) \in A \times A , such that  f(a_0) = f(a_1) , or  a_0 \sim a_1 and  f(a_1) = f(a_2) , or  a_1 \sim a_2 .  By the transitive property of equality, it is easy to see that  f(a_0) = f(a_2) , or  a_0 \sim a_2 .   


Pick an equivalence class,  E \in A^* .  Such  E = \{y \vert y \sim x\} ( y, x \in A ), so  f of any element  y \in E is  f(x) \in B .  In other words,  f(E) = f(x) , and such  f(x) is unique to that equivalence class  (having grouped all elements of  A that mapped to that  f(x) together and because equivalence classes are disjoint).  This shows injectivity.  Surjectivity is established by the fact that  f is surjective and all elements of  A belong to an equivalence class, so  f(E_i) sweeps all of  B .

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