# Upper set

Last updated

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, ≤) is a subset SX with the following property: if s is in S and if x in X is larger than s (i.e. if sx), 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 ${\displaystyle (X,\leq )}$ be a preordered set. An upper set in ${\displaystyle X}$ (also called an upward closed set, an upset, or an isotone set) [1] is a subset ${\displaystyle U\subseteq X}$ such that if ${\displaystyle u\in U}$ and if ${\displaystyle x\in X}$ satisfies ${\displaystyle u\leq x,}$ then ${\displaystyle x\in U.}$ That is, ${\displaystyle U}$ satisfies:

for all ${\displaystyle u\in U}$ and all ${\displaystyle x\in X,}$ if ${\displaystyle u\leq x}$ then ${\displaystyle 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 ${\displaystyle L\subseteq X}$ such that that if ${\displaystyle l\in L}$ and if ${\displaystyle x\in X}$ satisfies ${\displaystyle x\leq l,}$ then ${\displaystyle x\in L.}$ That is, ${\displaystyle L}$ satisfies:

for all ${\displaystyle l\in L}$ and all ${\displaystyle x\in X,}$ if ${\displaystyle x\leq l}$ then ${\displaystyle 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 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 upper sets of X ordered with the inclusion relation is a complete lattice, the upper set lattice.
• Given an arbitrary subset Y of a partially ordered set X, the smallest upper set containing Y is denoted using an up arrow as ↑Y (see upper closure and lower closure).
• 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 partially 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: xy for some y in A}. 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.

## Upper closure and lower closure

Given an element ${\displaystyle x}$ of a partially ordered set ${\displaystyle (X,\leq ),}$ we define the upper closure or upward closure of ${\displaystyle x,}$ denoted by ${\displaystyle x^{\uparrow X},}$${\displaystyle x^{\uparrow },}$ or ${\displaystyle \uparrow x,}$ is defined by:

${\displaystyle x^{\uparrow X}=\uparrow x=\left\{u\in X:x\leq u\right\}}$

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

${\displaystyle x^{\downarrow X}=\downarrow x=\left\{l\in X:l\leq x\right\}.}$

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

${\displaystyle A^{\uparrow X}=A^{\uparrow }=\bigcup _{a\in A}\uparrow \!a}$     and     ${\displaystyle A^{\downarrow X}=A^{\downarrow }=\bigcup _{a\in A}\downarrow \!a.}$

In this way, ↑x = ↑{x} and ↓x = ↓{x}, 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 function 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.

One can also speak of the strict upper closure of an element ${\displaystyle x\in X}$ defined as {yX : x<y}, and more generally, the strict upper closure of a subset ${\displaystyle A\subseteq X,}$ which is defined as the union of the strict upper closures of its elements, and we can make analogous definitions for strict lower closures. However note that these 'closures' are not actually closure operators, since for example the strict upper closure of a singleton set {x} does not contain {x}.

## 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.

• Cofinal set – a subset U of a partially ordered set (X, ≤) that contains for every element ${\displaystyle x\in X,}$ some element y such that ${\displaystyle x\leq y.}$

## Related Research Articles

In mathematics, a directed set is a nonempty set together with a reflexive and transitive binary relation , with the additional property that every pair of elements has an upper bound. In other words, for any and in there must exist in with and A directed set's preorder is called a direction.

In mathematics, a filter is a special subset of a partially ordered set. Filters appear in order and lattice theory, but can also be found in topology, from where they originate. The dual notion of a filter is an order ideal.

In mathematics, especially order theory, a partially ordered set formalizes and generalizes the intuitive concept of an ordering, sequencing, or arrangement of the elements of a set. A poset consists of a set together with a binary relation indicating that, for certain pairs of elements in the set, one of the elements precedes the other in the ordering. The relation itself is called a "partial order." The word partial in the names "partial order" and "partially ordered set" is used as an indication that not every pair of elements needs to be comparable. That is, there may be pairs of elements for which neither element precedes the other in the poset. Partial orders thus generalize total orders, in which every pair is comparable.

In mathematics, a set A is a subset of a set B if all elements of A are also elements of B; B is then a superset of A. It is possible for A and B to be equal; if they are unequal, then A is a proper subset of B. The relationship of one set being a subset of another is called inclusion. A is a subset of B may also be expressed as B includes A or A is included in B.

In mathematics, a total or linear order is a partial order in which any two elements are comparable. That is, a total order is a binary relation on some set , which satisfies the following for all and in :

1. (reflexive).
2. If and then (transitive)
3. If and then (antisymmetric)
4. or .

In mathematics, the infimum of a subset of a partially ordered set is the greatest element in that is less than or equal to all elements of if such an element exists. Consequently, the term greatest lower bound is also commonly used.

In the mathematical areas of order and lattice theory, the Knaster–Tarski theorem, named after Bronisław Knaster and Alfred Tarski, states the following:

In mathematics, especially in order theory, a maximal element of a subset S of some preordered set is an element of S that is not smaller than any other element in S. A minimal element of a subset S of some preordered set is defined dually as an element of S that is not greater than any other element in S.

In mathematics, in the area of order theory, an antichain is a subset of a partially ordered set such that any two distinct elements in the subset are incomparable.

This is a glossary of some terms used in various branches of mathematics that are related to the fields of order, lattice, and domain theory. Note that there is a structured list of order topics available as well. Other helpful resources might be the following overview articles:

A lattice is an abstract structure studied in the mathematical subdisciplines of order theory and abstract algebra. It consists of a partially ordered set in which every two elements have a unique supremum and a unique infimum. An example is given by the natural numbers, partially ordered by divisibility, for which the unique supremum is the least common multiple and the unique infimum is the greatest common divisor.

In mathematics, a closure operator on a set S is a function from the power set of S to itself that satisfies the following conditions for all sets

In mathematics, a Riesz space, lattice-ordered vector space or vector lattice is a partially ordered vector space where the order structure is a lattice.

In mathematics, a cardinal function is a function that returns cardinal numbers.

In mathematics, specifically order theory, the Dedekind–MacNeille completion of a partially ordered set is the smallest complete lattice that contains it. It is named after Holbrook Mann MacNeille whose 1937 paper first defined and constructed it, and after Richard Dedekind because its construction generalizes the Dedekind cuts used by Dedekind to construct the real numbers from the rational numbers. It is also called the completion by cuts or normal completion.

A schema is a template in computer science used in the field of genetic algorithms that identifies a subset of strings with similarities at certain string positions. Schemata are a special case of cylinder sets; and so form a topological space.

This is a glossary of set theory.

In topology, a subfield of mathematics, filters are special families of subsets of a set that can be used to study topological spaces and define all basic topological notions such a convergence, continuity, compactness, and more. Filters also provide a common framework for defining various types of limits of functions such as limits from the left/right, to infinity, to a point or a set, and many others. Special types of filters called ultrafilters have many useful technical properties and they may often be used in place of arbitrary filters.

In mathematics, a convergence space, also called a generalized convergence, is a set together with a relation called a convergence that satisfies certain properties relating elements of X with the family of filters on X. Convergence spaces generalize the notions of convergence that are found in point-set topology, including metric convergence and uniform convergence. Every topological space gives rise to a canonical convergence but there are convergences, known as non-topological convergences, that do not arise from any topological space. Examples of convergences that are in general non-topological include convergence in measure and almost everywhere convergence. Many topological properties have generalizations to convergence spaces.

In the mathematical field of set theory, an ultrafilter is a maximal proper filter: it is a filter on a given non-empty set which is a certain type of non-empty family of subsets of that is not equal to the power set of and that is also "maximal" in that there does not exist any other proper filter on that contains it as a proper subset. Said differently, a proper filter is called an ultrafilter if there exists exactly one proper filter that contains it as a subset, that proper filter (necessarily) being itself.

## References

1. Dolecki & Mynard 2016, pp. 27–29.
2. 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. 1. Cambridge University Press. p. 100. ISBN   978-0-521-66351-9.
4. Lawson, M.V. (1998). . World Scientific. p.  22. ISBN   978-981-02-3316-7.