partition is equivalent to an equivalence relation
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
For every partition of , is an equivalence relation. Conversely, every equivalence relation on can be formed this way.
|Title||partition is equivalent to an equivalence relation|
|Date of creation||2013-03-22 16:44:55|
|Last modified on||2013-03-22 16:44:55|
|Last modified by||CWoo (3771)|