Question

I am working on writing an easy to read document about denotational semantics of the lambda calculus. For that I introduce CPOs, monotonicity and continuity. A CPO is a set $M$ with a partial order $\leq$ and a bottom element $\bot$, requiring $\bot$ to be the smallest element in $M$ and the existence of the least upper bound ($\bigsqcup$) for every chain $d_0 \leq d_1 \leq d_2 \leq ...$ in $M$. A function $f$ between two CPOs $M$, $N$ is monotone, if for all $a, b \in M$ the following holds:

$$a \leq b \implies f(a) \leq f(b)$$

A function $f$ between two CPOs $M$, $N$ is continuous, if it is monotone and for all chains $d_0 \leq d_1 \leq d_2 \leq \dots$ we have

$$f(\bigsqcup_{i \in \mathbb{N}} d_i) = \bigsqcup_{i \in \mathbb{N}} f(d_i).$$

I want to give my readers a good intuition about the meaning of these definitions. However, I don't have one I could write down. Following Glynn Winskel in his book »The Formal Semantics of Programming Languages« (1993), $a \leq b$ has to be read as $a$ approximates $b$ (page 72), meaning $b$ has at least as much information as $a$. This leads to monotone functions reflecting more information about the input in more information about the output (page 122). This is somewhat understandable for me. However, the explanation of continuity is not clear for me:

As we shall see, that computable functions should be continuous follows from the idea that the appearance of a unit of information in the output of a computable function should only depend on the presence of finitely many units of information in the input.

(page 73)

This is still unclear to me after reading the stream example in section 8.2 (pages 121–123), or this answer.

So my final question is: How do I convince my readers that computable functions are continuous? Why is there no computable function which is not continuous?

It would be nice if you can give me answers/examples which do not require the rigorous introduction of computability or fix-point theory, since I do not want to focus on those things. Also it would be great if it is not necessary to know the lambda calculus and its denotational semantics in advance, because I want to (and have to) introduce monotonicity and continuity before them.

EDIT: By computable I mean Turing-computable. Please correct me if I misunderstand Winskels definition of computable on page 337, since it is not explicitly defined as Turing-computable but in an equivalent (at least in my eyes) manner.

Also I want to point out another source I found which tries to explain my problem. But still I don't understand its example, since it is basically the same as the stream example from Winskel.

EDIT 2: It would also be a good start in helping me to understand the matter to show that every computable function is monotone, i.e. there exists no non-monotone computable function.

No correct solution

Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top