Hubbry Logo
Upper setUpper setMain
Open search
Upper set
Community hub
Upper set
logo
8 pages, 0 posts
0 subscribers
Be the first to start a discussion here.
Be the first to start a discussion here.
Upper set
Upper set
Upper set
View on Wikipedia
from Wikipedia
A Hasse diagram of the divisors of , ordered by the relation is divisor of, with the upper set colored green. The white sets form the lower set

In mathematics, an upper set (also called an upward closed set, an upset, or an isotone set in X)[1] of a partially ordered set is a subset with the following property: if s is in S and if x in X is larger than s (that is, if ), then x is in S. In other words, this means that any x element of X that is greater than or equal to some element of S is necessarily also an element of S, or,

The term lower set (also called a downward closed set, down set, decreasing set, initial segment, or semi-ideal) is defined similarly as being a subset S of X with the property that any element x of X that is to some element of S is necessarily also an element of S.

Definition

[edit]

Let be a preordered set. An upper set in (also called an upward closed set, up set, increasing set, or an isotone set)[1] is a subset that is "closed under going up", in the sense that

for all and all if then

The dual notion is a lower set (also called a downward closed set, down set, decreasing set, initial segment, or a semi-ideal), which is a subset that is "closed under going down", in the sense that

for all and all if then

The terms order ideal or ideal are sometimes used as synonyms for lower set.[2][3][4] This choice of terminology fails to reflect the notion of an ideal of a lattice because a lower set of a lattice is not necessarily a sublattice.[2]

Properties

[edit]
  • Every preordered set is an upper set of itself.
  • The intersection and the union of any family of upper sets is again an upper set.
  • The complement of any upper set is a lower set, and vice versa.
  • Given a partially ordered set the family of upper sets of ordered with the inclusion relation is a complete lattice, the upper set lattice.
  • Given an arbitrary subset of a partially ordered set the smallest upper set containing is denoted using an up arrow as (see upper closure and lower closure).
    • Dually, the smallest lower set containing is denoted using a down arrow as
  • A lower set is called principal if it is of the form where is an element of
  • Every lower set of a finite partially ordered set is equal to the smallest lower set containing all maximal elements of
    • where denotes the set containing the maximal elements of
  • A directed lower set is called an order ideal.
  • For partial orders satisfying the descending chain condition, antichains and upper sets are in one-to-one correspondence via the following bijections: map each antichain to its upper closure (see below); conversely, map each upper set to the set of its minimal elements. This correspondence does not hold for more general partial orders; for example the sets of real numbers and are both mapped to the empty antichain.

Upper closure and lower closure

[edit]

Given an element of a partially ordered set the upper closure or upward closure of denoted by or is defined by while the lower closure or downward closure of , denoted by or is defined by

The sets and are, respectively, the smallest upper and lower sets containing as an element. More generally, given a subset define the upper/upward closure and the lower/downward closure of denoted by and respectively, as and

In this way, and where upper sets and lower sets of this form are called principal. The upper closure and lower closure of a set are, respectively, the smallest upper set and lower set containing it.

The upper and lower closures, when viewed as functions from the power set of to itself, are examples of closure operators since they satisfy all of the Kuratowski closure axioms. As a result, the upper closure of a set is equal to the intersection of all upper sets containing it, and similarly for lower sets. (Indeed, this is a general phenomenon of closure operators. For example, the topological closure of a set is the intersection of all closed sets containing it; the span of a set of vectors is the intersection of all subspaces containing it; the subgroup generated by a subset of a group is the intersection of all subgroups containing it; the ideal generated by a subset of a ring is the intersection of all ideals containing it; and so on.)

Ordinal numbers

[edit]

An ordinal number is usually identified with the set of all smaller ordinal numbers. Thus each ordinal number forms a lower set in the class of all ordinal numbers, which are totally ordered by set inclusion.

See also

[edit]
  • Abstract simplicial complex (also called: Independence system) - a set-family that is downwards-closed with respect to the containment relation.
  • Cofinal set – a subset of a partially ordered set that contains for every element some element such that

References

[edit]
Revisions and contributorsEdit on WikipediaRead on Wikipedia

Upper set

