Skip to main content
Contents Index
Search Book
Search Results:
No results.
Readability settings Prev Up Next \(\require{cancel}
\newcommand{\nth}[1][n]{{#1}^{\mathrm{th}}}
\newcommand{\bbrac}[1]{\bigl(#1\bigr)}
\newcommand{\Bbrac}[1]{\Bigl(#1\Bigr)}
\newcommand{\correct}{\boldsymbol{\checkmark}}
\newcommand{\incorrect}{\boldsymbol{\times}}
\newcommand{\inv}[2][1]{{#2}^{-{#1}}}
\newcommand{\leftsub}[3][1]{\mathord{{}_{#2\mkern-#1mu}#3}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\I}{\mathbb{I}}
\newcommand{\abs}[1]{\left\lvert #1 \right\rvert}
\DeclareMathOperator{\sqrtop}{sqrt}
\newcommand{\lgcnot}{\neg}
\newcommand{\lgcand}{\wedge}
\newcommand{\lgcor}{\vee}
\newcommand{\lgccond}{\rightarrow}
\newcommand{\lgcbicond}{\leftrightarrow}
\newcommand{\lgcimplies}{\Rightarrow}
\newcommand{\lgcequiv}{\Leftrightarrow}
\newcommand{\lgctrue}{\mathrm{T}}
\newcommand{\lgcfalse}{\mathrm{F}}
\newcommand{\boolnot}[1]{{#1}'}
\newcommand{\boolzero}{\mathbf{0}}
\newcommand{\boolone}{\mathbf{1}}
\newcommand{\setdef}[2]{\left\{\mathrel{}#1\mathrel{}\middle|\mathrel{}#2\mathrel{}\right\}}
\newcommand{\inlinesetdef}[2]{\{\mathrel{}#1\mathrel{}\mid\mathrel{}#2\mathrel{}\}}
\let\emptyword\emptyset
\renewcommand{\emptyset}{\varnothing}
\newcommand{\relcmplmnt}{\smallsetminus}
\newcommand{\union}{\cup}
\newcommand{\intersection}{\cap}
\newcommand{\cmplmnt}[1]{{#1}^{\mathrm{c}}}
\newcommand{\disjunion}{\sqcup}
\newcommand{\cartprod}{\times}
\newcommand{\words}[1]{{#1}^\ast}
\newcommand{\length}[1]{\abs{#1}}
\newcommand{\powsetbare}{\mathcal{P}}
\newcommand{\powset}[1]{\powsetbare(#1)}
\newcommand{\funcdef}[4][\to]{#2\colon #3 #1 #4}
\newcommand{\ifuncto}{\hookrightarrow}
\newcommand{\ifuncdef}[3]{\funcdef[\ifuncto]{#1}{#2}{#3}}
\newcommand{\sfuncto}{\twoheadrightarrow}
\newcommand{\sfuncdef}[3]{\funcdef[\sfuncto]{#1}{#2}{#3}}
\newcommand{\funcgraphbare}{\Delta}
\newcommand{\funcgraph}[1]{\funcgraphbare(#1)}
\newcommand{\nmathrel}[1]{\mathrel{\not #1}}
\newcommand{\relset}[3]{#1_{{} #2 #3}}
\newcommand{\gtset}[2]{\relset{#1}{\gt}{#2}}
\newcommand{\posset}[1]{\gtset{#1}{0}}
\newcommand{\geset}[2]{\relset{#1}{\ge}{#2}}
\newcommand{\nnegset}[1]{\geset{#1}{0}}
\newcommand{\neqset}[2]{\relset{#1}{\neq}{#2}}
\newcommand{\nzeroset}[1]{\neqset{#1}{0}}
\newcommand{\ltset}[2]{\relset{#1}{\lt}{#2}}
\newcommand{\leset}[2]{\relset{#1}{\le}{#2}}
\newcommand{\natnumlt}[1]{\ltset{\N}{#1}}
\DeclareMathOperator{\id}{id}
\newcommand{\inclfunc}[2]{\iota_{#1}^{#2}}
\newcommand{\projfunc}[1]{\rho_{#1}}
\DeclareMathOperator{\proj}{proj}
\newcommand{\funcres}[2]{\left.{#1}\right\rvert_{#2}}
\newcommand{\altfuncres}[2]{\left.{#1}\right\rvert{#2}}
\DeclareMathOperator{\res}{res}
\DeclareMathOperator{\flr}{flr}
\newcommand{\floor}[1]{\lfloor {#1} \rfloor}
\newcommand{\funccomp}{\circ}
\newcommand{\funcinvimg}[2]{\inv{#1}\left({#2}\right)}
\newcommand{\card}[1]{\left\lvert #1 \right\rvert}
\DeclareMathOperator{\cardop}{card}
\DeclareMathOperator{\ncardop}{\#}
\newcommand{\EngAlphabet}{\{ \mathrm{a}, \, \mathrm{b}, \, \mathrm{c}, \, \dotsc, \, \mathrm{y}, \, \mathrm{z} \}}
\newcommand{\ShortEngAlphabet}{\{ \mathrm{a}, \, \mathrm{b}, \, \dotsc, \, \mathrm{z} \}}
\newcommand{\eqclass}[1]{\left[#1\right]}
\newcommand{\partorder}{\preceq}
\newcommand{\partorderstrict}{\prec}
\newcommand{\npartorder}{\npreceq}
\newcommand{\subgraph}{\preceq}
\newcommand{\subgraphset}[1]{\mathcal{S}(#1)}
\newcommand{\connectedsubgraphset}[1]{\mathcal{C}(#1)}
\newcommand{\permcomb}[3]{{#1}(#2,#3)}
\newcommand{\permcombalt}[3]{{#1}^{#2}_{#3}}
\newcommand{\permcombaltalt}[3]{{\leftsub{#2}{#1}}_{#3}}
\newcommand{\permutation}[2]{\permcomb{P}{#1}{#2}}
\newcommand{\permutationalt}[2]{\permcombalt{P}{#1}{#2}}
\newcommand{\permutationaltalt}[2]{{\permcombaltalt{P}{#1}{#2}}}
\newcommand{\combination}[2]{\permcomb{C}{#1}{#2}}
\newcommand{\combinationalt}[2]{\permcombalt{C}{#1}{#2}}
\newcommand{\combinationaltalt}[2]{{\permcombaltalt{C}{#1}{#2}}}
\newcommand{\choosefuncformula}[3]{\frac{#1 !}{#2 ! \, #3 !}}
\DeclareMathOperator{\matrixring}{M}
\newcommand{\uvec}[1]{\mathbf{#1}}
\newcommand{\zerovec}{\uvec{0}}
\newcommand{\lt}{<}
\newcommand{\gt}{>}
\newcommand{\amp}{&}
\definecolor{fillinmathshade}{gray}{0.9}
\newcommand{\fillinmath}[1]{\mathchoice{\colorbox{fillinmathshade}{$\displaystyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\textstyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\scriptstyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\scriptscriptstyle\phantom{\,#1\,}$}}}
\)
Activities 10.6 Activities
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 to 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 (an
algorithm ) of how an output is to be produced from an input.
Activity 10.3 .
For each function defined below:
(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{.}\)
Note that to 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 (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.
(c) Describe specifically how to make
\(f \) bijective by
restricting the codomain .
(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
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 tasks in this activity 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?
