In mathematics, an upper set S {\displaystyle S} of a partially ordered set X {\displaystyle X} is a subset such that if s is in S and if x in X is larger than s, then x is in S. A lower set is defined similarly as being a subset S of X with the property that any element x of X that precedes an element of S is necessarily also an element of S. Upper sets and lower sets are also known by many other names. An upper set may also be called an upward closed set, an up-set, an isotone set, or an order filter, while a lower set may also be called a downward closed set, down-set, decreasing set, semi-ideal, or order ideal. However, the terms "order ideal" and "order filter" are also used for a more restrictive notion.
Definition Let ( X , ≤ ) {\displaystyle (X,\leq )} be a preordered set (the same as a partially ordered set except the requirement x ≤ y , y ≤ x {\displaystyle x\leq y,\,y\leq x} implying x = y {\displaystyle x=y} is dropped). An upper set in X {\displaystyle X} (also called an upward closed set, up set, increasing set, or an isotone set) is a subset U {\displaystyle U} that is "closed under going up", in the following sense: for all u {\displaystyle u} in U {\displaystyle U} and x {\displaystyle x} in X {\displaystyle X} , if u ≤ x {\displaystyle u\leq x} , then x {\displaystyle x} is in U {\displaystyle U} . The dual notion is a lower set (also called a downward closed set, down set, decreasing set, or a semi-ideal), which is a subset L {\displaystyle L} that is "closed under going down": for all l {\displaystyle l} in L {\displaystyle L} and all x {\displaystyle x} in X {\displaystyle X} , if x ≤ l {\displaystyle x\leq l} , then x {\displaystyle x} is in L . {\displaystyle L.}
The term order ideal 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 , ≤ ) , {\displaystyle (X,\leq ),} the family of upper sets of X {\displaystyle X} ordered with the inclusion relation is a complete lattice, the upper set lattice. Every upper set Y {\displaystyle Y} of a finite partially ordered set X {\displaystyle X} is equal to the smallest upper set containing all minimal elements of Y . {\displaystyle 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 ∈ R : x > 0 } {\displaystyle \{x\in \mathbb {R} :x>0\}} and { x ∈ R : x > 1 } {\displaystyle \{x\in \mathbb {R} :x>1\}} are both mapped to the empty antichain.
Examples Upper sets and lower sets appear in various fields of mathematics.
… excerpt ends here. Continue reading the full article.
