# Directed set

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:[1] In other words, for any a and b in A there must exist a c in A with ac and bc.

Directed sets are a generalization of nonempty totally ordered sets, that is, all totally ordered sets are directed sets (contrast partially ordered sets which need not be directed). In topology, 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 A with a preorder such that every finite subset of A has an upper bound. In this definition, the existence of an upper bound of the empty subset implies that A is nonempty.

## Examples

Examples of directed sets include:

Witness

## 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 c. The converse does not hold however, witness the directed set {1000,0001,1101,1011,1111} ordered bitwise (e.g. 1000 ≤ 1011 holds, but 0001 ≤ 1000 does not, since in the last bit 1 > 0), where {1000,0001} has three upper bounds but no least upper bound, cf. picture.

## Directed subsets

The order relation in a directed sets is not required to be antisymmetric, 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.[2] 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.