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 ...
, a directed set (or a directed preorder or a filtered set) is a nonempty
set
Set, The Set, SET or SETS may refer to:
Science, technology, and mathematics Mathematics
*Set (mathematics), a collection of elements
*Category of sets, the category whose objects and morphisms are sets and total functions, respectively
Electro ...
together with a
reflexive and
transitive binary relation (that is, a
preorder), with the additional property that every pair of elements has an
upper bound
In mathematics, particularly in order theory, an upper bound or majorant of a subset of some preordered set is an element of that is greater than or equal to every element of .
Dually, a lower bound or minorant of is defined to be an eleme ...
. In other words, for any
and
in
there must exist
in
with
and
A directed set's preorder is called a .
The notion defined above is sometimes called an . A is defined analogously, meaning that every pair of elements is bounded below.
Some authors (and this article) assume that a directed set is directed upward, unless otherwise stated. Other authors call a set directed if and only if it is directed both upward and downward.
Directed sets are a generalization of nonempty
totally ordered set
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 \leq on some set X, which satisfies the following for all a, b and c in X:
# a \leq a ( reflexive) ...
s. That is, all totally ordered sets are directed sets (contrast
ordered sets, which need not be directed).
Join-semilattices (which are partially ordered sets) are directed sets as well, but not conversely. Likewise,
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 ...
s are directed sets both upward and downward.
In
topology
In mathematics, topology (from the Greek words , and ) is concerned with the properties of a geometric object that are preserved under continuous deformations, such as stretching, twisting, crumpling, and bending; that is, without closing ...
, directed sets are used to define
nets, which generalize
sequence
In mathematics, a sequence is an enumerated collection of objects in which repetitions are allowed and order matters. Like a set, it contains members (also called ''elements'', or ''terms''). The number of elements (possibly infinite) is calle ...
s and unite the various notions of
limit
Limit or Limits may refer to:
Arts and media
* ''Limit'' (manga), a manga by Keiko Suenobu
* ''Limit'' (film), a South Korean film
* Limit (music), a way to characterize harmony
* "Limit" (song), a 2016 single by Luna Sea
* "Limits", a 2019 ...
used in
analysis
Analysis ( : analyses) is the process of breaking a complex topic or substance into smaller parts in order to gain a better understanding of it. The technique has been applied in the study of mathematics and logic since before Aristotle (38 ...
. Directed sets also give rise to
direct limits in
abstract algebra
In mathematics, more specifically algebra, abstract algebra or modern algebra is the study of algebraic structures. Algebraic structures include groups, rings, fields, modules, vector spaces, lattices, and algebras over a field. The term ''a ...
and (more generally)
category theory.
Equivalent definition
In addition to the definition above, there is an equivalent definition. A directed set is a set
with a
preorder such that every finite subset of
has an upper bound. In this definition, the existence of an upper bound of the
empty subset
In mathematics, the empty set is the unique Set (mathematics), set having no Element (mathematics), elements; its size or cardinality (count of elements in a set) is 0, zero. Some axiomatic set theories ensure that the empty set exists by inclu ...
implies that
is nonempty.
Examples
The set of
natural number
In mathematics, the natural numbers are those numbers used for counting (as in "there are ''six'' coins on the table") and ordering (as in "this is the ''third'' largest city in the country").
Numbers used for counting are called ''Cardinal n ...
s
with the ordinary order
is one of the most important examples of a directed set (and so is every
totally ordered set
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 \leq on some set X, which satisfies the following for all a, b and c in X:
# a \leq a ( reflexive) ...
). By definition, a is a function from a directed set and a
sequence
In mathematics, a sequence is an enumerated collection of objects in which repetitions are allowed and order matters. Like a set, it contains members (also called ''elements'', or ''terms''). The number of elements (possibly infinite) is calle ...
is a function from the natural numbers
Every sequence canonically becomes a net by endowing
with
A (trivial) example of a partially ordered set that is directed is the set
in which the only order relations are
and
A less trivial example is like the previous example of the "reals directed towards
" but in which the ordering rule only applies to pairs of elements on the same side of
(that is, if one takes an element
to the left of
and
to its right, then
and
are not comparable, and the subset
has no upper bound).
If
is a
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 ...
then the set
can be turned into a directed set by defining
if
(so "greater" elements are closer to
). We then say that the reals have been directed towards
This is an example of a directed set that is
partially ordered
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. A poset consists of a set together with a binary r ...
nor
totally ordered
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 \leq on some set X, which satisfies the following for all a, b and c in X:
# a \leq a ( reflexive ...
. This is because
antisymmetry
In linguistics, antisymmetry is a syntactic theory presented in Richard S. Kayne's 1994 monograph ''The Antisymmetry of Syntax''. It asserts that grammatical hierarchies in natural language follow a universal order, namely specifier-head-comple ...
breaks down for every pair
and
equidistant from
where
and
are on opposite sides of
Explicitly, this happens when
for some real
in which case
and
even though
Had this preorder been defined on
instead of
then it would still form a directed set but it would now have a (unique) greatest element, specifically
; however, it still wouldn't be partially ordered. This example can be generalized to a
metric space
In mathematics, a metric space is a set together with a notion of ''distance'' between its elements, usually called points. The distance is measured by a function called a metric or distance function. Metric spaces are the most general settin ...
by defining on
or
the preorder
if and only if
Maximal and greatest elements
An element
of a preordered set
is a
maximal element if for every
,
implies
.
It is a
greatest element
In mathematics, especially in order theory, the greatest element of a subset S of a partially ordered set (poset) is an element of S that is greater than every other element of S. The term least element is defined dually, that is, it is an elem ...
if for every
Some straightforward implications of the definition include:
- Any preordered set with a greatest element is a directed set with the same preorder.
* For instance, in a
poset
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. A poset consists of a set together with a binary r ...
every lower closure of an element; that is, every subset of the form where is a fixed element from is directed.
- Every maximal element of a directed preordered set is a greatest element. Indeed, a directed preordered set is characterized by equality of the (possibly empty) sets of maximal and of greatest elements.
Product of directed sets
Let
and
be directed sets. Then the Cartesian product set
can be made into a directed set by defining
if and only if
and
In analogy to the
product order
In mathematics, given two preordered sets A and B, the product order (also called the coordinatewise orderDavey & Priestley, ''Introduction to Lattices and Order'' (Second Edition), 2002, p. 18 or componentwise order) is a partial ordering o ...
this is the product direction on the Cartesian product. For example, the set
of pairs of natural numbers can be made into a directed set by defining
if and only if
and
Subset inclusion
The
subset inclusion
In mathematics, 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 ...
relation
along with its
dual define
partial order
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. A poset consists of a set together with a binary ...
s on any given
family of sets
In set theory and related branches of mathematics, a collection F of subsets of a given set S is called a family of subsets of S, or a family of sets over S. More generally, a collection of any sets whatsoever is called a family of sets, set fam ...
.
A non-empty
family of sets
In set theory and related branches of mathematics, a collection F of subsets of a given set S is called a family of subsets of S, or a family of sets over S. More generally, a collection of any sets whatsoever is called a family of sets, set fam ...
is a directed set with respect to the partial order
(respectively,
) if and only if the intersection (respectively, union) of any two of its members contains as a subset (respectively, is contained as a subset of) some third member.
In symbols, a family
of sets is directed with respect to
(respectively,
) if and only if
:for all
there exists some
such that
and
(respectively,
and
)
or equivalently,
:for all
there exists some
such that
(respectively,
).
Many important examples of directed sets can be defined using these partial orders.
For example, by definition, a
or is a non-empty
family of sets
In set theory and related branches of mathematics, a collection F of subsets of a given set S is called a family of subsets of S, or a family of sets over S. More generally, a collection of any sets whatsoever is called a family of sets, set fam ...
that is a directed set with respect to the
partial order
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. A poset consists of a set together with a binary ...
and that also does not contain the empty set (this condition prevents triviality because otherwise, the empty set would then be a
greatest element
In mathematics, especially in order theory, the greatest element of a subset S of a partially ordered set (poset) is an element of S that is greater than every other element of S. The term least element is defined dually, that is, it is an elem ...
with respect to
).
Every
-system, which is a non-empty
family of sets
In set theory and related branches of mathematics, a collection F of subsets of a given set S is called a family of subsets of S, or a family of sets over S. More generally, a collection of any sets whatsoever is called a family of sets, set fam ...
that is closed under the intersection of any two of its members, is a directed set with respect to
Every
λ-system is a directed set with respect to
Every
filter
Filter, filtering or filters may refer to:
Science and technology
Computing
* Filter (higher-order function), in functional programming
* Filter (software), a computer program to process a data stream
* Filter (video), a software component tha ...
,
topology
In mathematics, topology (from the Greek words , and ) is concerned with the properties of a geometric object that are preserved under continuous deformations, such as stretching, twisting, crumpling, and bending; that is, without closing ...
, and
σ-algebra
In mathematical analysis and in probability theory, a σ-algebra (also σ-field) on a set ''X'' is a collection Σ of subsets of ''X'' that includes the empty subset, is closed under complement, and is closed under countable unions and countabl ...
is a directed set with respect to both
and
If
is any
net
Net or net may refer to:
Mathematics and physics
* Net (mathematics), a filter-like topological generalization of a sequence
* Net, a linear system of divisors of dimension 2
* Net (polyhedron), an arrangement of polygons that can be folded up ...
from a directed set
then for any index
the set
is called the tail of
starting at
The family
of all tails is a directed set with respect to
in fact, it is even a prefilter.
If
is a
topological space
In mathematics, a topological space is, roughly speaking, a geometrical space in which closeness is defined but cannot necessarily be measured by a numeric distance. More specifically, a topological space is a set whose elements are called po ...
and
is a point in
set of all
neighbourhoods
A neighbourhood (British English, Irish English, Australian English and Canadian English) or neighborhood (American English; American and British English spelling differences, see spelling differences) is a geographically localised community ...
of
can be turned into a directed set by writing
if and only if
contains
For every
and
:
*
since
contains itself.
* if
and
then
and
which implies
Thus
* because
and since both
and
we have
and
Let
denote the set of all finite subsets of
Then
is directed with respect to
since given any two
the union
is an upper bound of
and
in
This particular directed set is used to define the sum
of a
generalized series of an
-indexed collection of numbers
(or
elements in an abelian topological group
Abelian may refer to:
Mathematics Group theory
* Abelian group, a group in which the binary operation is commutative
** Category of abelian groups (Ab), has abelian groups as objects and group homomorphisms as morphisms
* Metabelian group, a gro ...
, such as
vectors in a
topological vector space
In mathematics, a topological vector space (also called a linear topological space and commonly abbreviated TVS or t.v.s.) is one of the basic structures investigated in functional analysis.
A topological vector space is a vector space that is als ...
) as the
limit of the net of
partial sum
In mathematics, a series is, roughly speaking, a description of the operation of adding infinitely many quantities, one after the other, to a given starting quantity. The study of series is a major part of calculus and its generalization, math ...
s
that is:
Contrast with semilattices
![Directed_set,_but_no_join_semi-lattice](https://upload.wikimedia.org/wikipedia/commons/a/a2/Directed_set%2C_but_no_join_semi-lattice.png)
Directed sets are a more general concept than (join) semilattices: every
join semilattice is a directed set, as the join or least upper bound of two elements is the desired
The converse does not hold however, witness the directed set
ordered bitwise (e.g.
holds, but
does not, since in the last bit 1 > 0), where has three upper bounds but no upper bound, cf. picture. (Also note that without 1111, the set is not directed.)
Directed subsets
The order relation in a directed set is not required to be
antisymmetric, and therefore directed sets are not always
partial order
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. A poset consists of a set together with a binary ...
s. However, the term is also used frequently in the context of posets. In this setting, a subset
of a partially ordered set
is called a directed subset if it is a directed set according to the same partial order: in other words, it is not the
empty set, and every pair of elements has an upper bound. Here the order relation on the elements of
is inherited from
; for this reason, reflexivity and transitivity need not be required explicitly.
A directed subset of a poset is not required to be
downward closed; a subset of a poset is directed if and only if its downward closure is an
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 ...
. While the definition of a directed set is for an "upward-directed" set (every pair of elements has an upper bound), it is also possible to define a downward-directed set in which every pair of elements has a common lower bound. A subset of a poset is downward-directed if and only if its upper closure is a
filter
Filter, filtering or filters may refer to:
Science and technology
Computing
* Filter (higher-order function), in functional programming
* Filter (software), a computer program to process a data stream
* Filter (video), a software component tha ...
.
Directed subsets are used in
domain theory
Domain theory is a branch of mathematics that studies special kinds of partially ordered sets (posets) commonly called domains. Consequently, domain theory can be considered as a branch of order theory. The field has major applications in computer ...
, which studies
directed-complete partial orders.
[Gierz, p. 2.] These are posets in which every upward-directed set is required to have a
least upper bound
In mathematics, the infimum (abbreviated inf; plural infima) of a subset S of a partially ordered set P is a greatest element in P that is less than or equal to each element of S, if such an element exists. Consequently, the term ''greatest lo ...
. In this context, directed subsets again provide a generalization of convergent sequences.
See also
*
*
*
*
*
Notes
References
* J. L. Kelley (1955), ''General Topology''.
* Gierz, Hofmann, Keimel, ''et al.'' (2003), ''Continuous Lattices and Domains'', Cambridge University Press. .
{{Order theory
Binary relations
General topology
Order theory