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) r' iii) there exist such that where (x,y) r' means (x,y) r or (y,x) r and i=1,...,n-1
Aug 26th 2009, 02:15 PM
define relation this way:
It is easy to verify that is an equivalence relation and that .
Then consider an arbitrary equivalence relation such that and, again easily, show that .
So, you showed that ~ !! (and this answers your question).
Definition of ~ that you gave is sometimes called 'definition from above', while definition I gave for is called 'definition from below'. The claim you are proving states that they are equivalent.
Aug 26th 2009, 07:11 PM
Monkey D. Johnny
Thanks for the reply!
I have verified everything except for the reflexivity of . In order to show can we assume that such that ?
Aug 26th 2009, 07:33 PM
You're right, I omitted to add the diagonal to the definition of .
(e.g. empty set would lead to empty but to ~ = ).