Upper set

<h2 id="definition">Definition</h2>
<p>Let 
  
    
      
        (
        X
        ,
        ≤
        )
      
    
    {\displaystyle (X,\leq )}
  
 be a <a href="/facts/Preordered_set/uubzHSWm">preordered set</a>. 
An upper set in 
  
    
      
        X
      
    
    {\displaystyle X}
  
 (also called an upward closed set, an upset, or an isotone set)<a class="footnote-ref" id="fnref:2" href="#fn:2"><sup>2</sup></a> is a subset 
  
    
      
        U
        ⊆
        X
      
    
    {\displaystyle U\subseteq X}
  
 that is "closed under going up", in the sense that
</p>
for all 
  
    
      
        u
        ∈
        U
      
    
    {\displaystyle u\in U}
  
 and all 
  
    
      
        x
        ∈
        X
        ,
      
    
    {\displaystyle x\in X,}
  
 if 
  
    
      
        u
        ≤
        x
      
    
    {\displaystyle u\leq x}
  
 then 
  
    
      
        x
        ∈
        U
        .
      
    
    {\displaystyle x\in U.}

<p>The <a href="/facts/Duality_(order_theory)/TTTcqYQy">dual</a> notion is a lower set (also called a downward closed set, down set, decreasing set, initial segment, or semi-ideal), which is a subset 
  
    
      
        L
        ⊆
        X
      
    
    {\displaystyle L\subseteq X}
  
 that is "closed under going down", in the sense that
</p>
for all 
  
    
      
        l
        ∈
        L
      
    
    {\displaystyle l\in L}
  
 and all 
  
    
      
        x
        ∈
        X
        ,
      
    
    {\displaystyle x\in X,}
  
 if 
  
    
      
        x
        ≤
        l
      
    
    {\displaystyle x\leq l}
  
 then 
  
    
      
        x
        ∈
        L
        .
      
    
    {\displaystyle x\in L.}

<p>The terms order ideal or <a href="/facts/Ideal_(order_theory)/r1MMhToc">ideal</a> are sometimes used as synonyms for lower set.<a class="footnote-ref" id="fnref:3" href="#fn:3"><sup>3</sup></a><a class="footnote-ref" id="fnref:4" href="#fn:4"><sup>4</sup></a><a class="footnote-ref" id="fnref:5" href="#fn:5"><sup>5</sup></a> This choice of terminology fails to reflect the notion of an ideal of a <a href="/facts/Lattice_(order)/5ak6ufky">lattice</a> because a lower set of a lattice is not necessarily a sublattice.<a class="footnote-ref" id="fnref:6" href="#fn:6"><sup>6</sup></a>
</p>
<h2 id="properties">Properties</h2>
<ul><li>Every preordered set is an upper set of itself.</li>
<li>The <a href="/facts/Intersection_(set_theory)/RPfUNJh9">intersection</a> and the <a href="/facts/Union_(set_theory)/KVVXKfWl">union</a> of any family of upper sets is again an upper set.</li>
<li>The <a href="/facts/Complement_(set_theory)/yWUePIYY">complement</a> of any upper set is a lower set, and vice versa.</li>
<li>Given a partially ordered set 
  
    
      
        (
        X
        ,
        ≤
        )
        ,
      
    
    {\displaystyle (X,\leq ),}
  
 the family of upper sets of 
  
    
      
        X
      
    
    {\displaystyle X}
  
 ordered with the <a href="/facts/Inclusion_(set_theory)/SJGERmbA">inclusion</a> relation is a <a href="/facts/Complete_lattice/pQbphWeR">complete lattice</a>, the upper set lattice.</li>
<li>Given an arbitrary subset 
  
    
      
        Y
      
    
    {\displaystyle Y}
  
 of a partially ordered set 
  
    
      
        X
        ,
      
    
    {\displaystyle X,}
  
 the smallest upper set containing 
  
    
      
        Y
      
    
    {\displaystyle Y}
  
 is denoted using an up arrow as 
  
    
      
        ↑
        Y
      
    
    {\displaystyle \uparrow Y}
  
 (see upper closure and lower closure).
<ul><li>Dually, the smallest lower set containing 
  
    
      
        Y
      
    
    {\displaystyle Y}
  
 is denoted using a down arrow as 
  
    
      
        ↓
        Y
        .
      
    
    {\displaystyle \downarrow Y.}
  
</li></ul></li>
<li>A lower set is called principal if it is of the form 
  
    
      
        ↓
        {
        x
        }
      
    
    {\displaystyle \downarrow \{x\}}
  
 where 
  
    
      
        x
      
    
    {\displaystyle x}
  
 is an element of 
  
    
      
        X
        .
      
    
    {\displaystyle X.}
  
</li>
<li>Every lower set 
  
    
      
        Y
      
    
    {\displaystyle Y}
  
 of a finite partially ordered set 
  
    
      
        X
      
    
    {\displaystyle X}
  
 is equal to the smallest lower set containing all <a href="/facts/Maximal_element/7FCC9qAW">maximal elements</a> of 
  
    
      
        Y
      
    
    {\displaystyle Y}

