Directed set
Encyclopedia
In mathematics
, a directed set (or a directed preorder or a filtered set) is a nonempty set A 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 other words, for any a and b in A there must exist a c in A with a ≤ c and b ≤ c.
Directed sets are a generalization of nonempty totally ordered sets, that is, all totally ordered sets are directed sets (but not all partially ordered set
s). In topology
, directed sets are used to define nets, which generalize sequence
s and unite the various notions of limit
used in analysis
. Directed sets also give rise to direct limit
s in abstract algebra
and (more generally) category theory
.
is any existing element of A, because A is nonempty; furthermore, as provable with an induction argument over the size of nonempty finite subsets, the upper bound of a finite subset may be obtained by finding upper bounds of pairs iteratively.
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 (e.g. 1000 ≤ 1011 holds, but 1000 ≤ 0001 does not), where {1000,0001} has three upper bounds but no least upper bound.
, 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 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 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 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
.
Directed subsets are used in domain theory
, 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.
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
, a directed set (or a directed preorder or a filtered set) is a nonempty set A together with a reflexive
Reflexive relation
In mathematics, a reflexive relation is a binary relation on a set for which every element is related to itself, i.e., a relation ~ on S where x~x holds true for every x in S. For example, ~ could be "is equal to".-Related terms:...
and transitive
Transitive relation
In 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 relation
Binary relation
In 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 preorder
Preorder
In mathematics, especially in order theory, preorders are binary relations that are reflexive and transitive.For example, all partial orders and equivalence relations are preorders...
), with the additional property that every pair of elements has an upper bound
Upper bound
In 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...
: In other words, for any a and b in A there must exist a c in A with a ≤ c and b ≤ c.
Directed sets are a generalization of nonempty totally ordered sets, that is, all totally ordered sets are directed sets (but not all partially ordered set
Partially ordered set
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 that indicates that, for certain pairs of elements in the...
s). In topology
Topology
Topology is a major area of mathematics concerned with properties that are preserved under continuous deformations of objects, such as deformations that involve stretching, but no tearing or gluing...
, directed sets are used to define nets, which generalize sequence
Sequence
In 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. Unlike a set, order matters, and exactly the same elements can appear multiple times at different positions in the sequence...
s and unite the various notions of limit
Limit (mathematics)
In mathematics, the concept of a "limit" is used to describe the value that a function or sequence "approaches" as the input or index approaches some value. The concept of limit allows mathematicians to define a new point from a Cauchy sequence of previously defined points within a complete metric...
used in analysis
Mathematical analysis
Mathematical analysis, which mathematicians refer to simply as analysis, has its beginnings in the rigorous formulation of infinitesimal calculus. It is a branch of pure mathematics that includes the theories of differentiation, integration and measure, limits, infinite series, and analytic functions...
. Directed sets also give rise to direct limit
Direct limit
In 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 objects are understood to be...
s in abstract algebra
Abstract algebra
Abstract 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 theory
Category theory
Category theory is an area of study in mathematics that examines in an abstract way the properties of particular mathematical concepts, by formalising them as collections of objects and arrows , where these collections satisfy certain basic conditions...
.
Equivalent definition
In addition to the definition above, there is an equivalent definition. A directed set is a set A with a preorder such that every finite subset of A has an upper bound. The above definition implies this one: the upper bound of the empty subsetEmpty set
In mathematics, and more specifically set theory, the empty set is the unique set having no elements; its size or cardinality 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...
is any existing element of A, because A is nonempty; furthermore, as provable with an induction argument over the size of nonempty finite subsets, the upper bound of a finite subset may be obtained by finding upper bounds of pairs iteratively.
Examples
Examples of directed sets include:- The set of natural numberNatural numberIn mathematics, the natural numbers are the ordinary whole numbers used for counting and ordering . These purposes are related to the linguistic notions of cardinal and ordinal numbers, respectively...
s N with the ordinary order ≤ is a directed set (and so is every totally ordered setTotal orderIn 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 numberReal numberIn mathematics, a real number is a value that represents a quantity along a continuum, such as -5 , 4/3 , 8.6 , √2 and π...
, 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 spaceTopological spaceTopological 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 lower closure of an element, i.e. 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 semilatticeSemilattice
In mathematics, a join-semilattice is a partially ordered set which has a join for any nonempty finite subset. Dually, a meet-semilattice is a partially ordered set which has a meet for any nonempty 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 (e.g. 1000 ≤ 1011 holds, but 1000 ≤ 0001 does not), 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 antisymmetricAntisymmetric relation
In 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:\forall a, b \in X,\ R \and R \; \Rightarrow \; a = bor, equivalently,...
, 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 it is a directed set according to the same partial order: in other words, it is not the empty set
Empty set
In mathematics, and more specifically set theory, the empty set is the unique set having no elements; its size or cardinality 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 every pair of elements has an upper bound. 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 ideal
Ideal (order theory)
In 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 filter
Filter (mathematics)
In 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 theory
Domain theory
Domain 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.