Sunday, September 1, 2013

Complementary pairs

Given a lattice we can find certain elements that are both independent and covering which are called complements of one another. If we order pairs of such elements we can get complementary pairs. Here is an example of an expression of the boolean algebra on three elements as complementary pairs:
[#{0 1 2} #{}]
[#{1 2} #{0}], [#{0 2} #{1}], [#{0 1} #{2}]
[#{2} #{0 1}], [#{1} #{0 2}], [#{0} #{1 2}]
[#{} #{0 1 2}]
By convention such complementary pairs are expressed such that sets in a boolean algebra are equivalent to height two weak orders or in other words total functions from the underlying set to the two valued total order. One of the the major reasons I am interested in exploring such complementary pairs is their applications to set partitions:
[#{#{0} #{1} #{2}} #{#{0 1 2}}]
[#{#{1} #{0 2}} #{#{0 1} #{2}}], 
[#{#{0} #{1 2}} #{#{0 1} #{2}}], 
[#{#{0 1} #{2}} #{#{1} #{0 2}}], 
[#{#{0} #{1 2}} #{#{1} #{0 2}}], 
[#{#{0 1} #{2}} #{#{0} #{1 2}}],
[#{#{1} #{0 2}} #{#{0} #{1 2}}]
[#{#{0 1 2}} #{#{0} #{1} #{2}}]
Such complementary pairs of set partitions are a generalization of place forms applicable to other means of decomposing structures. In the most general setting we simply consider set partitions that are covering by ignoring the independence property but such pairs of set partitions aren't necessarily decompositions so that makes them much less interesting to us.

No comments:

Post a Comment