\problemdata
{relations}
{transitive closures}
{symmetric relations}

\begin{problem}
% 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$.  Then $(b, a) \in R$ as well.  So, both 
$(a, b)$ and $(b, a)$ are in $S$ as $R \subseteq S$ by definition of
closure.  Likewise, $(b, a)$ and $(a, b)$ are also in $S^{-1}$ by the 
defintion of inverse.  Thus, $R \subseteq S^{-1}$.
\newline
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.
\newline
We know that the cardinality of $S$ and its inverse are both the same.  
Since $S$ was the transitive closure of $R$, it is the smallest set
such that $R \subseteq S$ and $S$ is transitive.  Since $S^{-1}$ has
the same cardinality as $S$, $R \subseteq S^{-1}$, and $S^{-1}$ 
is a transitive superset of (or equal to) $R$; $S^{-1}$ is also a
transitive closure of $R$.  But the transitive closure of $R$ is unique.
So, $S = S^{-1}$.
\newline
Therefore, since $S$ is the same set as its inverse, $S$ is symmetric.  
$QED$. 
\end{proof}
}
\end{problem}

