A Hasse diagram of the divisors of 
  
    
      
        210
      
    
    {\displaystyle 210}
  
, ordered by the relation is divisor of, with the upper set 
  
    
      
        ↑
        2
      
    
    {\displaystyle \uparrow 2}
  
 colored green. The white sets form the lower set 
  
    
      
        ↓
        105.
      
    
    {\displaystyle \downarrow 105.}
A Hasse diagram of the divisors of , ordered by the relation is divisor of, with the upper set colored green. The white sets form the lower set

In mathematics, an upper set (also called an upward closed set, an upset, or an isotone set in X)[1] 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 (that is, if ), then x is in S. In words, this means that any x element of X that is to some element of S is necessarily also an element of S. The term lower set (also called a downward closed set, down set, decreasing set, initial segment, or semi-ideal) 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 upper set in (also called an upward closed set, an upset, or an isotone set)[1] is a subset that is "closed under going up", in the sense that

for all and all if then

The dual notion is a lower set (also called a downward closed set, down set, decreasing set, initial segment, or semi-ideal), which is a subset that is "closed under going down", in the sense that

for all and all if then

The terms order ideal or ideal are sometimes used as synonyms for lower set.[2][3][4] 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.[2]

Properties

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 by

while 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 closures 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 closures and lower closures 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. (Indeed, this is a general phenomenon of closure operators. For example, the topological closure of a set is the intersection of all closed sets containing it; the span of a set of vectors is the intersection of all subspaces containing it; the subgroup generated by a subset of a group is the intersection of all subgroups containing it; the ideal generated by a subset of a ring is the intersection of all ideals containing it; and so on.)

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.

See also

References

  1. ^ a b Dolecki & Mynard 2016, pp. 27–29.
  2. ^ a b Brian A. Davey; Hilary Ann Priestley (2002). Introduction to Lattices and Order (2nd ed.). Cambridge University Press. pp. 20, 44. ISBN 0-521-78451-4. LCCN 2001043910.
  3. ^ Stanley, R.P. (2002). Enumerative combinatorics. Cambridge studies in advanced mathematics. Vol. 1. Cambridge University Press. p. 100. ISBN 978-0-521-66351-9.
  4. ^ Lawson, M.V. (1998). Inverse semigroups: the theory of partial symmetries. World Scientific. p. 22. ISBN 978-981-02-3316-7.