Directed set

related topics
{math, number, function}
{law, state, case}

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 ac and bc.

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 \times N of pairs of natural numbers can be made into a directed set by defining (n0 , n1) ≤ (m0, m1) if and only if n0m0 and n1m1.
  • If x0 is a real number, we can turn the set R − {x0} into a directed set by writing ab if and only if
    |ax0| ≥ |bx0|. We then say that the reals have been directed towards x0. 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 aa and bb. A less trivial example is like the previous example of the "reals directed towards x0" but in which the ordering rule only applies to pairs of elements on the same side of x0.
  • If T is a topological space and x0 is a point in T, we turn the set of all neighbourhoods of x0 into a directed set by writing UV if and only if U contains V.
    • For every U: UU; since U contains itself.
    • For every U,V,W: if UV and VW, then UW; since if U contains V and V contains W then U contains W.
    • For every U, V: there exists the set U \cap V such that UU \cap V and VU \cap V; since both U and V contain U \cap V.
  • In a poset P, every lower closure of an element, i.e. every subset of the form {a| a in P, ax} where x is a fixed element from P, is directed.

Full article ▸

related documents
Removable singularity
Axiom of extensionality
Addition of natural numbers
Hilbert's basis theorem
Symbolic logic
Bucket sort
Finitely generated abelian group
Recursively enumerable language
Haar wavelet
Generating set of a group
Wreath product
Cauchy's integral theorem
Snake lemma
Atlas (topology)
Equality (mathematics)
Unique factorization domain
Bogosort
Merge algorithm
Commutative diagram
BQP
Vector calculus
Concatenation
Sather
Nilpotent group
Symmetric tensor
Data integrity
Sharp-P-complete
Catalan's conjecture
Constant term
Interpreted language