{{short description|Subset of a preorder that contains all larger elements}} [[Image:Upset_210div.svg|thumb|A Hasse diagram of the divisors of <math>210</math>, ordered by the relation ''is divisor of'', with the upper set <math>\uparrow 2</math> colored green. The white sets form the lower set <math>\downarrow 105.</math>]] In mathematics, an '''upper set''' <math>S</math> of a partially ordered set <math>X</math> is a subset such that 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 element of ''X'' that is greater than or equal to some element of ''S'' is necessarily also an element of ''S'', or, <math>x\in X \land s\in S \land x\geq s\implies x\in S</math> --> 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''.{{sfn | Dolecki | Mynard | 2016 | pp=27–29}}<ref name=EC1>{{cite book |last1=Stanley |first1=R.P. |title=Enumerative combinatorics |series=Cambridge studies in advanced mathematics |volume=1 |year=2002 |publisher=Cambridge University Press |isbn=978-0-521-66351-9 | page=100}}</ref> However, the terms "order ideal" and "order filter" are also used for a more restrictive notion.<ref name=ideal/>
==Definition==
Let <math>(X, \leq)</math> be a preordered set (the same as a partially ordered set except the requirement <math>x \le y, \, y \le x</math> implying <math>x = y</math> is dropped).
An {{em|upper set}} in <math>X</math> (also called an {{em|upward closed set}}, {{em|up set}}, {{em|increasing set}}, or an {{em|isotone set}}){{sfn | Dolecki | Mynard | 2016 | pp=27–29}} is a subset <math>U</math> that is "closed under going up", in the following sense: for all <math>u</math> in <math>U</math> and <math>x</math> in <math>X</math>, if <math>u \le x</math>, then <math>x</math> is in <math>U</math>.
The dual notion is a {{em|lower set}} (also called a {{em|downward closed set}}, {{em|down set}}, {{em|decreasing set}}, or a {{em|semi-ideal}}), which is a subset <math>L</math> that is "closed under going down": for all <math>l</math> in <math>L</math> and all <math>x</math> in <math>X</math>, if <math>x \leq l</math>, then <math>x</math> is in <math>L.</math>
The term {{em|order ideal}} is sometimes used as a synonym for a lower set.<ref name="DP">{{cite book | author1=Brian A. Davey | author2= Hilary Ann Priestley | author2-link= Hilary Priestley | title=Introduction to Lattices and Order|title-link= Introduction to Lattices and Order | edition=2nd | year=2002 | publisher=Cambridge University Press | isbn=0-521-78451-4 | lccn=2001043910 |pages= 20, 44}}</ref><ref name=EC1/><ref>{{cite book |last1=Lawson |first1=M.V. |title=Inverse semigroups: the theory of partial symmetries |url=https://archive.org/details/inversesemigroup00laws|url-access=limited |year=1998 |publisher=World Scientific |isbn=978-981-02-3316-7 | page=[https://archive.org/details/inversesemigroup00laws/page/n34 22]}}</ref> However, an ideal is also commonly defined specifically as a lower set which is upward directed.<ref name=ideal>{{harvtxt|Taylor|1999}}, [{{Google books|plainurl=y|id=iSCqyNgzamcC|page=141}} p. 141]: "A directed lower subset of a poset ''X'' is called an ideal"</ref><ref>{{cite book |last1=Gierz |first1=G. |last2=Hofmann |first2=K. H. |last3=Keimel |first3=K. |last4=Lawson |first4=J. D. |last5=Mislove |first5=M. W. |last6=Scott |first6=D. S. |title=Continuous Lattices and Domains |volume=93 |series=Encyclopedia of Mathematics and its Applications |publisher=Cambridge University Press |year=2003 |isbn=0521803381 |page=[https://archive.org/details/continuouslattic0000unse/page/3 3] |url=https://archive.org/details/continuouslattic0000unse/page/3 }}</ref> 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 <math>(X, \leq),</math> the family of upper sets of <math>X</math> ordered with the inclusion relation is a complete lattice, the '''upper set lattice'''. * Every upper set <math>Y</math> of a finite partially ordered set <math>X</math> is equal to the smallest upper set containing all minimal elements of <math>Y.</math> * 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 <math>\{ x \in \R: x > 0 \}</math> and <math>\{ x \in \R: x > 1 \}</math> are both mapped to the empty antichain.
== Examples == Upper sets and lower sets appear in various fields of mathematics. * In the totally ordered set of the real numbers <math>(\R,\le)</math>, lower sets include "left rays" like <math>(-\infty,3]</math> and <math>(-\infty,5)</math>, as well as the empty set <math>\emptyset</math> and the whole set. Upper sets include "right rays" like <math>(3,\infty)</math> and <math>[5,\infty)</math>. * In real analysis, a real number is often defined as a Dedekind cut. By definition, this is a nonempty proper lower subset of <math>\Q</math> with no maximal element. * Let <math>X</math> be a topological space and <math>x</math> a point in it. Let <math>F</math> be the set of all (not-necessarily-open) neighborhoods of <math>x</math>. Then <math>F</math> is an upper set in the power set of <math>X</math> ordered by inclusion, since any set containing a neighborhood of the point is a neighborhood of that point. * Any filter on a set <math>X</math> is an upper set in the power set of <math>X</math> ordered by inclusion. The previous example of the neighbourhood filter of a point in a topological space is an instance of this. * Abstract simplicial complex - a set-family that is downwards-closed with respect to the containment relation.
{{anchor|Upper closure|Upward closure|Lower closure|Downward closure}}
==Upper closure and lower closure== Given an element <math>x</math> of a preordered set <math>(X, \leq),</math> the '''upper closure''' or '''upward closure''' of <math>x</math> is defined by :<math>\uparrow\! x = \{ u \in X : x \leq u\}</math> while the '''lower closure''' or '''downward closure''' of <math>x</math> by :<math>\downarrow\! x = \{l \in X : l \leq x\}.</math><ref name=Goubault-Larrecq>{{harvnb|Goubault-Larrecq|2013|loc=§ 2.3.}}</ref>
Upper and lower sets of the form <math>\uparrow\! x</math> and <math>\downarrow\! x</math> are called '''principal'''. The upper closure of an element is the same thing as the principal filter generated by that element, since it is also directed downward.
More generally, given a subset <math>A \subset X,</math> the upper closure and lower closure of <math>A</math> are defined as <math>\uparrow\! A = \bigcup_{a \in A} \uparrow\!a</math> and <math>\downarrow\! A = \bigcup_{a \in A} \downarrow\!a</math>;<ref name=Goubault-Larrecq /> they are, respectively, the smallest upper set and lower set containing <math>A</math>. The upper and lower closures, when viewed as functions from the power set of <math>X</math> to itself, are examples of Kuratowski closure operators. 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.
In category theory, a poset can be (and often is) viewed as a category by writing a morphism <math>x \to y</math> if and only if <math>x \le y</math>. Then the lower closure <math>\downarrow x</math> corresponds to the slice category over <math>x</math>, while the upper closure that under <math>x</math>.<ref>{{harvnb|Taylor|1999|loc=Example 3.1.6. (f)., footnote 1.}}</ref>
Let <math>X</math> be a poset. Then we have<ref>{{harvnb|Taylor|1999|loc=Proposition 3.2.7.}}</ref> :<math>\eta : X \hookrightarrow \mathfrak{P}(X)</math> where <math>\mathfrak{P}(X)</math> is the power set of <math>X</math> and <math>\eta(x) = {\downarrow\! x}</math> is the lower closure of <math>x</math>. The map <math>\eta</math> is an embedding in the sense it is injective and monotone: :<math>x \le y \Longleftrightarrow {\downarrow\! x} \subseteq {\downarrow\! y}.</math><ref>{{harvnb|Taylor|1999|loc=Proposition 3.1.8. (a).}}</ref> Thus, the above construction can be used to replace a given ordering by set inclusion and also yields advantages such as that a least upper bound always exists (possibly outside the image of <math>\eta</math>); namely, a union. For example, this trick can be used to reduce a proof of Zorn's lemma to the case of posets of sets.<ref>{{harvnb|Halmos|1960|loc=§ 16.}}</ref>
As Paul Taylor points out, the above <math>\eta</math> is an analog of an embedding in the Yoneda lemma in category theory.<ref>{{harvnb|Taylor|1999|loc=§ 3.1. NB: This exact remark does not appear directly but is clearly implicit in the cited section.}}</ref><ref>{{harvnb|Rosiak|2022|loc=§ 6.2 Downsets and Yoneda in the Miniature}}</ref>
The image of <math>\eta</math> lies in the set of all lower sets in <math>X</math>. But, more specifically, it lies in the set of all ''directed'' lower sets (ideals), denoted by <math>I(X)</math> and called the ideal completion of <math>X</math>.<ref>{{harvnb|Goubault-Larrecq|2013|loc=Definition 5.1.45.}}</ref> Then <math>\eta : X \hookrightarrow I(X)</math> satisfies the universal property that makes <math>I</math> a free functor in the sense: it is left adjoint to the forgetful functor from the category of dcpos to the category of posets.<ref>{{harvnb|Goubault-Larrecq|2013|loc=Exercise 5.5.3.}}</ref>
== Scott topology == {{main|Scott topology}}
A function between posets is said to be Scott-continuous if it is monotone (it preserves <math>\le</math>) and preserves directed sups.<ref>{{harvnb|Taylor|1999|loc=§ 3.4.}}</ref> Then a poset <math>X</math> carries a topology where a subset <math>U</math> is open if and only if the characteristic function on <math>U</math> is Scott-continuous. This topology is called the Scott topology. Explicitly, an open set in this topology is exactly an upper set such that if <math>\textstyle \sup_i x_i \in U</math> for a directed set <math>x_i</math>, then <math>x_i</math> is in <math>U</math> for some <math>i</math>.<ref>{{harvnb|Taylor|1999|loc=Proposition 3.4.9.}}</ref> The intuition here is that a sup corresponds to the best approximation and so if the best approximation is available in the set, some finite approximation is already in that set.
The Scott topology appears prominently in domain theory, a branch of order theory with a strong connection to computer science. Like the Zariski topology used in algebraic geometry, the Scott topology is an important example of a non-Hausdorff topological space.
==Birkhoff's theorem== {{main|Birkhoff's representation theorem}} The set of all lower sets of a given poset <math>P</math> may be ordered by inclusion. The resulting poset, denoted <math>J(P)</math>, is a lattice (meaning that every subset of <math>J(P)</math> has a least upper bound and a greatest lower bound), and indeed a distributive lattice (meaning that the two operations of least upper bound and greatest lower bound distribute over one another). Birkhoff's representation theorem asserts that every finite distributive lattice arises (up to isomorphism) in this way as the lattice of lower sets of a unique finite poset.
==Related notions==
* Cofinal set – a subset <math>U</math> of a partially ordered set <math>(X, \leq)</math> that contains for every element <math>x \in X,</math> some element <math>y</math> such that <math>x \leq y.</math> <!-- already mentioned. * Filter and ideal - upper and lower sets with the additional property of being directed.-->
== See also == *Upper topology<!-- Do we need this as a separate article? -->
==Notes== {{notelist}} {{reflist}} ==References== * {{cite journal|author=Blanck, J.|year=2000|title=Domain representations of topological spaces|journal=Theoretical Computer Science|volume=247|issue=1–2|pages=229–255|url=http://www-compsci.swan.ac.uk/~csjens/pdf/top.pdf|doi=10.1016/s0304-3975(99)00045-6|doi-access=free|archive-date=2017-08-08|access-date=2014-07-21|archive-url=https://web.archive.org/web/20170808152856/http://www-compsci.swan.ac.uk/~csjens/pdf/top.pdf|url-status=dead}} * {{Dolecki Mynard Convergence Foundations Of Topology}} <!-- {{sfn|Dolecki|Mynard|2016|p=}} --> * Hoffman, K. H. (2001), [https://web.archive.org/web/20070621125416/http://www.mathematik.tu-darmstadt.de:8080/Math-Net/Lehrveranstaltungen/Lehrmaterial/SS2003/Topology/separation.pdf ''The low separation axioms (T<sub>0</sub>) and (T<sub>1</sub>)''] * {{cite book|first=Paul|last=Halmos|author-link=Paul Halmos|title= Naive Set Theory|location=Princeton, NJ|publisher=D. Van Nostrand Company|year=1960}}. Reprinted by Springer-Verlag, New York, 1974. {{ISBN|0-387-90092-6}} (Springer-Verlag edition). * {{cite book |last1=Taylor |first1=Paul |title=Practical Foundations of Mathematics |date=13 May 1999 |publisher=Cambridge University Press |isbn=978-0-521-63107-5 |url=https://books.google.com/books?hl=en&lr=&id=iSCqyNgzamcC&oi=fnd&pg=PR8&dq=Taylor+practical+foundations+of+mathematics+&ots=9uqLHUWDXn&sig=sUTyabXfHnoFmKDXzlQH7m2UljA |language=en}}, nlab entry at [https://ncatlab.org/nlab/show/Practical+Foundations+of+Mathematics] *{{cite book |title=Sheaf Theory through Examples |chapter=There's a Yoneda Lemma for That |date=2022 |pages=171–194 |doi=10.7551/mitpress/12581.003.0009 |isbn=978-0-262-37042-4|last1=Rosiak |first1=Daniel}} *{{cite book |last1=Goubault-Larrecq |first1=Jean |title=Non-Hausdorff Topology and Domain Theory: Selected Topics in Point-Set Topology |date=2013 |publisher=Cambridge University Press |isbn=978-1-107-03413-6 |url=https://www.cambridge.org/core/books/nonhausdorff-topology-and-domain-theory/47A93B1951D60717E2E71030CB0A4441}}
{{Order theory}}
Category:Order theory Category:Set theory Category:Coalgebras
ru:Частично упорядоченное множество#Верхнее и нижнее множество