10.7: Exercises

Exercise \(\PageIndex{1}\)

Use predicate logic to write formal definitions of surjective function, injective function, and bijective function. Be sure to state the domains of your free variables.

Exercise \(\PageIndex{2}\)

Let \(A\) represent the set of all university students and let \(C\) be the set of all university courses. Does the rule \(f:A \rightarrow C\) given by

\begin{equation*} f(a) = c \text{ if student is registered in course } \end{equation*}
define a function? Justify your answer.

Testing bijectivity and determining inverses.

In each of Exercises 3–7, determine whether or not the described function is a bijection. For those functions that are bijective, describe the inverse function; that is, specify the inverse function's

1. domain,
2. codomain, and
3. input-output rule.

Exercise \(\PageIndex{3}\)

\(\Lambda = \{T, \, F\}\text{,}\) \(n: \Lambda\rightarrow \Lambda\) is the logical negation function \(n(p) = \neg p\text{.}\)

Exercise \(\PageIndex{4}\)

\(\mathscr{L}\) represents the set of all possible logical statements, \(n: \mathscr{L} \rightarrow \mathscr{L}\) is the logical negation function \(N(A) = \neg A\) for \(A\) a logical statement.

(Note: You may treat equivalent statements as being the same statement.)

Exercise \(\PageIndex{5}\)

\(\mathscr{N}: \mathbb{Z} \rightarrow \mathbb{Z}\) is the numerical negation function \(\mathscr{N}(n) = -n\text{.}\)

Exercise \(\PageIndex{6}\)

\(\Sigma = \{0,1\}\text{,}\) \(\Sigma^{\ast}\) represents the set of all binary words, \(c: \Sigma^{\ast} \rightarrow \Sigma^{\ast}\) is the bitwise complement function defined by: if \(w\) is a binary word, let \(c(w)\) be a binary word of the same length 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{.}\) For example, \(c(010) = 101\) and \(c(0000) = 1111\text{.}\)

Exercise \(\PageIndex{7}\)

\(U\) represents a universal set, \(c: \mathscr{P}(U)\rightarrow \mathscr{P}(U)\) is the complement function \(C(A) = A^c\text{,}\) for \(A \subseteq U\text{.}\)

Exercise \(\PageIndex{8}\)

Let \(E \subseteq \mathbb{Z}\) represent the set of even integers, and consider the function \(f: {\mathbb{Z}}{E}\text{,}\) \(f(n) = 2n\text{.}\)

1. Prove that \(f\) is a bijection.
2. Describe the inverse function \(f^{-1}: E \rightarrow \mathbb{Z}\text{.}\) That is, describe the rule to determine \(f^{-1}(n)\text{,}\) given even number \(n\text{.}\)

Exercise \(\PageIndex{9}\)

As usual, \(\mathbb{R}^m = \mathbb{R} \times \mathbb{R} \times \cdots \times \mathbb{R}\) represents the Cartesian product of \(m\) copies of \(\mathbb{R}\text{,}\) where \(m\) is a positive integer. Consider the function \(D: \mathbb{R}\rightarrow \mathbb{R}^m\) defined by \(D(x) = (x,x,\ldots ,x)\text{.}\)

Terminology.

The function \(D\) in this exercise is called a diagonal embedding. We can define a similar diagonal embedding \(D: A \hookrightarrow A^m\) for every nonempty set \(A\text{.}\)

1. Prove that \(D\) embeds \(\mathbb{R}\) into \(\mathbb{R}^m\text{.}\)
2. Fill in the right-hand side of the set definition in Candidate-condition notation for the image of \(D\) below.

\begin{equation*} D(\mathbb{R}) = \{(x_1,x_2,\ldots ,x_m) \in \mathbb{R}^m \vert \underline{\qquad \qquad } \} \end{equation*}

3. Provide a set definition for the graph \(\Delta(D)\) in Form-parameter notation. Of what set is \(\Delta(D)\) a subset?
4. Can you come up with other “natural” embeddings \(\mathbb{R} \hookrightarrow \mathbb{R}^m\text{?}\)

Exercise \(\PageIndex{10}\)

