Exercise 2.4

Question

ewcommand\inv[1]{#1^{-1}}

Let $f: A 	o B$ and $g: B 	o C$.
\begin{enumerate}[label=(\alph*)]
\item If $C_0 \subset C$, show that $\inv{(g \circ f)}(C_0) = \inv{f}(\inv{g}(C_0))$.
\item If $f$ and $g$ are injective, show that $g \circ f$ is injective.
\item If $g \circ f$ is injective, what can you say about the injectivity of $f$ and $g$?
\item If $f$ and $g$ are surjective, show that $g \circ f$ is surjective.
\item If $g \circ f$ is surjective, what can you say about the surjectivity of $f$ and $g$?
\item Summarize your answers to (b)-(e) in the form of a theorem.
\end{enumerate}

Dan Whitman · Accepted Answer

ewcommand\braces[1]{\left\{ #1 ight\}}

ewcommand\inv[1]{#1^{-1}}

\begin{enumerate}[label=(\alph*)]
\item
  \begin{proof}
    Suppose that $C_0 \subset C$.
    We can show this with a string of biconditionals.
    For any $x$, we have
    \begin{align*}
      x \in \inv{(g \circ f)}(C_0) &\Leftrightarrow (g \circ f)(x) \in C_0 \
                                   &\Leftrightarrow g(f(x)) \in C_0 \
                                   &\Leftrightarrow f(x) \in \inv{g}(C_0) \
                                   &\Leftrightarrow x \in \inv{f}(\inv{g}(C_0)) \,,
    \end{align*}
    which of course shows the desired result.
  \end{proof}

\item
  \begin{proof}
    Suppose that $x,y \in A$ and $x 
eq y$.
    Then, since $f$ is injective, it has to be that $f(x) 
eq f(y)$ by the contrapositive of the definition of an injection.
    Then again $(g \circ f)(x) = g(f(x)) 
eq g(f(y)) = (g \circ f)(y)$ since $f(x) 
eq f(y)$ and $g$ is injective.
    This shows that $g \circ f$ is injective by the contrapositive of the definition.
  \end{proof}

\item
  Here we claim that if $g \circ f$ is injective, then $f$ must be injective but $g$ may not be.
  \begin{proof}
    Suppose that $g \circ f$ is injective but that $f$ is not.
    Then there are $x,y \in A$ where $x 
eq y$ but $f(x) = f(y)$.
    Then we have
    \begin{gather*}
      (g \circ f)(x) = g(f(x)) = g(f(y)) = (g \circ f)(y) \,,
    \end{gather*}
    which contradicts the fact that $g \circ f$ is injective since $x 
eq y$.
    So it must be that $f$ is injective.

To show that $g$ need not be injective, consider the sets
    \begin{align*}
      A &= \braces{1,2} &
                          B &= \braces{1,2,3} &
                                                C &= \braces{a,b}
    \end{align*}
    and the function sets
    \begin{align*}
      f &= \braces{(1,1), (2,2)} &
                                   g &= \braces{(1,a), (2,b), (3,b)} \,.
    \end{align*}
    It is easy to see that $f: A 	o B$ is injective as is the composition $g \circ f = \braces{(1,a), (2,b)}$, but that $g: B 	o C$ is not since $g(2) = b = g(3)$.
  \end{proof}

\item
  \begin{proof}
    Suppose that $f$ and $g$ are surjective and consider any $z \in C$.
    Then there is a $y \in B$ where $z = g(y)$ since $g$ is surjective.
    Since $f$ is also surjective, there is then an $x \in A$ where $y = f(x)$.
    Then we have
    \begin{gather*}
      (g \circ f)(x) = g(f(x)) = g(y) = z \,,
    \end{gather*}
    which shows that $g \circ f$ is surjective as desired since $z$ was arbitrary.
  \end{proof}

\item
  We claim that if $g \circ f$ is surjective, then $g$ must be surjective, but $f$ may not be.
  \begin{proof}
    Suppose that $g \circ f$ is surjective and consider any $z \in C$ so that there is an $x \in A$ where $(g \circ f)(x) = z$.
    Then we have that $g(f(x)) = z$ so that $y = f(x)$ is an element of $B$ where $g(y) = z$.
    This shows that $g$ is surjective since $z$ was arbitrary.

To show that $f$ need not be surjective we can use the same example sets $A,B,C$ and functions $f,g$ used in part~(c).
    It is easy to see there that $g \circ f$ and $g$ are surjective but $f$ is not since there is no element of $A$ that maps to $3 \in B$.
  \end{proof}

\item We can summarize these facts in the following theorem, whose proof is of course found in the previous parts:
  \begin{theorem}
    Suppose that $f: A 	o B$ and $g: B 	o C$.
    We assert the following:
    \begin{itemize}
    \item If $f$ and $g$ are injective then $g \circ f$ is injective.
    \item If $g \circ f$ is injective then $f$ is also injective.
    \item If $f$ and $g$ are surjective then $g \circ f$ is surjective.
    \item If $g \circ f$ is surjective then $g$ is also surjective.
    \end{itemize}
  \end{theorem}
\end{enumerate}

Exercise 2.4

Answers

Comments

Exercise 2.4

Answers

Comments

Add answer