Exercise. [dt-001N]

Liam O'Connor

Show that if a function on cpos $f : A \rightarrow B$ is monotonic, then $\bigsqcup \{ f(x) \mid x \in X \}$ exists for any directed $X \subseteq A$ (i.e.the first condition for continuity in Definition [dt-001J]).

Hint: It suffices to show that $\{ f(x) \mid x \in X \} \subseteq B$ is directed.

Solution.

Liam O'Connor

Because $B$ is a cpo, it suffices to show that $\{ f(x) \mid x \in X \} \subseteq B$ is directed. Let $a,b \in \{ f(x) \mid x \in X \}$ . Let $x_a, x_b \in X$ be the values that $f$ maps to $a$ and $b$ respectively, i.e. $f(x_a) = a$ and $f(x_b) = b$ . Because $X$ is directed, an upper bound of $x_a$ and $x_b$ exists in $X$ . Call this upper bound $x_c$ . Because $x_a \sqsubseteq x_c$ and $x_b \sqsubseteq x_c$ , we know that $f(x_a) = a \sqsubseteq f(x_c)$ and $f(x_b) = b \sqsubseteq f(x_c)$ by monotonicity of $f$ . Also, $f(x_c) \in \{ f(x) \mid x \in X \}$ because $x_c \in X$ . Therefore, because two arbitrary elements in $\{ f(x) \mid x \in X \}$ have an upper bound within the set, the set $\{ f(x) \mid x \in X \}$ is directed.

Exercise. [dt-001N]

Solution.

Problem. Monotonicity is insufficient [dt-001K]

Definition. Continuity [dt-001J]

Theorem. Continuity implies monotonicity [dt-001L]

Proof.

Example. Monotonic but not continuous [dt-001M]

Exercise. [dt-001N]

Solution.

Theorem. Alternative characterisation of continuity [dt-001O]

Proof.

Thesis.

Exercise. [dt-001W]

Solution.

Theorem. The Kleene fixed point theorem [dt-001P]

Proof.

Definition. The $\textbf {fix}$ operator [dt-001Q]

Exercise. [dt-001S]

Solution.

Solution.

Solution.

Solution.

Proof.