Directed set

Inmathematics,adirected set(or adirected preorderor afiltered set) is a nonemptyset$A$together with areflexiveandtransitivebinary relation$\,\leq \,$(that is, apreorder), with the additional property that every pair of elements has anupper bound.In other words, for any$a$and$b$in$A$there must exist$c$in$A$with$a\leq c$and$b\leq c.$A directed set's preorder is called adirection.

The notion defined above is sometimes called anupward directed set.Adownward directed setis defined analogously,meaning that every pair of elements is bounded below. 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 nonemptytotally ordered sets.That is, all totally ordered sets are directed sets (contrastpartiallyordered sets,which need not be directed).Join-semilattices(which are partially ordered sets) are directed sets as well, but not conversely. Likewise,latticesare directed sets both upward and downward.

Intopology,directed sets are used to definenets,which generalizesequencesand unite the various notions oflimitused inanalysis.Directed sets also give rise todirect limitsinabstract algebraand (more generally)category theory.

Equivalent definition

In addition to the definition above, there is an equivalent definition. Adirected setis a set$A$with apreordersuch that every finite subset of$A$has an upper bound. In this definition, the existence of an upper bound of theempty subsetimplies that$A$is nonempty.

Examples

The set ofnatural numbers$\mathbb {N}$with the ordinary order$\,\leq \,$is one of the most important examples of a directed set. Everytotally ordered setis a directed set, including$(\mathbb {N},\leq ),$$(\mathbb {N},\geq ),$$(\mathbb {R},\leq ),$and$(\mathbb {R},\geq ).$

A (trivial) example of a partially ordered set that isnotdirected is the set$\{a,b\},$in which the only order relations are$a\leq a$and$b\leq b.$A less trivial example is like the following 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}$(that is, if one takes an element$a$to the left of$x_{0},$and$b$to its right, then$a$and$b$are not comparable, and the subset$\{a,b\}$has no upper bound).

Product of directed sets

Let$\mathbb {D} _{1}$and$\mathbb {D} _{2}$be directed sets. Then theCartesian productset$\mathbb {D} _{1}\times \mathbb {D} _{2}$can be made into a directed set by defining$\left(n_{1},n_{2}\right)\leq \left(m_{1},m_{2}\right)$if and only if$n_{1}\leq m_{1}$and$n_{2}\leq m_{2}.$In analogy to theproduct orderthis is the product direction on the Cartesian product. For example, the set$\mathbb {N} \times \mathbb {N}$of pairs of natural numbers can be made into a directed set by defining$\left(n_{0},n_{1}\right)\leq \left(m_{0},m_{1}\right)$if and only if$n_{0}\leq m_{0}$and$n_{1}\leq m_{1}.$

Directed towards a point

If$x_{0}$is areal numberthen the set$I:=\mathbb {R} \backslash \lbrace x_{0}\rbrace$can be turned into a directed set by defining$a\leq _{I}b$if$\left|a-x_{0}\right|\geq \left|b-x_{0}\right|$(so "greater" elements are closer to$x_{0}$). We then say that the reals have beendirected towards$x_{0}.$This is an example of a directed set that isneitherpartially orderednortotally ordered.This is becauseantisymmetrybreaks down for every pair$a$and$b$equidistant from$x_{0},$where$a$and$b$are on opposite sides of$x_{0}.$Explicitly, this happens when$\{a,b\}=\left\{x_{0}-r,x_{0}+r\right\}$for some real$r\neq 0,$in which case$a\leq _{I}b$and$b\leq _{I}a$even though$a\neq b.$Had this preorder been defined on$\mathbb {R}$instead of$\mathbb {R} \backslash \lbrace x_{0}\rbrace$then it would still form a directed set but it would now have a (unique)greatest element,specifically$x_{0}$;however, it still wouldn't be partially ordered. This example can be generalized to ametric space$(X,d)$by defining on$X$or$X\setminus \left\{x_{0}\right\}$the preorder$a\leq b$if and only if$d\left(a,x_{0}\right)\geq d\left(b,x_{0}\right).$

Maximal and greatest elements

An element$m$of a preordered set$(I,\leq )$is amaximal elementif for every$j\in I,$$m\leq j$implies$j\leq m.$ It is agreatest elementif for every$j\in I,$$j\leq m.$

Any preordered set with a greatest element is a directed set with the same preorder. For instance, in aposet$P,$everylower closureof an element; that is, every subset of the form$\{a\in P:a\leq x\}$where$x$is a fixed element from$P,$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

Thesubset inclusionrelation$\,\subseteq,\,$along with itsdual$\,\supseteq,\,$definepartial orderson any givenfamily of sets. A non-emptyfamily of setsis a directed set with respect to the partial order$\,\supseteq \,$(respectively,$\,\subseteq \,$) 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$I$of sets is directed with respect to$\,\supseteq \,$(respectively,$\,\subseteq \,$) if and only if

for all$A,B\in I,$there exists some$C\in I$such that$A\supseteq C$and$B\supseteq C$(respectively,$A\subseteq C$and$B\subseteq C$)

