downsets

Downsets are a basic notion in order theory. Let P be a partially ordered set with relation ≤. A subset D ⊆ P is called a downset (also called a lower set or, in some texts, an order ideal) if whenever x ∈ D and y ≤ x in P, then y ∈ D. Equivalently, D is downward closed: it contains all predecessors of its elements.

Examples help illustrate the concept. In the set N of natural numbers with the usual order, a downset is either empty or of the form {0,1,...,n} for some n. In the powerset of a base set, ordered by inclusion, a downset is any family of sets closed under taking subsets: if A is in the family and B ⊆ A, then B is also in the family.

The collection D(P) of all downsets of P forms a complete lattice under inclusion. The join (least upper bound) of a family of downsets is their union, and the meet (greatest lower bound) is their intersection. The bottom and top elements are the empty set and P, respectively. Each principal downset ↓p = {x ∈ P : x ≤ p} plays a generating role: every downset D is the union of the principal downsets ↓p for p ∈ D.

Downsets are dual to upsets (upper sets), which are closed upward under the order. The theory of downsets connects to representation theorems: for finite distributive lattices, there is a poset P such that the lattice is isomorphic to the lattice of downsets of P (Birkhoff's representation).

Applications appear in lattice theory, domain theory, and combinatorics, where downsets provide a convenient way to study order-structural properties via their principal components and closure properties.