downwardclosed

Downward closed describes a property of a subset within a partially ordered set. Specifically, a subset D of a poset (P, ≤) is downward closed if whenever x is in D and y ≤ x in P, then y is also in D. This concept is also called a lower set or, in some contexts, an order ideal. Downward closed sets are closed under taking smaller elements.

In simple terms, downward closed sets collect elements along with all elements not greater than them. For example, in the natural numbers with the usual order, downward closed sets are the initial segments: empty, {0}, {0,1}, {0,1,2}, and so on, including the entire set of natural numbers.

In the power set P(U) with the subset relation, a family F ⊆ P(U) is downward closed if A ∈ F implies every B ⊆ A is also in F. Such families are often called hereditary in combinatorics. Examples include all subsets of U of size at most k, or the family of finite subsets of N. These illustrate how downward closure corresponds to being closed under taking smaller or simpler elements.

Algebraically, the intersection of downward closed sets is downward closed, and, for any downward closed set D, one can write D as the downward closure of some generating set: D = ↓M = { y ∈ P | ∃ x ∈ M with y ≤ x }. In finite posets, D is determined by its maximal elements, which form an antichain.

Applications span order and lattice theory, formal concept analysis, and computer science, where downward closed (hereditary) properties model monotone behaviors and are central in data mining for characterizing families of itemsets.