The function H : \mathbb {B}_\bot \rightarrow \mathbb {B}_\bot seems to let us solve the halting problem, assuming \bot represents non-termination: H(v) \; = \; \begin {cases} F & \text {if}\ v = \bot \\ T & \text {otherwise} \end {cases}

A function f : X \rightarrow Y between posets X and Y is monotone (or monotonic) if, for all x, y \in X: x \sqsubseteq y\; \text {implies}\; f(x) \sqsubseteq f(y)

A function f : X \rightarrow Y on pointed posets X and Y is strict if it preserves the bottom value, i.e. f(\bot _X) = \bot _Y.

Consider the functions \mathbb {B}_\bot \rightarrow \mathbb {B}_\bot . Which ones are monotonic? There are a total of 27 such functions but only three significant classes.

Let \mathbf {K}_K denote the chain of values x_1, x_2, x_3, \dots , x_K where a \leq b implies x_a \sqsubseteq x_b. There is one monotonic function \mathbf {K}_1 \rightarrow \mathbf {K}_1:

And there are three monotonic functions \mathbf {K}_2 \rightarrow \mathbf {K}_2:

1. Write down the monotonic functions \mathbf {K}_3 \rightarrow \mathbf {K}_3.

Solution.

• Liam O'Connor

When drawn as a diagram like the above, the monotonic functions are all those whose lines do not cross.

2. Write a simple recursive program to calculate the number of monotonic functions \mathbf {K}_n \rightarrow \mathbf {K}_m.

Solution.

• Liam O'Connor

In Haskell:

monotonics :: Int -> Int -> Int
monotonics n 1 = 1
monotonics n m = sum [monotonics (n-x) (m-1) | x <- [0..n]]