<ul><li>
  
    
      
        ↓
        Y
        =↓
        Max
        ⁡
        (
        Y
        )
      
    
    {\displaystyle \downarrow Y=\downarrow \operatorname {Max} (Y)}
  
 where 
  
    
      
        Max
        ⁡
        (
        Y
        )
      
    
    {\displaystyle \operatorname {Max} (Y)}
  
 denotes the set containing the maximal elements of 
  
    
      
        Y
        .
      
    
    {\displaystyle Y.}
  
</li></ul></li>
<li>A <a href="/facts/Directed_set/GmWcqe3L">directed</a> lower set is called an <a href="/facts/Order_ideal/r1MMhToc">order ideal</a>.</li>
<li>For partial orders satisfying the <a href="/facts/Descending_chain_condition/0K7K2u02">descending chain condition</a>, antichains and upper sets are in one-to-one correspondence via the following <a href="/facts/Bijections/j4gTuTmW">bijections</a>: 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 <a href="/facts/Real_number/R02gw5Pb">real numbers</a> 
  
    
      
        {
        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.</li></ul>

<h2 id="upper-closure-and-lower-closure">Upper closure and lower closure</h2>
<p>Given an element 
  
    
      
        x
      
    
    {\displaystyle x}
  
 of a partially ordered set 
  
    
      
        (
        X
        ,
        ≤
        )
        ,
      
    
    {\displaystyle (X,\leq ),}
  
 the upper closure or upward closure of 
  
    
      
        x
        ,
      
    
    {\displaystyle x,}
  
 denoted by 
  
    
      
        
          x
          
            ↑
            X
          
        
        ,
      
    
    {\displaystyle x^{\uparrow X},}
  
 
  
    
      
        
          x
          
            ↑
          
        
        ,
      
    
    {\displaystyle x^{\uparrow },}
  
 or 
  
    
      
        ↑
        
        x
        ,
      
    
    {\displaystyle \uparrow \!x,}
  
 is defined by

x
          
            ↑
            X
          
        
        =
        
        ↑
        
        x
        =
        {
        u
        ∈
        X
        :
        x
        ≤
        u
        }
      
    
    {\displaystyle x^{\uparrow X}=\;\uparrow \!x=\{u\in X:x\leq u\}}

while the lower closure or downward closure of 
  
    
      
        x
      
    
    {\displaystyle x}
  
, denoted by 
  
    
      
        
          x
          
            ↓
            X
          
        
        ,
      
    
    {\displaystyle x^{\downarrow X},}
  
 
  
    
      
        
          x
          
            ↓
          
        
        ,
      
    
    {\displaystyle x^{\downarrow },}
  
 or 
  
    
      
        ↓
        
        x
        ,
      
    
    {\displaystyle \downarrow \!x,}
  
 is defined by

x
          
            ↓
            X
          
        
        =
        
        ↓
        
        x
        =
        {
        l
        ∈
        X
        :
        l
        ≤
        x
        }
        .
      
    
    {\displaystyle x^{\downarrow X}=\;\downarrow \!x=\{l\in X:l\leq x\}.}

</p><p>The sets 
  
    
      
        ↑
        
        x
      
    
    {\displaystyle \uparrow \!x}
  
  and 
  
    
      
        ↓
        
        x
      
    
    {\displaystyle \downarrow \!x}
  
  are, respectively, the smallest upper and lower sets containing 
  
    
      
        x
      
    
    {\displaystyle x}
  
 as an element.  
More generally, given a subset 
  
    
      
        A
        ⊆
        X
        ,
      
    
    {\displaystyle A\subseteq X,}
  
 define the upper/upward closure and the lower/downward closure of 
  
    
      
        A
        ,
      
    
    {\displaystyle A,}
  
 denoted by 
  
    
      
        
          A
          
            ↑
            X
          
        
      
    
    {\displaystyle A^{\uparrow X}}
  
 and 
  
    
      
        
          A
          
            ↓
            X
          
        
      
    
    {\displaystyle A^{\downarrow X}}
  
 respectively, as

A
          
            ↑
            X
          
        
        =
        
          A
          
            ↑
          
        
        =
        
          ⋃
          
            a
            ∈
            A
          
        
        ↑
        
        a
      
    
    {\displaystyle A^{\uparrow X}=A^{\uparrow }=\bigcup _{a\in A}\uparrow \!a}

and

A
          
            ↓
            X
          
        
        =
        
          A
          
            ↓
          
        
        =
        
          ⋃
          
            a
            ∈
            A
          
        
        ↓
        
        a
        .
      
    
    {\displaystyle A^{\downarrow X}=A^{\downarrow }=\bigcup _{a\in A}\downarrow \!a.}
  
 
</p><p>In this way, 
  
    
      
        ↑
        x
        =↑
        {
        x
        }
      
    
    {\displaystyle \uparrow x=\uparrow \{x\}}
  
 and 
  
    
      
        ↓
        x
        =↓
        {
        x
        }
        ,
      
    
    {\displaystyle \downarrow x=\downarrow \{x\},}
  
 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.
</p><p>The upper and lower closures, when viewed as functions from the power set of 
  
    
      
        X
      
    
    {\displaystyle X}
  
 to itself, are examples of <a href="/facts/Kuratowski_closure_axioms/ovjzpSms">closure operators</a> since they satisfy all of the <a href="/facts/Kuratowski_closure_axioms/ovjzpSms">Kuratowski closure axioms</a>. 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 <a href="/facts/Topological_closure/9x2wlgUW">topological closure</a> of a set is the intersection of all <a href="/facts/Closed_sets/upYnRTUj">closed sets</a> containing it; the <a href="/facts/Linear_span/vPjclEtb">span</a> of a set of vectors is the intersection of all <a href="/facts/Linear_subspace/2wtKTgHL">subspaces</a> containing it; the <a href="/facts/Generating_set_of_a_group/B9q5lnFY">subgroup generated by a subset</a> of a <a href="/facts/Group_(mathematics)/IQTYqINt">group</a> is the intersection of all subgroups containing it; the <a href="/facts/Ideal_(ring_theory)/vCvytduX">ideal</a> generated by a subset of a <a href="/facts/Ring_(mathematics)/JnCUXz63">ring</a> is the intersection of all ideals containing it; and so on.)
