Upper set
In mathematics, an upper set of a partially ordered set is a subset with the following property: if s is in S and if x in X is larger than s, then x is in S. In other words, this means that any x element of X that is greater than or equal to some element of S is necessarily also an element of S, or,
The term lower set is defined similarly as being a subset S of X with the property that any element x of X that is to some element of S is necessarily also an element of S.
Definition
Let be a preordered set.An ' in is a subset that is "closed under going up", in the sense that
The dual notion is a ', which is a subset that is "closed under going down", in the sense that
The terms ' or ' are sometimes used as synonyms for lower set. 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.
Properties
- 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 any upper set is a lower set, and vice versa.
- Given a partially ordered set the family of upper sets of ordered with the inclusion relation is a complete lattice, the upper set lattice.
- Given an arbitrary subset of a partially ordered set the smallest upper set containing is denoted using an up arrow as .
- * Dually, the smallest lower set containing is denoted using a down arrow as
- A lower set is called principal if it is of the form where is an element of
- Every lower set of a finite partially ordered set is equal to the smallest lower set containing all maximal elements of
- * where denotes the set containing the maximal elements of
- A directed lower set is called an order ideal.
- 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 ; 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 and are both mapped to the empty antichain.
Upper closure and lower closure
Given an element of a partially ordered set the upper closure or upward closure of denoted by or is defined bywhile the lower closure or downward closure of, denoted by or is defined by
The sets and are, respectively, the smallest upper and lower sets containing as an element.
More generally, given a subset define the upper/'upward closure and the lower/downward closure of denoted by and respectively, as
and
In this way, and where upper sets and lower sets of this form are called principal'. The [|upper closure and lower closure] of a set are, respectively, the smallest upper set and lower set containing it.
The upper and lower closures, when viewed as functions from the power set of to itself, are examples of closure operators since they satisfy all of the Kuratowski closure axioms. As a result, the upper closure of a set is equal to the intersection of all upper sets containing it, and similarly for lower sets.