Skip to main content
Contents Index Dark Mode Prev Up Next \(\newcommand{\im}{{\mathrm{im}}}
\newcommand{\given}{{\, :\,}}
\newcommand{\hanoi}{\mathrm{hanoi}}
\newcommand{\lcm}{{\mathrm{lcm}}}
\newcommand{\ID}{{\mathrm{ID}}}
\newcommand{\chr}{{\mathtt{chr}}}
\newcommand{\ord}{{\mathtt{ord}}}
\newcommand{\set}[1]{\left\lbrace #1 \right\rbrace}
\newcommand{\seq}[2]{( #1 )_{#2}}
\newcommand{\gr}[1]{\left( #1 \right)}
\newcommand{\abs}[1]{\left| #1 \right|}
\newcommand{\size}[1]{\# #1}
\newcommand{\id}[1]{\mathrm{id}_{#1}}
\newcommand{\ip}[1]{\left\langle #1 \right\rangle}
\newcommand{\floor}[1]{\left\lfloor #1\right\rfloor}
\newcommand{\ceiling}[1]{\left\lceil #1\right\rceil}
\newcommand{\indemph}[1]{{\textbf{\emph{#1}}\index{#1}}}
\renewcommand{\implies}{\to}
\renewcommand{\iff}{\leftrightarrow}
\newcommand{\lxor}{\oplus}
\newcommand{\cP}{\wp}
\newcommand{\pset}{\cP}
\newcommand{\ZZ}{\mathbb{Z}}
\newcommand{\QQ}{\mathbb{Q}}
\newcommand{\NN}{\mathbb{N}}
\newcommand{\CC}{\mathbb{C}}
\newcommand{\RR}{\mathbb{R}}
\newcommand{\barr}[1]{\overline{#1}}
\newcommand{\sage}{\textsc{Sage}}
\newcommand{\magma}{\textsc{Magma}}
\newcommand{\bob}{\text{Bob}}
\newcommand{\true}{\text{T}}
\newcommand{\false}{\text{F}}
\newcommand{\ahat}{\hat{a}}
\newcommand{\ah}{\ahat}
\newcommand{\bhat}{\hat{b}}
\newcommand{\abar}{\bar{a}}
\newcommand{\cA}{\mathcal{A}}
\newcommand{\cF}{\mathcal{F}}
\newcommand{\cW}{\mathcal{W}}
\newcommand{\todo}[1]{{\color{red} TODO: #1}}
\renewcommand{\div}{\operatorname{div}}
\newcommand{\gexp}[3]{#1^{#2 #3}}
\newcommand{\gexpp}[3]{\displaystyle\left(#1\right)^{#2 #3}}
\newcommand{\glog}[3]{\log_{#1}^{#3}#2}
\def\dbend{{!!!}}
\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 6.1.4 Exercises
1.
Give the definition for these terms. Be sure to set up any notation that is required.
binary relation from one set to another
2.
Consider the relation \(R = \{(a,b) \given a \text{~divides~} b\}\) on the set \(\{1,2,3,4\}\text{.}\)
List all of the ordered pairs in
\(R\text{.}\)
Is
\(R\) reflexive ? Explain.
Is
\(R\) symmetric ? Explain.
Is
\(R\) antisymmetric ? Explain.
Is
\(R\) transitive ? Explain.
3.
Which of these relations on the set of all people are reflexive ? Which are symmetric ? Which are antisymmetric ? Which are transitive ? Justify.
\(\displaystyle \{(a,b) \given a \text{ and } b \text{ are the same height}\}\)
\(\displaystyle \{(a,b) \given a \text{ and } b \text{ live in the same state}\}\)
\(\displaystyle \{(a,b) \given a \text{ and } b \text{ have met}\}\)
\(\displaystyle \{(a,b) \given a \text{ and } b \text{ are blood relatives
}\}\)
\(\displaystyle \{(a,b) \given a \text{ and } b \text{ speak a common language}\}\)
4.
Which of these relations on \(\{1,2,3,4\}\) are reflexive ? Which are symmetric ? Which are antisymmetric ? Which are transitive ? Justify.
\(\displaystyle \{(1,1),(2,2),(3,3),(4,4)\}\)
\(\displaystyle \{(1,2),(2,1),(1,3),(3,1),(1,4),(4,1)\}\)
\(\displaystyle \{(1,1),(2,2),(1,2),(2,1),(3,3),(4,4)\}\)
\(\displaystyle \{(1,1),(2,2),(1,2),(2,1),(1,3),(3,1),(3,3),(4,4)\}\)
5.
Consider the following relations \(R\) on the set of real numbers. For each of these relations, determine whether or not it is reflexive, symmetric, antisymmetric, and/or transitive. Justify.
\((x,y) \in R\) if and only if
\(x + y = 0\)
\((x,y) \in R\) if and only if
\(x - y \in \ZZ\)
\((x,y) \in R\) if and only if
\(x = 253\)
\((x,y) \in R\) if and only if
\(xy = 0\)
\((x,y) \in R\) if and only if
\(x = 1\) or
\(y = 1\)
6.
Let \(A = \{0,1,2,3,4\}\text{,}\) and let \(B = \{0,1,2,3\}\text{.}\) Consider the following relations from \(A\) to \(B\text{.}\) For each of these relations, list the ordered pairs in the relation.
\((a, b) \in R\) if and only if
\(a = b\)
\((a, b) \in R\) if and only if
\(a \gt b\)
\((a, b) \in R\) if and only if
\(\gcd(a,b)= 1\)
\((a, b) \in R\) if and only if
\(\lcm(a,b)= 2\)
\((a, b) \in R\) if and only if
\(a \mid b\)
\((a, b) \in R\) if and only if
\(a + b = 4\)
7.
Let \(R\) and \(S\) be the relations
\begin{align*}
R \amp = \{(1,2),(2,3),(3,4)\} \\
S \amp = \{(1,1),(1,2),(2,1),(2,3),(3,1),(3,4)\}
\end{align*}
Compute the following relations.
\(\displaystyle R \cup S\)
\(\displaystyle R \cap S\)
8.
Let \(R\) and \(S\) be relations on \(\{1,2,3,4\}\) defined by
\begin{align*}
R \amp = \{(2,2),(2, 3), (3,4), (4,4)\} \\
S \amp =\{(1,2),(2,1),(2,4),(3,1),(3,4)\}.
\end{align*}
Compute the following relations.
\(\displaystyle R \circ R\)
\(\displaystyle R \circ S\)
\(\displaystyle R \circ R\)
\(\displaystyle S \circ S\)
9. Let
\(P\) be the relation on the set of people consisting of pairs
\((a,b)\text{,}\) where
\(a\) is a parent of
\(b\text{.}\) Let
\(S\) be the relation consisting of pairs
\((a,b)\text{,}\) where
\(a\) and
\(b\) are siblings (brothers or sisters). Describe the composition relations
\(P \circ S\) and
\(S \circ P\text{.}\)
10.
Let \(B\) be the relation on the set of states in the US consisting of pairs \((a,b)\) where \(a\) shares a land border with \(b\text{.}\)
Give three examples of elements in
\(B\text{.}\)
Give three examples of elements not in
\(B\text{.}\)
11.
Give an example of a relation on a set that is
reflexive, but not symmetric.
symmetric, but not reflexive.
reflexive and symmetric, but not transitive.
