In mathematics, a directed set (or a directed preorder or a filtered set) is a nonempty set 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 and in there must exist in with and A directed set's preorder is called a direction.

The notion defined above is sometimes called an upward directed set. A downward directed set is defined analogously,[2] meaning that every pair of elements is bounded below.[3] 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.[4]

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, lattices are directed sets both upward and downward.

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 edit

In addition to the definition above, there is an equivalent definition. A directed set is a set   with a preorder such that every finite subset of   has an upper bound. In this definition, the existence of an upper bound of the empty subset implies that   is nonempty.

Examples edit

The set of natural numbers   with the ordinary order   is one of the most important examples of a directed set. Every totally ordered set is a directed set, including       and  

A (trivial) example of a partially ordered set that is not directed is the set   in which the only order relations are   and   A less trivial example is like the following example of the "reals directed towards  " but in which the ordering rule only applies to pairs of elements on the same side of   (that is, if one takes an element   to the left of   and   to its right, then   and   are not comparable, and the subset   has no upper bound).

Product of directed sets edit

Let   and   be directed sets. Then the Cartesian product set   can be made into a directed set by defining   if and only if   and   In analogy to the product order this is the product direction on the Cartesian product. For example, the set   of pairs of natural numbers can be made into a directed set by defining   if and only if   and  

Directed towards a point edit

If   is a real number then the set   can be turned into a directed set by defining   if   (so "greater" elements are closer to  ). We then say that the reals have been directed towards   This is an example of a directed set that is neither partially ordered nor totally ordered. This is because antisymmetry breaks down for every pair   and   equidistant from   where   and   are on opposite sides of   Explicitly, this happens when   for some real   in which case   and   even though   Had this preorder been defined on   instead of   then it would still form a directed set but it would now have a (unique) greatest element, specifically  ; however, it still wouldn't be partially ordered. This example can be generalized to a metric space   by defining on   or   the preorder   if and only if  

Maximal and greatest elements edit

An element   of a preordered set   is a maximal element if for every     implies  [5] It is a greatest element if for every    

Any preordered set with a greatest element is a directed set with the same preorder. For instance, in a poset   every lower closure of an element; that is, every subset of the form   where   is a fixed element from   is directed.

Every maximal element of a directed preordered set is a greatest element. Indeed, a directed preordered set is characterized by equality of the (possibly empty) sets of maximal and of greatest elements.

Subset inclusion edit

The subset inclusion relation   along with its dual   define partial orders on any given family of sets. A non-empty family of sets is a directed set with respect to the partial order   (respectively,  ) if and only if the intersection (respectively, union) of any two of its members contains as a subset (respectively, is contained as a subset of) some third member. In symbols, a family   of sets is directed with respect to   (respectively,  ) if and only if

for all   there exists some   such that   and   (respectively,   and  )

or equivalently,

for all   there exists some   such that   (respectively,  ).

Many important examples of directed sets can be defined using these partial orders. For example, by definition, a prefilter or filter base 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 with respect to  ). Every π-system, which is a non-empty family of sets that is closed under the intersection of any two of its members, is a directed set with respect to   Every λ-system is a directed set with respect to   Every filter, topology, and σ-algebra is a directed set with respect to both   and  

Tails of nets edit

By definition, a net is a function from a directed set and a sequence is a function from the natural numbers   Every sequence canonically becomes a net by endowing   with  

If   is any net from a directed set   then for any index   the set   is called the tail of   starting at   The family   of all tails is a directed set with respect to   in fact, it is even a prefilter.

Neighborhoods edit

If   is a topological space and   is a point in   set of all neighbourhoods of   can be turned into a directed set by writing   if and only if   contains   For every     and   :

  •   since   contains itself.
  • if   and   then   and   which implies   Thus  
  • because   and since both   and   we have   and  

Finite subsets edit

The set   of all finite subsets of a set   is directed with respect to   since given any two   their union   is an upper bound of   and   in   This particular directed set is used to define the sum   of a generalized series of an  -indexed collection of numbers   (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   that is:


Logic edit

Let   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). For instance,   could be a first-order theory (like Zermelo–Fraenkel set theory) or a simpler zeroth-order theory. The preordered set   is a directed set because if   and if   denotes the sentence formed by logical conjunction   then   and   where   If   is the Lindenbaum–Tarski algebra associated with   then   is a partially ordered set that is also a directed set.

Contrast with semilattices edit

Example of a directed set which is not a join-semilattice

Directed set is a more general concept than (join) semilattice: every join semilattice is a directed set, as the join or least upper bound of two elements is the desired   The converse does not hold however, witness the directed set {1000,0001,1101,1011,1111} ordered bitwise (e.g.   holds, but   does not, since in the last bit 1 > 0), where {1000,0001} has three upper bounds but no least upper bound, cf. picture. (Also note that without 1111, the set is not directed.)

Directed subsets edit

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 directed set is also used frequently in the context of posets. In this setting, a subset   of a partially ordered set   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   is inherited from  ; 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.[6] 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.[further explanation needed]

See also edit

Notes edit

  1. ^ Kelley, p. 65.
  2. ^ Robert S. Borden (1988). A Course in Advanced Calculus. Courier Corporation. p. 20. ISBN 978-0-486-15038-3.
  3. ^ Arlen Brown; Carl Pearcy (1995). An Introduction to Analysis. Springer. p. 13. ISBN 978-1-4612-0787-0.
  4. ^ Siegfried Carl; Seppo Heikkilä (2010). Fixed Point Theory in Ordered Sets and Applications: From Differential and Integral Equations to Game Theory. Springer. p. 77. ISBN 978-1-4419-7585-0.
  5. ^ This implies   if   is a partially ordered set.
  6. ^ Gierz, p. 2.

References edit

  • J. L. Kelley (1955), General Topology.
  • Gierz, Hofmann, Keimel, et al. (2003), Continuous Lattices and Domains, Cambridge University Press. ISBN 0-521-80338-1.