View on Grokipedia
from Grokipedia
In , an upper set (also known as an upset) is a UU of a (P,≤)(P, \leq) such that if p∈Up \in U and p≤qp \leq q, then q∈Uq \in U. 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. Upper sets generalize naturally from preorders—reflexive and transitive binary relations—to partially ordered sets (posets), where the relation is additionally antisymmetric. The dual concept to an upper set is a lower set (or down-set), which is downward closed: if p∈Lp \in L and q≤pq \leq p, then q∈Lq \in L. In posets, the collection of all upper sets, denoted U(P)U(P), itself forms a poset under inclusion, where U≤VU \leq V if U⊆VU \subseteq V. This structure highlights the duality principle in , whereby many theorems and constructions have symmetric counterparts by reversing the order relation. Principal upper sets, generated by a single element x∈Px \in P as {y∈P∣x≤y}\{ y \in P \mid x \leq y \}, provide a basis for understanding more complex upper sets. Upper sets play a foundational role in several mathematical areas beyond basic . In , preorders can be viewed as thin categories (with at most one between objects), and upper sets correspond to subcategories closed under existing morphisms. They underpin the Alexandroff topology on a poset, where open sets are precisely the upper sets, yielding a that reflects the order structure. In 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. Applications extend to , such as modeling feasibility in resource theories via profunctors, where upper sets represent sets of achievable outcomes assuming monotonicity. Examples illustrate the concept clearly. In the poset of natural numbers (N,≤)(\mathbb{N}, \leq), the subset {n∈N∣n≥5}\{ n \in \mathbb{N} \mid n \geq 5 \} is an upper set, as any larger number is also included. For the boolean preorder {false,true}\{ \text{false}, \text{true} \} with false≤true\text{false} \leq \text{true}, the upper sets are ∅\emptyset, {true}\{ \text{true} \}, and {false,true}\{ \text{false}, \text{true} \}. In the real numbers (R,≤)(\mathbb{R}, \leq), {x∈R∣x>0}\{ x \in \mathbb{R} \mid x > 0 \} qualifies as an upper set. These properties make upper sets essential for analyzing completeness, compactness, and fixed points in ordered structures.

Fundamentals

Definition

In , a , or poset, is a set XX equipped with a ≤\leq that is reflexive, antisymmetric, and transitive. An (also called an upset or upward closed set) in a poset (X,≤)(X, \leq) is a S⊆XS \subseteq X such that for all s∈Ss \in S and x∈Xx \in X, if s≤xs \leq x, then x∈Sx \in S. This property ensures that SS 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, SS can be defined using the strict order << (where s<xs < x if s≤xs \leq x and s≠xs \neq x): for all s∈Ss \in S and x∈Xx \in X, if s<xs < x, then x∈Sx \in S. In posets, these two formulations are equivalent because the reflexive nature of ≤\leq guarantees that equal elements are already contained in SS, and the upward closure under << extends naturally to ≤\leq. The notation ↑\uparrow is commonly used to denote the upward direction; for example, the principal upper set generated by an element s∈Xs \in X is s↑={x∈X∣s≤x}s^\uparrow = \{x \in X \mid s \leq x\}. 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. This definition captures the downward closure property, ensuring that all elements below any member of the set are included. Lower sets thus mirror the upward closure of upper sets but in the reverse direction along the order relation. 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. 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. 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. 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 }. 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. Every lower set can be expressed as a union of principal lower sets, just as upper sets arise from unions of principal upper sets. 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. 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. In broader order-theoretic contexts, they underpin closure systems and topological dualities, such as those in domain theory.

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 PP—whether finite or infinite—is itself an upper set. To see this, suppose {Ui}i∈I\{U_i\}_{i \in I} is a family of upper sets and x∈⋂i∈IUix \in \bigcap_{i \in I} U_i. For any y∈Py \in P with y≥xy \geq x, yy belongs to each UiU_i by the upper set property of UiU_i, so y∈⋂i∈IUiy \in \bigcap_{i \in I} U_i. This holds for arbitrary families, including infinite ones, due to the pointwise nature of the intersection. Similarly, the union of any family of upper sets is an upper set. Consider x∈⋃i∈IUix \in \bigcup_{i \in I} U_i, so x∈Ujx \in U_j for some j∈Ij \in I. If y≥xy \geq x, then y∈Ujy \in U_j since UjU_j is upper, and thus y∈⋃i∈IUiy \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. 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 PP, if U⊆PU \subseteq P is upper, its complement L=P∖UL = P \setminus U satisfies the lower set condition—if z∈Lz \in L and w≤zw \leq z, then w∈Lw \in L (for if w∉Lw \notin L, then w∈Uw \in U, and since z≥wz \geq w and UU is upper, z∈Uz \in U, contradicting z∈Lz \in L). However, LL need not be upper; for example, in the poset of natural numbers N\mathbb{N} under the usual order, the upper set U={n∈N∣n≥5}U = \{n \in \mathbb{N} \mid n \geq 5\} has complement L={1,2,3,4}L = \{1, 2, 3, 4\}, which contains 4 but not 5 despite 5>45 > 4. Finally, every poset PP is itself an upper set within PP, as for any x∈Px \in P and y≥xy \geq x, yy remains in PP by definition.

