Upper set

From Wikipedia, the free encyclopedia
Jump to navigation Jump to search
The powerset algebra of the set {1,2,3,4} with the upset ↑{1} colored green. The white sets form the downset ↓{2,3,4}.

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 xy, 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 yx, 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]


  • 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.
  • 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, xy}. 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.

Ordinal numbers[edit]

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[edit]

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


  1. ^ a b Davey & Priestley, Introduction to Lattices and Order (Second Edition), 2002, p. 20 and 44
  2. ^ Stanley, R.P. (2002). Enumerative combinatorics. Cambridge studies in advanced mathematics. 1. Cambridge University Press. p. 100. ISBN 978-0-521-66351-9.
  3. ^ Lawson, M.V. (1998). Inverse semigroups: the theory of partial symmetries. World Scientific. p. 22. ISBN 978-981-02-3316-7.