Skip to main content

Chapter 7 Fun with Functions

Exercises Practice Problems

1. A function from \(\R^2\) to \(\R^2\).

Let \(f: \R \times \R \rightarrow \R \times \R\) be defined by \(f(x,y) = (2y, x-y)\text{.}\) Is \(f\) injective? surjective? Justify your answer with either a proof or a counterexample. Solution.

The function \(f\) is injective. Suppose that \(f(x_1, y_1) = f(x_2, y_2)\text{.}\) This means that \((2y_1, x_1-y_1) = (2y_2, x_2 - y_2)\text{.}\) We find that \​begin{eqnarray*} 2y_1 &=& 2y_2 \\ y_1 &=& y_2 \end{eqnarray*} and then \​begin{eqnarray*} x_1 - y_1 &=& x_2 - y_2 \\ x_1 - y_1 &=& x_2 - y_1 \\ x_1 &=& x_2 \end{eqnarray*} Therefore \((x_1, y_1) = (x_2, y_2)\text{.}\)

The function \(f\) is surjective. Pick any \((a,b) \in \R \times \R)\text{.}\) We must find \((x,y) \in \R \times \R\) such that \(f(x,y)=(a,b)\text{.}\) In order for this to hold, we need \​begin{eqnarray*} 2y &=& a \\ x-y &=& b \end{eqnarray*} Solving this linear systems gives \(x= b+ \frac{a}{2}\) and \(y=\frac{a}{2}\text{.}\) We can then check that

\begin{equation*} f \left(b+ \frac{a}{2}, \frac{a}{2} \right) = \left( 2 \cdot \frac{a}{2}, b+ \frac{a}{2} - \frac{a}{2} \right) = (a,b). \end{equation*}

2. Another function from \(\R^2\) to \(\R^2\).

Let \(f: \R \times \R \rightarrow \R \times \R\) be defined by \(f(x,y) = (5x+5y, x+y)\text{.}\) Is \(f\) injective? surjective? Justify your answer with either a proof or a counterexample. Solution.

The function \(f\) is not injective. We just need to find two different points in the domain that map to the same point in the target. There are lots of choices here. One example is \(f(1,0) = (5,1)\) and \(f(1/2, 1/2) = (5,1)\text{.}\) The function \(f\) is not surjective. We can see that every point in the image is of the form \((5b, b)\) where \(b \in \R\text{.}\) So there are lots of points in the target \(\R \times \R\) that are missed. For example, no point maps to \((1,0)\text{.}\)

3. Functions from \(\Z\) to \(\Z\).

  1. Create a function \(f: \Z \rightarrow \Z\) that is bijective. Solution.

    \begin{equation*} f(x) = x \end{equation*}

  2. Create a function \(f: \Z \rightarrow \Z\) that is injective but not surjective. Solution.

    \begin{equation*} f(x) = 2x \end{equation*}

  3. Create a function \(f: \Z \rightarrow \Z\) that is surjective but not injective. Solution.

    \begin{equation*} f(x) = \left\lfloor \frac{x}{2} \right\rfloor \end{equation*}

  4. Create a function \(f: \Z \rightarrow \Z\) that is not injective and not surjective. Solution.

    \begin{equation*} f(x) = x^2 \end{equation*}

4. The Image of a Subset.

Let \(f : X \rightarrow Y\) be a function. Let \(A \subset X\) and \(B \subset X\text{.}\) For a subset \(S \subset X\text{,}\) define the subset \(f(S) \subset Y\) by

\begin{equation*} f(S) = \{ y \in Y \mid \exists s \in S, f(s) = y \} \end{equation*}

  1. Prove that if \(A \subset B\) then \(f(A) \subset f(B)\) Solution.

    • Know: If \(x \in A\) then \(x \in B\) \qquad \((\star)\)

    • Show: If \(y \in f(A)\) then \(y \in f(B)\text{.}\)

    • Given \(y \in f(A)\)

    • \(\Longrightarrow\) There exists \(x \in A\) such that \(f(x) = y\text{.}\)

    • Note that \(x \in B\) by \((\star)\text{.}\)

    • \(\Longrightarrow\) \(f(x) \in f(B)\)

    In other words, \(y \in f(B)\text{.}\)

  2. Draw an example for which \(A \not\subset B\text{,}\) but \(f(A) \subset f(B)\text{.}\) Solution.

  3. Prove that \(f(A \cap B) \subset f(A) \cap f(B)\text{.}\) Solution.

    • Know: \(y \in f(A \cap B)\)

    • Show: \(y \in f(A) \cap f(B)\)

    • Suppose that \(y \in f(A \cap B)\)

    • \(\Longrightarrow\) There exists \(x \in A \cap B\) such that \(y = f(x)\text{.}\)

    • \(\Longrightarrow\) \(x \in A\) and \(x \in B\)

    • \(\Longrightarrow\) \(f(x) \in f(A)\) and \(f(x) \in f(B)\)

    • \(\Longrightarrow\) \(f(x) \in f(A) \cap f(B)\)

    • \(\Longrightarrow\) \(y \in f(A) \cap f(B)\)

  4. Draw an example for which \(f(A \cap B) \neq f(A) \cap f(B)\) Solution.

5. The Identity Function.

