Injections and surjections are `alike but different,' much as
intersection and union are `alike but different.'
This is another example of
*duality.*

Theorem 4.4.1 Suppose $f\colon A\to B$ and $g\colon B\to C$ are functions.

a) If $g\circ f$ is injective then $f$ is injective.

b) If $g\circ f$ is surjective then $g$ is surjective.

**Proof.**

We prove part (a), leaving part (b) as an exercise. Suppose
$a,a'\in A$ and $f(a)=f(a')$. We wish to prove $a=a'$. We have
$$
(g\circ f)(a)= g(f(a))=g(f(a'))=(g\circ f)(a')
$$
and since $g\circ f$ is injective, we conclude $a=a'$, as
desired.

The next result shows that injective and surjective functions can be "canceled.'' As in theorem 4.4.1, the result in the two cases is `the same, but different.'

Theorem 4.4.2 Suppose $f_1,f_2\colon A\to B$, $g\colon B\to C$, $h_1,h_2\colon C\to D$ are functions.

a) If $g$ is injective and $g\circ f_1=g\circ f_2$ then $f_1=f_2$.

b) If $g$ is surjective and $h_1\circ g=h_2\circ g$ then $h_1=h_2$.

**Proof.**

We prove part (b), leaving part (a) as an exercise. Suppose $c\in
C$. We wish to show $h_1(c)=h_2(c)$. By hypothesis $g$ is
surjective, so there is a $b\in B$ such that $g(b)=c$. So
$$
h_1(c)=h_1(g(b))=(h_1\circ g)(b)=(h_2\circ g)(b)=h_2(g(b))=h_2(c),
$$
as desired.

## Exercises 4.4

**Ex 4.4.1**
Show by example that if $g\circ f$ is injective, then $g$
need not be injective.

**Ex 4.4.2**
Show by example that if $g\circ f$ is surjective, then $f$
need not be surjective.

**Ex 4.4.3**
Show by example that a function $g$ that is not injective
may not be "cancellable'' when it appears on the left, i.e., there
may exist $f_1\ne f_2$ such that $g\circ f_1=g\circ f_2$.

**Ex 4.4.4**
Show by example that a function $f$ that is not surjective
may not be "cancellable'' when it appears on the right, i.e., there
may exist $g_1\ne g_2$ such that $g_1\circ f=g_2\circ f$.

**Ex 4.4.5**
Prove 4.4.1(b).

**Ex 4.4.6**
Prove 4.4.2(a).

**Ex 4.4.7**
Suppose $f\colon A\to B$ is a surjection and $Y\subseteq B$. Show
that $f(f^{-1}(Y))=Y$.

**Ex 4.4.8**
Suppose $f\colon A\to B$ is injective and $W$, $X$ are disjoint
subsets of $A$. Prove that $f(W)$ and $f(X)$ are disjoint subsets of
$B$.