Scott continuity: Difference between revisions

Content deleted Content added

Inline

Latest revision as of 09:40, 6 January 2024

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. $\sqcup f[D]=f(\sqcup D)$ , where $\sqcup$ is the directed join.^[1] When $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.^[2]

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.^[1]

The Scott topology was first defined by Dana Scott for complete lattices and later defined for arbitrary partially ordered sets.^[3]

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

Properties

A Scott-continuous function is always monotonic, meaning that if $A\leq _{P}B$ for $A,B\subset P$ , then $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.^[4]

A directed complete partial order (dcpo) with the Scott topology is always a Kolmogorov space (i.e., it satisfies the T₀ separation axiom).^[4] However, a dcpo with the Scott topology is a Hausdorff space if and only if the order is trivial.^[4] The Scott-open sets form a complete lattice when ordered by inclusion.^[5]

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.^[4]

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.^[5]

For CPO, the cartesian closed category of dcpo's, two particularly notable examples of Scott-continuous functions are curry and apply.^[6]

Nuel Belnap used Scott continuity to extend logical connectives to a four-valued logic.^[7]

Footnotes

^ ^a ^b Vickers, Steven (1989). Topology via Logic. Cambridge University Press. ISBN 978-0-521-36062-3.
^ Scott topology at the nLab
^ ^a ^b Scott, Dana (1972). "Continuous lattices". In Lawvere, Bill (ed.). Toposes, Algebraic Geometry and Logic. Lecture Notes in Mathematics. Vol. 274. Springer-Verlag.
^ ^a ^b ^c ^d 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.
^ ^a ^b 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.
^ Barendregt, H.P. (1984). The Lambda Calculus. North-Holland. ISBN 978-0-444-87508-2. (See theorems 1.2.13, 1.2.14)
^ 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

"Scott Topology". PlanetMath.

[Vickers1989-1] Vickers, Steven (1989). Topology via Logic. Cambridge University Press. ISBN 978-0-521-36062-3.

[2] Scott topology at the nLab

[Scott1972-3] Scott, Dana (1972). "Continuous lattices". In Lawvere, Bill (ed.). Toposes, Algebraic Geometry and Logic. Lecture Notes in Mathematics. Vol. 274. Springer-Verlag.

[AbramskyJung1994-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.

[BauerTaylor2009-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

[1]

[2]

[3]

[4]

[5]

[6]

[7]

@@ Line 1: / Line 1: @@
+{{Short description|Definition of continuity for functions between posets}}
-In [[mathematics]], given two [[partially ordered set]]s ''P'' and ''Q'', a [[Function (mathematics)|function]] <math>f : P \rightarrow Q</math> between them is '''Scott-continuous''' (named after the mathematician [[Dana Scott]]) if it [[limit preserving function (order theory)|preserves]] all directed suprema, i.e. if for every [[directed set|directed subset]] ''D'' of ''P'' with [[supremum]] in ''P'' its [[image (mathematics)|image]] has a supremum in ''Q'', and that supremum is the image of the supremum of ''D'': that is, <math>\sqcup f[D] = f(\sqcup D)</math>, where <math>\sqcup</math> is the [[directed join]].{{nowrap end}}<ref name="Vickers1989">{{Cite book |last=Vickers |first=Steven |authorlink=Steve Vickers (academia) |title=Topology via Logic |publisher=[[Cambridge University Press]] |year=1989 |isbn=0-521-36062-5}}</ref> When <math>Q</math> is the poset of truth values, i.e. [[Sierpinski space]], then the <math>f</math> are [[characteristic function]]s, and thus, Sierpinski space is the [[classifying topos]] for open sets.<ref>{{nlab|id=Scott+topology|title=Scott topology}}</ref>
+In [[mathematics]], given two [[partially ordered set]]s ''P'' and ''Q'', a [[Function (mathematics)|function]] ''f'': ''P'' → ''Q'' between them is '''Scott-continuous''' (named after the mathematician [[Dana Scott]]) if it [[limit preserving function (order theory)|preserves]] all [[directed supremum|directed suprema]]. That is, for every [[directed subset]] ''D'' of ''P'' with [[supremum]] in ''P'', its [[image (mathematics)|image]] has a supremum in ''Q'', and that supremum is the image of the supremum of ''D'', i.e. <math>\sqcup f[D] = f(\sqcup D)</math>, where <math>\sqcup</math> is the directed join.<ref name="Vickers1989">{{Cite book |last=Vickers |first=Steven |author-link=Steve Vickers (academia) |title=Topology via Logic |publisher=[[Cambridge University Press]] |year=1989 |isbn=978-0-521-36062-3}}</ref> When <math>Q</math> is the poset of truth values, i.e. [[Sierpiński space]], then Scott-continuous functions are [[Indicator function|characteristic functions]] of open sets, and thus Sierpiński space is the classifying space for open sets.<ref>{{nlab|id=Scott+topology|title=Scott topology}}</ref>
 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 (set theory)|intersection]] with ''O''. The Scott-open subsets of a partially ordered set ''P'' form a [[topological space|topology]] on ''P'', the '''Scott topology'''. A function between partially ordered sets is Scott-continuous if and only if it is [[continuous function (topology)|continuous]] with respect to the Scott topology.<ref name="Vickers1989"/>