Let \(A = \{0,1,2,3,4,5,6,7,8,9\}\) and let \(P \subseteq \mathscr{P}(A)\) represent the set of all subsets of \(A\) which contain an odd number of elements. Define \(\nu: P\rightarrow A\) by setting \(\nu(X)\) to be the “middle” element of \(X\) when the elements of \(X\) are listed in order by size. For example, \(\nu(\{0,8,9\}) = 8\text{.}\)

Is \(\nu\) injective? Surjective? Bijective?

Exercise \(\PageIndex{11}\)

Let \(\Sigma = \{0,1\}\text{.}\) Recall that for \(n \in \N\text{,}\) \(\Sigma^{\ast}_n\) is the subset of \(\Sigma^{\ast}\) consisting of all binary words of 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{.}\)

Exercise \(\PageIndex{12}\)

Call a function with domain \(\emptyset\) an empty function.

1. Verify that every empty function is injective.

Hint

Use your formal expression of injective from Exercise 10.7.1, along with what you learned in Section 4.3.

2. Verify that an empty function with empty codomain is bijective.

Hint

You have already verified injectivity of an empty function more generally in Task a. For surjectivity in this more specific setting, use your formal expression of surjective from Exercise 10.7.1, along with what you learned in Section 4.3.

Exercise \(\PageIndex{13}\)

Let \(f: A \rightarrow B\) and \(g: B \rightarrow C\) be functions.

Exercise \(\PageIndex{14}\)

Let \(f: {A}{B}\) be a function. Suppose there exists a function \(g:B \rightarrow A\) such that \(g \circ f = \id_A\) and \(f \circ g = \id_B\text{.}\)

Function image sets and inverse image sets

In each of Exercises 15–18, consider abstract function \(f: {A}{B}\) and subsets \(A_1, A_2 \subseteq A\text{,}\) \(B_1, B_2 \subseteq B\text{.}\)

Exercise \(\PageIndex{15}\)

1. Draw a Venn diagram illustrating that \(A_1 \subseteq f^{-1}(f(A_1))\text{.}\)

Include all of the sets

\begin{equation*} A, \;\; B, \;\; A_1, \;\; f(A_1), \text{ and } \;\; f^{-1}(f(A_1)) \end{equation*}
in your diagram.

2. Formally prove that \(A_1 \subseteq f^{-1}(f(A_1))\text{,}\) using the Subset Test.
3. Devise an explicit example where \(A_1 \subsetneqq f^{-1}(f(A_1))\text{.}\)

Exercise \(\PageIndex{16}\)

1. Draw a diagram illustrating that \(f(f^{-1}(B_1)) \subseteq B_1\text{.}\)

Include all of the sets

\begin{equation*} A, \;\; B, \;\; B_1, \;\; f^{-1}(B_1), \;\; \text{ and } \;\; f(f^{-1}(B_1)) \end{equation*}
in your diagram.

2. Formally prove that \(f(f^{-1}(B_1)) \subseteq B_1\text{,}\) using the Subset Test.
3. Devise an explicit example where \(f(f^{-1}(B_1)) \subsetneqq B_1\text{.}\)

Exercise \(\PageIndex{17}\)

1. Draw a diagram illustrating that \(f(A_1 \cap A_2) \subseteq f(A_1) \cap f(A_2)\text{.}\)

Include all of the sets

\begin{gather*} A, \;\; B, \;\; A_1, \;\; A_2, \;\; A_1 \cap A_2, \;\; f(A_1), \;\; f(A_2), \\ f(A_1) \cap f(A_2), \;\; \text{ and } \;\; f(A_1 \cap A_2) \end{gather*}
in your diagram.

2. Formally prove that \(f(A_1 \cap A_2) \subseteq f(A_1) \cap f(A_2)\text{,}\) using the Subset Test.
3. Devise an explicit example where \(f(A_1 \cap A_2) \subsetneqq f(A_1) \cap f(A_2)\text{.}\)

Exercise \(\PageIndex{18}\)

1. Draw a 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.

Exercise \(\PageIndex{19}\)

Suppose \(f: A\rightarrow B\) is an injection. Use \(f\) to devise an injection \(F:\mathscr{P}(A) \hookrightarrow \mathscr{P}( B)\text{.}\) Be sure to verify that your proposed function \(F\) is injective. If \(f\) is bijective, will \(F\) also be bijective?