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


\begin{problem}
%-----------------------------------------------------------------%
% Problem Repository, only used two parts (Rad)
% source: spring00 ps3, Velleman 4.3.9 
% topic: relations, compositions, reflexive, symmetric, transitive

Suppose $R$ and $S$ are binary relations on a set $A$.  For each part,
give either proofs or counterexamples to justify your answers.

\begin{problemparts}

\problempart Suppose $R$ and $S$ are symmetric.  Must $R \intersect S$
be symmetric?  What about $R \union S$?  What about $R^{-1}$?  What
about $R \composition S$?

\solution{
$R \intersect S$: \textbf{Yes.} If $(x, y) \in R \intersect S$, we must
prove that $(y, x) \in R \intersect S$.  We have that $xRy$ (in which case
$yRx$ as well) and $xSy$ (in which case $ySx$ as well).  Since $yRx \land
ySx$, we have $(y, x) \in R \intersect S$.

$R \union S$: \textbf{Yes.} Suppose $(x, y) \in R \union S$.  Therefore,
either $xRy$ (in which case $yRx$ and $\therefore (y, x) \in R \union S$)
or $xSy$ (in which case $ySx$ and $\therefore (y, x) \in R \union S$).  So
by cases $(y, x) \in R \union S$.

$R^{-1}$: \textbf{Yes.} Suppose $(x, y) \in R^{-1}$.  By the definition of
inverse, this means that $yRx$.  But since $R$ is symmetric, this means
that $xRy$.  By the definition of inverse again, this means that $(y, x)
\in R^{-1}$.  So $R^{-1}$ is symmetric.

$R \composition S$: \textbf{No.}  Suppose $A = \{a,b,c\}$, $R = \{(b, c),
(c, b)\}$ , and $S = \{(a, b), (b, a)\}$ .  Then $R \composition S = \{(a,
c)\}$, which is not symmetric.

} %end solution

\problempart Suppose $R$ and $S$ are transitive.  Must $R \intersect
S$ be transitive?  What about $R \union S$?  What about $R^{-1}$?
What about $R \composition S$?

\solution{
$R \intersect S$: \textbf{Yes.} Suppose there is 
a walk from $x$ to $y$ in $R \intersect S$.  We need to prove $(x,y) \in
R \intersect S$.  In order for there to
be a walk from $x$ to $y$ in $R \intersect S$, there must have been a walk 
from $x$ to $y$ 
in both of $R$ and $S$ (otherwise, those walks would not appear in their 
intersection as walks).  Thus, $xRy$ and $xSy$, so $(x, y) \in R 
\intersect S$ as needed.

$R \union S$: \textbf{No.} Suppose $R = \{(a, b), (b, c), (a, c)\}$ and 
$S = \{(b, c), (c, a), (b, a)\}$.  Then $U = R \union S = \{(a, b), (b, a), 
(b, c), (c, a), (a, c)\}$, so that $cUa$ and $aUb$ but $\neg (cUb)$.

$R^{-1}$: \textbf{Yes.} Suppose $(a, b) \in R^{-1} \land 
(b, c) \in R^{-1}$.  We must prove that $(a, c) \in R^{-1}$.  
We know from the definition of inverse that
$bRa \land cRb$.  Furthermore, since $R$ is transitive, we have that $cRa$.  
By the definition of inverse again we have that $(a, c) \in 
R^{-1}$, as needed.

$R \composition S$: \textbf{No.} Suppose $R = \{(b, a), (b, c), (c, a)\}$ and 
$S = \{(a, b), (a, c), (b, c)\}$.  Then $(b, a) \in R \composition S$ and 
$(a, c) \in R \composition S$ but $(b, c) \notin R \composition S$.  
Transitivity fails for the composition. 

} % end{solution}
\end{problemparts}

\end{problem}