-The Scott topology was first defined by Dana Scott for [[complete lattice]]s and later defined for arbitrary partially ordered sets.<ref name="Scott1972">{{cite book |last1=Scott |first1=Dana |authorlink1=Dana Scott |editor1-last=Lawvere |editor1-first=Bill |editor1-link=Bill Lawvere |title=Toposes, Algebraic Geometry and Logic |series=Lecture Notes in Mathematics |volume=274 |year=1972 |publisher=Springer-Verlag |chapter=Continuous lattices}}</ref>
+The Scott topology was first defined by Dana Scott for [[complete lattice]]s and later defined for arbitrary partially ordered sets.<ref name="Scott1972">{{cite book |last1=Scott |first1=Dana |author-link1=Dana Scott |editor1-last=Lawvere |editor1-first=Bill |editor1-link=Bill Lawvere |title=Toposes, Algebraic Geometry and Logic |series=Lecture Notes in Mathematics |volume=274 |year=1972 |publisher=Springer-Verlag |chapter=Continuous lattices}}</ref>
-Scott-continuous functions show up in the study of models for [[lambda calculi]]<ref name=Scott1972 /> and the [[denotational semantics]] of computer programs.
+Scott-continuous functions are used in the study of models for [[lambda calculi]]<ref name=Scott1972 /> and the [[denotational semantics]] of computer programs.
 ==Properties==
