Exercise. [dt-001W]

Liam O'Connor

Show that if a function $f : A \rightarrow B$ on cpos $A$ and $B$ is monotonic and $A$ is finite, then $f$ is continuous.

Hint: Finite directed sets contain their lub

Solution.

Liam O'Connor

Because of Theorem [dt-001O], it suffices to show the second condition of continuity, as $f$ is monotonic.

Because $A$ is finite, any directed subset $X \subseteq A$ is also finite, and therefore $\bigsqcup X \in X$ . Because $f$ is monotone, $f(x) \sqsubseteq f (\bigsqcup X)$ for all $x \in X$ .

The solution to Exercise [dt-001N] shows that $\{f(x) \mid x \in X\}$ is directed and therefore contains its upper bound $c$ . Because $f$ is monotone, $f(\bigsqcup X)$ must be $c$ (else it would contradict the above).

Therefore $\bigsqcup \{f(x) \mid x \in X\} = f (\bigsqcup X)$ , as required.

Exercise. [dt-001W]

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.