Upper 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 ${\displaystyle (X,\leq )}$ is a subset ${\displaystyle S\subseteq X}$ with the following property: if s is in S and if x in X is larger than s (that is, if ${\displaystyle s<x}$), then x is in S. In other words, this means that any x element of X that is ${\displaystyle \,\geq \,}$ 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 ${\displaystyle \,\leq \,}$ to some element of S is necessarily also an element of S.

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

Definition

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

for all ${\displaystyle u\in U}$  and all ${\displaystyle x\in X,}$  if ${\displaystyle u\leq x}$  then ${\displaystyle x\in U.}$ 

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

for all ${\displaystyle l\in L}$  and all ${\displaystyle x\in X,}$  if ${\displaystyle x\leq l}$  then ${\displaystyle x\in L.}$ 

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

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

Upper closure and lower closure

Given an element ${\displaystyle x}$  of a partially ordered set ${\displaystyle (X,\leq ),}$  the upper closure or upward closure of ${\displaystyle x,}$  denoted by ${\displaystyle x^{\uparrow X},}$  ${\displaystyle x^{\uparrow },}$  or ${\displaystyle \uparrow \!x,}$  is defined by

$${\displaystyle x^{\uparrow X}=\;\uparrow \!x=\{u\in X:x\leq u\}}$$

 

while the lower closure or downward closure of ${\displaystyle x}$ , denoted by ${\displaystyle x^{\downarrow X},}$  ${\displaystyle x^{\downarrow },}$  or ${\displaystyle \downarrow \!x,}$  is defined by

$${\displaystyle x^{\downarrow X}=\;\downarrow \!x=\{l\in X:l\leq x\}.}$$

 

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

$${\displaystyle A^{\uparrow X}=A^{\uparrow }=\bigcup _{a\in A}\uparrow \!a}$$

 

and

$${\displaystyle A^{\downarrow X}=A^{\downarrow }=\bigcup _{a\in A}\downarrow \!a.}$$

 

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

References

1. Dolecki & Mynard 2016, pp. 27–29.
2. Brian A. Davey; Hilary Ann Priestley (2002). Introduction to Lattices and Order (2nd ed.). Cambridge University Press. pp. 20, 44. ISBN 0-521-78451-4. LCCN 2001043910.
3. Stanley, R.P. (2002). Enumerative combinatorics. Cambridge studies in advanced mathematics. Vol. 1. Cambridge University Press. p. 100. ISBN 978-0-521-66351-9.
4. Lawson, M.V. (1998). Inverse semigroups: the theory of partial symmetries. World Scientific. p. 22. ISBN 978-981-02-3316-7.

• Blanck, J. (2000). "Domain representations of topological spaces" (PDF). Theoretical Computer Science. 247 (1–2): 229–255. doi:10.1016/s0304-3975(99)00045-6.
• 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),