Suppose $P=\lbrace P_i\mid i\in I\rbrace$ is a partition of $S$ . Form $E=\bigcup \lbrace P_i\times P_i\mid i\in I\rbrace$ . Given any $a\in S$ , $a\in P_i$ for some $i\in I$ . Then $(a,a)\in P_i\times P_i\in E$ . If $(a,b)\in E$ , then $(a,b)\in P_i\times P_i$ for some $i\in I$ , so $a,b\in P_i$ , whence $(b,a)\in P_i\times P_i\subseteq E$ . Finally, suppose $(a,b),(b,c)\in E$ . Then $(a,b)\in P_i\times P_i$ and $(b,c)\in P_j\times P_j$ , or $a,b\in P_i$ and $b,c\in P_j$ . Since $b\in P_i\cap P_j$ , $P_i=P_j$ since $P$ is a partition. So $a,c\in P_i=P_j$ , or $(a,c)\in P_i\times P_i\subseteq E$ .

Conversely, suppose $E$ is an equivalence relation on $S$ . For each $a\in S$ , define $$[a]=\lbrace b\in S\mid (a,b)\in E\rbrace.$$ Then each $a\in [a]$ since $E$ is reflexive. If $b\in [a]$ , then $(a,b)\in E$ or $(b,a)\in E$ as $E$ is symmetric. So $a\in [b]$ as well. Next, pick any $c\in [b]$ . Then $(b,c)\in E$ . But $(a,b)\in E$ . So $(a,c)\in E$ since $E$ is transitive. Therefore $c\in [a]$ , which implies $[b]\subseteq [a]$ . Collect all the information we have so far, this implies $[a]=[b]$ . Therefore $P=\lbrace [a]\mid a\in S\rbrace$ forms a partitition of $S$ ($P$ is being interpreted as a set, not a multiset). In fact, $E=\bigcup \lbrace [a]\times [a]\mid a\in S\rbrace$ .