Scott domain

From Wikipedia, the free encyclopedia

In the mathematical fields of order and domain theory, a Scott domain is an algebraic, bounded complete cpo. It has been named in honour of Dana S. Scott, who was the first to study these structures at the advent of domain theory. Scott domains are very closely related to algebraic lattices, being different only in possibly lacking a greatest element.

Formally, a non-empty partially ordered set (D, ≤) is called a Scott domain if the following hold:

D is directed complete, i.e. all directed subsets of D have a supremum.
D is bounded complete, i.e. all subsets of D that have some upper bound have a supremum.
D is algebraic, i.e. every element of D can be obtained as the supremum of a directed set of compact elements of D.

Since the empty set certainly has some upper bound, we can conclude the existence of a least element (the supremum of the empty set) from bounded completeness. Also note that, while the term "Scott domain" is widely used with this definition, the term "domain" does not have such a general meaning: it may be used to refer to many structures in domain theory and is usually explained before it is used. Yet, "domain" is the term that Scott himself originally used for these structures. Additionally, Scott domains appear with other names like "algebraic semilattice" in some publications.

It should be remarked that the property of being bounded complete is equivalent to the existence of all non-empty infima. It is well known that the existence of all infima implies the existence of all suprema and thus makes a partially ordered set into a complete lattice. Thus, when a top element (the infimum of the empty set) is adjoined to a Scott domain, one can conclude that:

the new top element is compact (since the order was directed complete before) and
the resulting poset will be an algebraic lattice (i.e. a complete lattice that is algebraic).

Consequently, Scott domains are in a sense "almost" algebraic lattices.

Scott domains are closely related to Scott information systems, which constitute a "syntactic" representation of Scott domains.

[edit] Examples

Every finite poset is directed complete and algebraic. Thus any bounded complete finite poset trivially is a Scott domain.

The natural numbers with an additional top element ω constitute an algebraic lattice, hence a Scott domain. For more examples in this direction, see the article on algebraic lattices.

Consider the set of all finite and infinite words over the alphabet {0,1}, ordered by the prefix order on words. Thus, a word w is smaller than some word v if w is a prefix of v, i.e. if there is some (finite or infinite) word v' such that w v' = v. For example 10 ≤ 10110. The empty word is the bottom element of this ordering and every directed set (which is always a chain) is easily seen to have a supremum. Likewise, one immediately verifies bounded completeness. However, the resulting poset is certainly missing a top having many maximal elements instead (like 111... or 000...). It is also algebraic, since every finite word happens to be compact and we certainly can approximate infinite words by chains of finite ones. Thus this is a Scott domain which is not an algebraic lattice.

For a negative example, consider the real numbers in the unit interval [0,1], ordered by their natural order. This bounded complete cpo is not algebraic. In fact its only compact element is 0.