In
mathematics
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
, an upper set (also called an upward closed set, an upset, or an isotone set in ''X'') of a
partially ordered set
In mathematics, especially order theory, a partially ordered set (also poset) formalizes and generalizes the intuitive concept of an ordering, sequencing, or arrangement of the elements of a Set (mathematics), set. A poset consists of a set toget ...
is a subset
with the following property: if ''s'' is in ''S'' and if ''x'' in ''X'' is larger than ''s'' (that is, if
), 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
be a
preordered set
In mathematics, especially in order theory, a preorder or quasiorder is a binary relation that is reflexive relation, reflexive and Transitive relation, transitive. Preorders are more general than equivalence relations and (non-strict) partia ...
.
An in
(also called an , an , or an set) is a subset
that is "closed under going up", in the sense that
:for all
and all
if
then
The
dual notion is a (also called a , , , , or ), which is a subset
that is "closed under going down", in the sense that
:for all
and all
if
then
The terms or are sometimes used as synonyms for lower set.
This choice of terminology fails to reflect the notion of an ideal of a
lattice
Lattice may refer to:
Arts and design
* Latticework, an ornamental criss-crossed framework, an arrangement of crossing laths or other thin strips of material
* Lattice (music), an organized grid model of pitch ratios
* Lattice (pastry), an orna ...
because a lower set of a lattice is not necessarily a sublattice.
Properties
* Every partially ordered set is an upper set of itself.
* The
intersection and the
union
Union commonly refers to:
* Trade union, an organization of workers
* Union (set theory), in mathematics, a fundamental operation on sets
Union may also refer to:
Arts and entertainment
Music
* Union (band), an American rock group
** ''Un ...
of any family of upper sets is again an upper set.
* The
complement
A complement is something that completes something else.
Complement may refer specifically to:
The arts
* Complement (music), an interval that, when added to another, spans an octave
** Aggregate complementation, the separation of pitch-clas ...
of any upper set is a lower set, and vice versa.
* Given a partially ordered set
the family of upper sets of
ordered with the
inclusion
Inclusion or Include may refer to:
Sociology
* Social inclusion, aims to create an environment that supports equal opportunity for individuals and groups that form a society.
** Inclusion (disability rights), promotion of people with disabiliti ...
relation is a
complete lattice
In mathematics, a complete lattice is a partially ordered set in which ''all'' subsets have both a supremum (join) and an infimum (meet). A lattice which satisfies at least one of these properties is known as a ''conditionally complete lattice.'' ...
, the upper set lattice.
* Given an arbitrary subset
of a partially ordered set
the smallest upper set containing
is denoted using an up arrow as
(see
upper closure and lower closure).
** Dually, the smallest lower set containing
is denoted using a down arrow as
* A lower set is called principal if it is of the form
where
is an element of
* Every lower set
of a finite partially ordered set
is equal to the smallest lower set containing all
maximal element
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 defin ...
s of
where
denotes the set containing the maximal elements of
* A
directed
Director may refer to:
Literature
* ''Director'' (magazine), a British magazine
* ''The Director'' (novel), a 1971 novel by Henry Denker
* ''The Director'' (play), a 2000 play by Nancy Hasty
Music
* Director (band), an Irish rock band
* ''D ...
lower set is called an
order ideal
In mathematical order theory, an ideal is a special subset of a partially ordered set (poset). Although this term historically was derived from the notion of a ring ideal of abstract algebra, it has subsequently been generalized to a different noti ...
.
* For partial orders satisfying the
descending chain condition In mathematics, the ascending chain condition (ACC) and descending chain condition (DCC) are finiteness properties satisfied by some algebraic structures, most importantly ideals in certain commutative rings.Jacobson (2009), p. 142 and 147 These con ...
, antichains and upper sets are in one-to-one correspondence via the following
bijections
In mathematics, a bijection, also known as a bijective function, one-to-one correspondence, or invertible function, is a function between the elements of two sets, where each element of one set is paired with exactly one element of the other ...
: 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 number
In mathematics, a real number is a number that can be used to measure a ''continuous'' one-dimensional quantity such as a distance, duration or temperature. Here, ''continuous'' means that values can have arbitrarily small variations. Every real ...
s
and
are both mapped to the empty antichain.
Upper closure and lower closure
Given an element
of a partially ordered set
the upper closure or upward closure of
denoted by
or
is defined by
while the lower closure or downward closure of
, denoted by
or
is defined by
The sets
and
are, respectively, the smallest upper and lower sets containing
as an element.
More generally, given a subset
define the upper/upward closure and the lower/downward closures of
denoted by
and
respectively, as
and
In this way,
and
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 functions from the power set of
to itself, are examples of
closure operators
Closure may refer to:
Conceptual Psychology
* Closure (psychology), the state of experiencing an emotional conclusion to a difficult life event
Computer science
* Closure (computer programming), an abstraction binding a function to its scope
* ...
since they satisfy all of the
Kuratowski closure axioms In topology and related branches of mathematics, the Kuratowski closure axioms are a set of axioms that can be used to define a topological structure on a set. They are equivalent to the more commonly used open set definition. They were first forma ...
. 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
In topology, the closure of a subset of points in a topological space consists of all points in together with all limit points of . The closure of may equivalently be defined as the union of and its boundary, and also as the intersection ...
of a set is the intersection of all
closed sets containing it; the
span
Span may refer to:
Science, technology and engineering
* Span (unit), the width of a human hand
* Span (engineering), a section between two intermediate supports
* Wingspan, the distance between the wingtips of a bird or aircraft
* Sorbitan ester ...
of a set of vectors is the intersection of all
subspaces containing it; the
subgroup generated by a subset of a
group
A group is a number of persons or things that are located, gathered, or classed together.
Groups of people
* Cultural group, a group whose members share the same cultural identity
* Ethnic group, a group whose members share the same ethnic ide ...
is the intersection of all subgroups containing it; the
ideal
Ideal may refer to:
Philosophy
* Ideal (ethics), values that one actively pursues as goals
* Platonic ideal, a philosophical idea of trueness of form, associated with Plato
Mathematics
* Ideal (ring theory), special subsets of a ring considere ...
generated by a subset of a
ring
Ring may refer to:
* Ring (jewellery), a round band, usually made of metal, worn as ornamental jewelry
* To make a sound with a bell, and the sound made by a bell
:(hence) to initiate a telephone connection
Arts, entertainment and media Film and ...
is the intersection of all ideals containing it; and so on.)
Ordinal numbers
An
ordinal number
In set theory, an ordinal number, or ordinal, is a generalization of ordinal numerals (first, second, th, etc.) aimed to extend enumeration to infinite sets.
A finite set can be enumerated by successively labeling each element with the least n ...
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
*
Abstract simplicial complex
In combinatorics, an abstract simplicial complex (ASC), often called an abstract complex or just a complex, is a family of sets that is closed under taking subsets, i.e., every subset of a set in the family is also in the family. It is a purely c ...
(also called:
Independence system In combinatorics, combinatorial mathematics, an independence system is a pair (V, \mathcal), where is a finite Set (mathematics), set and is a collection of subsets of (called the independent sets or feasible sets) with the following properties: ...
) - a set-family that is downwards-closed with respect to the containment relation.
*
Cofinal set
In mathematics, a subset B \subseteq A of a preordered set (A, \leq) is said to be cofinal or frequent in A if for every a \in A, it is possible to find an element b in B that is "larger than a" (explicitly, "larger than a" means a \leq b).
Co ...
– a subset
of a partially ordered set
that contains for every element
some element
such that
References
*
*
* Hoffman, K. H. (2001)
''The low separation axioms (T0) and (T1)''
{{Order theory
Order theory
ru:Частично упорядоченное множество#Верхнее и нижнее множество