In

mathematicsMathematics 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

reflexiveIn 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

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 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 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...

: 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 setIn 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

topologyTopology 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

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. 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

limitIn 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

analysisMathematical 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 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 objects are understood 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 theoryCategory 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 subsetIn 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 number
In 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 setIn 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 (*n*_{0}, *n*_{1}) ≤ (*m*_{0}, *m*_{1}) if and only if *n*_{0} ≤ *m*_{0} and *n*_{1} ≤ *m*_{1}.
- If
*x*_{0} is a real 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** − {*x*_{0}} into a directed set by writing *a* ≤ *b* if and only if

|*a* − *x*_{0}| ≥ |*b* − *x*_{0}|. We then say that the reals have been *directed towards x*_{0}. 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 x_{0}" but in which the ordering rule only applies to pairs of elements on the same side of x_{0}.
- If
*T* is a topological 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 *x*_{0} is a point in *T*, we turn the set of all neighbourhoods of *x*_{0} 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 semilatticeIn 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

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:\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 setIn 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

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.