Partial Order

A Relation ``$\leq$'' is a partial order on a Set $S$ if it has:

1. Reflexivity: $a\leq a$ for all $a\in S$.

2. Antisymmetry: $a\leq b$ and $b\leq a$ implies $a=b$.

3. Transitivity: $a\leq b$ and $b\leq c$ implies $a\leq c$.

For a partial order, the size of the longest Chain (Antichain) is called the Length (Width). A partially ordered set is also called a Poset.

See also Antichain, Chain, Fence Poset, Ideal (Partial Order), Length (Partial Order), Linear Extension, Partially Ordered Set, Total Order, Width (Partial Order)

References

Ruskey, F. ``Information on Linear Extension.'' http://sue.csc.uvic.ca/~cos/inf/pose/LinearExt.html.