Equivalence classes

• May 18th 2011, 09:25 AM
Conn
Equivalence classes
\Rightarrow "Let $\displaystyle R$ be an equivalence relation on $\displaystyle A$. For any $\displaystyle x, y \in A$ either

$\displaystyle \left[ x \right]_{R} = \left[ y \right]_{R}$

or

$\displaystyle \left[ x \right]_{R} \cap \left[ y \right]_{R} = \emptyset$"

My professor gave the following proof to the preceding lemma in his notes, but he starts it by saying "It is enough to assume" then footnoting this and writing "no it isn't". So how do I need to add to this to make it a complete proof?

It is enough to assume (footnoted here)
$\displaystyle \left[ x \right]_{R} \cap \left[ y \right]_{R} \neq \emptyset$
and deduce that
$\displaystyle \left[ x \right]_{R} = \left[ y \right]_{R}$

First, fix $\displaystyle w \in \left[ x \right]_{R}.$ For any $\displaystyle z \in \left[ x \right]_{R}$,

$\displaystyle z \in \left[ x \right]_{R}$ means $\displaystyle xRz$
$\displaystyle xRw$ (similarly)
$\displaystyle wRx$ (symmetry)
Therefore$\displaystyle wRz$ (transitivity), i.e.,
$\displaystyle z \in \left[ w \right]_{R}$

That is, for every $\displaystyle z \in \left[ x \right]_{R}, z \in \left[ w \right]_{R}.$

In other words,

$\displaystyle w \in \left[ x \right]_{R} \Rightarrow \left[ x \right]_{R} \subseteq \left[ w \right]_{R}$

In particular, $\displaystyle w \in \left[ x \right]_{R}\Rightarrow x \in \left[ w \right]_{R}$
and also $\displaystyle x \in \left[ w \right]_{R} \Rightarrow \left[ x \right]_{R} \subseteq \left[ w \right]_{R}$

Therefore $\displaystyle w \in \left[ x \right]_{R} \Rightarrow \left[ x \right]_{R} = \left[ w \right]_{R}$

So, if $\displaystyle \left[ x \right]_{R} \cap \left[ y \right]_{R} \neq \emptyset$ choose some $\displaystyle w \in \left[ x \right]_{R} \cap \left[ y \right]_{R}$

Then $\displaystyle \left[ x \right]_{R} = \left[ w \right]_{R}$ and $\displaystyle \left[ y \right]_{R} = \left[ w \right]_{R}$, so

$\displaystyle \left[ x \right]_{R} = \left[ y \right]_{R}$
• May 18th 2011, 08:12 PM
Drexel28
Quote:

Originally Posted by Conn
\Rightarrow "Let $\displaystyle R$ be an equivalence relation on $\displaystyle A$. For any $\displaystyle x, y \in A$ either

$\displaystyle \left[ x \right]_{R} = \left[ y \right]_{R}$

or

$\displaystyle \left[ x \right]_{R} \cap \left[ y \right]_{R} = \emptyset$"

My professor gave the following proof to the preceding lemma in his notes, but he starts it by saying "It is enough to assume" then footnoting this and writing "no it isn't". So how do I need to add to this to make it a complete proof?

It is enough to assume (footnoted here)
$\displaystyle \left[ x \right]_{R} \cap \left[ y \right]_{R} \neq \emptyset$
and deduce that
$\displaystyle \left[ x \right]_{R} = \left[ y \right]_{R}$

First, fix $\displaystyle w \in \left[ x \right]_{R}.$ For any $\displaystyle z \in \left[ x \right]_{R}$,

$\displaystyle z \in \left[ x \right]_{R}$ means $\displaystyle xRz$
$\displaystyle xRw$ (similarly)
$\displaystyle wRx$ (symmetry)
Therefore$\displaystyle wRz$ (transitivity), i.e.,
$\displaystyle z \in \left[ w \right]_{R}$

That is, for every $\displaystyle z \in \left[ x \right]_{R}, z \in \left[ w \right]_{R}.$

In other words,

$\displaystyle w \in \left[ x \right]_{R} \Rightarrow \left[ x \right]_{R} \subseteq \left[ w \right]_{R}$

In particular, $\displaystyle w \in \left[ x \right]_{R}\Rightarrow x \in \left[ w \right]_{R}$
and also $\displaystyle x \in \left[ w \right]_{R} \Rightarrow \left[ x \right]_{R} \subseteq \left[ w \right]_{R}$

Therefore $\displaystyle w \in \left[ x \right]_{R} \Rightarrow \left[ x \right]_{R} = \left[ w \right]_{R}$

So, if $\displaystyle \left[ x \right]_{R} \cap \left[ y \right]_{R} \neq \emptyset$ choose some $\displaystyle w \in \left[ x \right]_{R} \cap \left[ y \right]_{R}$

Then $\displaystyle \left[ x \right]_{R} = \left[ w \right]_{R}$ and $\displaystyle \left[ y \right]_{R} = \left[ w \right]_{R}$, so

$\displaystyle \left[ x \right]_{R} = \left[ y \right]_{R}$

It is complete. What you want to show is that given two equivalence classes $\displaystyle [x],[y]$ they're equal or disjoint? You've showed that their not disjoint implies their equal and so either they are equal, or they're not equal in which case they must be disjoint (otherwise they'd be equal!).