Inclusion Order

In the mathematical field of order theory, an inclusion order is the partial order that arises as the subset-inclusion relation on some collection of objects. In a simple way, every poset ''P'' = (''X'',≤) is ( isomorphic to) an inclusion order (just as every group is isomorphic to a permutation group – see Cayley's theorem). To see this, associate to each element ''x'' of ''X'' the set

:$X_ = \ ;$

then the transitivity of ≤ ensures that for all ''a'' and ''b'' in ''X'', we have

:$X_ \subseteq X_ \text a \leq b .$

There can be sets $S$ of cardinality less than $, X,$ such that ''P'' is isomorphic to the inclusion order on ''S''. The size of the smallest possible ''S'' is called the 2-dimension of ''P''.

Several important classes of poset arise as inclusion orders for some natural collections, like the Boolean lattice ''Q''^''n'', which is the collection of all 2^''n'' subsets of an ''n''-element set, the interval-containment orders, which are precisely the orders of order dimension at most two, and the dimension-''n'' orders, which are the containment orders on collections of ''n''-boxes anchored at the origin. Other containment orders that are interesting in their own right include the circle orders, which arise from disks in the plane, and the angle orders.

See also

*Birkhoff's representation theorem
*Tree (a data structure defined by the inclusion order)
*Intersection graph
*Interval order

References

*
*

Order theory

{{algebra-stub