Skip to main content
Logo image

Elementary Foundations: An introduction to topics in discrete mathematics

Jeremy Sylvestre

Activities 10.6 Activities
A4US

Activity 10.1.

Suppose \(n\) is a fixed but unknown positive integer, and let \(\funcdef{D}{\R}{\R^n}\) represent the function defined by \(D(x) = (x,x,\dotsc,x)\text{.}\)
Write a set definition in Candidate-condition notation for the image set \(D(\R)\text{.}\) Then do the same for the graph \(\funcgraph{D}\text{.}\)

Activity 10.2.

(a)

Devise an example of a function \(\N \to \N\) that is bijective.

(b)

Devise an example of a function \(\N \to \N\) that is injective but not surjective.

(c)

Devise an example of a function \(\N \to \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 10.3.

For each function \(\funcdef{f}{A}{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.

(a)

\(\Sigma = \{0,1\}\text{,}\) \(\funcdef{c}{\words{\Sigma}}{\words{\Sigma}}\) 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{.}\)

(b)

\(\funcdef{f}{\R}{\R \times \R}\text{,}\) \(f(x) = (x+1,x-1)\text{.}\)

(c)

\(A = \powset{\N} \relcmplmnt \{\emptyset\}\text{,}\) \(\funcdef{m}{A}{\N}\text{,}\) \(m(X) = \) the smallest number in \(X\text{.}\)

Activity 10.4.

Consider \(\Sigma = \{0,1\}\text{,}\) and recall that for \(n \in \N\text{,}\) \(\words{\Sigma}_n\) is the subset of \(\words{\Sigma}\) consisting of all words from the alphabet \(\Sigma\) with length \(n\text{.}\) Suppose \(A = \{a_1,a_2,\dotsc,a_n\}\) is a set with \(n\) distinct elements. Construct a bijection \(\powset{A} \to \words{\Sigma}_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 10.5.

Suppose \(A\) is a set that definitely does not contain any cats, and let
\begin{equation*} \funcdef{f}{\powset{A}}{\powset{A \union \{\text{Grumpy Cat}\}}} \end{equation*}
represent the function defined by
\begin{equation*} f(X) = X \union \{\text{Grumpy Cat}\} \text{.} \end{equation*}

(a)

Verify that \(f\) is injective.

(b)

Verify that \(f\) is not surjective.

(d)

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
  2. codomain, and

Activity 10.6.

Let \(\funcdef{\ell}{\words{\Sigma}}{\N}\) represent the length function, using alphabet is \(\Sigma = \{\alpha,\omega\}\text{.}\)

(a)

Compute \(\ell\bbrac{\funcinvimg{\ell}{B}}\) for \(B = \{1,10,100\}\text{.}\)

(b)

How many elements are there in \(\inv{\ell}\bbrac{\ell(A)}\) for \(A = \{\alpha\alpha, \alpha\omega, \omega\omega\alpha\omega \}\text{?}\)

Activity 10.7.

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

(a)

Draw a Venn diagram illustrating that
\begin{equation*} \funcinvimg{f}{B_1 \intersection B_2} = \funcinvimg{f}{B_1} \intersection \funcinvimg{f}{B_2} \text{.} \end{equation*}
Include all of the sets
\begin{gather*} A, \;\; B, \;\; B_1, \;\; B_2, \;\; B_1 \intersection B_2, \;\; \funcinvimg{f}{B_1}, \;\; \funcinvimg{f}{B_2},\\ \funcinvimg{f}{B_1} \intersection \funcinvimg{f}{B_2}, \;\; \text{ and } \;\; \funcinvimg{f}{B_1 \intersection B_2} \end{gather*}
in your diagram.

(b)

Formally prove that \(\funcinvimg{f}{B_1 \intersection B_2} = \funcinvimg{f}{B_1} \intersection \inv{f}{B_2}\text{,}\) using the Test for Set Equality.

Activity 10.8.

(Note: The parts of this question are independent of one another.)
Suppose \(\funcdef{f}{A}{B}\) and \(\funcdef{g}{B}{C}\) are functions.

(a)

Argue that if \(f\) and \(g\) are both surjective, then so is \(g \funccomp f\text{.}\)

(b)

If \(g \funccomp f\) is surjective, must \(g\) be? Must \(f\) be?

(c)

Argue that if \(f\) and \(g\) are both injective, then so is \(g \funccomp f\text{.}\)

(d)

If \(g \funccomp f\) is injective, must \(g\) be? Must \(f\) be?
<Prev^TopNext>