\problemdata     
{S01-PS6-8}           
{Functions: in/sur/bij}              
{F98-PS7, S01-PS6} 		
{S01 Karger}

\begin{problem}


Suppose that $f$ is a function of the form
$f: A \mapsto B$, and $g$ is a function of the form $g: B \mapsto C$.
The composed function $g \circ f$ has domain $A$, range $C$, and is
defined by $(g \circ f)(a) = g(f(a))$.

\begin{problemparts}
  
\problempart Prove that if the composition $g \circ f$ is
  a bijection, then $f$ is an injection and $g$ is a surjection.

\solution{
\begin{proof}
Suppose that $g \circ f$ is a bijection.

Assume for the purpose of contradiction that $f$ is not an injection.
Then there exist elements $a_1, a_2 \in A$, such that $f(a_1) =
f(a_2)$.  This implies that $g(f(a_1)) = g(f(a_2))$.  Therefore, $g
\circ f$ is not an injection and thus not a bijection.  This is a
contradiction; therefore, $f$ must be an injection.

Now assume for the purpose of contradiction that $g$ is not a
surjection.  Then there exists an element $c \in C$ such that for all
$b \in B$, $g(b) \neq c$.  Therefore, for all $a \in A$, $g(f(a)) \neq
c$.  This implies that $g \circ f$ is not a surjection and thus not a
bijection.  This is again a contradiction; therefore, $g$ must be a
surjection.
\end{proof}
}

\problempart If $f$ is an injection and $g$ is a surjection,
then is $g \circ f$ necessarily a bijection?

\solution{
No.  For example, consider the following setup.

\begin{eqnarray*}
A & = & \{ 1 \} \\
B & = & \{ 1, 2 \} \\
C & = & \{ 1, 2 \} \\
\\
f(x) & = & x \\
g(x) & = & x
\end{eqnarray*}

In this case, $f$ is injective, $g$ is surjective, but $g \circ f$ is
not bijective.  }

\end{problemparts}
\end{problem}
