I am working on proving the following:
Let $A$ be a non-empty set and $~$ be an equivalence relation. Let $A/\sim$ := { [a] | a $\in$ A } be the set of equivalence classes of $A$ under $\sim$. In other words, $[a]$ := {$b \in A$ | $b \sim a$}. Prove that either $[a] = [b]$ or $[a] \cap [b] = \emptyset$ for any $a, b \in A.$ In particular, $A/\sim$ is a partition of $A$.
I am comfortable showing that $[a] = [b]$ but am having difficulty showing that if $[a] \neq [b]$ then $[a] \cap [b] = \emptyset$. I have an attempt at a proof but I'm pretty sure it's wrong:
- Assume that $[a] \neq [b]$.
- We know that $[a] \cap [b]$ = {$a: a \in [a]$ and $a\in [b]$}.
- Take $a \in [a]$, where $[a] =$ {$b \in A: b \sim a$}. Now, take $b \in [b]$, where $[b] =$ {$c \in B : c \sim d$}.
- If $[a] \neq [b]$, then no element of $[b]$ will be an element in $[a]$.
- This implies that the union of $[a]$ and $[b]$ must be the empty set.
I know that my proof is wrong but I'm having trouble fleshing out the details. I feel like I understand intuitively what this means but I'm not sure how to prove it. Any help would be appreciated.
You can't flesh out the details because you are not on a right track. Your step (4) is just restating what you are trying to prove. In (5) you want to have the intersection be empty, not the union.
You can get back on track by starting step (3) by supposing $[a] \cap [b]$ is not empty and picking some $c$ in it. Then use $c$ and the properties of an equivalence relation to show anything in $[a]$ must be in $[b]$ and vice versa.