\problemdata
{S00 ps3}
{weakly transitive}

\begin{problem}
% topic: relations, special definition ``weakly transitive''
% source: fall98 pset3 Problem 2

A relation $R$ on a set $A$ is {\em weakly
transitive} if for all $a, b, c, d \in A$, the relations $aRb$, $bRc$,
and $cRd$ imply the relation $aRd$.

Prove or disprove the following statements.

\begin{problemparts}

\problempart Every symmetric, weakly transitive relation is transitive.

\solution{
The claim is false.  The diagram below shows a counterexample.

\begin{figure}[htbp]
\centerline{\resizebox{!}{1.0in}{\includegraphics{figures/ps3-relation-cx.eps}}}
\end{figure}
}


\problempart Every reflexive, symmetric, weakly transitive relation
is an equivalence relation.

\solution{
\begin{proof}
The relation $R$ is an equivalence relation if it is reflexive,
symmetric, and transitive.  The first two properties hold by
assumption; all that remains is to show that $R$ is a transitive
relation.  Suppose that the relations $aRb$ and $bRc$ hold.  Because
$R$ is reflexive, the relation $aRa$ also holds.  Because $R$ is
weakly transitive, the relations $aRa$, $aRb$, and $bRc$ imply the
relation $aRc$.  Therefore, $R$ is transitive.
\end{proof}
}


\end{problemparts}
\end{problem}
