Chain (order theory)

A chain is a subset of a partially ordered set in which every pair of elements is comparable. It inherits a total order from the surrounding partial order.

Partially ordered set: A set equipped with a reflexive, antisymmetric, and transitive relation. A chain is a subset of this structure, inheriting its order.
Dilworth's theorem: A finite partially ordered set's width equals the minimum number of chains covering its elements. It turns chain decompositions into an exact statement about antichains.
Chain decomposition: A partition of a partially ordered set into chains. It expresses the whole order as a collection of totally ordered pieces.
Hausdorff maximal principle: The principle that every chain in a partially ordered set is contained in a maximal chain. It guarantees maximal extensions of chains and is equivalent to the axiom of choice.
Comparable elements: Two elements are comparable when one is less than or equal to the other in a given order. Every pair in a chain must satisfy this relation.
Mirsky's theorem: In a finite partially ordered set, the minimum number of antichains partitioning it equals its maximum chain size. It relates chain height to a partition into incomparable layers.
Width of a partially ordered set: The maximum cardinality of an antichain in a partially ordered set. Width constrains how many chains are needed to cover a finite order.
Zorn's lemma: A maximal-element principle asserting that a partially ordered set has a maximal element when every chain has an upper bound. Its hypothesis is stated for all chains, including infinite ones.
Total order: A partial order in which every pair of elements is comparable. The order induced on a chain is total.
Longest increasing subsequence: A longest subsequence of a sequence whose terms increase strictly in their original order. Increasing subsequences form chains under coordinatewise comparison of sequence positions and values.

Linked from 8 pages