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.

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\}\}$.

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

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.

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.

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

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

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

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.

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.

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