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


\begin{problem}
For any function $f:A \to B$, define a binary relation,
$\relsub{R}{f}$, on $A$ by the condition:
\[
a_1 \relsub{R}{f} a_2 \iff f(a_1) = f(a_2).
\]

\begin{problemparts}

\problempart Show that $\relsub{R}{f}$ is an equivalence relation.

\solution{We first prove $\relsub{R}{f}$ is transitive.
\begin{proof}
Suppose $a_1 \relsub{R}{f}
a_2$ and $a_2 \relsub{R}{f} a_3$.  So $f(a_1) = f(a_2)$ and $f(a_2) =
f(a_3)$.  So $f(a_1) = f(a_3)$ (becuase equality is transitive, a basic
fact we can assume w/o proof).  That is, $a_1 \relsub{R}{f} a_3$.
\end{proof}
The proofs that $\relsub{R}{f}$ is reflexive and symmetric are equally
easy, and we omit them.}

\problempart (*) Show that for \emph{every} equivalence relation, $E$, on $A$,
there is a $B$ and an $f:A\to B$ such that $E = \relsub{R}{f}$.

\solution{Let $B$ be the blocks of the partition of $A$ defined by $E$, that
is,
\[
B \eqdef \set{[a]_{E} \suchthat a \in A}.
\]
Define $f:A\to B$ by the rule
\[
f(a) \eqdef [a]_{E}.
\]
So
\begin{eqnarray*}
a_1 \relsub{R}{f} a_2 & \iff & f(a_1) = f(a_2)\\
& \iff & [a_1]_{E} = [a_2]_{E}\\
& \iff & a_1 \,E\, a_2,
\end{eqnarray*}
which means that $\relsub{R}{f} = E$ as required.}
\end{problemparts}
\end{problem}