\problemdata     
{relations-3}           
{relations, compositions, properties}              
{Velleman 4.3.9, rosen 6.1.36}              
{S00-ps3, S02-ps3} 		
{S02 Radhika}        	


\begin{problem} Suppose $R$ and $S$ are binary relations on a set $A$, and
that both $R$ and $S$ are symmetric. Must each of the following new
relations be symmetric? For each part, justify your answer with a
brief argument if the new relation is symmetric and a counterexample
if it is not.

\begin{problemparts}
\problempart $R^{-1}$

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

\problempart $R \intersect S$

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

% \problempart $R \union S$ 

% \solution{\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$.}

\problempart $R \composition S$

\solution{ 
\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.
}

\problempart $R \composition R$

\solution{\textbf{Yes.} $R^2$ is symmetric.  For every ordered pair
$(a,b)$ that is a member of $R$, $(b,a)$ must also be in $R$.  Then in
the composition, $R^2$, $(a,a)$ is certainly symmetric.  What about
the case where $(a,b)$ is in $R$, and so is $(b,c)$?  $(a,c)$ will be
in $R^2$, but so will $(c,a)$ since $(c,b)$ and $(b,a)$ are both in
$R$ because of symmetry. In fact, $R^n$ is symmetric if $R$ is
symmetric.}

% \problempart $R^n$, where $n$ is a positive integer greater than
% 0. ??? TOO HARD/LONG ??
% \solution{It is symmetric, add proof - use induction?rosen 6.1.36,
% solution should be in instructor's manual}

\end{problemparts}
\end{problem}