or equivalently,

for all$A,B\in I,$there exists some$C\in I$such that$A\cap B\supseteq C$(respectively,$A\cup B\subseteq C$).

Many important examples of directed sets can be defined using these partial orders. For example, by definition, aprefilterorfilter baseis a non-emptyfamily of setsthat is a directed set with respect to thepartial order$\,\supseteq \,$and that also does not contain the empty set (this condition prevents triviality because otherwise, the empty set would then be agreatest elementwith respect to$\,\supseteq \,$). Everyπ-system,which is a non-emptyfamily of setsthat is closed under the intersection of any two of its members, is a directed set with respect to$\,\supseteq \,.$Everyλ-systemis a directed set with respect to$\,\subseteq \,.$Everyfilter,topology,andσ-algebrais a directed set with respect to both$\,\supseteq \,$and$\,\subseteq \,.$

Tails of nets

By definition, anetis a function from a directed set and asequenceis a function from the natural numbers$\mathbb {N}.$Every sequence canonically becomes a net by endowing$\mathbb {N}$with$\,\leq.\,$

If$x_{\bullet }=\left(x_{i}\right)_{i\in I}$is anynetfrom a directed set$(I,\leq )$then for any index$i\in I,$the set$x_{\geq i}:=\left\{x_{j}:j\geq i{\text{ with }}j\in I\right\}$is called the tail of$(I,\leq )$starting at$i.$The family$\operatorname {Tails} \left(x_{\bullet }\right):=\left\{x_{\geq i}:i\in I\right\}$of all tails is a directed set with respect to$\,\supseteq;\,$in fact, it is even a prefilter.

Neighborhoods

If$T$is atopological spaceand$x_{0}$is a point in$T,$set of allneighbourhoodsof$x_{0}$can be turned into a directed set by writing$U\leq V$if and only if$U$contains$V.$For every$U,$$V,$and$W$ :

• $U\leq U$since$U$contains itself.
• if$U\leq V$and$V\leq W,$then$U\supseteq V$and$V\supseteq W,$which implies$U\supseteq W.$Thus$U\leq W.$
• because$x_{0}\in U\cap V,$and since both$U\supseteq U\cap V$and$V\supseteq U\cap V,$we have$U\leq U\cap V$and$V\leq U\cap V.$

Finite subsets

The set$\operatorname {Finite} (I)$of all finite subsets of a set$I$is directed with respect to$\,\subseteq \,$since given any two$A,B\in \operatorname {Finite} (I),$their union$A\cup B\in \operatorname {Finite} (I)$is an upper bound of$A$and$B$in$\operatorname {Finite} (I).$This particular directed set is used to define the sum${\textstyle \sum \limits _{i\in I}}r_{i}$of ageneralized seriesof an$I$-indexed collection of numbers$\left(r_{i}\right)_{i\in I}$(or more generally, the sum ofelements in anabelian topological group,such asvectorsin atopological vector space) as thelimit of the netofpartial sums$F\in \operatorname {Finite} (I)\mapsto {\textstyle \sum \limits _{i\in F}}r_{i};$that is: $$\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\}.$$

Logic

See also:Preorder § Preorders and partial orders on partitions

Let$S$be aformal theory,which is a set ofsentenceswith certain properties (details of which can be found inthe article on the subject). For instance,$S$could be afirst-order theory(likeZermelo–Fraenkel set theory) or a simplerzeroth-order theory.The preordered set$(S,\Leftarrow )$is a directed set because if$A,B\in S$and if$C:=A\wedge B$denotes the sentence formed bylogical conjunction$\,\wedge,\,$then$A\Leftarrow C$and$B\Leftarrow C$where$C\in S.$ If$S/\sim$is theLindenbaum–Tarski algebraassociated with$S$then$\left(S/\sim,\Leftarrow \right)$is a partially ordered set that is also a directed set.

Contrast with semilattices

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

Directed set is a more general concept than (join) semilattice: everyjoin semilatticeis 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\leq 1011$holds, but$0001\leq 1000$does not, since in the last bit 1 > 0), where {1000,0001} has three upper bounds but noleastupper 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 beantisymmetric,and therefore directed sets are not alwayspartial orders.However, the termdirected setis also used frequently in the context of posets. In this setting, a subset$A$of a partially ordered set$(P,\leq )$is called adirected subsetif it is a directed set according to the same partial order: in other words, it is not theempty 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 bedownward closed;a subset of a poset is directed if and only if its downward closure is anideal.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 afilter.

Directed subsets are used indomain theory,which studiesdirected-complete partial orders.These are posets in which every upward-directed set is required to have aleast upper bound.In this context, directed subsets again provide a generalization of convergent sequences.

See also

• Centered set– Order theory
• Filtered category
• Filters in topology– Use of filters to describe and characterize all basic topological notions and results.
• Linked set– Mathematical concept regarding posets in (partial) order theory
• Net (mathematics)– A generalization of a sequence of points

References

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