 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 a ≤ c and b ≤ c.
Directed sets are a generalization of nonempty totally ordered sets, that is, all totally ordered sets are directed sets (but not all partially ordered sets). 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.
Contents
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. The above definition implies this one: the upper bound of the empty subset is any existing element of A, because A is nonempty; furthermore, as provable with an induction argument over the size of nonempty finite subsets, the upper bound of a finite subset may be obtained by finding upper bounds of pairs iteratively.
Examples
Examples of directed sets include:
 The set of natural numbers N with the ordinary order ≤ is a directed set (and so is every totally ordered set).
 The set N N of pairs of natural numbers can be made into a directed set by defining (n_{0}, n_{1}) ≤ (m_{0}, m_{1}) if and only if n_{0} ≤ m_{0} and n_{1} ≤ m_{1}.
 If x_{0} is a real number, we can turn the set R − {x_{0}} into a directed set by writing a ≤ b if and only if
a − x_{0} ≥ b − x_{0}. We then say that the reals have been directed towards x_{0}. This is an example of a directed set that is not ordered (neither totally nor partially).  A (trivial) example of a partially ordered set that is not directed is the set {a, b}, in which the only order relations are a ≤ a and b ≤ b. A less trivial example is like the previous 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}.
 If T is a topological space and x_{0} is a point in T, we turn the set of all neighbourhoods of x_{0} into a directed set by writing U ≤ V if and only if U contains V.
 For every U: U ≤ U; since U contains itself.
 For every U,V,W: if U ≤ V and V ≤ W, then U ≤ W; since if U contains V and V contains W then U contains W.
 For every U, V: there exists the set U V such that U ≤ U V and V ≤ U V; since both U and V contain U V.
 In a poset P, every lower closure of an element, i.e. every subset of the form {a a in P, a ≤x} where x is a fixed element from P, is directed.
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 1000 ≤ 0001 does not), where {1000,0001} has three upper bounds but no least upper bound.
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 "upwarddirected" set (every pair of elements has an upper bound), it is also possible to define a downwarddirected set in which every pair of elements has a common lower bound. A subset of a poset is downwarddirected 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 upwarddirected set is required to have a least upper bound. In this context, directed subsets again provide a generalization of convergent sequences.
See also
 Filtered category
 Centered set
 Linked set
Notes
References
 J. L. Kelley (1955), General Topology.
 Gierz, Hofmann, Keimel, et al. (2003), Continuous Lattices and Domains, Cambridge University Press. ISBN 0521803381.
Categories: Mathematical relations
 Order theory
 General topology
Wikimedia Foundation. 2010.
Look at other dictionaries:
Directed by John Ford — Directed by Peter Bogdanovich Produced by David H. Shepard James R. Silke George Stevens, Jr. Written by Peter Bogdanovich … Wikipedia
Set Free (disambiguation) — Set Free can refer to:* Set Free (EP) by Patti Smith Group released in 1978 * Set Free (album) by The American Analog Set released in 2005 * Set Free (film), a 1918 film directed by Tod Browning … Wikipedia
directed trust — A trust in which certain assets are managed by someone other than the trustee. For example, someone might set up a trust and name a banks trust department as trustee, but specify in the trust document that a business held in trust be managed by… … Law dictionary
Directed acyclic graph — An example of a directed acyclic graph In mathematics and computer science, a directed acyclic graph (DAG i … Wikipedia
Directed graph — A directed graph. A directed graph or digraph is a pair G = (V,A) (sometimes G = (V,E)) of:[1] a set V, whose elements are called vertices or … Wikipedia
Directed percolation — In statistical physics Directed Percolation (DP) refers to a class of models that mimic filtering of fluids through porous materials along a given direction. Varying the microscopic connectivity of the pores, these models display a phase… … Wikipedia
Directed acyclic word graph — For the US Department of Defense review panel, see Deputy’s Advisory Working Group. The strings tap , taps , top , and tops stored in a Trie (left) and a DAWG (right), EOW stands for End of word. In computer science, a directed acyclic word graph … Wikipedia
Set Me Free (album) — Infobox Album Name = Set Me Free Type = Album Artist = Marion Raven Released = flagiconGermany June 8 2007 flagiconUnited Kingdom June 18 2007 flagiconNetherlands June 25 2007 flagiconUnited States July 24 2007 Recorded = 2005 2007 Genre =… … Wikipedia
Directed listening and thinking activity — The directed listening and thinking activity (DLTA) is a strategy that was first identified by Stauffer (1980). It is used with early childhood students or students who are not yet successful independent readers. Teachers use this strategy to… … Wikipedia
Set It Off (N.O.R.E. Song) — Infobox Single Name = Set It Off Artist = N.O.R.E. featuring J. Ru$$ Swizz Beatz from Album = Noreality Released = August 6 2007 Format = Digital download Recorded = Genre = East Coast hip hop Length = 3:04 Label = Babygrande Records Producer =… … Wikipedia