# Upper set

In mathematics, an **upper set** (also called an **upward closed** set or just an **upset**) of a partially ordered set (*X*,≤) is a subset *U* with the property that, if *x* is in *U* and *x*≤*y*, then *y* is in *U*.

The dual notion is **lower set** (alternatively, **down set**, **decreasing set**, **initial segment**, **semi-ideal**; the set is **downward closed**), which is a subset *L* with the property that, if *x* is in *L* and *y*≤*x*, then *y* is in *L*.

The terms **order ideal** or **ideal** are sometimes used as synonyms for lower set.^{[1]}^{[2]}^{[3]} 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.^{[1]}

## Properties

- Every partially ordered set is an upper set of itself.
- The intersection and the union 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*,≤), the family of lower sets of*X*ordered with the inclusion relation is a complete lattice, the**down-set lattice**O(*X*). - Given an arbitrary subset
*Y*of an ordered set*X*, the smallest upper set containing*Y*is denoted using an up arrow as ↑*Y*.- Dually, the smallest lower set containing
*Y*is denoted using a down arrow as ↓*Y*.

- Dually, the smallest lower set containing
- A lower set is called
**principal**if it is of the form ↓{*x*} where*x*is an element of*X*. - Every lower set
*Y*of a finite ordered set*X*is equal to the smallest lower set containing all maximal elements of*Y*:*Y*= ↓Max(*Y*) where Max(*Y*) denotes the set containing the maximal elements of*Y*. - A directed lower set is called an order ideal.
- The minimal elements of any upper set form an antichain.
- Conversely any antichain
*A*determines an upper set {*x*: for some*y*in*A*,*x*≥*y*}. For partial orders satisfying the descending chain condition this correspondence between antichains and upper sets is 1-1, but for more general partial orders this is not true.

- Conversely any antichain

## 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

- Cofinal set – a subset
*U*of a partially ordered set (*P*,≤) that contains for every element*x*of*P*an element*y*such that*x*≤*y*

## References

- 1 2 Davey & Priestley,
*Introduction to Lattices and Order*(Second Edition), 2002, p. 20 and 44 - ↑ Stanley, R.P. (2002).
*Enumerative combinatorics*. Cambridge studies in advanced mathematics.**1**. Cambridge University Press. p. 100. ISBN 978-0-521-66351-9. - ↑ 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**: 229–255. doi:10.1016/s0304-3975(99)00045-6. - Hoffman, K. H. (2001),
*The low separation axioms (T*_{0}) and (T_{1}) - Davey, B.A. & Priestley, H. A. (2002).
*Introduction to Lattices and Order*(2nd ed.). Cambridge University Press. ISBN 0-521-78451-4.