\problemdata      
        {relations-5} % latex-friendly label for the prob.
        {equivalence relations} % The topic(s) of the problem content.
        {?} % Source (if known)
        {S02 cp3W} % Usage (list ones you are aware of).
        {Radhika Nagpal, S02} % Last revision info (author, date).

\begin{problem}
Let $R$ be an equivalence relation on the set $A$. For an element
$a\in A$, let $[a]$ denote the set $\{b\in A \mbox{ given } aR
b\}$.  This set is the \emph{equivalence class of $a$ under $R$} and
we call $a$ a \emph{representative} of the set $[a]$.


Prove that the sets $[a]$ for $a \in A$ constitute a partition of $A$.
That is, for every $a,b\in A$, either $[a]=[b]$ or $[a]\cap
[b]=\emptyset$.

\solution{

From the notes:

\begin{proof}
  Consider some arbitrary $a,b\in A$. If either $[a]=[b]$ or $[a] \cap
  [b]=\emptyset$ then we are done, so suppose not.  Let $c$ be any
  element that is in one of the sets but not the other.  Without loss
  of generality we can assume that $c \in [b]-[a]$.  (We know that
  either $c \in [b]-[a]$ or $c \in [a]-[b]$. In the latter case we can
  simply swap $a$ and $b$ and reduce to the first case.)  Let $d$ be
  any element in $d \in [a] \cap [b]$. We will get a contradiction by
  showing that $aRc$ and therefore that $c\in [a]$. First,
  $aRd$ because $d\in [a]$ (note that $d=a$ is a possibility but
  this is ok because $R$ is reflexive).  Second, $dRb$ and
  $bRc$ because both $c,d\in [b]$ and $R$ is symmetric.  This
  implies, by transitivity, that $dRc$.  Finally, by
  transitivity, $aRc$ because $aRd$ and $dRc$.  Also, we know that for every $a \in A$, $a$ is in its own equivalence class since $R$ is reflexive.  Therefore the union of all the equivalence classes gives us $A$, and thus the sets [$a$] for $a \in A$  constitute a parition of $A$.

Note that all three properties of equivalence relations were used in this proof.  Checking that the proof uses all available assumptions is usually a good sanity check when writing proofs.  If one of the properties you assumed were not needed, you have either made a mistake or proven a much more strong theorem than you thought.  For example, if you didn't use transitivity anywhere in the proof of this problem, you would have falsely proven that any reflexive symmetric relation produces a partition.  
\end{proof}
}

\end{problem}
