Options

Exercise 40 - Chapter 2

edited June 2 in Exercises

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 \( = \)

Previous Next

Comments

  • 1.
    edited July 13

    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
Sign In or Register to comment.