Upper and lower sets

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)^[1] 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.^[4][2][5] However, an ideal is also commonly defined specifically as a lower set which is upward directed.^[3][6] Dually, a filter is an upper set that is directed downward (that is, every pair of elements in the set has a common 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.

Summarize Timeline Top Qs Fact Check

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\}.}$^[7]

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\subseteq 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}$;^{[citation needed]} 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}$.^[8]

Let ${\displaystyle X}$ be a poset. Then we have^[9]

${\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}.}$^[10]

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.^[11]

As Paul Taylor points out, the above ${\displaystyle \eta }$ is an analog of an embedding in the Yoneda lemma in category theory.^[12][13]

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}$.^[14] 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.^[15]

A function between posets is said to be Scott-continuous if it is monotone (it preserves ${\displaystyle \leq }$) and preserves directed sups.^[16] 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}$.^[17] 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.

• 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.}$
• Filter and ideal - upper and lower sets with the additional property of being directed.

• Upper topology