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
In group theory, Cayley's theorem, named in honour of Arthur Cayley, states that every group is isomorphic to a subgroup of a symmetric group.
More specifically, is isomorphic to a subgroup of the symmetric group \operatorname(G) whose element ...
). To see this, associate to each element ''x'' of ''X'' the set
:
then the transitivity of ≤ ensures that for all ''a'' and ''b'' in ''X'', we have
:
There can be sets
of
cardinality
In mathematics, the cardinality of a set is a measure of the number of elements of the set. For example, the set A = \ contains 3 elements, and therefore A has a cardinality of 3. Beginning in the late 19th century, this concept was generalized ...
less than
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
In abstract algebra, a Boolean algebra or Boolean lattice is a complemented distributive lattice. This type of algebraic structure captures essential properties of both set operations and logic operations. A Boolean algebra can be seen as a gen ...
''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
In mathematics, the dimension of a partially ordered set (poset) is the smallest number of total orders the intersection of which gives rise to the partial order.
This concept is also sometimes called the order dimension or the Dushnik–Miller d ...
at most two, and the dimension-''n'' orders, which are the containment orders on collections of ''n''-boxes anchored at the
origin
Origin(s) or The Origin may refer to:
Arts, entertainment, and media
Comics and manga
* Origin (comics), ''Origin'' (comics), a Wolverine comic book mini-series published by Marvel Comics in 2002
* The Origin (Buffy comic), ''The Origin'' (Bu ...
. 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
In graph theory, an intersection graph is a graph that represents the pattern of intersections of a family of sets. Any graph can be represented as an intersection graph, but some important special classes of graphs can be defined by the types o ...
*
Interval order
In mathematics, especially order theory,
the interval order for a collection of intervals on the real line
is the partial order corresponding to their left-to-right precedence relation—one interval, ''I''1, being considered less than another, '' ...
References
*
*
Order theory
{{algebra-stub