Scott continuous

Let $P_1,P_2$ be two dcpos (http://planetmath.org/Dcpo). A function $f:P_1\to P_2$ is said to be Scott continuous if for any directed set $D\subseteq P_1$, $f(\bigvee D)=\bigvee f(D)$.

First, observe that $f$ is monotone. If $a\le b$, then $f(b)=f(\bigvee \{a,b\})=\bigvee \{f(a),f(b)\}$, so that $f(a)\le f(b)$. As a result, if $D$ is directed, so is $f(D)$.

Proposition 1.

$f:P_1\to P_2$ is Scott continuous iff it is continuous when $P_{\mathrm{1}}$ and $P_{\mathrm{2}}$ are equipped with the Scott topologies.

Before proving this, let’s make one additional observation:

Lemma 1.

If $f$ is continuous (under Scott topologies), then $f$ is monotone.

Proof.

Suppose $a\le b\in P_1$. We wish to show that $f(a)\le f(b)$, or $f(a)\in \downarrow f(b)$. Assume the contrary. Consider $U=P_2-\downarrow f(b)$. Then $f(a)\in U$ and $U$ is Scott open, hence $a\in f^{-1}(U)$ is Scott open also. Since $a\le b$ and $f^{-1}(U)$ is upper, $b\in f^{-1}(U)$, which implies $f(b)\in U=P_2-\downarrow f(b)$, a contradiction. Therefore, $f(a)\le f(b)$. ∎

Now the proof of the proposition.

Proof.

Suppose first that $f$ is Scott continuous. Take an open set $U\in P_2$. We want to show that $V:=f^{-1}(U)$ is open in $P_1$. In other words, $V$ is upper and that $V$ has non-empty intersection with any directed set $D\in P_1$ whenever its supremum $\bigvee D$ lies in $V$. If $a\in \uparrow V$, then some $b\in V$ with $b\le a$, which implies $f(b)\le f(a)$. Since $f(b)\in U$, $f(a)\in \uparrow U=U$, so $a\in f^{-1}(U)=V$, $V$ is upper. Now, suppose $\bigvee D\in V$. So $\bigvee f(D)=f(\bigvee D)\in U$. Since $f(D)$ is directed, there is $y\in f(D)\cap U$, which means there is $x\in P_1$ such that $f(x)=y$ and $x\in D\cap V$. This shows that $V$ is Scott open.

Conversely, suppose $f$ is continuous (inverse of a Scott open set is Scott open). Let $D$ be a directed subset of $P_1$ and let $d=\bigvee D$. We want to show that $f(d)=\bigvee f(D)$. First, for any $e\in D$, we have that $e\le d$ so that $f(e)\le f(d)$ since $f$ is monotone. This shows $\bigvee f(D)\le f(d)$. Now suppose $r$ is any upper bound of $f(D)$. We want to show that $f(d)\le r$, or $f(d)\in \downarrow r$. Assume not. Then $f(d)$ lies in $U:=P_2-\downarrow r$, a Scott open set. So $\bigvee D=d\in f^{-1}(U)$, also Scott open, which implies some $e\in D$ with $e\in f^{-1}(U)$, or $f(e)\in U$. This means $f(e)\nleqq r$, a contradiction. Thus $f(d)\le r$, and the proof is complete. ∎

Remark. This notion of continuity is attributed to Dana Scott when he was trying to come up with a model for the formal system of untyped lambda calculus.

Title	Scott continuous
Canonical name	ScottContinuous
Date of creation	2013-03-22 16:49:53
Last modified on	2013-03-22 16:49:53
Owner	CWoo (3771)
Last modified by	CWoo (3771)
Numerical id	6
Author	CWoo (3771)
Entry type	Definition
Classification	msc 06B35