1. ## 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,...,n-1

2. 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_{n-1},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.

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'$?
4. 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_{n-1},x_n)\in r' \& (x_n,y) \in r' \} \cup \{(x,x); x \in A\}$