Suppose $f\colon A\to B$ is a function. For $x,y\in A$ let $x\sim y$ mean $f(x)=f(y)$.
Lemma 5.2.1 $\sim$ is an equivalence relation on $A$.
Proof. Since $f(x)=f(x)$, $x\sim x$ and $\sim$ is reflexive. If $x\sim y$, then $f(x)=f(y)$, so $f(y)=f(x)$ and $y\sim x$; hence , $\sim$ is symmetric. If $x\sim y$ and $y\sim z$, then $f(x)=f(y)$ and $f(y)=f(z)$, so $f(x)=f(z)$, which implies that $x\sim z$, so $\sim$ is transitive.$\qed$
Example 5.2.2 Suppose $A=\{1,2,3,4,5,6,7,8,9\}$, $B=\{a,b,c,d,e\}$ and $$ \matrix{ f(1) = b, & f(4) = a, & f(7) = a, \cr f(2) = a, & f(5) = d, & f(8) = b, \cr f(3) = e, & f(6) = b, & f(9) = e.\cr} $$ Then $A/\!\!\sim\;=\{\{1,6,8\}, \{2,4,7\}, \{3, 9\}, \{5\}\}$. $\square$
Example 5.2.3 Suppose $A=\R^2$, $B=\R$ and $f((x,y))=x^2+y^2$; then an equivalence class is a circle centered at the origin—for example, $[(1,0)]$ is the unit circle. Thus, $A/\!\!\sim$ is the collection of all circles centered at the origin (if we call $\{(0,0)\}$ a circle of radius 0). $\square$
Example 5.2.4 Suppose $A$ is the set of all people, $B=\Z$, and $f\colon A\to B$ is the function that assigns to each person his or her age in years. An equivalence class consists of all people of some given age. $\square$
Suppose $C$ is the image of $f$. If $[x]\in A/\!\!\sim$, let $\overline f\colon (A/\!\!\sim) \to C$ be defined by $\overline f([x])=f(x)$.
Theorem 5.2.5 $\overline f$ is a bijection.
Proof. Note that $[x]=[y]$ iff $x\sim y$ iff $f(x)=f(y)$. Reading these in the direction $\Rightarrow$ shows that the definition of $\overline f$ does not depend on which representative of a given equivalence class is used, so $\overline f$ is well defined. Reading in the direction $\Leftarrow$ shows that $\overline f$ is an injection. Since the image of $\overline f$ is $C$, $\overline f$ is a bijection.$\qed$
Example 5.2.6 In 5.2.2, $C=\{a,b,d,e\}$, $\overline f(\{1,6,8\})=b$, $\overline f(\{2,4,7\})=a$, $\overline f(\{3,9\})=e$, $\overline f(\{5\})=d$. $\square$
Example 5.2.7 In example 5.2.3, if $C_r\subseteq A$ is the circle of radius $r$, then $\overline f(C_r)=r^2$. $\square$
Example 5.2.8 In example 5.2.4, if $P_n$ is the set of all people of age $n$, then $\overline f(P_n)=n$. $\square$
Definition 5.2.9 Let $\pi\colon A\to (A/\!\!\sim)$ be defined by $\pi(x)=[x]$, so $\pi(x)=\pi(y)$ if and only if $x\sim y$. Note that $\pi$ is a surjection since every equivalence class has at least one representative. $\square$
Theorem 5.2.10 Every function is, in a natural way, the composition of an injection, a bijection and a surjection.
Proof. Given $f\colon A\to B$, with image $C$, let $g\colon C\to B$ be the inclusion map, an injection. We have already observed that $\overline f\colon (A/\!\!\sim)\to C$ is a bijection and $\pi\colon A\to A/\!\!\sim$ is a surjection. Now for any $x\in A$, $$ (g\circ \overline f\circ \pi)(x) = g(\overline f(\pi(x)))= g(\overline f([x]))=g(f(x)) = f(x). $$ So $f=g\circ \overline f\circ \pi$ as required. $\qed$
Exercises 5.2
Ex 5.2.1 Suppose $A=\{1,2,3,4,5,6,7,8,9,10,11,12\}$, $B=\{a,b,c,d,e,f\}$ and $$ \matrix{ f(1) = b, & f(5) = f, & f(9) = b, \cr f(2) = a, & f(6) = e, & f(10) = b, \cr f(3) = e, & f(7) = a, & f(11) = a,\cr f(4) = f, & f(8) = b, & f(12) = a.\cr} $$ Find $C=f(A)$, $A/\!\!\sim$, and $\overline f$.
Ex 5.2.2 Suppose $A=\R^3$, $B=\R^2$ and $f\colon A\to B$ is $f((x,y,z))= (0,z)$. Describe $C=f(A)$, $A/\!\!\sim$, and $\overline f$. Use the relation $\sim$ defined at the beginning of the section.
Ex 5.2.3 When is $\pi$ an injection? When is $g$ (as defined in theorem 5.2.10) a surjection?
Ex 5.2.4 Suppose $A$ and $B$ have $m$ and $n$ elements, respectively, and the image, $C$, of $f\colon A\to B$ has $k$ elements. If $A/\!\!\sim = \{S_1, S_2, …, S_k\}$ and each $S_i$ has $m_i$ elements in it, how many pseudo-inverses does $f$ have? When does $f$ have exactly one pseudo-inverse?
Ex 5.2.5 If $h$ is a pseudo-inverse to $f$, what is $\pi\circ h\circ g\circ \overline f$? ($g$ is as defined in theorem 5.2.10.)
Ex 5.2.6 If $X\subseteq A$, show that $f^{-1}(f(X))=\bigcup_{x\in X}[x]$, using the relation $\sim$ defined at the beginning of the section.