\problemdata
{Velleman}
{relations}
{S00 ps3}

\begin{problem} 
% topic: relations, compositions, reflexive, symmetric, transitive
% source: Velleman 4.3.9

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 reflexive. Must $R \intersect S$ be reflexive?  What
about $R \union S$?  What about $R^{-1}$?  What about $R \composition S$?

\solution{
\newline
$R \intersect S$: \textbf{Yes.} $\forall a \in R \; (a, a) \land \forall a \in
S \; (a, a)$.  Therefore, $R \intersect S$ contains $(a, a)$ for every 
$a \in A$.
\newline
$R \union S$: \textbf{Yes.} Their intersection contained $(a, a) \forall a \in
A$, so their union does too.
\newline
$R^{-1}$: \textbf{Yes.} For every $(a, a) \in R$, it holds that $(a, a) 
\in R^{-1}$ by the definition of inverse.  Thus, since $\forall a \in A 
(a, a) \in R$, it holds that $\forall a \in A (a, a) \in R^{-1}$, so the 
inverse is reflexive.
\newline
$R \composition S$: \textbf{Yes.} It holds that $\forall a \in A ((a, a) \in
S \land (a, a) \in R)$.  Thus, $\forall a \in A \; \exists b \in A \;
((a, b) \in S \land (b, a) \in R)$, so that $\forall a \in A \; ((a, a) \in 
R \composition S)$ by the definition of composition.
}

\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{
\newline
$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$.
\newline
$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$.
\newline
$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.
\newline
$R \composition S$: \textbf{No.}  Suppose $A = \naturals$, 
$R = \{(b, c), (c, b)\}$ 
, and 
$S = \{(a, b), (b, a)\}$
.  Then $R \composition S = \{(a, c)\}$, which is not symmetric.
}

\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{
\newline
$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.
\newline
$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)$.
\newline
$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.
\newline
$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. 
}

\problempart
% topic: equivalence relations, intersection, union, composition
% source: Velleman 4.6.9

Suppose $R$ and $S$ are equivalence relations.  Must $R \intersect S$ 
be an equivalence relation on $A$?  What about $R \union S$?  What about 
$R \composition S$?

\solution{
\newline
$R \intersect S$: \textbf{Yes.}  Here we are supposing $R$ and $S$ are 
reflexive, symmetric, and transitive.  Since we showed above that these 
properties hold over intersection, $R \intersect S$ is reflexive, symmetric,
transitive, and therefore an equivalence relation as well.
\newline
$R \union S$: \textbf{No.}  Suppose $R = \{(a, a), (b, b), (c, c), (a, b),
(b, a)\}$ and 
$S = \{(a, a), (b, b), (c, c), (b, c), (c, b)\}$.  Then $(c, b) \in R \union 
S$ and $(b, a) \in R \union S$ but $(c, a) \notin R \union S$.  Transitivity
fails and $R \union S$ is not an equivalence relation.
\newline
$R \composition S$: \textbf{No.}  Suppose $R$ and $S$ are as in the above 
counterexample.  Then $(a, b) \in R \composition S$ and $(b, c) \in R
\composition S$ but $(a, c) \notin R \composition S$.  Transitivity fails
and $R \composition S$ is not an equivalence relation.
}

\end{problemparts}
\end{problem}


