partition is equivalent to an equivalence relation

Proposition 1.

There is a one-to-one correspondence between the set Part(S) of partitions of S and the set Equiv(S) of equivalence relationsMathworldPlanetmath on S.


Let S be a set.

Suppose P={PiiI} is a partition of S. Form E={Pi×PiiI}. Given any aS, aPi for some iI. Then (a,a)Pi×PiE. If (a,b)E, then (a,b)Pi×Pi for some iI, so a,bPi, whence (b,a)Pi×PiE. Finally, suppose (a,b),(b,c)E. Then (a,b)Pi×Pi and (b,c)Pj×Pj, or a,bPi and b,cPj. Since bPiPj, Pi=Pj since P is a partition. So a,cPi=Pj, or (a,c)Pi×PiE.

Conversely, suppose E is an equivalence relation on S. For each aS, define


Then each a[a] since E is reflexiveMathworldPlanetmathPlanetmathPlanetmathPlanetmathPlanetmath. If b[a], then (a,b)E or (b,a)E as E is symmetricPlanetmathPlanetmathPlanetmath. So a[b] as well. Next, pick any c[b]. Then (b,c)E. But (a,b)E. So (a,c)E since E is transitiveMathworldPlanetmathPlanetmathPlanetmathPlanetmath. Therefore c[a], which implies [b][a]. Collect all the information we have so far, this implies [a]=[b]. Therefore P={[a]aS} forms a partitition of S (P is being interpreted as a set, not a multiset). In fact, E={[a]×[a]aS}. ∎

From the above proof, we also have

Corollary 1.

For every partition P={PiiI} of S, E={Pi2iI} is an equivalence relation. Conversely, every equivalence relation on S can be formed this way.

Title partition is equivalentMathworldPlanetmathPlanetmathPlanetmath to an equivalence relation
Canonical name PartitionIsEquivalentToAnEquivalenceRelation
Date of creation 2013-03-22 16:44:55
Last modified on 2013-03-22 16:44:55
Owner CWoo (3771)
Last modified by CWoo (3771)
Numerical id 7
Author CWoo (3771)
Entry type DerivationPlanetmathPlanetmath
Classification msc 03-00