Upper set
From Wikipedia, the free encyclopedia
In mathematics, an upper set is a subset Y of a given partially ordered set (X,≤) such that, for all elements x and y, if x is less than or equal to y and x is an element of Y, then y is also in Y. More formally,
![\forall x\forall y\left[x \le y \and x \in Y \Rightarrow \; y \in Y\right].](../../../math/f/f/f/fff52898933c9c5ff8ae96ebd6af1356.png)
The dual notion is lower set (alternatively, down set or decreasing set), which is any subset Y of a given partially ordered set (X,≤) such that, for all elements x and y, if x is less than or equal to y and y is an element of Y, then x is also in Y. More formally,
![\forall x\forall y\left[x \le y \and y \in Y \Rightarrow \; x \in Y\right].](../../../math/0/9/c/09c40371659e3f3e6f7227c927166c78.png)
[edit] Properties
Every partially ordered set is an upper set of itself. The intersection 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, 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.
[edit] References
- Blanck, J. (2000) "Domain representations of topological spaces". Theoretical Computer Science, 247, 229–255.
- Hoffman, K. H. (2001), The low separation axioms (T0) and (T1)
- Davey, B.A., and Priestley, H. A. (2002). Introduction to Lattices and Order, Second Edition, Cambridge University Press. ISBN 0521784514.