The identity function \(\mbox{Id}_X: X \rightarrow X\) is given by \(\mbox{Id}_X(x) = x\text{.}\) (So every element just maps to itself.) Let \(f : X \rightarrow Y\) and \(g: Y \rightarrow X\) be functions so that \(g \circ f = \mbox{Id}_X\text{.}\)

  1. Give an example where \(g \circ f = \mbox{Id}_X\) but \(f \circ g \neq \mbox{Id}_Y\text{.}\) Solution.

  2. Prove that if \(g \circ f = \mbox{Id}_X\) then \(f\) is injective. Solution.

    First Proof: Let's prove the contrapositive: If \(f\) is not injective then \(g \circ f \neq \mbox{Id}_X\text{.}\) Since \(f\) is not injective, there exist \(x_1 \neq x_2\) such that \(f(x_1) = f(x_2)\text{.}\) AFSOC that \(g \circ f = \mbox{Id}_X.\) But then

    \begin{equation*} x_1 = g \circ f (x_1) = g(f(x_1)) = g(f(x_2)) = g \circ f(x_2) = x_2. \end{equation*}

    But this means that \(x_1 = x_2\text{,}\) a contradiction. Therefore, \(g \circ f \neq \mbox{Id}_X.\) Second Proof: We must show that if \(x_1 \neq x_2\) then \(f(x_1) \neq f(x_2)\text{.}\) We have \​begin{eqnarray*} x_1 & \neq & x_2 \\ \mbox{Id}_X(x_1) & \neq &\mbox{Id}_X(x_2) \\ g \circ f(x_1) & \neq & g \circ f(x_2) \\ g ( f(x_1) )& \neq & g ( f(x_2)). \end{eqnarray*} Because \(g\) is a well-defined function, we must have \(f(x_1) \neq f(x_2)\) because these elements (which are in \(Y\)) map to different elements in \(Z\text{.}\)

  3. Prove that if \(g \circ f = \mbox{Id}_X\) then \(g\) is surjective. Solution.

    Given \(x \in X\) we must find a \(y \in Y\) such that \(g(y)=x\text{.}\) We have \[ x = \mbox{Id}_X(x) = g \circ f (x) = g(f(x)). \] This says that the element \(y = f(x)\) (which is in \(Y\)) satisfies \(g(y)=x\text{.}\)

6. Clock Math.

For a fixed \(n\text{,}\) let \(\Z_n = \{ 0,1,2, \ldots, n-1 \}\text{.}\) We define a function \(f: \Z \rightarrow \Z_n\) by \(f(k) = k \mbox{ mod } n\text{,}\) which is the integer remainder when \(k\) is divided by \(n\text{.}\)

  1. Consider the function \(f: \Z \rightarrow \Z_{5}\) given by \(f(k) = k \mbox{ mod } 5.\) Is \(f\) injective? Is \(f\) surjective? Justify your answers. Solution.

    The function \(f\) is surjective because \(f(k)=k\) for \(0 \leq k \leq 4.\) The function is not injective: every multiple of 5 maps to 0.

  2. Consider the function \(g: \Z_{6} \rightarrow \Z_{6}\) given by \(g(k) = 2k \mbox{ mod } 6\text{.}\) Is \(g\) injective? Is \(g\) surjective? Justify your answer. Solution.

    The function is:

    \begin{equation*} f(0)=0, \qquad f(1) = 2, \qquad f(2) = 4, \qquad f(3) = 0, \qquad f(4) = 2, \qquad f(5)=4. \end{equation*}

    Clearly, this function is not injective and it is not surjective.

  3. Consider the function \(h: \Z_{7} \rightarrow \Z_{7}\) given by \(g(k) = 2k \mbox{ mod } 7\text{.}\) Is \(h\) injective? Is \(f\) surjective? Justify your answer. Solution.

    The function is:

    \begin{equation*} f(0)=0, \qquad f(1) = 2, \qquad f(2) = 4, \qquad f(4) = 6, \qquad f(4) = 1, \qquad f(5)=3, \qquad f(6) = 5 \end{equation*}

    Clearly, this function is both injective and surjective.

  4. Fix a positive integer \(n\text{,}\) and consider the function the function \(g: \Z_{n} \rightarrow \Z_{n}\) given by \(g(k) = 2k \mbox{ mod } n\text{.}\) Prove that this function is injective if and only if \(n\) is odd. Then prove that this function is surjective if and only if \(n\) is odd. Solution.

    First, we prove that if \(n=2k\) is even then \(g: \Z_{n} \rightarrow \Z_{n}\) is not injective and not surjective

    • We have \(g(0) = 0\) and \(g(k) = 2k \mbox{ mod } (2k) = 0\text{.}\) Therefore \(g\) is not injective.

    • If \(m\) is odd, \(g(i) \neq m\) for all \(i \in \Z_n\) because \(g(i)\) is always even. Therefore \(g\) is not surjective.

    Next, we prove that if \(n=2k+1\) is odd, then \(g: \Z_{n} \rightarrow \Z_{n}\) is bijective.

    • First, we show that \(g\) is surjective. If \(m=2r\) is even (where \(0 \leq r \leq k\)), then \(g(r)=2r=m\text{.}\) If \(m=2r+1 \in \Z_n\) is odd (where \(0 \leq r \leq k\)) then \​begin{eqnarray*} g(k+r+1) &=& 2(k+r+1) \mbox{ mod } (2k+1) \\ &=& \left( ( 2k+1) + (2r+1) \right) \mbox{ mod } (2k+1) \\ &=& 2r+1. \end{eqnarray*}

    • We now know that \(g\) is surjective. Since both the domain and the target (codomain) have the same size, the function \(g\) must also be bijective. We prove this by contradiction. Suppose that the function is not injective. This means that there are \(k_1 \neq k_2\) such that \(g(k_1)=g(k_2)\text{.}\) But this would mean that the size of the image \(g([n])\) must be smaller than the size of \([n]\text{.}\) Therefore the function is not surjective. But this contradicts the fact that we already know: \(g\) is surjective. Therefore \(g\) must also be injective.