Show that an equivalence relation is equal to the union of the cartesian product of its equivalence classes Given an equivalence relation $\sim$ with equivalence classes $C_1,\dots,C_n$, show that $$\mathbin{\sim} = \bigcup_{j=1}^n\bigcup_{i=1}^n(C_j\times C_i)\;.$$
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 symmetry 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$.
 A: 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?
