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 17.5 Activities
Activity 17.1 .
In each of the following, describe the requested combination of relations in words. (That is, in the form “a is related to b if …”.) Try to “simplify” your description, if possible.
In
Task h and
Task i , the symbol
\(\mathord{\equiv}_k \) represents a relation on
\(\Z \text{,}\) where
\(m \equiv_k n \) means that
\(m \) and
\(n \) have the same remainder when divided by
\(k \text{.}\) (It may help to know that this is equivalent to
\(k \) dividing the difference
\(m - n \text{.}\) )
(a)
\(\mathord{\lt} \cup \mathord{\gt} \) on
\(\R \text{.}\)
(b) Union of “longer than” and “shorter than” on
\(\words{\Sigma} \) for some alphabet
\(\Sigma \text{.}\)
(c) Union of “longer than”, “shorter than”, and “same length as” on
\(\words{\Sigma} \) for some alphabet
\(\Sigma \text{.}\)
(d) Intersection of “longer than” and “shorter than” on
\(\words{\Sigma} \) for some alphabet
\(\Sigma \text{.}\)
(e) The complement of
\(\mathord{\le} \) on
\(\R \text{.}\)
(f) The inverse of
\(\mathord{\le} \) on
\(\R \text{.}\)
(g) The inverse of “
\(x \mathrel{R} y \) if
\(2 x + 3 y = 0 \) ” on
\(\R \text{.}\)
(h) The intersection of
\(\mathord{\equiv_5} \) and
\(\mathord{\equiv_7} \) on
\(\Z \text{.}\)
(i) The intersection of
\(\mathord{\equiv_2} \) and
\(\mathord{\equiv_4} \) on
\(\Z \text{.}\)
Activity 17.2 .
(a)
\(A = \R \text{,}\) \(R \) is
\(\mathord{\lt} \text{.}\)
(b)
\(A \) is the set of all straight lines in the plane,
\(R \) means “is parallel to.”
(c)
\(A \) is the set of all straight lines in the plane,
\(R \) means “is perpendicular to.”
(d)
\(A = \words{\Sigma} \) for some alphabet
\(\Sigma \text{,}\) \(R \) means “is the same length as.”
(e)
\(A = \words{\Sigma} \) for some alphabet
\(\Sigma \text{,}\) \(R \) means “is shorter than.”
(f)
\(A = \words{\Sigma} \) for some alphabet
\(\Sigma \text{,}\) \(x \) is some fixed choice of letter in
\(\Sigma \text{,}\) \(R \) means “contains the same number of occurrences of
\(x \) as.”
(g) (h)
Activity 17.3 .
(a) Suppose
\(R \) is a relation on a set
\(A \text{.}\) Convince yourself that
\(R \union \inv{R} \) is symmetric. (See the
Symmetric Relation Test .)
(b) Recall that
\(\mathord{\mid} \) represents the relation “divides” on sets of integers. Draw the directed graph for
\(\mathord{\mid} \) on the set
\(A = \{2,4,6,8,10,12,14,16\} \text{.}\) Then describe how to obtain the graph for the symmetric relation
\(\mathord{\mid} \cup \inv{\mathord{\mid}} \) as an undirected graph from the graph of
\(R \) using only an eraser.
Activity 17.4 .
Assume that \(R \) and \(S \) are nonempty relations on a set \(A \) that both have the property. For each of \(\cmplmnt{R} \text{,}\) \(R \union S \text{,}\) \(R \intersection S \text{,}\) and \(\inv{R} \text{,}\) determine whether the new relation
must also have that property;
might have that property, but might not; or
cannot have that property.
Any time you answer
Statement i or
Statement iii , outline a proof. Any time you answer
Statement ii , provide two examples: one where the new relation has the property, and one where the new relation does not. (You may use graphs to describe your examples.)
