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

-------------

SOLUTION

(a)

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 .   

(b)  

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.

*