In mathematics, a directed set (or a directed preorder or a filtered set) is a preordered set in which every finite subset has an upper bound.. A directed set's preorder is called a direction.

The notion defined above is sometimes called an . A is defined symmetrically, meaning that every finite subset has a lower bound. 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 partially ordered sets, which need not be directed). Join-semilattices (which are partially ordered sets) are directed sets as well, but not conversely. Likewise, latticess are directed sets both upward and downward.

In topology, directed sets are used to define nets, which generalize sequences and unify the various notions of limit used in analysis. Directed sets also give rise to direct limits in abstract algebra and (more generally) category theory.

Examples

The set of natural numbers is one of the most important examples of a directed set. Every totally ordered set

A (trivial) example of a partially ordered set that is has no upper bound).

If an abstract rewriting system is confluent is a directed set.

Product of directed sets

be directed sets. Then the Cartesian product In analogy to the product order

Directed towards a point

is a real number). We then say that the reals have been This is an example of a directed set that is partially ordered nor totally ordered. This is because antisymmetry then it would still form a directed set but it would now have a (unique) greatest element; however, it still wouldn't be partially ordered. This example can be generalized to a metric space

Maximal and greatest elements

is a maximal element It is a greatest element

Any preordered set with a greatest element is a directed set with the same preorder. For instance, in a poset every lower closure is directed.

A preordered set is directed if and only if the (possibly empty) set of maximal elements is equal to the set of greatest elements.

Subset inclusion

The subset inclusion along with its dual define partial orders on any given family of sets. A non-empty family of sets) if and only if

1. )

or equivalently,

1. ).

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 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). Every -system, which is a non-empty family of sets Every λ-system Every filter, topology, and σ-algebra

Tails of nets

By definition, a is a function from a directed set and a sequence

is any net in fact, it is even a prefilter.

Neighborhoods

is a topological space the set of all neighbourhoods:

• contains itself.

Finite subsets

of a generalized series (or more generally, the sum of elements in an abelian topological group, such as vectors in a topological vector space) as the limit of the net of partial sums

Logic

be a formal theory, which is a set of sentences with certain properties (details of which can be found in the article on the subject could be a first-order theory (like Zermelo–Fraenkel set theory) or a simpler zeroth-order theory denotes the sentence formed by logical conjunction is the Lindenbaum–Tarski algebra is a partially ordered set that is also a directed set.

Contrast with semilattices

Directed set is a more general concept than (join) semilattice: every join semilattice The converse does not hold however, witness the directed set {1000,0001,1101,1011,1111} ordered bitwise does not, since in the last bit 1 > 0), where {1000,0001} 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 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; 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 orderss. 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.

See also

Notes

Footnotes

Works cited