partition is equivalent to an equivalence relation
Proposition 1.
There is a one-to-one correspondence between the set of partitions of and the set of equivalence relations on .
Proof.
Let be a set.
Suppose is a partition of . Form . Given any , for some . Then . If , then for some , so , whence . Finally, suppose . Then and , or and . Since , since is a partition. So , or .
Conversely, suppose is an equivalence relation on . For each , define
Then each since is reflexive. If , then or as is symmetric
. So as well. Next, pick any . Then . But . So since is transitive
. Therefore , which implies . Collect all the information we have so far, this implies . Therefore forms a partitition of ( is being interpreted as a set, not a multiset). In fact, .∎
From the above proof, we also have
Corollary 1.
For every partition of , is an equivalence relation. Conversely, every equivalence relation on can be formed this way.