Exercises for self study. Complete these exercises in the textbook and
compare your solutions against those in the back of the book. These exercises
will not be graded.
pp. 608, 609, Exercises 7 and 29
pp. 646, 647, Exercises 9 and 15
Exercises to be graded. Complete these exercises and turn in your
solutions. As usual, ${\bf Z}$ denotes the set of all integers. For a
relation $R$ from a set $A$ to a set $B$, the inverse of $R$ is a
relation from $B$ to $A$ defined by
$R^{-1} = \{ (b, a) \in B \times A : (a, b) \in R \}$, and the
complement of $R$ is a relation from $A$ to $B$ defined by
$\smash{\overline{R}} = \{ (a, b) \in A \times B : (a, b) \not\in R \}$.
Let $R_1$ be a relation on ${\bf Z}$ defined by $(x, y) \in R_1$ if $x$
divides $y$ for $x, y \in {\bf Z}$ and $R_2$ be a relation on
${\bf Z}$ defined by $(x, y) \in R_2$ if $x$ is a multiple of $y$
for $x, y \in {\bf Z}$.
(a) Prove that $R_2 = {R_1}^{\!-1}$.
(b) Is $R_2 = \smash{\overline{R_1}}$? Prove your claim.
(c) Is $R_1$ an equivalence relation? Is $R_2$ an equivalence relation? Prove your
claims.
Let $R$ be an equivalence relation on ${\bf Z}$ defined by $(x, y) \in R$
if $x \equiv y \pmod{5}$ for $x, y \in {\bf Z}$. What are the equivalence classes of $R$?
Formally define each equivalence class as a subset of ${\bf Z}$ using the set-builder
notation $\{ n \in {\bf Z} : \ldots \, \}$. Then, for each such class, list three elements.
Let $R$ be an equivalence relation on a set $S$.
(a) Prove that $R = R^{-1}$.
(b) Is $R = \smash{\overline{R}}$? Prove your claim.
For the set of all positive integers ${\bf Z}^+$, let $R$ be a relation
on ${\bf Z}^+ \times {\bf Z}^+$ defined by $((a, b), (c, d)) \in R$ if
$ad = bc$. Prove that $R$ is an equivalence relation.
Plagiarism and academic dishonesty.
Remember, under any circumstance, you must not copy part or all of another's
work and present it as your own. For more details, read
our course policy on plagiarism and
academic dishonesty.
