Misplaced Pages

Scott continuity

Article snapshot taken from Wikipedia with creative commons attribution-sharealike license. Give it a read and then ask your questions in the chat. We can research this topic together.
Definition of continuity for functions between posets

In mathematics, given two partially ordered sets P and Q, a function f: P → Q between them is Scott-continuous (named after the mathematician Dana Scott) 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. ⊔ f [ D ] = f ( ⊔ D ) {\displaystyle \sqcup f=f(\sqcup D)} , where ⊔ {\displaystyle \sqcup } is the directed join. When Q {\displaystyle Q} 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.

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 lattices and later defined for arbitrary partially ordered sets.

Scott-continuous functions are used in the study of models for lambda calculi and the denotational semantics of computer programs.

Properties

A Scott-continuous function is always monotonic, meaning that if A ≤ P B {\displaystyle A\leq _{P}B} for A , B ⊂ P {\displaystyle A,B\subset P} , then f ( A ) ≤ Q f ( B ) {\displaystyle f(A)\leq _{Q}f(B)} .

A subset of a directed complete partial order 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 Kolmogorov space, the topology induces an order relation on that space, the specialization order: x ≤ y 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.

Examples

The open sets in a given topological space when ordered by inclusion form a lattice 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 dcpo's, two particularly notable examples of Scott-continuous functions are curry and apply.

Nuel Belnap used Scott continuity to extend logical connectives to a four-valued logic.

See also

Footnotes

  1. ^ Vickers, Steven (1989). Topology via Logic. Cambridge University Press. ISBN 978-0-521-36062-3.
  2. Scott topology at the nLab
  3. ^ Scott, Dana (1972). "Continuous lattices". In Lawvere, Bill (ed.). Toposes, Algebraic Geometry and Logic. Lecture Notes in Mathematics. Vol. 274. Springer-Verlag.
  4. ^ Abramsky, S.; Jung, A. (1994). "Domain theory" (PDF). In Abramsky, S.; Gabbay, D.M.; Maibaum, T.S.E. (eds.). Handbook of Logic in Computer Science. Vol. III. Oxford University Press. ISBN 978-0-19-853762-5.
  5. ^ Bauer, Andrej & Taylor, Paul (2009). "The Dedekind Reals in Abstract Stone Duality". Mathematical Structures in Computer Science. 19 (4): 757–838. CiteSeerX 10.1.1.424.6069. doi:10.1017/S0960129509007695. S2CID 6774320. Retrieved October 8, 2010.
  6. Barendregt, H.P. (1984). The Lambda Calculus. North-Holland. ISBN 978-0-444-87508-2. (See theorems 1.2.13, 1.2.14)
  7. N. Belnap (1975) "How Computers Should Think", pages 30 to 56 in Contemporary Aspects of Philosophy, Gilbert Ryle editor, Oriel Press ISBN 0-85362-161-6

References

Categories: