Upper and lower sets

Let (X, \leq) be a preordered set (the same as a partially ordered set except the requirement x \le y, \, y \le x implying x = y is dropped). An in X (also called an , , , or an ) is a subset U that is "closed under going up", in the following sense: for all u in U and x in X, if u \le x, then x is in U. The dual notion is a (also called a , , , or a ), which is a subset L that is "closed under going down": for all l in L and all x in X, if x \leq l, then x is in L. The term is sometimes used as a synonym for a lower set. However, an ideal is also commonly defined specifically as a lower set which is upward directed. Dually, a filter is an upper set that is directed downward (that is, every finite subset has a lower bound). For a well-ordered set, a lower set is usually called an initial segment. ==Properties ==

The following properties are stated in terms of upper sets; the corresponding dual properties for lower sets also hold. • 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 an 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. • Every upper set Y of a finite partially ordered set X is equal to the smallest upper set containing all minimal elements of Y. • 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 \{ x \in \R: x > 0 \} and \{ x \in \R: x > 1 \} are both mapped to the empty antichain. ==Upper closure and lower closure==

Given an element x of a preordered set (X, \leq), the upper closure or upward closure of x is defined by :\uparrow\! x = \{ u \in X : x \leq u\} while the lower closure or downward closure of x by :\downarrow\! x = \{l \in X : l \leq x\}. Upper and lower sets of the form \uparrow\! x and \downarrow\! x are called principal. The upper closure of an element is the same thing as the principal filter generated by that element, since it is also directed downward. More generally, given a subset A \subset X, the upper closure and lower closure of A are defined as \uparrow\! A = \bigcup_{a \in A} \uparrow\!a and \downarrow\! A = \bigcup_{a \in A} \downarrow\!a; Let X be a poset. Then we have :\eta : X \hookrightarrow \mathfrak{P}(X) where \mathfrak{P}(X) is the power set of X and \eta(x) = {\downarrow\! x} is the lower closure of x. The map \eta is an embedding in the sense it is injective and monotone: :x \le y \Longleftrightarrow {\downarrow\! x} \subseteq {\downarrow\! y}. Thus, the above construction can be used to replace a given ordering by set inclusion and also yields advantages such as that a least upper bound always exists (possibly outside the image of \eta); namely, a union. For example, this trick can be used to reduce a proof of Zorn's lemma to the case of posets of sets. As Paul Taylor points out, the above \eta is an analog of an embedding in the Yoneda lemma in category theory. The image of \eta lies in the set of all lower sets in X. But, more specifically, it lies in the set of all directed lower sets (ideals), denoted by I(X) and called the ideal completion of X. Then \eta : X \hookrightarrow I(X) satisfies the universal property that makes I a free functor in the sense: it is left adjoint to the forgetful functor from the category of dcpos to the category of posets. == Scott topology ==

A function between posets is said to be Scott-continuous if it is monotone (it preserves \le) and preserves directed sups. Then a poset X carries a topology where a subset U is open if and only if the characteristic function on U is Scott-continuous. This topology is called the Scott topology. Explicitly, an open set in this topology is exactly an upper set such that if \textstyle \sup_i x_i \in U for a directed set x_i, then x_i is in U for some i. The intuition here is that a sup corresponds to the best approximation and so if the best approximation is available in the set, some finite approximation is already in that set. The Scott topology appears prominently in domain theory, a branch of order theory with a strong connection to computer science. Like the Zariski topology used in algebraic geometry, the Scott topology is an important example of a non-Hausdorff topological space. ==Birkhoff's theorem==

The set of all lower sets of a given poset P may be ordered by inclusion. The resulting poset, denoted J(P), is a lattice (meaning that every subset of J(P) has a least upper bound and a greatest lower bound), and indeed a distributive lattice (meaning that the two operations of least upper bound and greatest lower bound distribute over one another). Birkhoff's representation theorem asserts that every finite distributive lattice arises (up to isomorphism) in this way as the lattice of lower sets of a unique finite poset. ==Related notions==

• 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. • Filter and ideal - upper and lower sets with the additional property of being directed. == See also ==