# Upper set

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,\leq )$ 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 $\,\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 $\,\leq \,$ to some element of S is necessarily also an element of S.

## Definition

Let $(X,\leq )$ be a preordered set. An upper set in $X$ (also called an upward closed set, an upset, 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\leq 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 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\leq 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 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 $(X,\leq ),$ 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 \operatorname {Max} (Y)$ where $\operatorname {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 {R} :x>0\}$ and $\{x\in \mathbb {R} :x>1\}$ are both mapped to the empty antichain.

## Upper closure and lower closure

Given an element $x$ of a partially ordered set $(X,\leq ),$ 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\leq 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\leq 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.