Upper and lower sets

In mathematics, an upper set ${\displaystyle S}$ of a partially ordered set ${\displaystyle X}$ is a subset such that if s is in S and if x in X is larger than s, then x is in S. A lower set is defined similarly as being a subset S of X with the property that any element x of X that precedes an element of S is necessarily also an element of S.

Upper sets and lower sets are also known by many other names. An upper set may also be called an upward closed set, an up-set, an isotone set, or an order filter, while a lower set may also be called a downward closed set, down-set, decreasing set, semi-ideal, or order ideal.¹² However, the terms "order ideal" and "order filter" are also used for a more restrictive notion.³

Let ${\displaystyle (X,\leq )}$ be a preordered set (the same as a partially ordered set except the requirement ${\displaystyle x\leq y,\,y\leq x}$ implying ${\displaystyle x=y}$ is dropped).

An upper set in ${\displaystyle X}$ (also called an upward closed set, up set, increasing set, or an isotone set)¹ is a subset ${\displaystyle U}$ that is "closed under going up", in the following sense: for all ${\displaystyle u}$ in ${\displaystyle U}$ and ${\displaystyle x}$ in ${\displaystyle X}$, if ${\displaystyle u\leq x}$, then ${\displaystyle x}$ is in ${\displaystyle U}$.

The dual notion is a lower set (also called a downward closed set, down set, decreasing set, or a semi-ideal), which is a subset ${\displaystyle L}$ that is "closed under going down": for all ${\displaystyle l}$ in ${\displaystyle L}$ and all ${\displaystyle x}$ in ${\displaystyle X}$, if ${\displaystyle x\leq l}$, then ${\displaystyle x}$ is in ${\displaystyle L.}$

The term order ideal is sometimes used as a synonym for a lower set.⁴²⁵ However, an ideal is also commonly defined specifically as a lower set which is upward directed.³⁶ Dually, a filter is an upper set that is directed downward (that is, every finite subset has a lower bound).

For a well-ordered set, a lower set is usually called an initial segment.

The following properties are stated in terms of upper sets; the corresponding dual properties for lower sets also hold.

• 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 an 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.
• Every upper set ${\displaystyle Y}$ of a finite partially ordered set ${\displaystyle X}$ is equal to the smallest upper set containing all minimal elements of ${\displaystyle Y.}$
• 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 sets and lower sets appear in various fields of mathematics.

• In the totally ordered set of the real numbers ${\displaystyle (\mathbb {R} ,\leq )}$, lower sets include "left rays" like ${\displaystyle (-\infty ,3]}$ and ${\displaystyle (-\infty ,5)}$, as well as the empty set ${\displaystyle \emptyset }$ and the whole set. Upper sets include "right rays" like ${\displaystyle (3,\infty )}$ and ${\displaystyle [5,\infty )}$.
• In real analysis, a real number is often defined as a Dedekind cut. By definition, this is a nonempty proper lower subset of ${\displaystyle \mathbb {Q} }$ with no maximal element.
• Let ${\displaystyle X}$ be a topological space and ${\displaystyle x}$ a point in it. Let ${\displaystyle F}$ be the set of all (not-necessarily-open) neighborhoods of ${\displaystyle x}$. Then ${\displaystyle F}$ is an upper set in the power set of ${\displaystyle X}$ ordered by inclusion, since any set containing a neighborhood of the point is a neighborhood of that point.
• Any filter on a set ${\displaystyle X}$ is an upper set in the power set of ${\displaystyle X}$ ordered by inclusion. The previous example of the neighbourhood filter of a point in a topological space is an instance of this.
• Abstract simplicial complex - a set-family that is downwards-closed with respect to the containment relation.

Given an element ${\displaystyle x}$ of a preordered set ${\displaystyle (X,\leq ),}$ the upper closure or upward closure of ${\displaystyle x}$ is defined by

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

while the lower closure or downward closure of ${\displaystyle x}$ by

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

Upper and lower sets of the form ${\displaystyle \uparrow \!x}$ and ${\displaystyle \downarrow \!x}$ are called principal. The upper closure of an element is the same thing as the principal filter generated by that element, since it is also directed downward.

