Complete Partial Order - Examples

Examples

  • Every finite poset is directed complete.
  • All complete lattices are also directed complete.
  • For any poset, the set of all non-empty filters, ordered by subset inclusion, is a dcpo. Together with the empty filter it is also pointed. If the order has binary meets, then this construction (including the empty filter) actually yields a complete lattice.
  • The set of all partial functions on some given set S can be ordered by defining f ≤ g for functions f and g if and only if g extends f, i.e. if the domain of f is a subset of the domain of g and the values of f and g agree on all inputs for which both functions are defined. (Equivalently, f ≤ g if and only if f ⊆ g where f and g are identified with their respective graphs.) This order is a pointed dcpo, where the least element is the nowhere defined function (with empty domain). In fact, ≤ is also bounded complete. This example also demonstrates why it is not always natural to have a greatest element.
  • The specialization order of any sober space is a dcpo.
  • Let us use the term “deductive system” as a set of sentences closed under consequence (for defining notion of consequence, let us use e.g. Tarski's algebraic approach). There are interesting theorems which concern a set of deductive systems being a directed complete partial ordering. Also, a set of deductive systems can be chosen to have a least element in a natural way (so that it can be also a complete partial ordering), because the set of all consequences of the empty set (i.e. “the set of the logically provable / logically valid sentences”) is (1) a deductive system (2) contained by all deductive systems.

Read more about this topic:  Complete Partial Order

Famous quotes containing the word examples:

    “Histories are more full of examples of the fidelity of dogs than of friends.”
    —Alexander Pope (1688–1744)

    “It is hardly to be believed how spiritual reflections when mixed with a little physics can hold people’s attention and give them a livelier idea of God than do the often ill-applied examples of his wrath.”
    —G.C. (Georg Christoph)

    “In the examples that I here bring in of what I have [read], heard, done or said, I have refrained from daring to alter even the smallest and most indifferent circumstances. My conscience falsifies not an iota; for my knowledge I cannot answer.”
    —Michel de Montaigne (1533–1592)