
Equivalence Relations
I need help to get started with proving the 'only if' part of the following claim:
Let r be a relation. Define ~ to be the intersection of all equivalence relations containing r (So ~ is an equivalence relation.)
Show that x~y if and only if one of the following holds:
i) x=y
ii) (x,y) $\displaystyle \in$ r'
iii) there exist $\displaystyle z_1,z_2,...,z_n$ such that $\displaystyle (x,z_1)\in r', (z_i,z_{i+1})\in r', (z_n,y) \in r' $ where (x,y) $\displaystyle \in$ r' means (x,y) $\displaystyle \in$ r or (y,x) $\displaystyle \in$ r and i=1,...,n1

Hello !
define relation $\displaystyle R$ this way:
$\displaystyle
R = \{(x,y); (\exists n \in \mathbb{N})(\exists x_1, x_2,\dots, x_n) (x,x_1)\in r' \& (x_1,x_2)\in r' \&
$
$\displaystyle
(x_2,x_3)\in r' \& \dots \& (x_{n1},x_n)\in r' \& (x_n,y) \in r' \}
$
It is easy to verify that $\displaystyle R$ is an equivalence relation and that $\displaystyle r \subseteq R$.
Then consider an arbitrary equivalence relation $\displaystyle S$ such that $\displaystyle r \subseteq S$ and, again easily, show that $\displaystyle R \subseteq S$.
So, you showed that ~ $\displaystyle = R$ !! (and this answers your question).
note:
Definition of ~ that you gave is sometimes called 'definition from above', while definition I gave for $\displaystyle R$ is called 'definition from below'. The claim you are proving states that they are equivalent.

Thanks for the reply!
I have verified everything except for the reflexivity of $\displaystyle R$. In order to show $\displaystyle (x,x)\in R$ can we assume that $\displaystyle \exists x_1$ such that $\displaystyle (x,x_1)\in r'$?

You're right, I omitted to add the diagonal to the definition of $\displaystyle R$.
(e.g. empty set $\displaystyle r$ would lead to empty$\displaystyle R$ but to ~ = $\displaystyle \{(x,x); x \in A\}$).
So set $\displaystyle R = \{(x,y); (\exists n \in \mathbb{N})(\exists x_1, x_2,\dots, x_n) (x,x_1)\in r' \& (x_1,x_2)\in r' \&$
$\displaystyle (x_2,x_3)\in r' \& \dots \& (x_{n1},x_n)\in r' \& (x_n,y) \in r' \} \cup \{(x,x); x \in A\}
$
and it's allright. Sorry for confusion.