Scott domain

Scott domain

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.

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.

ee also

*Scott information system

Literature

"See the literature given for domain theory."


Wikimedia Foundation. 2010.

Игры ⚽ Нужен реферат?

Look at other dictionaries:

  • 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,… …   Wikipedia

  • 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.DefinitionA Scott information system, A , is… …   Wikipedia

  • Scott Bullock — Scott G. Bullock is a senior attorney at the Institute for Justice a public interest law firm in Arlington, Virginia founded in 1991 by Chip Mellor and Clint Bolick. He was lead counsel for Susette Kelo in the landmark case, Kelo v. City of New… …   Wikipedia

  • Domain name scams — are types of Intellectual property scams or confidence scams in which unscrupulous domain name registrars attempt to generate revenue by tricking businesses into buying, listing or converting a domain name. The Office of Fair Trading has outlined …   Wikipedia

  • Scott Air Force Base — Part of Air Mobility Command (AMC) Located near: Mascoutah, Illinois …   Wikipedia

  • Scott Bradner — is a senior figure in the area of Internet governance. He serves as the secretary to the Internet Society and was formerly a trustee. He is on the board of ARIN, the North American IP address registry. He has also held numerous senior leadership… …   Wikipedia

  • Scott–Potter set theory — An approach to the foundations of mathematics that is of relatively recent origin, Scott–Potter set theory is a collection of nested axiomatic set theories set out by the philosopher Michael Potter, building on earlier work by the mathematician… …   Wikipedia

  • Scott Colton — Colt Cabana Nacimiento 6 de mayo de 1980 (31 años) Deerfield, Illinois Nombres artísticos Chris Guy Colt Cabana …   Wikipedia Español

  • Scott continuity — In mathematics, given two partially ordered sets P and Q a function between them is Scott continuous (named after the mathematician Dana Scott) if it preserves all directed suprema, i.e. if for every directed subset D of P with supremum in P its… …   Wikipedia

  • Scott Mountains (Antarctica) — For other uses, see Scott Mountains …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”