\problemdata     
{relations-2}           
{relational properties}              
{}              
{S02 ps3} 		
{Radhika, S02}        	

\begin{problem} 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$.

\textbf{Claim 1:} Every symmetric, weakly transitive relation is transitive.

\textbf{Claim 2:} Every reflexive, symmetric, weakly transitive relation
is an equivalence relation.

One of the claims above is true, and one is false. Which is which? Prove it.

\solution{

Claim 1 is false. 

Here is a simple counterexample. Let $A = \{1,2,3,4\}$ $R = \{(1,2) (1,4)
(2,1) (2,3) (3,2) (3,4) (4,1) (4,3)\}$. $R$ is weakly transitive but not transitive ---
$(1,2)$ and $(2,3)$ are in $R$ but $(1,3)$ is not in $R$.

Claim 2 is true.

\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 transtive, the relations $aRa$, $aRb$, and $bRc$ imply the
relation $aRc$.  Therefore, $R$ is transitive.
\end{proof}
}
\end{problem}
