World Library  
Flag as Inappropriate
Email this Article

Directed set

Article Id: WHEBN0000009165
Reproduction Date:

Title: Directed set  
Author: World Heritage Encyclopedia
Language: English
Subject: Net (mathematics), Filter (mathematics), Preorder, General topology, Inverse limit
Collection: General Topology, Mathematical Relations, Order Theory
Publisher: World Heritage Encyclopedia
Publication
Date:
 

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

The notion defined above is sometimes called an upward directed set. A downward directed set is defined analogously,[2] meaning when every doubleton is bounded below.[3] Some authors (and this article) assume that a directed set is directed upward, unless otherwise stated. Beware that 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.

Contents

  • Equivalent definition 1
  • Examples 2
  • Contrast with semilattices 3
  • Directed subsets 4
  • See also 5
  • Notes 6
  • References 7

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. In this definition, the existence of an upper bound of the empty subset implies that A is nonempty.

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).
  • Let D1 and D2 be directed sets. Then the Cartesian product set D1 \times D2 can be made into a directed set by defining (n1, n2) ≤ (m1, m2) if and only if n1m1 and n2m2. In analogy to the product order this is the product direction on the Cartesian product.
  • It follows from previous example that 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.

Contrast with semilattices

Witness

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 0001 ≤ 1000 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

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 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 "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.[5] 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.

See also

Notes

  1. ^ Kelley, p. 65.
  2. ^
  3. ^
  4. ^
  5. ^ Gierz, p. 2.

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.
This article was sourced from Creative Commons Attribution-ShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and USA.gov, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for USA.gov and content contributors is made possible from the U.S. Congress, E-Government Act of 2002.
 
Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.
 
By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a non-profit organization.
 


Copyright © World Library Foundation. All rights reserved. eBooks from Project Gutenberg are sponsored by the World Library Foundation,
a 501c(4) Member's Support Non-Profit Organization, and is NOT affiliated with any governmental agency or department.