Upper set

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

A Hasse diagram of the divisors of $210$, ordered by the relation is divisor of, with the upper set $\uparrow 2$ colored green. The white sets form the lower set $\downarrow 105.$

In mathematics, an upper set (also called an upward closed set, an upset, or an isotone set in X) of a partially ordered set $(X,\le )$ is a subset $S\subseteq X$ with the following property: if s is in S and if x in X is larger than s (that is, if $s<x$), 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,

$a\in S\wedge b\ge a⟹b\in 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 $\le$ to some element of S is necessarily also an element of S.

Definition

Let $(X,\le )$ be a preordered set. An upper set in $X$ (also called an upward closed set, up set, increasing set, or an isotone set) is a subset $U\subseteq X$ that is "closed under going up", in the sense that

for all $u\in U$ and all $x\in X,$ if $u\le x$ then $x\in U.$

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 $L\subseteq X$ that is "closed under going down", in the sense that

for all $l\in L$ and all $x\in X,$ if $x\le l$ then $x\in L.$

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

Upper closure and lower closure

Given an element $x$ of a partially ordered set $(X,\le ),$ the upper closure or upward closure of $x,$ denoted by $x^{\uparrow X},$ $x^{\uparrow },$ or $\uparrow x,$ is defined by $$x^{\uparrow X}=\uparrow x=\{u\in X:x\le u\}$$ while the lower closure or downward closure of $x$, denoted by $x^{\downarrow X},$ $x^{\downarrow },$ or $\downarrow x,$ is defined by $$x^{\downarrow X}=\downarrow x=\{l\in X:l\le x\}.$$

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

In this way, $\uparrow x=\uparrow \{x\}$ and $\downarrow x=\downarrow \{x\},$ 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 $X$ 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 $U$ of a partially ordered set $(X,\le )$ that contains for every element $x\in X,$ some element $y$ such that $x\le y.$

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. Retrieved 2014-07-21. 
• 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:Частично упорядоченное множество#Верхнее и нижнее множество