Tuesday, August 27, 2013

Properties of elements of posets

There are a variety of properties specific to elements of a partial order. Any combination of these properties can be used to define a weak order of the partial order which combined with the lexicographic ordering of matrices can be used to canonize any partial order.

Atomic: (= (count (parts order x)) 1)
Minimal: (= (count (parts order x)) 0)
Maximal: (= (count (parents order x)) 0)
Join irreducible: (every? #(contains % x) (join-representations x)
Meet irreducible: (every? #(contains % x) (meet-representations x)
Irreducible: join-irreducible? and meet-irreducible?
Isolated: (count (ground-set (connected-component x))) = 1

If an element is not isolated it has a connected component, if it is not minimal it has parts, and if it is not maximal it has parents, if it isn't join irreducible it has join representations, and if it isn't meet irreducible it has meet representations:

Parts: (query order ? x)
Parents: (query order ? x)
Proper parts: (clojure.set/difference (query order ? x) #{x})
Proper parents: (clojure.set/difference (query order x ?) #{x})
Connected components: (connected-component x)
Join representations: all elements that whose join is x
Meet representations: all elements whose meet is x

In lattices that aren't necessarily modular we can consider modular elements and in other lattices we consider when those elements are join prime or meet prime. Additionally, a variety of lattices including boolean algebras are complemented so they have specific elements associated with them:

Modular element: specific elements for which the modular law holds
Join prime: if (<= x (join a b)) then (<= x a) or (<= x b)
Meet prime: if (<= x (meet a b)) then (<= x a) or (<= x b)
Complement: in complemented lattices elements may be associated with complements

Related to the notion of parts is the height of an element of a well founded partial order which is defined to be the length of the partial ordering on its parts. Another type of partial order is one whose parts order forms a chain such elements form the lower subforest of a partial order and the dual notion of elements whose parents form a chain forms the upper subforest of the partial order. Related to join and meet representations is the minimal number of elements in a representation which generalizes the dimension of a partial order.

No comments:

Post a Comment