Upper set

Short description: Subset of a preorder that contains all larger elements

A Hasse diagram of the divisors of [math]\displaystyle{ 210 }[/math], ordered by the relation is divisor of, with the upper set [math]\displaystyle{ \uparrow 2 }[/math] colored green. The white sets form the lower set [math]\displaystyle{ \downarrow 105. }[/math]

In mathematics, an upper set (also called an upward closed set, an upset, or an isotone set in X) of a partially ordered set [math]\displaystyle{ (X, \leq) }[/math] is a subset [math]\displaystyle{ S \subseteq X }[/math] with the following property: if s is in S and if x in X is larger than s (that is, if [math]\displaystyle{ s \lt x }[/math]), then x is in S. In other words, this means that any x element of X that is [math]\displaystyle{ \,\geq\, }[/math] to some element of S is necessarily also an element of S. 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 [math]\displaystyle{ \,\leq\, }[/math] to some element of S is necessarily also an element of S.

Definition

Let [math]\displaystyle{ (X, \leq) }[/math] be a preordered set. An upper set in [math]\displaystyle{ X }[/math] (also called an upward closed set, an upset, or an isotone set) is a subset [math]\displaystyle{ U \subseteq X }[/math] that is "closed under going up", in the sense that

for all [math]\displaystyle{ u \in U }[/math] and all [math]\displaystyle{ x \in X, }[/math] if [math]\displaystyle{ u \leq x }[/math] then [math]\displaystyle{ x \in U. }[/math]

The dual notion is a lower set (also called a downward closed set, down set, decreasing set, initial segment, or semi-ideal), which is a subset [math]\displaystyle{ L \subseteq X }[/math] that is "closed under going down", in the sense that

for all [math]\displaystyle{ l \in L }[/math] and all [math]\displaystyle{ x \in X, }[/math] if [math]\displaystyle{ x \leq l }[/math] then [math]\displaystyle{ x \in L. }[/math]

The terms order ideal or ideal are sometimes used as synonyms for lower set. 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.

Properties

• Every partially ordered 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 [math]\displaystyle{ (X, \leq), }[/math] the family of upper sets of [math]\displaystyle{ X }[/math] ordered with the inclusion relation is a complete lattice, the upper set lattice.
• Given an arbitrary subset [math]\displaystyle{ Y }[/math] of a partially ordered set [math]\displaystyle{ X, }[/math] the smallest upper set containing [math]\displaystyle{ Y }[/math] is denoted using an up arrow as [math]\displaystyle{ \uparrow Y }[/math] (see upper closure and lower closure).
  • Dually, the smallest lower set containing [math]\displaystyle{ Y }[/math] is denoted using a down arrow as [math]\displaystyle{ \downarrow Y. }[/math]
• A lower set is called principal if it is of the form [math]\displaystyle{ \downarrow\{x\} }[/math] where [math]\displaystyle{ x }[/math] is an element of [math]\displaystyle{ X. }[/math]
• Every lower set [math]\displaystyle{ Y }[/math] of a finite partially ordered set [math]\displaystyle{ X }[/math] is equal to the smallest lower set containing all maximal elements of [math]\displaystyle{ Y }[/math]
  • [math]\displaystyle{ \downarrow Y = \downarrow \operatorname{Max}(Y) }[/math] where [math]\displaystyle{ \operatorname{Max}(Y) }[/math] denotes the set containing the maximal elements of [math]\displaystyle{ Y. }[/math]
• 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 [math]\displaystyle{ \{ x \in \R: x \gt 0 \} }[/math] and [math]\displaystyle{ \{ x \in \R: x \gt 1 \} }[/math] are both mapped to the empty antichain.

Upper closure and lower closure

Given an element [math]\displaystyle{ x }[/math] of a partially ordered set [math]\displaystyle{ (X, \leq), }[/math] the upper closure or upward closure of [math]\displaystyle{ x, }[/math] denoted by [math]\displaystyle{ x^{\uparrow X}, }[/math] [math]\displaystyle{ x^{\uparrow}, }[/math] or [math]\displaystyle{ \uparrow\! x, }[/math] is defined by [math]\displaystyle{ x^{\uparrow X} =\; \uparrow\! x = \{ u \in X : x \leq u\} }[/math] while the lower closure or downward closure of [math]\displaystyle{ x }[/math], denoted by [math]\displaystyle{ x^{\downarrow X}, }[/math] [math]\displaystyle{ x^{\downarrow}, }[/math] or [math]\displaystyle{ \downarrow\! x, }[/math] is defined by [math]\displaystyle{ x^{\downarrow X} =\; \downarrow\! x = \{l \in X : l \leq x\}. }[/math]

The sets [math]\displaystyle{ \uparrow\! x }[/math] and [math]\displaystyle{ \downarrow\! x }[/math] are, respectively, the smallest upper and lower sets containing [math]\displaystyle{ x }[/math] as an element. More generally, given a subset [math]\displaystyle{ A \subseteq X, }[/math] define the upper/upward closure and the lower/downward closure of [math]\displaystyle{ A, }[/math] denoted by [math]\displaystyle{ A^{\uparrow X} }[/math] and [math]\displaystyle{ A^{\downarrow X} }[/math] respectively, as [math]\displaystyle{ A^{\uparrow X} = A^{\uparrow} = \bigcup_{a \in A} \uparrow\!a }[/math] and [math]\displaystyle{ A^{\downarrow X} = A^{\downarrow} = \bigcup_{a \in A} \downarrow\!a. }[/math]

In this way, [math]\displaystyle{ \uparrow x = \uparrow\{x\} }[/math] and [math]\displaystyle{ \downarrow x = \downarrow\{x\}, }[/math] 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 [math]\displaystyle{ X }[/math] 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

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

• Abstract simplicial complex (also called: Independence system) - a set-family that is downwards-closed with respect to the containment relation.
• Cofinal set – a subset [math]\displaystyle{ U }[/math] of a partially ordered set [math]\displaystyle{ (X, \leq) }[/math] that contains for every element [math]\displaystyle{ x \in X, }[/math] some element [math]\displaystyle{ y }[/math] such that [math]\displaystyle{ x \leq y. }[/math]

References

• Blanck, J. (2000). "Domain representations of topological spaces". Theoretical Computer Science 247 (1–2): 229–255. doi:10.1016/s0304-3975(99)00045-6. http://www-compsci.swan.ac.uk/~csjens/pdf/top.pdf. 
• Dolecki, Szymon; Mynard, Frederic (2016). Convergence Foundations Of Topology. New Jersey: World Scientific Publishing Company. ISBN 978-981-4571-52-4. OCLC 945169917. 
• Hoffman, K. H. (2001), The low separation axioms (T₀) and (T₁)

ru:Частично упорядоченное множество#Верхнее и нижнее множество