Scott domain
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:
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:
Consequently, Scott domains are in a sense "almost" algebraic lattices.
Scott domains are closely related to Scott information system
s, which constitute a "syntactic" representation of Scott domains.
is a piece of data that might not be fully defined. The statement 
means "
contains all the information that 
does".
With this interpretation we can see that the supremum
of a subset 
is the element that contains all the information that any element of 
contains, but no more. Obviously such a supremum only exists (i.e., makes sense) provided 
does not contain inconsistent information; hence the domain is directed and bounded complete, but not all suprema necessarily exist. The algebraicity axiom essentially ensures that all elements get all their information from (non-strictly) lower down in the ordering; in particular, the jump from compact or "finite" to non-compact or "infinite" elements does not covertly introduce any extra information that cannot be reached at some finite stage. The bottom element is the supremum of the empty set, i.e. the element containing no information at all; its existence is implied by bounded completeness, since, vacuously, the empty set has an upper bound in any non-empty poset.
On the other hand, the infimum
is the element that contains all the information that is shared by all elements of 
, and no less; if 
contains inconsistent information, then its elements have no information in common and so its infimum is 
. In this way all infima exist, but not all infima are necessarily interesting.
This definition in terms of partial data allows an algebra to be defined as the limit of a sequence of increasingly more defined partial algebras — in other words a fixed point of an operator that adds progressively more information to the algebra. For more information, see Domain theory
.
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
fields of order
Order theory
Order theory is a branch of mathematics which investigates our intuitive notion of order using binary relations. It provides a formal framework for describing statements such as "this is less than that" or "this precedes that". This article introduces the field and gives some basic definitions...
and domain theory
Domain theory
Domain theory is a branch of mathematics that studies special kinds of partially ordered sets commonly called domains. Consequently, domain theory can be considered as a branch of order theory. The field has major applications in computer science, where it is used to specify denotational...
, a Scott domain is an algebraic, bounded complete cpo
Complete partial order
In mathematics, directed complete partial orders and ω-complete partial orders are special classes of partially ordered sets, characterized by particular completeness properties...
. It has been named in honour of Dana S. Scott, who was the first to study these structures at the advent of domain theory
Domain theory
Domain theory is a branch of mathematics that studies special kinds of partially ordered sets commonly called domains. Consequently, domain theory can be considered as a branch of order theory. The field has major applications in computer science, where it is used to specify denotational...
. Scott domains are very closely related to algebraic lattices, being different only in possibly lacking a greatest element
Greatest element
In mathematics, especially in order theory, the greatest element of a subset S of a partially ordered set is an element of S which is greater than or equal to any other element of S. The term least element is defined dually...
.
Formally, a non-empty partially ordered set
Partially ordered set
In mathematics, especially order theory, a partially ordered set formalizes and generalizes the intuitive concept of an ordering, sequencing, or arrangement of the elements of a set. A poset consists of a set together with a binary relation that indicates that, for certain pairs of elements in the...
(D, ≤) is called a Scott domain if the following hold:
- D is directed completeComplete partial orderIn mathematics, directed complete partial orders and ω-complete partial orders are special classes of partially ordered sets, characterized by particular completeness properties...
, i.e. all directed subsetsDirected setIn mathematics, a directed set is a nonempty set A together with a reflexive and transitive binary relation ≤ , with the additional property that every pair of elements has an upper bound: In other words, for any a and b in A there must exist a c in A with a ≤ c and b ≤...
of D have a supremumSupremumIn mathematics, given a subset S of a totally or partially ordered set T, the supremum of S, if it exists, is the least element of T that is greater than or equal to every element of S. Consequently, the supremum is also referred to as the least upper bound . If the supremum exists, it is unique...
. - D is bounded complete, i.e. all subsets of D that have some upper boundUpper boundIn mathematics, especially in order theory, an upper bound of a subset S of some partially ordered set is an element of P which is greater than or equal to every element of S. The term lower bound is defined dually as an element of P which is lesser than or equal to every element of S...
have a supremum. - D is algebraic, i.e. every element of D can be obtained as the supremum of a directed set of compact elementCompact elementIn the mathematical area of order theory, the compact or finite elements of a partially ordered set are those elements that cannot be subsumed by a supremum of any non-empty directed set that does not already contain members above the compact element....
s 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
Infimum
In mathematics, the infimum of a subset S of some partially ordered set T is the greatest element of T that is less than or equal to all elements of S. Consequently the term greatest lower bound is also commonly used...
. 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
Complete lattice
In mathematics, a complete lattice is a partially ordered set in which all subsets have both a supremum and an infimum . Complete lattices appear in many applications in mathematics and computer science...
. 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 system
Scott information system
In domain theory, a branch of mathematics and computer science, a Scott information system is a primitive kind of logical deductive system often used as an alternative way of presenting Scott domains.-Definition:...
s, which constitute a "syntactic" representation of Scott domains.
Explanation
Scott domains are intended to represent partial algebraic data, ordered by information content. An element is a piece of data that might not be fully defined. The statement means " contains all the information that does".With this interpretation we can see that the supremum
Supremum
In mathematics, given a subset S of a totally or partially ordered set T, the supremum of S, if it exists, is the least element of T that is greater than or equal to every element of S. Consequently, the supremum is also referred to as the least upper bound . If the supremum exists, it is unique...
of a subset is the element that contains all the information that any element of contains, but no more. Obviously such a supremum only exists (i.e., makes sense) provided does not contain inconsistent information; hence the domain is directed and bounded complete, but not all suprema necessarily exist. The algebraicity axiom essentially ensures that all elements get all their information from (non-strictly) lower down in the ordering; in particular, the jump from compact or "finite" to non-compact or "infinite" elements does not covertly introduce any extra information that cannot be reached at some finite stage. The bottom element is the supremum of the empty set, i.e. the element containing no information at all; its existence is implied by bounded completeness, since, vacuously, the empty set has an upper bound in any non-empty poset.On the other hand, the infimum
is the element that contains all the information that is shared by all elements of , and no less; if contains inconsistent information, then its elements have no information in common and so its infimum is . In this way all infima exist, but not all infima are necessarily interesting.This definition in terms of partial data allows an algebra to be defined as the limit of a sequence of increasingly more defined partial algebras — in other words a fixed point of an operator that adds progressively more information to the algebra. For more information, see Domain theory
Domain theory
Domain theory is a branch of mathematics that studies special kinds of partially ordered sets commonly called domains. Consequently, domain theory can be considered as a branch of order theory. The field has major applications in computer science, where it is used to specify denotational...
.
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 chainTotal orderIn set theory, a total order, linear order, simple order, or ordering is a binary relation on some set X. The relation is transitive, antisymmetric, and total...
) 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 numberReal numberIn mathematics, a real number is a value that represents a quantity along a continuum, such as -5 , 4/3 , 8.6 , √2 and π...
s 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.