Upper set

In order theory, an upper set (also known as an upset) is a subset U of a preorder (P, \leq) such that if p \in U and p \leq q, then q \in U.^[1] This upward-closed property ensures that the subset includes all elements greater than or equal to any of its members under the given order relation.^[2] Upper sets generalize naturally from preorders—reflexive and transitive binary relations—to partially ordered sets (posets), where the relation is additionally antisymmetric.^[1] The dual concept to an upper set is a lower set (or down-set), which is downward closed: if p \in L and q \leq p, then q \in L.^[2] In posets, the collection of all upper sets, denoted U(P), itself forms a poset under inclusion, where U \leq V if U \subseteq V.^[1] This structure highlights the duality principle in order theory, whereby many theorems and constructions have symmetric counterparts by reversing the order relation.^[2] Principal upper sets, generated by a single element x \in P as \{ y \in P \mid x \leq y \}, provide a basis for understanding more complex upper sets.^[1] Upper sets play a foundational role in several mathematical areas beyond basic order theory. In category theory, preorders can be viewed as thin categories (with at most one morphism between objects), and upper sets correspond to subcategories closed under existing morphisms.^[1] They underpin the Alexandroff topology on a poset, where open sets are precisely the upper sets, yielding a topological space that reflects the order structure.^[2] In domain theory and lattice theory, upper sets relate to filters and ideals; for instance, a filter is an inhabited upper set closed under finite meets, while ideals are directed lower sets.^[2] Applications extend to applied category theory, such as modeling feasibility in resource theories via profunctors, where upper sets represent sets of achievable outcomes assuming monotonicity.^[1] Examples illustrate the concept clearly. In the poset of natural numbers (\mathbb{N}, \leq), the subset \{ n \in \mathbb{N} \mid n \geq 5 \} is an upper set, as any larger number is also included.^[1] For the boolean preorder \{ \text{false}, \text{true} \} with \text{false} \leq \text{true}, the upper sets are \emptyset, \{ \text{true} \}, and \{ \text{false}, \text{true} \}.^[1] In the real numbers (\mathbb{R}, \leq), \{ x \in \mathbb{R} \mid x > 0 \} qualifies as an upper set.^[1] These properties make upper sets essential for analyzing completeness, compactness, and fixed points in ordered structures.

Fundamentals

Definition

In order theory, a partially ordered set, or poset, is a set X equipped with a binary relation \leq that is reflexive, antisymmetric, and transitive. An upper set (also called an upset or upward closed set) in a poset (X, \leq) is a subset S \subseteq X such that for all s \in S and x \in X, if s \leq x, then x \in S. This property ensures that S is closed under the order relation in the upward direction: once an element is included, all elements greater than or equal to it must also be included. Equivalently, S can be defined using the strict order < (where s < x if s \leq x and s \neq x): for all s \in S and x \in X, if s < x, then x \in S.^[3] In posets, these two formulations are equivalent because the reflexive nature of \leq guarantees that equal elements are already contained in S, and the upward closure under < extends naturally to \leq.^[3] The notation \uparrow is commonly used to denote the upward direction; for example, the principal upper set generated by an element s \in X is s^\uparrow = \{x \in X \mid s \leq x\}.^[3] The dual concept to an upper set is a lower set (or down-set), which is closed downward under the order.

Duality with lower sets

In order theory, the concept of an upper set in a partially ordered set (poset) (X, ≤) has a symmetric dual known as a lower set, or down-set, which is a subset T ⊆ X such that if t ∈ T and y ∈ X satisfies y ≤ t, then y ∈ T.^[4] This definition captures the downward closure property, ensuring that all elements below any member of the set are included.^[5] Lower sets thus mirror the upward closure of upper sets but in the reverse direction along the order relation.^[6] The duality principle in order theory establishes a precise correspondence between upper sets and lower sets through order reversal. Specifically, if the order ≤ on X is reversed to form the opposite poset (X, ≥), then the upper sets of (X, ≤) become exactly the lower sets of (X, ≥), and vice versa.^[4] Formally, a subset U ⊆ X is an upper set in (X, ≤) if and only if its complement (in the set-theoretic sense, when considering the full power set) transforms appropriately under this reversal, but the key bijection maps the collection of all upper sets in the original poset to the collection of all lower sets in the dual poset.^[5] This symmetry, often denoted by considering the dual poset X^{op}, underpins many theorems in order theory by allowing proofs for one concept to be adapted to its dual via simple order inversion.^[6] Principal lower sets provide a canonical example of this duality, defined as ↓x = { y \in X \mid y \leq x } for each x \in X, which is the dual counterpart to the principal upper set ↑x = { y \in X \mid x \leq y }.^[4] These principal lower sets are the smallest lower sets containing x and are generated by single elements, paralleling how principal upper sets are generated upward from their base.^[5] Every lower set can be expressed as a union of principal lower sets, just as upper sets arise from unions of principal upper sets.^[6] Upper and lower sets serve as foundational building blocks in lattice theory, where directed lower sets (closed under finite joins) form ideals, and directed upper sets (closed under finite meets) form filters.^[4] This duality extends to lattice homomorphisms and representations, enabling the study of lattice varieties through dual pairs of ideals and filters, as seen in distributive lattices where such structures facilitate embeddings into power sets.^[4] In broader order-theoretic contexts, they underpin closure systems and topological dualities, such as those in domain theory.^[6]

