Tuesday, October 2, 2012

The shape of an equivalence relation

Every equivalence relation has a multiset of equivalence class sizes associated with it that completely describes that equivalence relation up to relation isomorphism. For example,
(= (shape #{#{1,2,3} #{4 5}, #{6 7} #{8}})
   {3 1, 2 2, 1 1})
Divisions are precisely those equivalence relations that have only one distinct element in their multiset, so they evenly divide a set into parts:
(= (shape #{#{1,2}, #{3,4}, #{5,6}, #{7,8}})
   {2 4})
The division shapes {∞ 1} and {1 ∞} are the bottom and top level shapes, because {∞ 1} has no parts and {1 ∞} is the universal element that contains everything as a part. Place forms have divisions as their equivalence relation, such that the top place form is the identity function.

No comments:

Post a Comment