initial segment

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 in $X$ (also called an , an , or an 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 (also called a , , , , or ), 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 or 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, \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\$ 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(Y)$ where $\operatorname(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 $\$ and $\$ 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^,$ $x^,$ or $\uparrow\! x,$ is defined by
$x^ =\; \uparrow\! x = \$
while the lower closure or downward closure of $x$, denoted by $x^,$ $x^,$ or $\downarrow\! x,$ is defined by
$x^ =\; \downarrow\! 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^$ and $A^$ respectively, as
$A^ = A^ = \bigcup_ \uparrow\!a$
and
$A^ = A^ = \bigcup_ \downarrow\!a.$

In this way, $\uparrow x = \uparrow\$ and $\downarrow x = \downarrow\,$ 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, \leq)$ that contains for every element $x \in X,$ some element $y$ such that $x \leq y.$

References

*
*
* Hoffman, K. H. (2001)
''The low separation axioms (T₀) and (T₁)''

{{Order theory

Order theory

ru:Частично упорядоченное множество#Верхнее и нижнее множество