Properties

Closure under operations

Upper sets exhibit closure under certain set-theoretic operations, reflecting their structural properties in partially ordered sets (posets). Specifically, the intersection of any family of upper sets in a poset P—whether finite or infinite—is itself an upper set. To see this, suppose \{U_i\}_{i \in I} is a family of upper sets and x \in \bigcap_{i \in I} U_i. For any y \in P with y \geq x, y belongs to each U_i by the upper set property of U_i, so y \in \bigcap_{i \in I} U_i. This holds for arbitrary families, including infinite ones, due to the pointwise nature of the intersection.^[7]^[8] Similarly, the union of any family of upper sets is an upper set. Consider x \in \bigcup_{i \in I} U_i, so x \in U_j for some j \in I. If y \geq x, then y \in U_j since U_j is upper, and thus y \in \bigcup_{i \in I} U_i. Again, this property extends to arbitrary unions, emphasizing the completeness of upper sets under these operations in the lattice of subsets ordered by inclusion.^[7]^[8] Upper sets do not preserve under complementation: the complement of an upper set is a lower set, but generally not an upper set. In a poset P, if U \subseteq P is upper, its complement L = P \setminus U satisfies the lower set condition—if z \in L and w \leq z, then w \in L (for if w \notin L, then w \in U, and since z \geq w and U is upper, z \in U, contradicting z \in L). However, L need not be upper; for example, in the poset of natural numbers \mathbb{N} under the usual order, the upper set U = \{n \in \mathbb{N} \mid n \geq 5\} has complement L = \{1, 2, 3, 4\}, which contains 4 but not 5 despite $5 > 4.^[7]^[8] Finally, every poset P is itself an upper set within P, as for any x \in P and y \geq x, y remains in P by definition.^[7]

Lattice structure

In a partially ordered set (X, \leq), the collection of all upper sets, denoted U(X), ordered by inclusion \subseteq, forms a complete lattice.^[9]^[10] The meet operation in U(X) is given by the intersection of upper sets, which serves as the greatest lower bound under inclusion, since the intersection of any family of upper sets is itself an upper set.^[9] The join operation is the union of upper sets, acting as the least upper bound, as the union of any family of upper sets remains an upper set.^[9] The bottom element of U(X) is the empty set \emptyset, which is vacuously an upper set.^[9] The top element is the entire poset X, which is trivially an upper set.^[9] The lattice U(X) is distributive, as it is a sublattice of the power set lattice closed under unions and intersections, where these set operations distribute over each other.^[9]^[10] For finite posets, every finite distributive lattice is isomorphic to the lattice of upper sets of some poset.^[10] The principal upper sets \uparrow x = \{ y \in X \mid y \geq x \} embed the poset X order-reversingly into U(X), providing a conceptual link to completions such as the Dedekind-MacNeille completion, which can be constructed using cuts defined by upper and lower bounds within such lattices.^[9]^[10]

Closure operations

Upper closure

In a partially ordered set (poset) (X, \leq), the upper closure of a subset Y \subseteq X, denoted \uparrow Y, is defined as \uparrow Y = \{ x \in X \mid \exists y \in Y \text{ such that } y \leq x \}. This set consists of all elements in X that are greater than or equal to at least one element of Y, and it is the smallest upper set containing Y.^[11] For a singleton subset Y = \{x\}, the upper closure \uparrow x = \{ u \in X \mid x \leq u \} is known as the principal upper set generated by x. In the context of lattice theory, where the poset is a lattice, \uparrow x corresponds to the principal filter generated by x, which is the set of all elements greater than or equal to x under the lattice order.^[12] The upper closure operator \uparrow: 2^X \to 2^X satisfies the defining properties of a closure operator on the power set lattice. It is extensive, meaning \uparrow Y \supseteq Y for all Y \subseteq X, since reflexivity of \leq ensures each y \in Y satisfies y \leq y, placing y in \uparrow Y. It is monotonic, so if Y \subseteq Z, then \uparrow Y \subseteq \uparrow Z, as any element above some y \in Y is also above some element in the larger set Z. Finally, it is idempotent, with \uparrow(\uparrow Y) = \uparrow Y, because \uparrow Y is already an upper set: if z \in \uparrow Y, then z \geq y for some y \in Y, and by transitivity of \leq, any w \geq z satisfies w \geq y, so w \in \uparrow Y. These properties follow directly from the reflexive, transitive, and antisymmetric nature of the poset order.^[13]^[11]

Lower closure