-A Scott-continuous function is always [[monotone function|monotonic]].
+A Scott-continuous function is always [[monotone function|monotonic]], meaning that if <math>A \le_{P} B</math> for <math>A, B \subset P</math>, then <math>f(A) \le_{Q} f(B)</math>.
-A subset of a partially ordered set is [[closed set|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.<ref name="AbramskyJung1994"/>
+A subset of a directed complete partial order is [[closed set|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.<ref name="AbramskyJung1994"/>
 A [[directed complete partial order]] (dcpo) with the Scott topology is always a [[Kolmogorov space]] (i.e., it satisfies the [[T0 separation axiom|T<sub>0</sub> separation axiom]]).<ref name="AbramskyJung1994"/> However, a dcpo with the Scott topology is a [[Hausdorff space]] if and only if the order is trivial.<ref name="AbramskyJung1994"/> The Scott-open sets form a [[complete lattice]] when ordered by [[inclusion (set theory)|inclusion]].<ref name="BauerTaylor2009"/>
-For any topological space satisfying the T<sub>0</sub> separation axiom, the topology induces an order relation on that space, the [[specialization order]]: {{nowrap|''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 space|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.<ref name="AbramskyJung1994">{{cite book |last1=Abramsky |first1=S. |last2=Jung |first2=A. |editor1-first=S. |editor1-last=Abramsky |editor2-first=D.M. |editor2-last=Gabbay |editor3-first=T.S.E. |editor3-last=Maibaum |title=Handbook of Logic in Computer Science |series= |volume=Vol. III |year=1994 |publisher=Oxford University Press |isbn=0-19-853762-X |chapter=Domain theory |chapterurl=http://www.cs.bham.ac.uk/~axj/pub/papers/handy1.pdf }}</ref>
+For any Kolmogorov space, the topology induces an order relation on that space, the [[specialization order]]: {{nowrap|''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 space|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.<ref name="AbramskyJung1994">{{cite book |last1=Abramsky |first1=S. |last2=Jung |first2=A. |editor1-first=S. |editor1-last=Abramsky |editor2-first=D.M. |editor2-last=Gabbay |editor3-first=T.S.E. |editor3-last=Maibaum |title=Handbook of Logic in Computer Science |volume=III |year=1994 |publisher=Oxford University Press |isbn=978-0-19-853762-5 |chapter=Domain theory |chapter-url=http://www.cs.bham.ac.uk/~axj/pub/papers/handy1.pdf }}</ref>
 ==Examples==
-The open sets in a given topological space when ordered by [[inclusion (set theory)|inclusion]] form a [[lattice (order)|lattice]] on which the Scott topology can be defined. A subset ''X'' of a topological space ''T'' is [[compact space|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 neighbourhood]]s of ''X'' is open with respect to the Scott topology.<ref name="BauerTaylor2009">{{cite journal |author1=Bauer, Andrej  |author2=Taylor, Paul  |lastauthoramp=yes |year=2009 |title=The Dedekind Reals in Abstract Stone Duality |journal=Mathematical Structures in Computer Science |volume=19 |pages=757–838 |publisher=[[Cambridge University Press]] |doi=10.1017/S0960129509007695 |url=http://PaulTaylor.EU/ASD/dedras/ |accessdate=October 8, 2010 }}</ref>
+The open sets in a given topological space when ordered by [[inclusion (set theory)|inclusion]] form a [[lattice (order)|lattice]] on which the Scott topology can be defined. A subset ''X'' of a topological space ''T'' is [[compact space|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 neighbourhood]]s of ''X'' is open with respect to the Scott topology.<ref name="BauerTaylor2009">{{cite journal |author1=Bauer, Andrej  |author2=Taylor, Paul  |name-list-style=amp |year=2009 |title=The Dedekind Reals in Abstract Stone Duality |journal=Mathematical Structures in Computer Science |volume=19 |issue=4  |pages=757–838 |doi=10.1017/S0960129509007695 |url=http://PaulTaylor.EU/ASD/dedras/ |access-date=October 8, 2010 |citeseerx=10.1.1.424.6069  |s2cid=6774320 }}</ref>
-For '''CPO''', the [[cartesian closed category]] of dcpo's, two particularly notable examples of Scott-continuous functions are [[currying|curry]] and [[apply]].<ref>{{cite book |last1=Barendregt |first1=H.P. |authorlink1=Henk Barendregt |title=The Lambda Calculus |year=1984 |publisher=North-Holland |isbn=0-444-87508-5}} ''(See theorems 1.2.13, 1.2.14)''</ref>
+{{anchor|curryApply}}For '''CPO''', the [[cartesian closed category]] of dcpo's, two particularly notable examples of Scott-continuous functions are [[currying|curry]] and [[apply]].<ref>{{cite book |last1=Barendregt |first1=H.P. |author-link1=Henk Barendregt |title=The Lambda Calculus |year=1984 |publisher=North-Holland |isbn=978-0-444-87508-2}} ''(See theorems 1.2.13, 1.2.14)''</ref>
+[[Nuel Belnap]] used Scott continuity to extend [[logical connective]]s to a [[four-valued logic]].<ref>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}}</ref>
 ==See also==
@@ Line 29: / Line 32: @@
 ==References==
-* {{planetmath reference|id=9063|title=Scott Topology}}
+* {{planetmath reference|urlname=ScottTopology|title=Scott Topology}}
 [[Category:Order theory]]