</p>
<h2 id="ordinal-numbers">Ordinal numbers</h2>
<p>An <a href="/facts/Ordinal_number/GelFLjJt">ordinal number</a> 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.
</p>
<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/Abstract_simplicial_complex/ytwxClsf">Abstract simplicial complex</a> (also called: <a href="/facts/Independence_system/a2ctD9kN">Independence system</a>) - a set-family that is downwards-closed with respect to the containment relation.</li>
<li><a href="/facts/Cofinal_set/l5Hoqx3o">Cofinal set</a> – a subset 
  
    
      
        U
      
    
    {\displaystyle U}
  
 of a partially ordered set 
  
    
      
        (
        X
        ,
        ≤
        )
      
    
    {\displaystyle (X,\leq )}
  
 that contains for every element 
  
    
      
        x
        ∈
        X
        ,
      
    
    {\displaystyle x\in X,}
  
 some element 
  
    
      
        y
      
    
    {\displaystyle y}
  
 such that 
  
    
      
        x
        ≤
        y
        .
      
    
    {\displaystyle x\leq y.}
  
</li></ul>

<ul><li>Blanck, J. (2000). <a href="http://www-compsci.swan.ac.uk/~csjens/pdf/top.pdf">"Domain representations of topological spaces"</a> (PDF). <i>Theoretical Computer Science</i>. 247 (1–2): 229–255. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1016%2Fs0304-3975%2899%2900045-6">10.1016/s0304-3975(99)00045-6</a>.</li>
<li>Dolecki, Szymon; Mynard, Frédéric (2016). <i>Convergence Foundations Of Topology</i>. New Jersey: World Scientific Publishing Company. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-981-4571-52-4. <a href="/facts/OCLC_(identifier)/Yqad8waq">OCLC</a> <a href="https://search.worldcat.org/oclc/945169917">945169917</a>.</li>
<li>Hoffman, K. H. (2001), <a href="https://web.archive.org/web/20070621125416/http://www.mathematik.tu-darmstadt.de:8080/Math-Net/Lehrveranstaltungen/Lehrmaterial/SS2003/Topology/separation.pdf"><i>The low separation axioms (T0) and (T1)</i></a></li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1"><p>Dolecki & Mynard 2016, pp. 27–29. - Dolecki, Szymon; Mynard, Frédéric (2016). Convergence Foundations Of Topology. New Jersey: World Scientific Publishing Company. ISBN 978-981-4571-52-4. OCLC 945169917. <a href="https://search.worldcat.org/oclc/945169917" target="_blank">https://search.worldcat.org/oclc/945169917</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li>
<li id="fn:2"><p>Dolecki & Mynard 2016, pp. 27–29. - Dolecki, Szymon; Mynard, Frédéric (2016). Convergence Foundations Of Topology. New Jersey: World Scientific Publishing Company. ISBN 978-981-4571-52-4. OCLC 945169917. <a href="https://search.worldcat.org/oclc/945169917" target="_blank">https://search.worldcat.org/oclc/945169917</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li>
<li id="fn:3"><p>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. <a href="0-521-78451-4" target="_blank">0-521-78451-4</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li>
<li id="fn:4"><p>Stanley, R.P. (2002). Enumerative combinatorics. Cambridge studies in advanced mathematics. Vol. 1. Cambridge University Press. p. 100. ISBN 978-0-521-66351-9. <a href="978-0-521-66351-9" target="_blank">978-0-521-66351-9</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></p></li>
<li id="fn:5"><p>Lawson, M.V. (1998). Inverse semigroups: the theory of partial symmetries. World Scientific. p. 22. ISBN 978-981-02-3316-7. <a href="978-981-02-3316-7" target="_blank">978-981-02-3316-7</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></p></li>
<li id="fn:6"><p>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. <a href="0-521-78451-4" target="_blank">0-521-78451-4</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></p></li>
</ol>

Upper set open-in-new

Upper set