        \problemdata       % Takes 5 *mandatory* arguments
        {which-equiv}             % latex-friendly label for the prob.
        {relations}  % The topic(s) of the problem content.
        {Velleman 4.6, Exercise 3}               % Source (if known)
        {F01 PS3-1, F00 PS3} % Usage (list ones you are aware of).
        {}        % Last revision info (author, date).

%-----------------------------------------------------------------%
% source: Velleman 4.6, Exercise 3.
% topic: equivalence relations
% last used Fall00 Problem Set 3 (in ProblemRepository)

\begin{problem}
Which of the following relations are equivalence relations?  For those
that are equivalence relations, what are the equivalence classes? For
those that are not, give an example of how they fail.

\begin{problemparts}
\problempart
$R \eqdef \set{(x,y) \in W \times W \suchthat \text{ the words $x$ and
$y$ start with the same letter} }$ where $W$ is the set of all words
in the 2001 edition of the Oxford English dictionary.

\solution{
$R$ is an equivalence relation since it is reflexive, symmetric, and
transitive.  The equivalence class of $x$ with respect to $R$ is the
set $[x]_R = $ the set of words $y$, such that $y$ has the same first
letter as $x$. There are 26 equivalence classes, one for each letter
of the English alphabet.
}

\problempart
$S \eqdef \set{(x,y) \in W \times W \suchthat \text{ the words $x$ and $y$
have at least one letter in common} }$.

\solution{
$S$ is reflexive and symmetric, but it is not transitive.  Therefore, $S$
is not an equivalence relation.  For example, let $w_1$ be the word
``scream,'' let $w_2$ be the word ``and,'' and let $w_3$ be the word
``shout.''  Then $w_3 S w_1$, and $w_1 S w_2$, but it is \textbf{not} the
case that $w_3 S w_2$.}

\problempart
$R \eqdef \set{(x,y) \in \reals \times \reals \suchthat x-y \in \rationals }$.

\solution{
$R$ is reflexive since, for any $x\in R$, $x-x=0$.  $R$ is symmetric
because if $(x-y)$ is rational, then $(y-x)=-(x-y)$ is rational as well.
Finally, $R$ is also transitive.  To see this, consider $(x,y)\in R$ and
$(y,z)\in R$.  We would like to know if $(x,z)$ is also in $R$.  We start
by noting that $(x-y)\in \rationals$ and $(y-z)\in \rationals$ by
definition of our relation $R$.  Now, we can express $(x-z) =
(x-y)+(y-z)$.  Since the sum of any two rational numbers is another
rational number, and we have written $(x-z)$ as such, we have shown that
$(x,z)\in \rationals$.  Therefore, $R$ is transitive.  Since $R$ is also
reflexive and symmetric, $R$ is an equivalence relations on $\reals$.

The equivalence class for x is
\[
[x]_R = \set{x + r \suchthat r \in \rationals}.
\]
}

\problempart
$R \eqdef \set{(x,y) \in \reals \times \reals \suchthat \exists n \in
\integers\; y=10^{n} x}$.

\solution{
$R$ is reflexive, since we can set $n=0$.  $R$ is symmetric because if
$y=10^k x$, for some $k\in \integers$, then $x=10^{-k}y$, so if
$(x,y)\in R$, then $(y,x)\in R$.  We can show that $R$ is transitive
as follows: consider pairs $(x,y)\in R$ and $(y,z)\in R$.  So $y=10^nx$
and $z=10^m y$, for $m,n\in \integers$.  Then, substituting, we have
that $z=10^{m}(10^{n} x) = 10^{m+n}x$.  Since $m+n \in \ints$, we conclude
that $(x,z) \in R$.

The equivalence class for x is 
\[
[x]_R = \set{10^{n}x \suchthat n\in \integers}.
\]
There is a distinct equivalence class for every real number in the
intervals $(-10,-1] \union \{0\} \union [1, 10)$.
}

\end{problemparts}

\end{problem}