# Show that an equivalence relation is equal to the union of its equivalence classes

Given an equivalence relation $\sim$ with equivalence classes $C_1,\dots,C_n$, show that $$\mathbin{\sim} = \bigcup_{i=1}^n(C_n\times C_n)\;.$$

I could use a hint on where to start approaching this from.

The beginnings of my proof:

Suppose that $\langle a,b \rangle\in\sim$. This implies that $a\sim b$, and by the transitivity of $\sim$, $b\sim a$. The equivalence classes of $a$ and $b$ are defined $\bar{a}=\{b\in A | a\sim b\}$ and $\bar{b}=\{a\in A | b\sim a\}$. It follows from the properties of the equivalence relation that $a\sim b\iff \bar{a}=\bar{b}$. $\bar{a}=\bar{b}\implies \{b\in A | a\sim b\}=\{a\in A | b\sim a\}$.

Now suppose that $\langle a,b\rangle\in\bigcup_{i=1}^n(C_i\times C_i)$. This means there exists $i\in\{1,\dots,n\}$ such that $\langle a,b \rangle\in C_i\times C_i$. Consequently, $\langle a,b \rangle\in C_i\times C_i\implies a\in C_i$ and $b\in C_i$.

-
What are your thoughts? What did you try so far? What is the standard way of proving that two sets are equal? – N. S. Feb 6 '13 at 3:40
I'm not entirely sure what I need to show. Is it that all elements $a\in\sim$ exist in$C_1\cup C_2\cup C_3\dots\cup C_n$? – tacoTaco Feb 6 '13 at 3:52

HINT: Let $A$ be the underlying set for the equivalence relation $\sim$; then $\sim$ is a subset of $A\times A$. $\bigcup_{i=1}^n(C_i\times C_i)$ is also a subset of $A\times A$, and you’re to show that these two subsets of $A\times A$ are actually the same subset. You can approach it as you would approach any other problem of showing that two sets are equal: try to show that each is a subset of the other.
• Suppose that $\langle a,b\rangle\in\;\sim$, i.e., that $a\sim b$; you want to show that there is an $i\in\{1,\dots,n\}$ such that $\langle a,b\rangle\in C_i\times C_i$. This is the case if and only if $a\in C_i$ and $b\in C_i$, i.e., if and only if $a$ and $b$ are in the same equivalence class. Is this true if $a\sim b$? Why?
• Then suppose that $\langle a,b\rangle\in\bigcup_{i=1}^n(C_i\times C_i)$, and try to show that $\langle a,b\rangle\in\;\sim$, i.e., that $a\sim b$. If $\langle a,b\rangle\in\bigcup_{i=1}^n(C_i\times C_i)$, then $\langle a,b\rangle\in C_i\times C_i$ for some $i\in\{1,\dots,n\}$. Does that imply that $a\sim b$? Why?
I understand the first part as you have it written, but I can't seem to recognize the method to prove that $i\in \{1,\dots,n\}|(a,b)\in C_i\times C_i$. Perhaps I'm not entirely clear on how it relates to $C_i\times C_i$. – tacoTaco Feb 6 '13 at 17:11
@tacoTaco: Suppose that $a\sim b$. Then by definition $b\in[a]$, where $[a]$ is the $\sim$-equivalence class of $a$. And $a\sim a$, so $a\in[a]$ as well. Thus, $\langle a,b\rangle\in[a]\times[a]$. $C_1,\dots,C_n$ are all the equivalence classes, so $[a]$ is one of them, say $C_i$, and therefore $\langle a,b\rangle\in C_i\times C_i$. That proves that $\sim~\subseteq\bigcup_{k=1}^n(C_k\times C_k)$; now you just have to prove the other direction. – Brian M. Scott Feb 6 '13 at 22:18