Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!

Options

Exercise 40 - Chapter 2

edited June 2018

Recall $$\textbf{Bool} = ( \mathbb{B} , \le, true, \wedge)$$ from Example 2.24 and $$\textbf{Cost} = ([0, \infty], \ge, 0, +)$$ from Example 2.34. There is a monoidal monotone $$g : \textbf{Bool} \rightarrow \textbf{Cost}$$, given by $$g(false) := \infty \text{ and } g(true) := 0$$.

1. Check that the map $$g : ( \mathbb{B} , \le, \text{true}, \wedge) \rightarrow ([0, \infty], \ge, 0, +)$$ presented above indeed
• is monotonic,
• satisfies the condition a. of Definition 2.34, and
• satisfies the condition b. of Definition 2.34.
2. Is $$g$$ a strict monoidal monotone?

Definition 2.34. Let $$\mathcal{P} = (P, \le_P , I_P , \otimes_P )$$ and $$\mathcal{Q} = (Q, \le_Q , I_Q , \otimes_Q )$$ be monoidal preorders. A monoidal monotone from $$\mathcal{P}$$ to $$\mathcal{Q}$$ is a monotone map $$f : (P, \le_P ) \rightarrow (Q, \le_Q )$$, satisfying two conditions:

a. $$I_Q ≤ f ( I_P )$$, and

b. $$f(p_1 ) \otimes_Q f(p_2 ) ≤ Q f (p_1 \otimes_P p_2 )$$

for all $$p_1 , p_2 \in P$$ .

strong monoidal monotone replace $$\le$$ with $$\cong$$

strict monoidal monotone replace $$\le$$ with $$=$$

• Options
1.
edited July 2018

1) Notice that the relation is flipped in g. So proving the monotonicity of (g) involves showing that, for $$a, b \in B$$

$a \leq b \Rightarrow g(a) \geq g(b)$

In cases where $$a = b$$, this holds trivially - and otherwise we have $$a = F, b = T$$

Since $$g(F) = \infty$$ and $$g(T) = 0$$ then we know $$g(F) \geq g(T)$$ which proves monotonicity.

The unit condition (a) is satisfied by the fact that $$g(T) = 0$$ and $$0 \geq 0$$

The homomorphism-looking condition (b) can be shown by constructing the table of $$g$$:

$$\begin{array}{c|cccc} \text{g(a) + g(b)} & a & b & a \land b & g(a \land b) \\ \hline \infty & F & F & F & \infty\\ \infty & F & T & F & \infty \\ \infty & T & F & F & \infty \\ 0 & T & T & T & 0 \end{array}$$ 2) Yes, since we can use $$=$$ in a and b above and the statements still holds

Comment Source:1) Notice that the relation is flipped in g. So proving the monotonicity of $$g$$ involves showing that, for \$$a, b \in B\$$ \$a \leq b \Rightarrow g(a) \geq g(b)\$ In cases where \$$a = b\$$, this holds trivially - and otherwise we have \$$a = F, b = T\$$ Since \$$g(F) = \infty\$$ and \$$g(T) = 0\$$ then we know \$$g(F) \geq g(T) \$$ which proves monotonicity. The unit condition (a) is satisfied by the fact that \$$g(T) = 0 \$$ and \$$0 \geq 0 \$$ The homomorphism-looking condition (b) can be shown by constructing the table of \$$g \$$: $\begin{array}{c|cccc} \text{g(a) + g(b)} & a & b & a \land b & g(a \land b) \\\\ \hline \infty & F & F & F & \infty\\\\ \infty & F & T & F & \infty \\\\ \infty & T & F & F & \infty \\\\ 0 & T & T & T & 0 \end{array}$ 2) Yes, since we can use \$$= \$$ in a and b above and the statements still holds