In mathematics, an upper set, or upward closed 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. In symbols,
![\forall x\forall y\left[x \le y \and x \in Y \Rightarrow \; y \in Y\right].](http://upload.wikimedia.org/math/f/f/f/fff52898933c9c5ff8ae96ebd6af1356.png)
The dual notion is lower set (alternatively, down set, decreasing set, initial segment; the set is downward closed), 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. In symbols,
![\forall x\forall y\left[x \le y \and y \in Y \Rightarrow \; x \in Y\right].](http://upload.wikimedia.org/math/0/9/c/09c40371659e3f3e6f7227c927166c78.png)
Contents |
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.
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.
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 ed.). Cambridge University Press. ISBN 0-521-78451-4.
External links
Open source encyclopedia content modification information:
This page was last modified on 25 October 2009 at 19:11.
Authorship and Review
Open source encyclopedia content provided here is not reviewed directly by MedLibrary.org. Content is sourced directly from Wikipedia and is authored by an open community of volunteers. It is not produced by or in any way affiliated with MedLibrary.org.
Usage Guidelines
This article is licensed under the GNU Free Documentation License. It uses material from the Wikipedia article on "Initial segment", which is available in its original form here:
http://en.wikipedia.org/w/index.php?title=Initial_segment
All material adapted used from Wikipedia is available under the terms of the GNU Free Documentation License. Wikipedia® itself is a registered trademark of the Wikimedia Foundation, Inc.