In the mathematical fields of order and domain theory, a Scott domain is an algebraic, bounded-complete cpo. They are 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. They are also closely related to Scott information systems, which constitute a "syntactic" representation of Scott domains.
While the term "Scott domain" is widely used with the above definition, the term "domain" does not have such a generally accepted meaning and different authors will use different definitions; Scott himself used "domain" for the structures now called "Scott domains". Additionally, Scott domains appear with other names like "algebraic semilattice" in some publications.
Originally, Dana Scott demanded a complete lattice, and the Russian mathematician Yuri Yershov constructed the isomorphic structure of cpo. But this was not recognized until after scientific communications improved after the fall of the Iron Curtain. In honour of their work, a number of mathematical papers now dub this fundamental construction a "Scott–Ershov" domain.
Formally, a non-empty partially ordered set 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.
The property of being bounded complete is equivalent to the existence of infima of all non-empty subsets of D. 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. However, removing the top element from a complete lattice does not always produce a Scott domain. (Consider the complete lattice . The finite subsets of form a directed set, but have no upper bound in .)
Scott domains become topological spaces by introducing the Scott topology.
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 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 no consistent information, then its elements have no information in common and so its infimum is . In this way all non-empty 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.
See the literature given for domain theory.
In mathematics, a directed set is a nonempty set 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 and in there must exist in with and A directed set's preorder is called a direction.
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 indicating that, for certain pairs of elements in the set, one of the elements precedes the other in the ordering. The relation itself is called a "partial order."
In mathematics, the infimum of a subset of a partially ordered set is a greatest element in that is less than or equal to each element of if such an element exists. Consequently, the term greatest lower bound is also commonly used.
In mathematics, a complete lattice is a partially ordered set in which all subsets have both a supremum (join) and an infimum (meet). Specifically, every non-empty finite lattice is complete. Complete lattices appear in many applications in mathematics and computer science. Being a special instance of lattices, they are studied both in order theory and universal algebra.
Domain theory is a branch of mathematics that studies special kinds of partially ordered sets (posets) 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 semantics, especially for functional programming languages. Domain theory formalizes the intuitive ideas of approximation and convergence in a very general way and is closely related to topology.
Order theory is a branch of mathematics that investigates the 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 provides basic definitions. A list of order-theoretic terms can be found in the order theory glossary.
This is a glossary of some terms used in various branches of mathematics that are related to the fields of order, lattice, and domain theory. Note that there is a structured list of order topics available as well. Other helpful resources might be the following overview articles:
A lattice is an abstract structure studied in the mathematical subdisciplines of order theory and abstract algebra. It consists of a partially ordered set in which every pair of elements has a unique supremum and a unique infimum. An example is given by the power set of a set, partially ordered by inclusion, for which the supremum is the union and the infimum is the intersection. Another example is given by the natural numbers, partially ordered by divisibility, for which the supremum is the least common multiple and the infimum is the greatest common divisor.
In the mathematical area of order theory, one often speaks about functions that preserve certain limits, i.e. certain suprema or infima. Roughly speaking, these functions map the supremum/infimum of a set to the supremum/infimum of the image of the set. Depending on the type of sets for which a function satisfies this property, it may preserve finite, directed, non-empty, or just arbitrary suprema or infima. Each of these requirements appears naturally and frequently in many areas of order theory and there are various important relationships among these concepts and other notions such as monotonicity. If the implication of limit preservation is inverted, such that the existence of limits in the range of a function implies the existence of limits in the domain, then one obtains functions that are limit-reflecting.
In mathematical order theory, an ideal is a special subset of a partially ordered set (poset). Although this term historically was derived from the notion of a ring ideal of abstract algebra, it has subsequently been generalized to a different notion. Ideals are of great importance for many constructions in order and lattice theory.
In the mathematical area of order theory, completeness properties assert the existence of certain infima or suprema of a given partially ordered set (poset). The most familiar example is the completeness of the real numbers. A special use of the term refers to complete partial orders or complete lattices. However, many other interesting notions of completeness exist.
In mathematics, the phrase complete partial order is variously used to refer to at least three similar, but distinct, classes of partially ordered sets, characterized by particular completeness properties. Complete partial orders play a central role in theoretical computer science: in denotational semantics and domain theory.
In the mathematical area of order theory, the compact elements 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. This notion of compactness simultaneously generalizes the notions of finite sets in set theory, compact sets in topology, and finitely generated modules in algebra.
In mathematics, given two partially ordered sets P and Q, a function f: P → Q between them is Scott-continuous if it preserves all directed suprema. That is, for every directed subset D of P with supremum in P, its image has a supremum in Q, and that supremum is the image of the supremum of D, i.e. , where is the directed join. When is the poset of truth values, i.e. Sierpiński space, then Scott-continuous functions are characteristic functions of open sets, and thus Sierpiński space is the classifying space for open sets.
In mathematics, a join-semilattice is a partially ordered set that has a join for any nonempty finite subset. Dually, a meet-semilattice is a partially ordered set which has a meet for any nonempty finite subset. Every join-semilattice is a meet-semilattice in the inverse order and vice versa.
In mathematics, a complete Boolean algebra is a Boolean algebra in which every subset has a supremum. Complete Boolean algebras are used to construct Boolean-valued models of set theory in the theory of forcing. Every Boolean algebra A has an essentially unique completion, which is a complete Boolean algebra containing A such that every element is the supremum of some subset of A. As a partially ordered set, this completion of A is the Dedekind–MacNeille completion.
In mathematics, specifically order theory, the join of a subset of a partially ordered set is the supremum of denoted and similarly, the meet of is the infimum, denoted In general, the join and meet of a subset of a partially ordered set need not exist. Join and meet are dual to one another with respect to order inversion.
In mathematics, a Riesz space, lattice-ordered vector space or vector lattice is a partially ordered vector space where the order structure is a lattice.
In mathematical optimization, ordinal optimization is the maximization of functions taking values in a partially ordered set ("poset"). Ordinal optimization has applications in the theory of queuing networks.