0

I want to prove that an equivalence relation $\sim$ on a set $A$ has disjoint equivalence classes—that is, for any nonequivalent elements $a,b\in A$, we have $[a]\cap [b]=\emptyset$.

Here is my attempt at the proof:

If $\sim$ is an equivalence relation on $A$, then by transitivity, $a\sim b$ and $b\sim c$ implies $a\sim c$. Therefore, $\forall a\in A$, $a$ can only be equivalent to an element of the equivalence class $[a]$. Therefore, for two distinct, non-equivalent elements $a,b\in A$, $[a]\cap [b]=\emptyset$.

I would like to know if

$1)$ Are there any corrections to be made, and

$2)$ Any better wording for the proof.

高田航
  • 2,125
  • 13
  • 30
  • 1
    It sounds like you have the right idea, but I'm not sure about the wording. I would have instead opted to word it using a proof by contradiction. Suppose that $a$ and $b$ are not equivalent and yet that $[a]\cap[b]\neq \emptyset$. So there is some $c$ such that $c\in[a]$ and $c\in [b]$... – JMoravitz Sep 30 '17 at 18:14
  • @JMoravitz Ah, yes that makes the transitivity work better in the proof. Thanks for the suggestion. – 高田航 Sep 30 '17 at 18:15

1 Answers1

2

There is no need to jump to a proof by contradiction. (In general I find that students, more often than not, are actually just presenting convoluted proofs by contrapositive with a double negation thrown for no obvious reason.) Proving the contrapositive, i.e., That if two equivalence classes are not disjoint then they are identical:

For $c \in [a]\cap[b]$, then $a \sim c $ and $b\sim c$ (for all pairs of representatives $a\in[a], b\in[b]$), so by reflection $c\sim b$ and, by transitivity, $a\sim b$. It follows that every member of $[a]$ is in $[b]$ and vice-versa, i.e., $[a]\subseteq[b]$ and $[b]\subseteq [a]$, so by mutual inclusion $[a]=[b]$ and we are done.

This proof also hints at the power of the equivalence relations. It takes showing only one element in the intersection (of likely infinite sets) for every single element to be shown equivalent.

adfriedman
  • 3,641