Back to the index. Or to the chambers

This article has 22 links. View as Cloud or List.

Loading ...

Planetmath Browser (2008—2009)

BSD licence | A django site

All articles taken from PlanetMath.org snapshot under CC-BY-SA licence.

→ The original article on PlanetMath.org

Other Formats: LaTeX

New! You can click on formulas to copy the LaTeX source to your clipboard. | Math Videos

Domain

A poset is said to be a directed complete partially ordered set, or dcpo for short, if every directed set $D\subseteq P$ has a supremum.

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

Example. Let be sets. Consider the set of all partial functions from to . This means that any $f\in P$ is a function $C\to B$ , for some subset of . We show that is a domain.

is a poset: Define a binary relation on as follows: $f\le g$ iff is an extension of . In other words, if $f:C\to B$ and $g:D\to B$ , then $C \subseteq D$ and for all $x\in C$ . Clearly, $\le$ is reflexive, anti-symmetric, and transitive. So $\le$ turns into a poset.
is a dcpo: Suppose that is a directed subset of . Set $E=\bigcup \lbrace \operatorname{dom}(f) \mid f\in D\rbrace$ . Define $g:E\to B$ as follows: for any $x\in E$ , where $x\in \operatorname{dom}(f)$ for some $f\in D$ . Is this well-defined? Suppose $x\in \operatorname{dom}(f_1)\cap\operatorname{dom}(f_2)$ . Since is directed, there is an $f\in D$ extending both and . This means that . Therefore, $g:=\bigvee D$ is a well-defined function (on ). Hence is a dcpo.
If $f,g\ll h$ , then $f\vee g\ll h$ : Since extends both and , $a:=f\vee g:\operatorname{dom}(f)\cup\operatorname{dom}(g)\to B$ is well-defined (the construction is the same as above). To show that $a\ll h$ , suppose $D\subseteq P$ is directed and $h\le \bigvee D$ (note that $\bigvee D$ exists by 2 above). Since $f\ll h$ , there is $r\in D$ such that $f\le r$ . Similarly, $g\ll h$ implies an $s\in D$ with $g\le s$ . Since is directed, there is $t\in D$ with $r,s\le t$ . This means $f\le t$ and $g\le t$ , or $a=f\vee g\le t$ .
is continuous: Let $\operatorname{wb}(h)=\lbrace f \in P\mid f\ll h \rbrace$ . Then by 3 above, $\operatorname{wb}(h)$ is a directed set. By 2, $b:=\bigvee \operatorname{wb}(h)$ exists, and $b\le h$ . Suppose $x\in \operatorname{dom}(h)$ . Then the function $c_x:\lbrace x\rbrace\to B$ defined by is way below , for if $h\le \bigvee D$ , then $x\in \operatorname{dom}(f)$ for some $f\in D$ , or $\operatorname{dom}(c_x)=\lbrace x\rbrace \subseteq \operatorname{dom}(f)$ , which means $c_x\le f$ . Therefore, $c_x\le b$ . This implies that $\operatorname{dom}(h)= \bigvee \lbrace \operatorname{dom}(c_x)\mid x\in \operatorname{dom}(h)\rbrace \subseteq \operatorname{dom}(b)$ . As a result, $h\le b$ .

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 collection 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”.

1	Poset
1	Reflexive Non Degenerate Sesquilinear
1	Continuous
1	Extension Field
1	Well Defined
1	Collection
1	Relation
1	Function
1	Set
1	First Order Theories
1	Relation Theory
1	Biconditional
1	Implication
2	Lowest Upper Bound
4	Directed Set
4	Branch
5	Fisher Information Matrix
6	Skew Symmetric Bilinear Form
8	Order In An Algebra
11	Transitive
14	Way Below
15	Continuous Poset