\documentstyle[12pt,twoside]{article}
\input{macros-course}

\begin{document}

\begin{center}
\Large Quiz 1, Problem 6 
\end{center}


Let $R,S$ be equivalence relations on some set $A$.  Prove that if
$R \circ S = S \circ R$, then $R \circ S$ is also an equivalence relation
on $A$.

\begin{proof}
In order to prove that $R\circ S$ is an equivalence relation, 
we have to show that $R\circ S$ is reflexive, symmetric
and transitive.
\begin{itemize}
 \item $R\circ S$ is reflexive:
  for any $a\in A$, we have $(a,a)\in R$ and $(a,a)\in S$
  because $R$ and $S$ are equivalence relations.
  Therefore by definition of composite, 
  $(a,a)\in (R\circ S)$. This proves reflexivity.
 \item $R\circ S$ is symmetric:
  let $(a,b)$ be in relation $R\circ S$.
  We have to prove that also $(b,a)$ is in $R\circ S$.
  Since $R\circ S= S\circ R$, 
  $(a,b)$ is in $S\circ R$ and there exists a $b\in A$
  such that $(a,b)\in S$ and $(b,c)\in R$.
  Since $R$ and $S$ are equivalence relations,
  we also have $(b,a)\in S$ and $(c,b)\in R$
  and by definition of composite 
  $(c,a)\in (R\circ S)$.
 \item  $R\circ S$ is transitive:
  assume that $(a,b)\in R\circ S$ and $(b,c)\in R\circ S$.
  We have to prove that also $(a,c)$ is in $R\circ S$.
  Since $(a,b)\in R\circ S$, there is a $x\in A$
  such that $(a,x)\in R$ and $(x,b)\in S$.
  Analogously since $(b,c)\in R\circ S$ 
  there is a $y\in A$ such that $(b,y)\in R$ and $(y,c)\in S$.
  Now putting together $(x,b)\in S$ and $(b,y)\in R$, 
  we obtain $(x,y)\in S\circ R$ and 
  since $S\circ R= R\circ S$ there is a $z\in A$
  such that $(x,z)\in R$ and $(z,y)\in S$.
  At this point we use the transitivity of 
  $R$ and $(a,x),(x,z)\in R$
  to show that  $(a,z)\in R$. 
  Analogously from $(z,y),(y,c)\in S$ and by $S$ transitivity
  we have $(z,c)\in S$.
  Finally since $(a,z)\in R$ and $(z,c)\in S$, 
  the pair $(a,c)$ is in the composite relation $R\circ S$.
\end{itemize}
\end{proof}

The most common errors made in the solution of this problem 
are the following.

\begin{itemize}
 \item Many of you wrote something like this.
  \begin{quote}\em
    We have to prove that $R\circ S$ is an equivalence relation,
    i.e. it satisfies symmetry, reflexivity and transitivity.
    Symmetry: $R\circ S=S\circ R$ is already given, 
    so symmetry holds.
  \end{quote}

  The symmetric property for $R\circ S$ is 
  \[ \forall (a,b). (a,b)\in (R\circ S) \rightarrow (b,a)\in (S\circ R)\]
  which is different from $R\circ S = S\circ R$.
  The latter is not even a property of the relation $(R\circ S)$:
  it is a property of $R$, $S$ and the composition operation $\circ$.

  Analogous errors were found in the definition of 
  reflexivity, and transitivity:
  \begin{itemize}
   \item $R\circ S$ is reflexive if for all $a\in A$
     \[ (a,a)\in (R\circ S).\]
     ($R\circ S = R\circ S$ is a consequence of reflexivity
     of $=$, but has nothing to do with the reflexivity of $R\circ S$)
   \item $R\circ S$ is transitive if for all $a,b,c\in A$
     \[ (a,b)\in (R\circ S) \wedge (b,c)\in (R\circ S) \Rightarrow
        (a,c) \in (R\circ S).\]
  \end{itemize}
 \item The following proof is wrong.
   \begin{quote}\em
   Assume that  $(a,b)$ is in $R\circ S$. 
   By definition of composite there exists a $c\in A$ 
   such that $(a,c)\in R$ and $(c,b)\in S$.
   But $R\circ S=S\circ R$, so $(a,b)$ is also in $S\circ R$.
   Therefore there exists a $c\in A$ such that 
   $(a,c)\in S$ and $(c,b)\in R$.
   Now, from $(a,c)\in R$ and $(c,b)\in R$ we obtain 
   by transitivity of $R$ that $(a,b)\in R$ \ldots
   \end{quote}
   If $(a,b)$ is in $R\circ S$,
   there exists a value $c_1\in A$ such that
   $(a,c_1)\in R$ and $(c_1,b)\in S$.
   Also, from $(a,b)\in (S\circ R)$
   we know that there exists a $c_2\in A$ 
   such that $(a,c_2)\in S$ and $(c_2,b)\in R$.
   But in general $c_1$ and $c_2$ 
   are {\bf different}.
   Therefore from $(a,c_1)\in R$
   and $(c_2,b)\in R$ we cannot infer,
   by transitivity of $R$, 
   that $(a,b)\in R$.

 \item Some of you used the following ``function-like''
  notation for relation:
  \begin{quote}\em
    if $(a,b)\in R$, I write
    $R(a)=b$.
  \end{quote}
  The above notation is imprecise and error prone because 
  there can be more than one value $b$ such that 
  $(a,b)\in R$. It would be more appropriate to write 
  $b\in R(a)$.

  Consider for example the relation $R=\{(1,2),(1,3)\}$.
  We know that $(1,2)\in R$ and $(1,3)\in R$. 
  Using the above notation you would write 
  $R(1)=2$ and $R(1)=3$. Then, using the transitivity of 
  equality you could erroneously infer $2=R(1)=3$.
\end{itemize}


\end{document}

