text: Q:
  
  Induced relations
  
  I have question on relations:
  Let $R \subseteq X \times X$ be any relation on $X$, and define $\sim$ to be the intersection of all equivalence relations in $X \times X$ that contain $R$.
  
  Show that $\sim$ is an equivalence relation.
  Show that $x \sim y$ if and only if at least one of the following conditions is true: $x = y$, or $x R' y$, or there is a finite sequence of elements $z_1, \ldots z_n \in X$ such that $x R' z_1 R' \ldots R' z_n R' y$ where $x R' y$ means "$x R y$ or $y R x$".
  
  I think I understand how to prove all of the above except for proving the "only if" part of 2 above. That is, how can I show that $x \sim y$ implies $x = y$, or $x R' y$, or there is a finite sequence of elements $z_1, \ldots z_n \in X$ such that $x R' z_1 R' \ldots R' z_n R' y$? In particular I am stuck on how to show that a finite sequence of $z$s exists when neither $x=y$ nor $xR'y$ holds.
  Thanks for any hints.
  Raj
  
  A:
  
  Show that the relation $\sim'$ defined in 2. is also an equivalence relation and of course it contains $R$, and any other equivalence relation $E$ that contains $R$ must contain this $\sim'$.
  
  