## Saturday, September 14, 2013

### Ranking elements of distributive lattices

There is a correspondence between the number of join irreducibles contained in an element of a distributive lattice and its ordinal height minus one:
(= (dec (count [1 1 1 1]))
(count #{#{} #{#{}} #{#{} #{#{}}}}))

The same principle applies to multisets which are elements of a distributive inclusion lattice:
(= (rank {:x 1, :y 2})
(dec (count [1 2 2 1]))
(count #{{:x 1} {:y 1} {:y 2}))

This implies that we can use the idea of join irreducible elements as a basis for structured multisets and canonical forms of structures. A canonical labeling of a structure is one over a set-theoretic natural number such as #{#{} #{#{}} #{#{} #{#{}}}} and a structured multiset is a structure over the join irreducibles of the multiset. The key is to implement an effective partial canonization technique so that we can properly determine the equality of such structures.