In a partially ordered set (poset) (X, \leq), the lower closure of a subset Y \subseteq X, denoted \downarrow Y, is defined as \downarrow Y = \{ x \in X \mid \exists y \in Y \text{ such that } x \leq y \}.^[14] This is the smallest lower set containing Y, where a lower set (also called a down-set) is a subset L \subseteq X such that for all z \in L and w \in X with w \leq z, it holds that w \in L.^[15] A principal lower set is the lower closure generated by a single element, \downarrow x = \{ l \in X \mid l \leq x \} for some x \in X.^[16] The lower closure operator \downarrow: \mathcal{P}(X) \to \mathcal{P}(X) is a closure operator on the power set lattice \mathcal{P}(X), satisfying three key properties: it is extensive, meaning Y \subseteq \downarrow Y for all Y \subseteq X; idempotent, meaning \downarrow(\downarrow Y) = \downarrow Y for all Y \subseteq X; and monotonic, meaning if Y \subseteq Z, then \downarrow Y \subseteq \downarrow Z.^[17] These properties follow dually from the corresponding proofs for the upper closure operator, by reversing the order relation.^[14] The lower closure operator on (X, \leq) is the upper closure operator on the dual poset (X, \geq).^[18] In the context of lattice theory, principal lower sets coincide with principal ideals, which are the down-sets generated by a single element.^[16]

Applications and examples

In ordinal numbers

In set theory, the class of all ordinal numbers, often denoted Ord or On, forms a proper class poset under the membership relation ∈ (or equivalently the strict order <), where every non-empty subclass has a minimal element due to the well-ordering property.^[19] This structure is a total order extending the natural numbers transfinitely. Every ordinal α is itself a lower set (down-set) within Ord, as α consists precisely of all ordinals β < α, and thus if β ∈ α with γ < β, then γ ∈ β ⊆ α by transitivity of ordinals.^[19] Dually, an upper set (up-set) in Ord is a subclass U such that if α ∈ U and β ≥ α, then β ∈ U; these are precisely the final segments of the form {γ ∈ Ord | γ ≥ β} for some fixed ordinal β (the minimal element of U, if U is non-empty), along with the empty class and Ord itself.^[19] Such upper sets are closed under successors, since if α ∈ U then the successor α + 1 > α implies α + 1 ∈ U, and under limits above their elements: for an increasing sequence ⟨α_ξ | ξ < λ⟩ in U with λ a limit ordinal, the supremum sup α_ξ ≥ each α_ξ hence belongs to U. The well-ordered nature of Ord implies that every non-empty upper set U has a least element, namely its minimal ordinal β, making U the principal final segment starting at β; this is the dual of the fact that every non-empty subclass of Ord has a least element.^[19] In the context of cardinals, consider a regular cardinal κ (an uncountable regular limit ordinal). The poset of ordinals below κ inherits the well-ordering, and its non-empty upper sets are the final segments [β, κ) for β < κ. These are unbounded in κ (cofinal, with supremum κ) and closed: any increasing sequence of length less than κ from [β, κ) has supremum in [β, κ) by regularity of κ. Thus, such unbounded upper sets coincide with principal club sets (closed unbounded subsets) in κ.^[19]

In other posets

In the divisibility poset on the natural numbers, where m \leq n if m divides n, an upper set is a subset closed under taking multiples: if n is in the set and k is a multiple of n, then k must also be in the set.^[20] Principal upper sets in this poset are generated by a fixed divisor d, consisting of all multiples of d; for example, the principal upper set generated by 6 includes 6, 12, 18, 24, and so on.^[21] In the power set poset ordered by inclusion, filters are upper sets that are also closed under finite intersections: subsets that are upward-closed (if A is in the filter and A \subseteq B, then B is in the filter) and closed under finite intersections.^[22] Principal upper sets here correspond to the collection of all supersets of a fixed set S, forming a principal filter; for instance, in the power set of {1,2,3}, the principal upper set generated by {1} includes {1}, {1,2}, {1,3}, and {1,2,3}.^[22] In topology, upper sets play a key role in defining structures on posets. The Alexandroff topology on a poset (P, \leq) has as its open sets exactly the upper sets of P, making every upper set open and ensuring the topology reflects the order structure directly. In the Scott topology on a complete partial order (cpo), the open sets—known as Scott-open sets—are the upper sets that are inaccessible by directed suprema: if a directed set D has its supremum in the set, then some element of D must already be in it. This topology is fundamental for defining continuous functions in domain theory, where Scott continuity requires preserving directed suprema and being open in this topology.^[23] In lattice theory, filters are nonempty upper sets closed under finite meets.^[24] Ultrafilters are the maximal proper filters (maximal among filters not containing the bottom element), which cannot be properly extended while remaining filters; in distributive lattices, they coincide with prime filters.^[25] In computer science, particularly abstract interpretation for program analysis, upper sets in the lattice of program states (often the power set ordered by inclusion) represent over-approximations of reachable states, ensuring soundness by including all possible concrete behaviors within a safely larger abstract set.^[26] This framework, developed by Cousot and Cousot, uses such upper sets in collecting semantics to compute fixed points that bound the semantics from above, enabling static analyses like those for termination or resource usage.^[27]