In
mathematics, a directed set (or a directed preorder or a filtered set) is a nonempty
set 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 sets. 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
sequences and unite the various notions of
limit used in
analysis. Directed sets also give rise to
direct limits in
abstract algebra 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 ...
s
with the ordinary order
is one of the most important examples of a directed set (and so is every
totally ordered set). By definition, a is a function from a directed set and a
sequence 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 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. 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 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 relation
along with its
dual define
partial orders 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 fami ...
.
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 fami ...
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 fami ...
that is a directed set with respect to the
partial order 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 fami ...
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 and
is a point in
set of all
neighbourhoods 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, 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 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 orders. 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. 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