## 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 be a surjective function. Let us define a relation on by setting if

.

(a) Show that this is an equivalence relation.

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

(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 , and apply . By the reflexive property of equality, . So , .

Symmetry: Pick so that , or . By the symmetric property of equality, , or .

Transitivity: Pick , such that , or and , or . By the transitive property of equality, it is easy to see that , or .

(b)

Pick an equivalence class, . Such (), so of any element is . In other words, , and such is unique to that equivalence class (having grouped all elements of that mapped to that together and because equivalence classes are disjoint). This shows injectivity. Surjectivity is established by the fact that is surjective and all elements of belong to an equivalence class, so sweeps all of .