Skip to main content

Chapter 9 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. Even and Odd Subsets.

Let \(\mathcal{E} = \{S \subseteq [7] : |S| \text{ is even}\}\) and let \(\mathcal{O} = \{S \subseteq [7] : |S| \text{ is odd}\}\text{.}\) Consider the function \(\mathcal{C}:\mathcal{E} \to \mathcal{O}\) defined by the rule \(\mathcal{C}(S) = \overline{S}\text{,}\) the complement of \(S\text{.}\)

  1. Give an example of an element \(S\) of the domain of this function, then compute \(\mathcal{C}(S)\text{.}\) Solution.

    One example is \(S = \{ 1,2,3 \}\) and \(\mathcal{C}(S) = \{4,5,6,7\}\text{.}\)

  2. How do we know that \(\mathcal{C}\) is well-defined; that is, given \(S \in \mathcal{E}\text{,}\) how do we know \(\mathcal{C}(S) \in \mathcal{O}\text{?}\) Is there anything special about the choice of the number \(7\) in this problem? Solution.

    Since \(S \in \mathcal{E}\text{,}\) we know that \(|S|\) is an even number. So the size of \(\overline{S} = 7 - |S|\) is an odd number. This means that the function is well defined. What is special about 7 is that it is odd. This mapping from odd subsets to even subsets will work for any set \([2k+1]\text{.}\)

  3. What are the steps to prove that \(\mathcal{C}\) is injective? Solution.

    Let's prove the contrapositive. Suppose that \(A,B \in \mathcal{E}\text{,}\) and that \(A \neq B\text{.}\) Without loss of generality, there exists \(a \in A\) such that \(a \notin B\text{.}\) Equivalently, we have \(a \notin \overline{A}\) and \(a \in \overline{B}\text{.}\) Therefore \(\overline{A} \neq \overline{B}\text{.}\) We can now conclude that when \(A \neq B\text{,}\) we have \(\mathcal{C}(A) = \overline{A} \neq \overline{B} = \mathcal{C}(B)\text{.}\) This shows that \(\mathcal{C}\) is injective.

  4. What are the steps to prove that \(\mathcal{C}\) is surjective? Solution.

    Pick any set \(B \in \mathcal{O}\text{,}\) so that \(|B|\) is odd. Then \(|\overline{B}|\) is even, and therefore \(\overline{B} \in \mathcal{E}\text{.}\) Finally, we have \(\mathcal{C}(\overline{B}) = B\text{.}\) This proves that \(\mathcal{C}\) is surjective.

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

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.