In
mathematicsMathematics is the science and study of quantity, structure, space, and change. Mathematicians seek out patterns, formulate new conjectures, and establish truth by rigorous deduction from appropriately chosen axioms and definitions....
, a
directed set (or a
directed preorder or a
filtered set) is a nonempty set
A together with a
reflexiveIn mathematics, a reflexive relation is a binary relation on a set for which every element is related to itself, i.e., a relation R on S where xRx holds true for every x in S.-Related terms:...
and
transitiveIn mathematics, a binary relation R over a set X is transitive if whenever an element a is related to an element b, and b is in turn related to an element c, then a is also related to c....
binary relationIn mathematics, a binary relation on a set A is a collection of ordered pairs of elements of A. In other words, it is a subset of the Cartesian product A2 = . More generally, a binary relation between two sets A and B is a subset of...
≤ (that is, a
preorderIn mathematics, especially in order theory, preorders are binary relations that satisfy certain conditions. For example, all partial orders and equivalence relations are preorders. The name quasiorder is also common for preorders. Other names are pre-order, quasi-order, and quasi order...
), with the additional property that every pair of elements has an
upper boundIn mathematics, especially in order theory, an upper bound of a subset S of some partially ordered set is an element of P which is greater than or equal to every element of S. The term lower bound is defined dually as an element of P which is lesser than or equal to every element of S...
.
Directed sets are a generalization of nonempty totally ordered sets, that is, all totally ordered sets are directed sets (but not all
partially ordered setIn mathematics, especially order theory, a partially ordered set formalizes 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 that describes, for certain pairs of elements in the set, the requirement...
s). In
topologyTopology is a major area of mathematics concerned with spatial properties that are preserved under continuous deformations of objects, for example deformations that involve stretching, but no tearing or gluing...
, directed sets are used to define nets, which generalize
sequenceIn mathematics, a sequence is an ordered list of objects . Like a set, it contains members , and the number of terms is called the length of the sequence...
s and unite the various notions of
limit used in
analysisMathematical analysis, which mathematicians refer to simply as analysis, has its beginnings in the rigorous formulation of calculus. It is the branch of pure mathematics most explicitly concerned with the notion of a limit, whether the limit of a sequence or the limit of a function...
.
In
mathematicsMathematics is the science and study of quantity, structure, space, and change. Mathematicians seek out patterns, formulate new conjectures, and establish truth by rigorous deduction from appropriately chosen axioms and definitions....
, a
directed set (or a
directed preorder or a
filtered set) is a nonempty set
A together with a
reflexiveIn mathematics, a reflexive relation is a binary relation on a set for which every element is related to itself, i.e., a relation R on S where xRx holds true for every x in S.-Related terms:...
and
transitiveIn mathematics, a binary relation R over a set X is transitive if whenever an element a is related to an element b, and b is in turn related to an element c, then a is also related to c....
binary relationIn mathematics, a binary relation on a set A is a collection of ordered pairs of elements of A. In other words, it is a subset of the Cartesian product A2 = . More generally, a binary relation between two sets A and B is a subset of...
≤ (that is, a
preorderIn mathematics, especially in order theory, preorders are binary relations that satisfy certain conditions. For example, all partial orders and equivalence relations are preorders. The name quasiorder is also common for preorders. Other names are pre-order, quasi-order, and quasi order...
), with the additional property that every pair of elements has an
upper boundIn mathematics, especially in order theory, an upper bound of a subset S of some partially ordered set is an element of P which is greater than or equal to every element of S. The term lower bound is defined dually as an element of P which is lesser than or equal to every element of S...
.
Directed sets are a generalization of nonempty totally ordered sets, that is, all totally ordered sets are directed sets (but not all
partially ordered setIn mathematics, especially order theory, a partially ordered set formalizes 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 that describes, for certain pairs of elements in the set, the requirement...
s). In
topologyTopology is a major area of mathematics concerned with spatial properties that are preserved under continuous deformations of objects, for example deformations that involve stretching, but no tearing or gluing...
, directed sets are used to define nets, which generalize
sequenceIn mathematics, a sequence is an ordered list of objects . Like a set, it contains members , and the number of terms is called the length of the sequence...
s and unite the various notions of
limit used in
analysisMathematical analysis, which mathematicians refer to simply as analysis, has its beginnings in the rigorous formulation of calculus. It is the branch of pure mathematics most explicitly concerned with the notion of a limit, whether the limit of a sequence or the limit of a function...
. Directed sets also give rise to
direct limitIn mathematics, a direct limit is a colimit of a "directed family of objects". We will first give the definition for algebraic structures like groups and modules, and then the general definition which can be used in any category.- Algebraic objects :In this section we will understand objects to be...
s in
abstract algebraAbstract algebra is the subject area of mathematics that studies algebraic structures, such as groups, rings, fields, modules, vector spaces, and algebras...
and (more generally)
category theoryIn mathematics, category theory deals in an abstract way with mathematical structures and relationships between them: it abstracts from sets and functions to objects linked in diagrams by morphisms or arrows....
.
Examples
Examples of directed sets include:
- The set of natural number
In mathematics, there are two conventions for the set of natural numbers: it is either the set of positive integers {, , , ...} according to the traditional definition or the set of non-negative integers {, 1, 2, ...} according to...
s N with the ordinary order ≤ is a directed set (and so is every totally ordered setIn mathematics and set theory, a total order, linear order, simple order, or ordering is a binary relation on some set X. The relation is transitive, antisymmetric, and total...
).
- The set N N of pairs of natural numbers can be made into a directed set by defining (n0 , n1) ≤ (m0, m1) if and only if n0 ≤ m0 and n1 ≤ m1.
- If x0 is a real number
In mathematics, the real numbers include both rational numbers, such as 42 and −23/129, and irrational numbers, such as pi and the square root of two; or, a real number can be given by an infinite decimal representation, such as 2.4871773339..., where the digits continue in some way; or, the real...
, we can turn the set R − {x0} into a directed set by writing a ≤ b if and only if
|a − x0| ≥ |b − x0|. We then say that the reals have been directed towards x0. This is an example of a directed set that is not ordered (neither totally nor partially).
- A (trivial) example of a partially ordered set that is not directed is the set {a, b}, in which the only order relations are a ≤ a and b ≤ b. A less trivial example is like the previous example of the "reals directed towards x0" but in which the ordering rule only applies to pairs of elements on the same side of x0.
- If T is a topological space
Topological spaces are mathematical structures that allow the formal definition of concepts such as convergence, connectedness, and continuity. They appear in virtually every branch of modern mathematics and are a central unifying notion...
and x0 is a point in T, we turn the set of all neighbourhoods of x0 into a directed set by writing U ≤ V if and only if U contains V.
- For every U: U ≤ U; since U contains itself.
- For every U,V,W: if U ≤ V and V ≤ W, then U ≤ W; since if U contains V and V contains W then U contains W.
- For every U, V: there exists the set U V such that U ≤ U V and V ≤ U V; since both U and V contain U V.
- In a poset P, every subset of the form {a| a in P, a ≤x}, where x is a fixed element from P, is directed.
Contrast with semilattices
Directed sets are a more general concept than (join) semilattices: every
join semilatticeIn mathematics, a join-semilattice is a partially ordered set which has a join for any finite subset. Dually, a meet-semilattice is a partially ordered set which has a meet for any finite subset...
is a directed set, as the join or least upper bound of two elements is the desired
c. The converse does not hold however, witness the directed set {1000,0001,1101,1011,1111} ordered bitwise, where {1000,0001} has three upper bounds but no
least upper bound.
Directed subsets
The order relation in a directed sets is not required to be
antisymmetricIn mathematics, a binary relation R on a set X is antisymmetric if, for all a and b in Xor, equivalently,In mathematical notation, this is:or equally,An example of an antisymmetric relation is the subset relation:...
, and therefore directed sets are not always partial orders. However, the term
directed set is also used frequently in the context of posets. In this setting, a subset
A of a partially ordered set (
P,≤) is called a
directed subset if
A is not the
empty setIn mathematics, and more specifically set theory, the empty set is the unique set having no members; its size is zero. Some axiomatic set theories assure that the empty set exists by including an axiom of empty set; in other theories, its existence can be deduced...
, and for any
a and
b in
A there exists a
c in
A with
a ≤
c and
b ≤
c. Here the order relation on the elements of
A is inherited from
P; 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
idealIn mathematical order theory, an ideal is a special subset of a partially ordered set . Although this term historically was derived from the notion of a ring ideal of abstract algebra, it has subsequently been generalized to a different notion...
. 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
filterIn mathematics, a filter is a special subset of a partially ordered set. A frequently used special case is the situation that the ordered set under consideration is just the power set of some set, ordered by set inclusion. Filters appear in order and lattice theory, but can also be found in...
.
Directed subsets are used in
domain theoryDomain theory is a branch of mathematics that studies special kinds of partially ordered sets commonly called domains. Consequently, domain theory can be considered as a branch of order theory. The field has major applications in computer science, where it is used to specify denotational...
, which studies directed complete partial orders. These are posets in which every upward-directed set is required to have a least upper bound. In this context, directed subsets again provide a generalization of convergent sequences.