# Math Help - Equivalence Relations

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) $\in$ r'
iii) there exist $z_1,z_2,...,z_n$ such that $(x,z_1)\in r', (z_i,z_{i+1})\in r', (z_n,y) \in r'$ where (x,y) $\in$ r' means (x,y) $\in$ r or (y,x) $\in$ r and i=1,...,n-1

2. Hello !
define relation $R$ this way:

$
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' \&
$

$
(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 $R$ is an equivalence relation and that $r \subseteq R$.
Then consider an arbitrary equivalence relation $S$ such that $r \subseteq S$ and, again easily, show that $R \subseteq S$.
So, you showed that ~ $= R$ !! (and this answers your question).

note:
Definition of ~ that you gave is sometimes called 'definition from above', while definition I gave for $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 $R$.
In order to show $(x,x)\in R$ can we assume that $\exists x_1$ such that $(x,x_1)\in r'$?

4. You're right, I omitted to add the diagonal to the definition of $R$.
(e.g. empty set $r$ would lead to empty $R$ but to ~ = $\{(x,x); x \in A\}$).
So set $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' \&$
$(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\}
$

and it's allright. Sorry for confusion.