domain


A poset P is said to be a directed complete partially ordered set, or dcpo for short, if every directed setMathworldPlanetmath DP has a supremumMathworldPlanetmathPlanetmath. Since the empty setMathworldPlanetmath is directed, a dcpo must have a bottom element.

A domain P is a continuous dcpo. Here, continuous means that P is a continuous poset.

Example. Let A,B be sets. Consider the set P of all partial functionsMathworldPlanetmath from A to B. This means that any fP is a function CB, for some subset C of A. We show that P is a domain.

  1. 1.

    P is a poset: Define a binary relationMathworldPlanetmath on P as follows: fg iff g is an extensionPlanetmathPlanetmath of f. In other words, if f:CB and g:DB, then CD and f(x)=g(x) for all xC. Clearly, is reflexiveMathworldPlanetmathPlanetmath, anti-symmetric, and transitiveMathworldPlanetmathPlanetmathPlanetmath. So turns P into a poset.

  2. 2.

    P is a dcpo: Suppose that D is a directed subset of P. Set E={dom(f)fD}. Define g:EB as follows: for any xE, g(x)=f(x) where xdom(f) for some fD. Is this well-defined? Suppose xdom(f1)dom(f2). Since D is directed, there is an fD extending both f1 and f2. This means that f1(x)=f(x)=f2(x). Therefore, g:=D is a well-defined function (on E). Hence P is a dcpo.

  3. 3.

    If f,gh, then fgh: Since h extends both f and g, a:=fg:dom(f)dom(g)B is well-defined (the construction is the same as above). To show that ah, suppose DP is directed and hD (note that D exists by 2 above). Since fh, there is rD such that fr. Similarly, gh implies an sD with gs. Since D is directed, there is tD with r,st. This means ft and gt, or a=fgt.

  4. 4.

    P is continuous: Let wb(h)={fPfh}. Then by 3 above, wb(h) is a directed set. By 2, b:=wb(h) exists, and bh. Suppose xdom(h). Then the function cx:{x}B defined by cx(x)=h(x) is way below h, for if hD, then xdom(f) for some fD, or dom(cx)={x}dom(f), which means cxf. Therefore, cxb. This implies that dom(h)={dom(cx)xdom(h)}dom(b). As a result, hb.

Remark. Domain theory is a branch of order theory that is used extensively in theoretical computer science. As in the example, one can think of a domain as a collectionMathworldPlanetmath of partial pictures or pieces of partial information. Being continuous is the same as saying that any picture or piece of information can be pieced together by partial ones by way of “approximations”.

Title domain
Canonical name Domain12
Date of creation 2013-03-22 16:49:25
Last modified on 2013-03-22 16:49:25
Owner CWoo (3771)
Last modified by CWoo (3771)
Numerical id 8
Author CWoo (3771)
Entry type Definition
Classification msc 06B35
Synonym directed complete
Synonym directed complete poset
Synonym directed complete partially ordered set
Related topic CompleteLattice
Defines domain
Defines dcpo