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

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

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