Upper 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 $(X,\leq )$ is a subset $S\subseteq X$ with the following property: if s is in S and if x in X is larger than s (that is, if $s<x$ ), then x is in S. In other words, this means that any x element of X that is $\,\geq \,$ 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 $\,\leq \,$ to some element of S is necessarily also an element of S.

Definition

Let $(X,\leq )$ be a preordered set. An upper set in $X$ (also called an upward closed set, an upset, or an isotone set)^[1] is a subset $U\subseteq X$ that is "closed under going up", in the sense that

for all

u\in U

and all

x\in X,

if

u\leq x

then

x\in U.

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 $L\subseteq X$ that is "closed under going down", in the sense that

for all

l\in L

and all

x\in X,

if

x\leq l

then

x\in L.

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

Every partially ordered 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 $(X,\leq ),$ the family of upper sets of $X$ ordered with the inclusion relation is a complete lattice, the upper set lattice.
Given an arbitrary subset $Y$ $Y$ of a partially ordered set $X,$ $X,$ the smallest upper set containing $Y$ $Y$ is denoted using an up arrow as $\uparrow Y$ $\uparrow Y$ (see upper closure and lower closure).
- Dually, the smallest lower set containing $Y$ is denoted using a down arrow as $\downarrow Y.$
A lower set is called principal if it is of the form $\downarrow \{x\}$ where $x$ is an element of $X.$
Every lower set $Y$ $Y$ of a finite partially ordered set $X$ $X$ is equal to the smallest lower set containing all maximal elements of $Y$ $Y$
- $\downarrow Y=\downarrow \operatorname {Max} (Y)$ where $\operatorname {Max} (Y)$ denotes the set containing the maximal elements of $Y.$
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 (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 $\{x\in \mathbb {R} :x>0\}$ and $\{x\in \mathbb {R} :x>1\}$ are both mapped to the empty antichain.

Upper closure and lower closure

Given an element $x$ of a partially ordered set $(X,\leq ),$ the upper closure or upward closure of $x,$ denoted by $x^{\uparrow X},$ $x^{\uparrow },$ or $\uparrow \!x,$ is defined by $x^{\uparrow X}=\;\uparrow \!x=\{u\in X:x\leq u\}$ while the lower closure or downward closure of $x$ , denoted by $x^{\downarrow X},$ $x^{\downarrow },$ or $\downarrow \!x,$ is defined by $x^{\downarrow X}=\;\downarrow \!x=\{l\in X:l\leq x\}.$

The sets $\uparrow \!x$ and $\downarrow \!x$ are, respectively, the smallest upper and lower sets containing $x$ as an element. More generally, given a subset $A\subseteq X,$ define the upper/upward closure and the lower/downward closure of $A,$ denoted by $A^{\uparrow X}$ and $A^{\downarrow X}$ respectively, as $A^{\uparrow X}=A^{\uparrow }=\bigcup _{a\in A}\uparrow \!a$ and $A^{\downarrow X}=A^{\downarrow }=\bigcup _{a\in A}\downarrow \!a.$

In this way, $\uparrow x=\uparrow \{x\}$ and $\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.

The upper and lower closures, when viewed as functions from the power set of $X$ 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.

References

^ Jump up to: ^a ^b Dolecki & Mynard 2016, pp. 27–29.
^ Jump up to: ^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.
^ Stanley, R.P. (2002). Enumerative combinatorics. Cambridge studies in advanced mathematics. Vol. 1. Cambridge University Press. p. 100. ISBN 978-0-521-66351-9.
^ Lawson, M.V. (1998). Inverse semigroups: the theory of partial symmetries. World Scientific. p. 22. ISBN 978-981-02-3316-7.

Blanck, J. (2000). "Domain representations of topological spaces" (PDF). Theoretical Computer Science. 247 (1–2): 229–255. doi:10.1016/s0304-3975(99)00045-6.
Dolecki, Szymon; Mynard, Frederic (2016). Convergence Foundations Of Topology. New Jersey: World Scientific Publishing Company. ISBN 978-981-4571-52-4. OCLC 945169917.
Hoffman, K. H. (2001), The low separation axioms (T₀) and (T₁)

[FOOTNOTEDoleckiMynard201627–29-1] Jump up to: ^a ^b Dolecki & Mynard 2016, pp. 27–29.

[DP-2] Jump up to: ^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.

[1]

[2]

[3]

[4]

v t e Order theory
Topics Glossary Category
Key concepts	Binary relation Boolean algebra Cyclic order Lattice Partial order Preorder Total order Weak ordering
Results	Boolean prime ideal theorem Cantor–Bernstein theorem Cantor's isomorphism theorem Dilworth's theorem Dushnik–Miller theorem Hausdorff maximal principle Knaster–Tarski theorem Kruskal's tree theorem Laver's theorem Mirsky's theorem Szpilrajn extension theorem Zorn's lemma
Properties & Types (list)	Antisymmetric Asymmetric Boolean algebra topics Completeness Connected Covering Dense Directed (Partial) Equivalence Foundational Heyting algebra Homogeneous Idempotent Lattice Bounded Complemented Complete Distributive Join and meet Reflexive Partial order Chain-complete Graded Eulerian Strict Prefix order Preorder Total Semilattice Semiorder Symmetric Total Tolerance Transitive Well-founded Well-quasi-ordering (Better) (Pre) Well-order
Constructions	Composition Converse/Transpose Lexicographic order Linear extension Product order Reflexive closure Series-parallel partial order Star product Symmetric closure Transitive closure
Topology & Orders	Alexandrov topology & Specialization preorder Ordered topological vector space Normal cone Order topology Order topology Topological vector lattice Banach Fréchet Locally convex Normed
Related	Antichain Cofinal Cofinality Comparability Graph Duality Filter Hasse diagram Ideal Net Subnet Order morphism Embedding Isomorphism Order type Ordered field Positive cone of an ordered field Ordered vector space Partially ordered Positive cone of an ordered vector space Riesz space Partially ordered group Positive cone of a partially ordered group Upper set Young's lattice

Definition

Properties

Upper closure and lower closure

Ordinal numbers

See also

References