View source for Directed set

{{Short description|Mathematical ordering with upper bounds}}
In [[mathematics]], a '''directed set''' (or a '''directed preorder''' or a '''filtered set''') is a nonempty [[Set (mathematics)|set]] <math>A</math> together with a [[Reflexive relation|reflexive]] and [[Transitive relation|transitive]] [[binary relation]] <math>\,\leq\,</math> (that is, a [[preorder]]), with the additional property that every pair of elements has an [[upper bound]].<ref>Kelley, p. 65.</ref> In other words, for any <math>a</math> and <math>b</math> in <math>A</math> there must exist <math>c</math> in <math>A</math> with <math>a \leq c</math> and <math>b \leq c.</math> A directed set's preorder is called a '''direction'''.

The notion defined above is sometimes called an '''{{visible anchor|upward directed set}}'''. A '''{{visible anchor|downward directed set}}''' is defined analogously,<ref>{{cite book|author=Robert S. Borden|title=A Course in Advanced Calculus|year=1988|publisher=Courier Corporation|isbn=978-0-486-15038-3|page=20}}</ref> meaning that every pair of elements is bounded below.<ref name="Brown-Pearcy">{{cite book|author1=Arlen Brown|author2=Carl Pearcy|title=An Introduction to Analysis|url=https://archive.org/details/introductiontoan0000brow|url-access=registration|year=1995|publisher=Springer|isbn=978-1-4612-0787-0|page=[https://archive.org/details/introductiontoan0000brow/page/13 13]}}</ref> 
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.<ref name="CarlHeikkilä2010">{{cite book|author1=Siegfried Carl|author2=Seppo Heikkilä|title=Fixed Point Theory in Ordered Sets and Applications: From Differential and Integral Equations to Game Theory|year=2010|publisher=Springer|isbn=978-1-4419-7585-0|pages=77}}</ref>

Directed sets are a generalization of nonempty [[totally ordered set]]s. That is, all totally ordered sets are directed sets (contrast [[Partially ordered sets|{{em|partially}} ordered sets]], which need not be directed). [[Join-semilattice]]s (which are partially ordered sets) are directed sets as well, but not conversely. Likewise, [[Lattice (order)|lattice]]s are directed sets both upward and downward.

In [[topology]], directed sets are used to define [[Net (topology)|nets]], which generalize [[sequence]]s and unite the various notions of [[Limit (mathematics)|limit]] used in [[Mathematical analysis|analysis]]. Directed sets also give rise to [[direct limit]]s 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 <math>A</math> with a [[preorder]] such that every finite subset of <math>A</math> has an upper bound. In this definition, the existence of an upper bound of the [[Empty set|empty subset]] implies that <math>A</math> is nonempty.

==Examples==

The set of [[natural number]]s <math>\N</math> with the ordinary order <math>\,\leq\,</math> is one of the most important examples of a directed set. Every [[Total order|totally ordered set]] is a directed set, including <math>(\N, \leq),</math> <math>(\N, \geq),</math> <math>(\Reals, \leq),</math> and <math>(\Reals, \geq).</math>

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

===Product of directed sets===

Let <math>\mathbb{D}_1</math> and <math>\mathbb{D}_2</math> be directed sets. Then the [[Cartesian product]] set <math>\mathbb{D}_1 \times \mathbb{D}_2</math> can be made into a directed set by defining <math>\left(n_1, n_2\right) \leq \left(m_1, m_2\right)</math> if and only if <math>n_1 \leq m_1</math> and <math>n_2 \leq m_2.</math> In analogy to the [[product order]] this is the product direction on the Cartesian product.  For example, the set <math>\N \times \N</math> of pairs of natural numbers can be made into a directed set by defining <math>\left(n_0, n_1\right) \leq \left(m_0, m_1\right)</math> if and only if <math>n_0 \leq m_0</math> and <math>n_1 \leq m_1.</math>

===Directed towards a point===

If <math>x_0</math> is a [[real number]] then the set <math>I := \R \backslash \lbrace x_0 \rbrace</math> can be turned into a directed set by defining <math>a \leq_I b</math> if <math>\left|a - x_0\right| \geq \left|b - x_0\right|</math> (so "greater" elements are closer to <math>x_0</math>). We then say that the reals have been '''directed towards <math>x_0.</math>''' This is an example of a directed set that is {{em|neither}} [[Partial order|partially ordered]] nor [[Total order|totally ordered]]. This is because [[Antisymmetric relation|antisymmetry]] breaks down for every pair <math>a</math> and <math>b</math> equidistant from <math>x_0,</math> where <math>a</math> and <math>b</math> are on opposite sides of <math>x_0.</math> Explicitly, this happens when <math>\{a, b\} = \left\{x_0 - r, x_0 + r\right\}</math> for some real <math>r \neq 0,</math> in which case <math>a \leq_I b</math> and <math>b \leq_I a</math> even though <math>a \neq b.</math> Had this preorder been defined on <math>\R</math> instead of <math>\R \backslash \lbrace x_0 \rbrace</math> then it would still form a directed set but it would now have a (unique) [[greatest element]], specifically <math>x_0</math>; however, it still wouldn't be partially ordered. This example can be generalized to a [[metric space]] <math>(X, d)</math> by defining on <math>X</math> or <math>X \setminus \left\{x_0\right\}</math> the preorder <math>a \leq b</math> if and only if <math>d\left(a, x_0\right) \geq d\left(b, x_0\right).</math>

===Maximal and greatest elements===

An element <math>m</math> of a preordered set <math>(I, \leq)</math> is a ''[[Maximal and minimal elements|maximal element]]'' if for every <math>j \in I,</math> <math>m \leq j</math> implies <math>j \leq m.</math><ref>This implies <math>j = m</math> if <math>(I, \leq)</math> is a [[partially ordered set]].</ref>
It is a ''[[Greatest element and least element|greatest element]]'' if for every <math>j \in I,</math> <math>j \leq m.</math>

Any preordered set with a greatest element is a directed set with the same preorder. 
For instance, in a [[poset]] <math>P,</math> every [[Upper set#Upper closure and lower closure|lower closure]] of an element; that is, every subset of the form <math>\{a \in P : a \leq x\}</math> where <math>x</math> is a fixed element from <math>P,</math> 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===

The [[subset inclusion]] relation <math>\,\subseteq,\,</math> along with its [[Duality (order theory)|dual]] <math>\,\supseteq,\,</math> define [[partial order]]s on any given [[family of sets]]. 
A non-empty [[family of sets]] is a directed set with respect to the partial order <math>\,\supseteq\,</math> (respectively, <math>\,\subseteq\,</math>) 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 <math>I</math> of sets is directed with respect to <math>\,\supseteq\,</math> (respectively, <math>\,\subseteq\,</math>) if and only if 
:for all <math>A, B \in I,</math> there exists some <math>C \in I</math> such that <math>A \supseteq C</math> and <math>B \supseteq C</math> (respectively, <math>A \subseteq C</math> and <math>B \subseteq C</math>) 
or equivalently, 
:for all <math>A, B \in I,</math> there exists some <math>C \in I</math> such that <math>A \cap B \supseteq C</math> (respectively, <math>A \cup B \subseteq C</math>).

Many important examples of directed sets can be defined using these partial orders. 
For example, by definition, a [[Filter (set theory)|{{em|prefilter}}]] or {{em|filter base}} is a non-empty [[family of sets]] that is a directed set with respect to the [[partial order]] <math>\,\supseteq\,</math> and that also does not contain the empty set (this condition prevents triviality because otherwise, the empty set would then be a [[Greatest element and least element|greatest element]] with respect to <math>\,\supseteq\,</math>). 
Every [[Pi-system|{{pi}}-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 <math>\,\supseteq\,.</math> Every [[Dynkin system|λ-system]] is a directed set with respect to <math>\,\subseteq\,.</math> Every [[Filter (set theory)|filter]], [[Topology (structure)|topology]], and [[σ-algebra]] is a directed set with respect to both <math>\,\supseteq\,</math> and <math>\,\subseteq\,.</math>

====Tails of nets====

By definition, a {{em|[[Net (mathematics)|net]]}} is a function from a directed set and a [[Sequence (mathematics)|sequence]] is a function from the natural numbers <math>\N.</math> Every sequence canonically becomes a net by endowing <math>\N</math> with <math>\,\leq.\,</math>

If <math>x_{\bull} = \left(x_i\right)_{i \in I}</math> is any [[Net (mathematics)|net]] from a directed set <math>(I, \leq)</math> then for any index <math>i \in I,</math> the set <math>x_{\geq i} := \left\{x_j : j \geq i \text{ with } j \in I\right\}</math> is called the tail of <math>(I, \leq)</math> starting at <math>i.</math> The family <math>\operatorname{Tails}\left(x_{\bull}\right) := \left\{x_{\geq i} : i \in I\right\}</math> of all tails is a directed set with respect to <math>\,\supseteq;\,</math> in fact, it is even a prefilter.

====Neighborhoods====

If <math>T</math> is a [[topological space]] and <math>x_0</math> is a point in <math>T,</math> the set of all [[Topological neighbourhood|neighbourhoods]] of <math>x_0</math> can be turned into a directed set by writing <math>U \leq V</math> if and only if <math>U</math> contains <math>V.</math> For every <math>U,</math> <math>V,</math> and <math>W</math>{{hairsp}}:
* <math>U \leq U</math> since <math>U</math> contains itself.
* if <math>U \leq V</math> and <math>V \leq W,</math> then <math>U \supseteq V</math> and <math>V \supseteq W,</math> which implies <math>U \supseteq W.</math> Thus <math>U \leq W.</math>
* because <math>x_0 \in U \cap V,</math> and since both <math>U \supseteq U \cap V</math> and <math>V \supseteq U \cap V,</math> we have <math>U \leq U \cap V</math> and <math>V \leq U \cap V.</math>

====Finite subsets====

The set <math>\operatorname{Finite}(I)</math> of all finite subsets of a set <math>I</math> is directed with respect to <math>\,\subseteq\,</math> since given any two <math>A, B \in \operatorname{Finite}(I),</math> their union <math>A \cup B \in \operatorname{Finite}(I)</math> is an upper bound of <math>A</math> and <math>B</math> in <math>\operatorname{Finite}(I).</math> This particular directed set is used to define the sum <math>{\textstyle\sum\limits_{i \in I}} r_i</math> of a [[Generalized series (mathematics)|generalized series]] of an <math>I</math>-indexed collection of numbers <math>\left(r_i\right)_{i \in I}</math> (or more generally, the sum of [[Series (mathematics)#Abelian topological groups|elements in an]] [[abelian topological group]], such as [[Series (mathematics)#Series in topological vector spaces|vectors]] in a [[topological vector space]]) as the [[Limit of a net|limit of the net]] of [[partial sum]]s <math>F \in \operatorname{Finite}(I) \mapsto {\textstyle\sum\limits_{i \in F}} r_i;</math> that is:
<math display=block>\sum_{i \in I} r_i ~:=~ \lim_{F \in \operatorname{Finite}(I)} \ \sum_{i \in F} r_i ~=~ \lim \left\{\sum_{i \in F} r_i \,: F \subseteq I, F \text{ finite }\right\}.</math>

===Logic===

{{See also|Preorder#Preorders and partial orders on partitions}}

Let <math>S</math> be a [[Theory (mathematical logic)|formal theory]], which is a set of [[Sentence (mathematical logic)|sentences]] with certain properties (details of which can be found in [[Theory (mathematical logic)|the article on the subject]]). For instance, <math>S</math> could be a [[first-order theory]] (like [[Zermelo–Fraenkel set theory]]) or a simpler [[Propositional calculus|zeroth-order theory]]. The preordered set <math>(S, \Leftarrow)</math> is a directed set because if <math>A, B \in S</math> and if <math>C := A \wedge B</math> denotes the sentence formed by [[logical conjunction]] <math>\,\wedge,\,</math> then <math>A \Leftarrow C</math> and <math>B \Leftarrow C</math> where <math>C \in S.</math> 
If <math>S / \sim</math> is the [[Lindenbaum–Tarski algebra]] associated with <math>S</math> then <math>\left(S / \sim, \Leftarrow\right)</math> is a partially ordered set that is also a directed set.

==Contrast with semilattices==
[[File:Directed_set,_but_no_join_semi-lattice.png|thumb|x100px|Example of a directed set which is not a join-semilattice]]

Directed set is a more general concept than (join) semilattice: every [[Semilattice|join semilattice]] is a directed set, as the join or least upper bound of two elements is the desired <math>c.</math>  The converse does not hold however, witness the directed set {1000,0001,1101,1011,1111} [[Coordinatewise order|ordered bitwise]] (e.g. <math>1000 \leq 1011</math> holds, but <math>0001 \leq 1000</math> does not, since in the last bit 1 > 0), where {1000,0001} has three upper bounds but no {{em|least}} 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 relation|antisymmetric]], and therefore directed sets are not always [[partial order]]s. However, the term {{em|directed set}} is also used frequently in the context of posets. In this setting, a subset <math>A</math> of a partially ordered set <math>(P, \leq)</math> 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 <math>A</math> is inherited from <math>P</math>; for this reason, reflexivity and transitivity need not be required explicitly.

A directed subset of a poset is not required to be [[Lower set|downward closed]]; a subset of a poset is directed if and only if its downward closure is an [[Ideal (order theory)|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 (set theory)|filter]].

Directed subsets are used in [[domain theory]], which studies [[Complete partial order|directed-complete partial order]]s.<ref>Gierz, p. 2.</ref> 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.{{explain|reason=Again? Convergent sequences are never mentioned in this article.|date=December 2020}}

==See also==

* {{annotated link|Centered set}}
* {{annotated link|Filtered category}}
* {{annotated link|Filters in topology}}
* {{annotated link|Linked set}}
* {{annotated link|Net (mathematics)}}

==Notes==

{{reflist|group=note}}
{{reflist}}

==References==

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

{{Order theory}}

[[Category:Binary relations]]
[[Category:General topology]]
[[Category:Order theory]]