Lattice structure

In a partially ordered set (X,≤)(X, \leq), the collection of all upper sets, denoted U(X)U(X), ordered by inclusion ⊆\subseteq, forms a complete lattice. The meet operation in U(X)U(X) is given by the of upper sets, which serves as the greatest lower bound under inclusion, since the of any of upper sets is itself an upper set. The join operation is the union of upper sets, acting as the least upper bound, as the union of any of upper sets remains an upper set. The bottom element of U(X)U(X) is the ∅\emptyset, which is vacuously an upper set. The top element is the entire poset XX, which is trivially an upper set. The lattice U(X)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. For finite posets, every finite distributive lattice is isomorphic to the lattice of upper sets of some poset. The principal upper sets ↑x={y∈X∣y≥x}\uparrow x = \{ y \in X \mid y \geq x \} embed the poset XX order-reversingly into U(X)U(X), providing a conceptual link to completions such as the Dedekind-MacNeille completion, which can be constructed using cuts defined by within such lattices.

Closure operations

Upper closure

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

Lower closure

In a partially ordered set (poset) (X,≤)(X, \leq), the lower closure of a Y⊆XY \subseteq X, denoted ↓Y\downarrow Y, is defined as ↓Y={x∈X∣∃y∈Y such that x≤y}\downarrow Y = \{ x \in X \mid \exists y \in Y \text{ such that } x \leq y \}. This is the smallest lower set containing YY, where a lower set (also called a down-set) is a L⊆XL \subseteq X such that for all z∈Lz \in L and w∈Xw \in X with w≤zw \leq z, it holds that w∈Lw \in L. A principal lower set is the lower closure generated by a single element, ↓x={l∈X∣l≤x}\downarrow x = \{ l \in X \mid l \leq x \} for some x∈Xx \in X. The lower closure operator ↓:P(X)→P(X)\downarrow: \mathcal{P}(X) \to \mathcal{P}(X) is a closure operator on the power set lattice P(X)\mathcal{P}(X), satisfying three key : it is extensive, meaning Y⊆↓YY \subseteq \downarrow Y for all Y⊆XY \subseteq X; idempotent, meaning ↓(↓Y)=↓Y\downarrow(\downarrow Y) = \downarrow Y for all Y⊆XY \subseteq X; and monotonic, meaning if Y⊆ZY \subseteq Z, then ↓Y⊆↓Z\downarrow Y \subseteq \downarrow Z. These follow dually from the corresponding proofs for the upper closure operator, by reversing the order relation. The lower closure operator on (X,≤)(X, \leq) is the upper closure operator on the dual poset (X,≥)(X, \geq). In the context of lattice theory, principal lower sets coincide with principal ideals, which are the down-sets generated by a single element.

Applications and examples

In ordinal numbers

In , 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. 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. 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. 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. In the context of cardinals, consider a κ (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 κ.

In other posets

In the divisibility poset on the natural numbers, where m≤nm \leq n if mm divides nn, an upper set is a subset closed under taking multiples: if nn is in the set and kk is a multiple of nn, then kk must also be in the set. Principal upper sets in this poset are generated by a fixed dd, consisting of all multiples of dd; for example, the principal upper set generated by 6 includes 6, 12, 18, 24, and so on. 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 AA is in the filter and A⊆BA \subseteq B, then BB is in the filter) and closed under finite intersections. Principal upper sets here correspond to the collection of all supersets of a fixed set SS, 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}. In , upper sets play a key role in defining structures on posets. The Alexandroff topology on a poset (P,≤)(P, \leq) has as its open sets exactly the upper sets of PP, 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 DD has its supremum in the set, then some element of DD must already be in it. This topology is fundamental for defining continuous functions in , where Scott continuity requires preserving directed suprema and being open in this topology. In lattice theory, filters are nonempty upper sets closed under finite meets. 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. 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. 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.
Add your contribution
Related Hubs
User Avatar
No comments yet.