More generally, given a subset ${\displaystyle A\subset X,}$ the upper closure and lower closure of ${\displaystyle A}$ are defined as ${\displaystyle \uparrow \!A=\bigcup _{a\in A}\uparrow \!a}$ and ${\displaystyle \downarrow \!A=\bigcup _{a\in A}\downarrow \!a}$;⁷ they are, respectively, the smallest upper set and lower set containing ${\displaystyle A}$. The upper and lower closures, when viewed as functions from the power set of ${\displaystyle X}$ to itself, are examples of Kuratowski closure operators. 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.

In category theory, a poset can be (and often is) viewed as a category by writing a morphism ${\displaystyle x\to y}$ if and only if ${\displaystyle x\leq y}$. Then the lower closure ${\displaystyle \downarrow x}$ corresponds to the slice category over ${\displaystyle x}$, while the upper closure that under ${\displaystyle x}$.⁸

Let ${\displaystyle X}$ be a poset. Then we have⁹

${\displaystyle \eta :X\hookrightarrow {\mathfrak {P}}(X)}$

where ${\displaystyle {\mathfrak {P}}(X)}$ is the power set of ${\displaystyle X}$ and ${\displaystyle \eta (x)={\downarrow \!x}}$ is the lower closure of ${\displaystyle x}$. The map ${\displaystyle \eta }$ is an embedding in the sense it is injective and monotone:

${\displaystyle x\leq y\Longleftrightarrow {\downarrow \!x}\subseteq {\downarrow \!y}.}$¹⁰

Thus, the above construction can be used to replace a given ordering by set inclusion and also yields advantages such as that a least upper bound always exists (possibly outside the image of ${\displaystyle \eta }$); namely, a union. For example, this trick can be used to reduce a proof of Zorn's lemma to the case of posets of sets.¹¹

As Paul Taylor points out, the above ${\displaystyle \eta }$ is an analog of an embedding in the Yoneda lemma in category theory.¹²¹³

The image of ${\displaystyle \eta }$ lies in the set of all lower sets in ${\displaystyle X}$. But, more specifically, it lies in the set of all directed lower sets (ideals), denoted by ${\displaystyle I(X)}$ and called the ideal completion of ${\displaystyle X}$.¹⁴ Then ${\displaystyle \eta :X\hookrightarrow I(X)}$ satisfies the universal property that makes ${\displaystyle I}$ a free functor in the sense: it is left adjoint to the forgetful functor from the category of dcpos to the category of posets.¹⁵

A function between posets is said to be Scott-continuous if it is monotone (it preserves ${\displaystyle \leq }$) and preserves directed sups.¹⁶ Then a poset ${\displaystyle X}$ carries a topology where a subset ${\displaystyle U}$ is open if and only if the characteristic function on ${\displaystyle U}$ is Scott-continuous. This topology is called the Scott topology. Explicitly, an open set in this topology is exactly an upper set such that if ${\displaystyle \textstyle \sup _{i}x_{i}\in U}$ for a directed set ${\displaystyle x_{i}}$, then ${\displaystyle x_{i}}$ is in ${\displaystyle U}$ for some ${\displaystyle i}$.¹⁷ The intuition here is that a sup corresponds to the best approximation and so if the best approximation is available in the set, some finite approximation is already in that set.

The Scott topology appears prominently in domain theory, a branch of order theory with a strong connection to computer science. Like the Zariski topology used in algebraic geometry, the Scott topology is an important example of a non-Hausdorff topological space.

The set of all lower sets of a given poset ${\displaystyle P}$ may be ordered by inclusion. The resulting poset, denoted ${\displaystyle J(P)}$, is a lattice (meaning that every subset of ${\displaystyle J(P)}$ has a least upper bound and a greatest lower bound), and indeed a distributive lattice (meaning that the two operations of least upper bound and greatest lower bound distribute over one another). Birkhoff's representation theorem asserts that every finite distributive lattice arises (up to isomorphism) in this way as the lattice of lower sets of a unique finite poset.

• 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.}$