## 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$.

Categories: