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


\begin{problem}
%-----------------------------------------------------------------%
% From Problem Repository (Rad)
% topic: relations, transitive closures, symmetric relations
% source: Velleman 4.5.10

Suppose $R$ is a relation on $A$, and let $S$ be the
transitive closure of $R$.  Prove that if $R$ is symmetric, then so is
$S$.  (Hint: Assume that $R$ is symmetric.  Prove that $R \subseteq
S^{-1}$ and $S^{-1}$ is transitive.  What can you conclude about $S$
and $S^{-1}$?)

\solution{
\begin{proof}
Assume that $R$ is symmetric.  We can prove that
$R \subseteq S^{-1}$.  Suppose arbitrary $(a, b) \in R$.  Because R is
symmetric, $(b, a) \in R$ as well.  $R \subseteq S$ by definition of
closure, therefore both $(a, b)$ and $(b, a)$ must be in $S$. However
by definition of inverse, $(b, a)$ and $(a, b)$ are also in $S^{-1}$.
Thus, $R \subseteq S^{-1}$.

We must now prove that $S^{-1}$ is transitive.  Suppose we choose an 
arbitrary three elements $a \in A$, $b \in A$, and $c \in A$ such that
$((a, b) \in S^{-1} \; \land (b, c) \in S^{-1})$.  This means that 
$(b, a) \in S \; \land (c, b) \in S$ by definition of inverse.  But 
since $S$ is transitive this means $(c, a) \in S$.  Thus, by definition
of inverse $(a, c) \in S^{-1}$.  This is the necessary condition to 
satisfy transitivity.  Thus, $S^{-1}$ is transitive.

Since $S$ was the transitive closure of $R$, it is the smallest set
such that $R \subseteq S$ and $S$ is transitive (definition of
transitive closure). Since $R \subseteq S^{-1}$ and $S^{-1}$ is a
transitive, $S^{-1}$ contains the transitive closure $S$ of $R$. So $S
\subseteq S^{-1}$. We also know that $|S| = |S^{-1}|$ by definition of
inverse, so in fact $S = S^{-1}$.  Therefore, since $S$ is the same
set as its inverse, $S$ is symmetric.
\end{proof}
} % end solution

\end{problem}