Scott continuity
Encyclopedia
In mathematics
, given two partially ordered set
s 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 image
has a supremum in Q, and that supremum is the image of the supremum of D: sup f(D) = f(sup D).
A subset O of a partially ordered set P is called Scott-open if it is an upper set
and if it is inaccessible by directed joins, i.e. if all directed sets D with supremum in O have non-empty intersection
with O. The Scott-open subsets of a partially ordered set P form a topology
on P, the Scott topology. A function between partially ordered sets is Scott-continuous if and only if it is continuous with respect to the Scott topology.
The Scott topology was first defined by Dana Scott for complete lattice
s and later defined for arbitrary partially ordered sets.
Scott-continuous functions show up in the study of the denotational semantics
of computer programs.
A subset of a partially ordered set is closed
with respect to the Scott topology induced by the partial order if and only if it is a lower set and closed under suprema of directed subsets.
A directed complete partial order (dcpo) with the Scott topology is always a Kolmogorov space
(i.e., it satisfies the T0 separation axiom). However, a dcpo with the Scott topology is a Hausdorff space
if and only if the order is trivial. The Scott-open sets form a complete lattice
when ordered by inclusion.
For any topological space satisfying the T0 separation axiom, the topology induces an order relation on that space, the specialization order: if and only if every open neighbourhood of x is also an open neighbourhood of y. The order relation of a dcpo D can be reconstructed from the Scott-open sets as the specialization order induced by the Scott topology. However, a dcpo equipped with the Scott topology need not be sober
: The specialization order induced by the topology of a sober space makes that space into a dcpo, but the Scott topology derived from this order is finer than the original topology.
on which the Scott topology can be defined. A subset X of a topological space T is compact
with respect to the topology on T (in the sense that every open cover of X contains a finite subcover of X) if and only if the set of open neighbourhoods of X is open with respect to the Scott topology.
For CPO, the cartesian closed category
of complete partial order
s, two particularly notable examples of Scott-continuous functions are curry
and apply
.
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...
, given two 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...
s P and Q a function
Function (mathematics)
In mathematics, a function associates one quantity, the argument of the function, also known as the input, with another quantity, the value of the function, also known as the output. A function assigns exactly one output to each input. The argument and the value may be real numbers, but they can...
between them is Scott-continuous (named after the mathematician Dana ScottDana Scott
Dana Stewart Scott is the emeritus Hillman University Professor of Computer Science, Philosophy, and Mathematical Logic at Carnegie Mellon University; he is now retired and lives in Berkeley, California...
) if it preserves all directed suprema, i.e. if for every directed subset
Directed set
In 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 ≤...
D of P with 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...
in P its image
Image (mathematics)
In mathematics, an image is the subset of a function's codomain which is the output of the function on a subset of its domain. Precisely, evaluating the function at each element of a subset X of the domain produces a set called the image of X under or through the function...
has a supremum in Q, and that supremum is the image of the supremum of D: sup f(D) = f(sup D).
A subset O of a partially ordered set P is called Scott-open if it is an upper set
Upper set
In mathematics, an upper set of a partially ordered set is a subset U with the property that x is in U and x≤y imply y is in U....
and if it is inaccessible by directed joins, i.e. if all directed sets D with supremum in O have non-empty intersection
Intersection (set theory)
In mathematics, the intersection of two sets A and B is the set that contains all elements of A that also belong to B , but no other elements....
with O. The Scott-open subsets of a partially ordered set P form a topology
Topological space
Topological spaces are mathematical structures that allow the formal definition of concepts such as convergence, connectedness, and continuity. They appear in virtually every branch of modern mathematics and are a central unifying notion...
on P, the Scott topology. A function between partially ordered sets is Scott-continuous if and only if it is continuous with respect to the Scott topology.
The Scott topology was first defined by Dana Scott for 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...
s and later defined for arbitrary partially ordered sets.
Scott-continuous functions show up in the study of the denotational semantics
Denotational semantics
In computer science, denotational semantics is an approach to formalizing the meanings of programming languages by constructing mathematical objects which describe the meanings of expressions from the languages...
of computer programs.
Properties
A Scott-continuous function is always monotonic.A subset of a partially ordered set is closed
Closed set
In geometry, topology, and related branches of mathematics, a closed set is a set whose complement is an open set. In a topological space, a closed set can be defined as a set which contains all its limit points...
with respect to the Scott topology induced by the partial order if and only if it is a lower set and closed under suprema of directed subsets.
A directed complete partial order (dcpo) with the Scott topology is always a Kolmogorov space
Kolmogorov space
In topology and related branches of mathematics, a topological space X is a T0 space or Kolmogorov space if for every pair of distinct points of X, at least one of them has an open neighborhood not containing the other. This condition, called the T0 condition, is one of the separation axioms...
(i.e., it satisfies the T0 separation axiom). However, a dcpo with the Scott topology is a Hausdorff space
Hausdorff space
In topology and related branches of mathematics, a Hausdorff space, separated space or T2 space is a topological space in which distinct points have disjoint neighbourhoods. Of the many separation axioms that can be imposed on a topological space, the "Hausdorff condition" is the most frequently...
if and only if the order is trivial. The Scott-open sets form 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...
when ordered by inclusion.
For any topological space satisfying the T0 separation axiom, the topology induces an order relation on that space, the specialization order: if and only if every open neighbourhood of x is also an open neighbourhood of y. The order relation of a dcpo D can be reconstructed from the Scott-open sets as the specialization order induced by the Scott topology. However, a dcpo equipped with the Scott topology need not be sober
Sober space
In mathematics, a sober space is a topological spacesuch that every irreducible closed subset of X is the closure of exactly one point of X: that is, has a unique generic point.-Properties and examples :...
: The specialization order induced by the topology of a sober space makes that space into a dcpo, but the Scott topology derived from this order is finer than the original topology.
Examples
The open sets in a given topological space when ordered by inclusion form a latticeLattice (order)
In mathematics, a lattice is a partially ordered set in which any two elements have a unique supremum and an infimum . Lattices can also be characterized as algebraic structures satisfying certain axiomatic identities...
on which the Scott topology can be defined. A subset X of a topological space T is compact
Compact space
In mathematics, specifically general topology and metric topology, a compact space is an abstract mathematical space whose topology has the compactness property, which has many important implications not valid in general spaces...
with respect to the topology on T (in the sense that every open cover of X contains a finite subcover of X) if and only if the set of open neighbourhoods of X is open with respect to the Scott topology.
For CPO, the cartesian closed category
Cartesian closed category
In category theory, a category is cartesian closed if, roughly speaking, any morphism defined on a product of two objects can be naturally identified with a morphism defined on one of the factors. These categories are particularly important in mathematical logic and the theory of programming, in...
of complete partial order
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...
s, two particularly notable examples of Scott-continuous functions are curry
Currying
In mathematics and computer science, currying is the technique of transforming a function that takes multiple arguments in such a way that it can be called as a chain of functions each with a single argument...
and apply
Apply
In mathematics and computer science, Apply is a function that applies functions to arguments. It is central to programming languages derived from lambda calculus, such as LISP and Scheme, and also in functional languages...
.