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.
Exercises 10.7 Exercises
2.
Let \(A \) represent the set of all university students and let \(C \) be the set of all university courses. Does the rule \(\funcdef{f}{A}{C} \) given by
\begin{equation*}
f(a) = c \text{ if student } a \text{ is registered in course } c
\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
-
codomain, and
3.
\(\Lambda = \{\lgctrue, \, \lgcfalse\} \text{,}\) \(\funcdef{n}{\Lambda}{\Lambda} \) is the logical negation function \(n(p) = \lgcnot p \text{.}\)
4.
\(\mathscr{L} \) represents the set of all possible logical statements, \(\funcdef{N}{\mathscr{L}}{\mathscr{L}} \) is the logical negation function \(N(A) = \lgcnot A \) for \(A \) a logical statement.
(Note: You may treat equivalent statements as being the same statement.)
5.
\(\funcdef{\mathscr{N}}{\Z}{\Z} \) is the numerical negation function \(\mathscr{N}(n) = -n \text{.}\)
6.
\(\Sigma = \{0,1\} \text{,}\) \(\words{\Sigma} \) represents the set of all binary words, \(\funcdef{c}{\words{\Sigma}}{\words{\Sigma}} \) 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{.}\)
7.
\(U \) represents a universal set, \(\funcdef{C}{\powset{U}}{\powset{U}} \) is the complement function \(C(A) = \cmplmnt{A} \text{,}\) for \(A \subseteq U \text{.}\)
8.
Let \(E \subseteq \Z \) represent the set of even integers, and consider the function \(\funcdef{f}{\Z}{E} \text{,}\) \(f(n) = 2n \text{.}\)
(a)
Prove that \(f \) is a bijection.
(b)
Describe the inverse function \(\funcdef{\inv{f}}{E}{\Z} \text{.}\) That is, describe the rule to determine \(\inv{f}(n) \text{,}\) given even number \(n \text{.}\)
9.
As usual, \(\R^m = \R \cartprod \R \cartprod \dotsb \cartprod \R \) represents the Cartesian product of \(m \) copies of \(\R \text{,}\) where \(m \) is a positive integer. Consider the diagonal embedding \(\funcdef{D}{\R}{\R^m} \) defined by \(D(x) = (x,x,\dotsc,x) \text{.}\)
Aside: Generalize.
(a)
(b)
Fill in the right-hand side of the set definition in Candidate-condition notation for the image of \(D \) below.
\begin{equation*}
D(\R)
= \setdef{(x_1,x_2,\dotsc,x_m) \in \R^m}{\fillinmath{XXXXXXXXXX}}
\end{equation*}
(c)
Provide a set definition for the graph \(\funcgraph{D} \) in Form-parameter notation. Of what set is \(\funcgraph{D} \) a subset?
(d)
Can you come up with other “natural” embeddings \(\R \ifuncto \R^m \text{?}\)
10.
Let \(A = \{0,1,2,3,4,5,6,7,8,9\} \) and let \(P \subseteq \powset{A} \) represent the set of all subsets of \(A \) which contain an odd number of elements. Define \(\funcdef{\nu}{P}{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?
11.
Let \(\Sigma = \{0,1\} \text{.}\) Recall that for \(n \in \N \text{,}\) \(\words{\Sigma}_n \) is the subset of \(\words{\Sigma} \) consisting of all binary words of 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{.}\)
12.
Call a function with domain \(\emptyset \) an empty function.
(a)
What must the graph of an empty function be? Does this graph satisfy the formal definition of function?
(b)
Use your analysis in Task a to prove that for every set \(B \) there exists a unique function \(\emptyset \to B \text{.}\)
(c)
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.
(d)
Verify that an empty function with empty codomain is bijective.
Hint.
You have already verified injectivity of an empty function more generally in Task c. 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.
13.
Let \(\funcdef{f}{A}{B} \) and \(\funcdef{g}{B}{C} \) be functions.
(a)
Prove that if \(f \) and \(g \) are both surjective, then \(g \funccomp f \) is surjective.
(b)
If \(g \funccomp f \) is surjective, must either or both of \(f,g \) necessarily be surjective? Justify your answers.
(c)
Prove that if \(f \) and \(g \) are both injective, then \(g \funccomp f \) is injective.
(d)
If \(g \funccomp f \) is injective, must either or both of \(f,g \) necessarily be injective? Justify your answers.
(e)
Task a and Task c together prove that if \(f \) and \(g \) are both bijective, then \(g \funccomp f \) is bijective.
Prove that \(\inv{(g \funccomp f)} = \inv{f} \funccomp \inv{g} \text{.}\) (See the definition of equality of functions.)
14.
Let \(\funcdef{f}{A}{B} \) be a function. Suppose there exists a function \(\funcdef{g}{B}{A} \) such that \(g \funccomp f = \id_A \) and \(f \funccomp g = \id_B \text{.}\)
(a)
Prove that \(f \) is a bijection.
(b)
Prove that \(g = \inv{f} \text{.}\)
Function image sets and inverse image sets.
In each of Exercises 15–18, consider abstract function \(\funcdef{f}{A}{B} \) and subsets \(A_1, A_2 \subseteq A \text{,}\) \(B_1, B_2 \subseteq B \text{.}\)
15.
(a)
Draw a Venn diagram illustrating that \(A_1 \subseteq \inv{f}\bbrac{f(A_1)} \text{.}\)
Include all of the sets
\begin{equation*}
A, \;\; B, \;\; A_1, \;\; f(A_1), \text{ and } \;\; \inv{f}\bbrac{f(A_1)}
\end{equation*}
in your diagram.
(b)
Formally prove that \(A_1 \subseteq \inv{f}\bbrac{f(A_1)} \text{,}\) using the Subset Test.
(c)
Devise an explicit example where \(A_1 \subsetneqq \inv{f}\bbrac{f(A_1)} \text{.}\)
16.
(a)
Draw a diagram illustrating that \(f\bbrac{\inv{f}(B_1)} \subseteq B_1 \text{.}\)
Include all of the sets
\begin{equation*}
A, \;\; B, \;\; B_1, \;\; \inv{f}(B_1),
\;\; \text{ and } \;\; f\bbrac{\inv{f}(B_1)}
\end{equation*}
in your diagram.
(b)
Formally prove that \(f\bbrac{\inv{f}(B_1)} \subseteq B_1 \text{,}\) using the Subset Test.
(c)
Devise an explicit example where \(f\bbrac{\inv{f}(B_1)} \subsetneqq B_1 \text{.}\)
17.
(a)
Draw a diagram illustrating that \(f(A_1 \intersection A_2) \subseteq f(A_1) \intersection f(A_2) \text{.}\)
Include all of the sets
\begin{gather*}
A, \;\; B, \;\; A_1, \;\; A_2, \;\; A_1 \intersection A_2, \;\; f(A_1), \;\; f(A_2), \\
f(A_1) \intersection f(A_2), \;\; \text{ and } \;\; f(A_1 \intersection A_2)
\end{gather*}
in your diagram.
(b)
Formally prove that \(f(A_1 \intersection A_2) \subseteq f(A_1) \intersection f(A_2) \text{,}\) using the Subset Test.
(c)
Devise an explicit example where \(f(A_1 \intersection A_2) \subsetneqq f(A_1) \intersection f(A_2) \text{.}\)
18.
(a)
Draw a 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 \funcinvimg{f}{B_2} \text{,}\) using the Test for Set Equality.
19.
Suppose \(\funcdef{f}{A}{B} \) is an injection. Use \(f \) to devise an injection \(\ifuncdef{F}{\powset{A}}{\powset{B}} \text{.}\) Be sure to verify that your proposed function \(F \) is injective. If \(f \) is bijective, will \(F \) also be bijective?
