10.6: Activities

Activity \(\PageIndex{1}\)

Suppose \(n\) is a fixed but unknown positive integer, and let \(D: \mathbb{R} \rightarrow \mathbb{R}^n\) represent the function defined by \(D(x) = (x,x, \ldots ,x)\text{.}\)

Write a set definition in Candidate-condition notation for the image set \(D(\mathbb{R})\text{.}\) Then do the same for the graph \(\Delta (D)\text{.}\)

Activity \(\PageIndex{2}\)

1. Devise an example of a function \(\mathbb{N} \to \mathbb{N}\) that is bijective.
2. Devise an example of a function \(\mathbb{N} \to \mathbb{N}\) that is injective but not surjective.
3. Devise an example of a function \(\mathbb{N} \to \mathbb{N}\) that is surjective but not injective.

Note that when you define a function, you don't necessarily have to give an input-output formula — you can also use a table of input-output values or just a description in words (i.e. an algorithm) of how an output is to be produced from an input.

Activity \(\PageIndex{3}\)

For each function \(f: A \rightarrow B\) defined below, carry out the following.

1. Decide whether the function is injective. Use the Injective Function Test to verify your answer.
2. Determine some pattern that all elements of the image \(f(B)\) have in common. That is, if you were handed an arbitrary element of the codomain \(B\text{,}\) describe what property or properties you would use to determine whether it was in the subset \(f(A) \subseteq B\text{.}\)
3. Decide whether the function is surjective. Use the Surjective Function Test to verify your answer.

1. \(\Sigma = \{0,1\}\text{,}\) \(c: \Sigma^{\ast}\rightarrow \Sigma^{\ast}\) is the bitwise complement function: for input word \(w\text{,}\) the output word \(c(w)\) is the word of the same length as \(w\) but with a \(0\) at every position that \(w\) has a \(1\text{,}\) and a \(1\) at every position that \(w\) has a \(0\text{.}\)
2. \(f: \mathbb{R} \rightarrow \mathbb{R} \times \mathbb{R}\text{,}\) \(f(x) = (x+1,x-1)\text{.}\)
3. \(A = \mathscr{P}\mathbb{N} \setminus \{\emptyset\}\text{,}\) \(m: A \rightarrow \mathbb{N} \text{,}\) \(m(X) = \) the smallest number in \(X\text{.}\)

Activity \(\PageIndex{4}\)

Consider \(\Sigma = \{0,1\}\text{,}\) and recall that for \(n \in \mathbb{N}\text{,}\) \(\Sigma^{\ast}_n\) is the subset of \(\Sigma^{\ast}\) consisting of all words from the alphabet \(\Sigma\) with length \(n\text{.}\) Suppose \(A = \{a_1,a_2,\ldots ,a_n\}\) is a set with \(n\) distinct elements. Construct a bijection \(\mathscr{P}(A) \to \Sigma^{\ast}_n\text{.}\)

When attempting this activity, remember that when you define a function you don't necessarily have to give an input-output formula — you can also use a description in words (i.e. an algorithm) of how an output is to be produced from an input.

Activity \(\PageIndex{5}\)

Suppose \(A\) is a set that definitely does not contain any cats, and let

\begin{equation*} f: \mathscr{P}(A) \rightarrow \mathscr{P}(A \cup \{\text{Grumpy Cat}\}) \end{equation*}

represent the function defined by

\begin{equation*} f(X) = X \cup \{\text{Grumpy Cat}\} \text{.} \end{equation*}

1. Verify that \(f\) is injective.
2. Verify that \(f\) is not surjective.
3. Describe specifically how to make \(f\) bijective by restricting the codomain.
4. As all bijective functions are invertible, the bijective version of \(f\) from Task c has an inverse \(\inv{f}\text{.}\) Describe this inverse by specifying its
   1. domain,
   2. codomain, and
   3. input-output rule.

Activity \(\PageIndex{6}\)

Let \(\ell: \Sigma^{\ast} \rightarrow \mathbb{N}\) represent the length function, using alphabet is \(\Sigma = \{\alpha,\omega\}\text{.}\)

1. Compute \(\ell(\ell ^{-1} (B))\) for \(B = \{1,10,100\}\text{.}\)
2. How many elements are there in \(\ell^{-1}(\ell(A))\) for \(A = \{\alpha\alpha, \alpha\omega, \omega\omega\alpha\omega \}\text{?}\)

Activity \(\PageIndex{7}\)

Suppose \(f: A \rightarrow B\) is a function, and \(B_1,B_2\) are subsets of \(B\text{.}\)

1. Draw a Venn diagram illustrating that

\begin{equation*} f^{-1} ( B_1 \cap B_2) = f^{-1}(B_1) \cap f^{-1} (B_2) \text{.} \end{equation*}
Include all of the sets

\begin{gather*} A, \;\; B, \;\; B_1, \;\; B_2, \;\; B_1 \cap B_2, \;\; f^{-1}(B_1), \;\; f^{-1} (B_2),\\ f^{-1}(B_1) \cap f^{-1} (B_2), \;\; \text{ and } \;\; f^{-1} ( B_1 \cap B_2) \end{gather*}

in your diagram.

2. Formally prove that \(f^{-1} ( B_1 \cap B_2) = f^{-1}(B_1) \cap f^{-1}(B_2)\text{,}\) using the Test for Set Equality.

Activity \(\PageIndex{8}\)

(Note: The parts of this question are independent of one another.)

Suppose \(f: A \rightarrow B\) and \(g: B \rightarrow C\) are functions.

1. Argue that if \(f\) and \(g\) are both surjective, then so is \(g \circ f\text{.}\)
2. If \(g \circ f\) is surjective, must \(g\) be? Must \(f\) be?
3. Argue that if \(f\) and \(g\) are both injective, then so is \(g \circ f\text{.}\)
4. If \(g \circ f\) is injective, must \(g\) be? Must \(f\) be?