posets

A poset, or partially ordered set, is a set P together with a binary relation ≤ that is reflexive, antisymmetric, and transitive. The relation need not be total; not every pair of elements has to be comparable. Example: P(X), the power set of a set X, ordered by inclusion ⊆, is a poset; the natural numbers with the usual ≤ is also a poset and is in fact a total order; the divisibility relation on the positive integers (a|b) is another common poset.

In a finite poset, one often uses a Hasse diagram: a directed graph in which elements are drawn as points and edges represent cover relations a < b with no c satisfying a < c < b. The diagram omits reflexive loops and edges for non-cover comparabilities to provide a compact visualization.

Key structures within posets include chains and antichains. A chain is a subset in which every pair is comparable; an antichain is a subset with pairwise incomparable elements. The width of a poset is the size of the largest antichain; Dilworth's theorem relates width to decomposition into chains.

A lattice is a poset in which any two elements have a least upper bound (join) and greatest lower bound (meet). Lattices generalize Boolean algebras and arise in various areas of algebra and combinatorics. The dual poset, obtained by reversing the order, often clarifies dual properties.

Morphisms between posets are order-preserving (monotone) maps f:P→Q with a ≤P b implying f(a) ≤Q f(b). If such a map is bijective and its inverse is order-preserving, it is an isomorphism. Finite posets are often studied up to isomorphism, with automorphisms describing symmetries.