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\,}$}}}
\)
Exercises 17.6 Exercises
Directed graph for a relation.
In each of
Exercises 1–4 , you are given a relation on a specific set. Draw a directed graph that represents the relation.
1. Relation
\(\mathord{\subsetneqq} \) on
\(\powset{\{a,b,c\}} \text{.}\)
2. Relation
\(\mathord{\lt} \) on
\(\{1,2,3,4\} \text{.}\)
3. Relation
\(\mathord{\equiv_3} \) on
\(\natnumlt{13} \text{.}\)
4. Relation “has the same number of occurrences of the letter
\(\mathrm{a} \) as” on
\(\words{\Sigma}_4 \) for alphabet
\(\Sigma = \{\mathrm{a}, \mathrm{z}\} \text{.}\)
5. Recall that a relation on a set
\(A \) is just a subset of the Cartesian product
\(A \cartprod A \text{.}\) Write out all relations on the set
\(A = \{a,b\} \) as subsets of
\(A \cartprod A \text{.}\) Which of these relations are reflexive? Symmetric? Antisymmetric? Transitive?
Testing reflexivity/symmetry/antisymmetry/transitivity.
6. Relation
\(\mathord{\lt} \) on
\(\R \text{.}\)
7. Relation
\(\mathord{\ge} \) on
\(\R \text{.}\)
8. Relation
\(\mathord{\mid} \) on
\(\Z \text{.}\)
9. Relation
\(\mathord{\subseteq} \) on
\(\powset{X} \text{,}\) where
\(X \) is an arbitrary, unspecified set.
10. Relation “is taller than” on the set of all living humans.
11. Relation “is parallel to” on the set of all straight lines in the plane.
12. Relation “is perpendicular to” on the set of all straight lines in the plane.
13. Relation “has the same length as” on
\(\words{\Sigma} \text{,}\) where
\(\Sigma \) is an arbitrary, unspecified alphabet set.
14. Relation “is shorter than” on
\(\words{\Sigma} \text{,}\) where
\(\Sigma \) is an arbitrary, unspecified alphabet set.
15. Relation “contains the same number of occurrences of the letter
\(x \) as” on
\(\words{\Sigma} \text{,}\) where
\(\Sigma \) is an arbitrary, unspecified alphabet set and
\(x \) is some fixed choice of letter in
\(\Sigma \text{.}\)
16. Relation
\(\mathord{\lgcequiv} \) on the set of all logical statements involving the statement variables
\(p_1,p_2,p_3,\dotsc \text{.}\)
17. Relation
\(R \) defined by “
\(a_1 \mathrel{R} a_2 \) if
\(f(a_1) = f(a_2) \) ” on a set
\(A \text{,}\) where
\(\funcdef{f}{A}{B} \) is an arbitrary, unspecified function.
Properties of relations reflected in their graphs.
In each of
Exercises 18–19 , you are given a list of properties. Draw the directed graph of a relation on the set
\(\{a,b,c,d\} \) that possesses the given properties.
18. Symmetric and transitive, but neither reflexive nor antisymmetric.
19. Reflexive, antisymmetric, and transitive, but not symmetric.
20. Prove that a relation is symmetric if and only if it is equivalent to its own inverse relation.
21.
\begin{equation*}
(\forall a_1 \in A)(\forall a_2 \in A)({a_1 \neq a_2} \lgcimplies {{a_1 \nmathrel{R} a_2} \lgcor {a_2 \nmathrel{R} a_1}}) \text{.}
\end{equation*}
Prove that each of the two conditionals provided in the
Antisymmetric Relation Test are equivalent to the symbolic formulation of the definition of antisymmetric given above.
22. Suppose
\(R \) is a relation on a set
\(A \) that is both symmetric and antisymmetric. Prove that
\(R \) is a subset of the identity relation
\(\setdef{(x,x)}{x \in A} \text{.}\)
