Initial segment

In mathematics, an upper set (also called an upward closed set or just an upset) of a partially ordered set (X,≤) is a subset U with the property that, if x is in U and x≤y, then y is in U.

The dual notion is lower set (alternatively, down set, decreasing set, initial segment; the set is downward closed), which is a subset L with the property that, if x is in L and y≤x, then y is in L.

Properties

  • Every partially ordered set is an upper set of itself.
  • The intersection and the union 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.

See also

  • Cofinal set – a subset U of a partially ordered set (P,≤) that contains for every element x of P an element y such that x ≤ y

References

  • Blanck, J. (2000) "Domain representations of topological spaces". Theoretical Computer Science, 247, 229–255.
  • Hoffman, K. H. (2001),
  • ru:Частично упорядоченное множество#Верхнее и нижнее множество
This article was sourced from Creative Commons Attribution-ShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and USA.gov, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for USA.gov and content contributors is made possible from the U.S. Congress, E-Government Act of 2002.
 
Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.
 
By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a non-profit organization.