• Ex 2.34:
1. $$\text{min}(-,-)$$ $$\texttt{no}$$ $$\texttt{maybe}$$ $$\texttt{yes}$$
$$\texttt{no}$$ $$\texttt{no}$$ $$\texttt{no}$$ $$\texttt{no}$$
$$\texttt{maybe}$$ $$\texttt{no}$$ $$\texttt{maybe}$$ $$\texttt{maybe}$$
$$\texttt{yes}$$ $$\texttt{no}$$ $$\texttt{maybe}$$ $$\texttt{yes}$$
2. The symmetric monoidal preorder $$(P,\leq,\texttt{yes},\text{min})$$ satisfies:
1. $$(x_1 \leq y_1) \land (x_2 \leq y_2) \implies \text{min}(x_1, x_2) \leq \text{min}(y_1, y_2) \implies$$
• $$(\texttt{no} \leq \texttt{no}) \land (\texttt{maybe} \leq \texttt{yes}) \implies \text{min}(\texttt{no}, \texttt{maybe}) \leq \text{min}(\texttt{no}, \texttt{yes}) = \texttt{no}$$
• $$(\texttt{no} \leq \texttt{no}) \land (\texttt{no} \leq \texttt{maybe}) \implies \text{min}(\texttt{no}, \texttt{no}) \leq \text{min}(\texttt{no}, \texttt{maybe}) = \texttt{no}$$
• $$(\texttt{maybe} \leq \texttt{maybe}) \land (\texttt{maybe} \leq \texttt{yes}) \implies \text{min}(\texttt{maybe}, \texttt{maybe}) \leq \text{min}(\texttt{maybe}, \texttt{yes}) = \texttt{maybe}$$ - since both $$\texttt{no}$$ and $$\texttt{maybe}$$ are allowed, we arbitrarily choose $$\texttt{maybe}$$
2. $$\text{min}(\texttt{yes}, x) = x = \text{min}(x, \texttt{yes}) \implies$$ last row and column
3. $$\text{min}(\text{min}(x, y), z) = \text{min}(x, \text{min}(y, z))$$
4. $$\text{min}(x, y) = \text{min}(y, x) \implies$$ matrix is symmetric along the diagonal
• Ex 2.43: Let a monoidal monotone $$g : (\mathbf{Bool} = (\mathbb{B},\leq,\texttt{true},\land)) \rightarrow (\mathbf{Cost} = ([0,\infty],\geq,0,+))$$ be s.t. $$g(\texttt{false}) := \infty$$ and $$g(\texttt{true}) := 0$$.
• monotonic: $$b_1 \leq b_2 \implies g(b_1) \geq g(b_2)$$
• $$\texttt{false} \leq \texttt{false} \implies \infty \geq \infty$$
• $$\texttt{false} \leq \texttt{true} \implies \infty \geq 0$$
• $$\texttt{true} \leq \texttt{false} \implies 0 \geq \infty$$
• $$\texttt{true} \leq \texttt{true} \implies 0 \geq 0$$
• D 2.41 (a): $$0 \geq g(\texttt{true}) = 0$$
• D 2.41 (b): $$(g(b_1) + g(b_2)) \geq g(b_1 \land b_2)$$
• $$(\infty + \infty) \geq g(\texttt{false} \land \texttt{false}) = \infty$$
• $$(\infty + 0) \geq g(\texttt{false} \land \texttt{true}) = \infty$$
• $$(0 + \infty) \geq g(\texttt{true} \land \texttt{false}) = \infty$$
• $$(0 + 0) \geq g(\texttt{true} \land \texttt{true}) = 0$$
1. $$g$$ is strict.
• Ex 2.44:
1. $$n_1 \geq n_2 \implies d(n_1) \leq d(n_2)$$
• $$(->0) \leq (->0) \implies \texttt{false} \geq \texttt{false}$$
• $$(->0) \leq (-=0) \implies \texttt{false} \geq \texttt{true}$$
• $$(-=0) \leq (->0) \implies \texttt{true} \geq \texttt{false}$$
• $$(-=0) \leq (-=0) \implies \texttt{true} \geq \texttt{true}$$
• D 2.41 (a): $$\texttt{true} \geq d(0) = \texttt{true}$$
• D 2.41 (b): $$(d(n_1) \land d(n_2)) \leq d(n_1 + n_2)$$
• $$(\texttt{false} \land \texttt{false}) \leq d(->0) = \texttt{false}$$
• $$(\texttt{false} \land \texttt{true}) \leq d(->0) = \texttt{false}$$
• $$(\texttt{true} \land \texttt{false}) \leq d(->0) = \texttt{false}$$
• $$(\texttt{true} \land \texttt{true}) \leq d(-=0) = \texttt{true}$$
2. $$d$$ is strict.
3. $$n_1 \geq n_2 \implies u(n_1) \leq u(n_2)$$
• $$(-=\infty) \leq (-=\infty) \implies \texttt{false} \geq \texttt{false}$$
• $$(-=\infty) \leq (-<\infty) \implies \texttt{false} \geq \texttt{true}$$
• $$(-<\infty) \leq (-=\infty) \implies \texttt{true} \geq \texttt{false}$$
• $$(-<\infty) \leq (-<\infty) \implies \texttt{true} \geq \texttt{true}$$
• D 2.41 (a): $$\texttt{true} \geq u(0) = \texttt{true}$$
• D 2.41 (b): $$(u(n_1) \land u(n_2)) \leq u(n_1 + n_2)$$
• $$(\texttt{false} \land \texttt{false}) \leq u(-=\infty) = \texttt{false}$$
• $$(\texttt{false} \land \texttt{true}) \leq u(-=\infty) = \texttt{false}$$
• $$(\texttt{true} \land \texttt{false}) \leq u(-=\infty) = \texttt{false}$$
• $$(\texttt{true} \land \texttt{true}) \leq u(-<\infty) = \texttt{true}$$
4. $$u$$ is strict.
• PS1 5:
1. The proof is $$$\begin{split} & &&(t \leq v+w) \land (w+u \leq x+z) \land (v+x \leq y) &&& \\ &\implies &&(t \leq v+w) \land (u \leq u) \land (w+u \leq x+z) \land (v+x \leq y) &&&\text{(reflexivity)} \\ &\implies &&(t+u \leq (v+w)+u) \land (w+u \leq x+z) \land (v+x \leq y) &&&\text{(monotonicity)} \\ &\implies &&(t+u \leq (v+w)+u) \land (v \leq v) \land (w+u \leq x+z) \land (v+x \leq y) &&&\text{(reflexivity)} \\ &\implies &&(t+u \leq (v+w)+u) \land (v+(w+u) \leq v+(x+z)) \land (v+x \leq y) &&&\text{(monotonicity)} \\ &\implies &&(t+u \leq v+(w+u)) \land (v+(w+u) \leq v+(x+z)) \land (v+x \leq y) &&&\text{(associativity)} \\ &\implies &&(t+u \leq v+(x+z)) \land (v+x \leq y) &&&\text{(transitivity)} \\ &\implies &&(t+u \leq v+(x+z)) \land (v+x \leq y) \land (z \leq z) &&&\text{(reflexivity)} \\ &\implies &&(t+u \leq v+(x+z)) \land ((v+x)+z \leq y+z) &&&\text{(monotonicity)} \\ &\implies &&(t+u \leq (v+x)+z) \land ((v+x)+z \leq y+z) &&&\text{(associativity)} \\ &\implies &&(t+u \leq y+z) &&&\text{(transitivity)} \\ \end{split}$$$
2. When two interior assertions cannot be joined together by transitivity, then reflexivity and monotonicity introduces a new variable to both sides of an interior assertion, until transitivity can be used. While doing so, the proof ignores brackets by associativity.
3. Symmetry is not invoked as there are no wire crossings.
• PS1 6:
1. The graph is

2. The matrix is

$$\text{P}(M)$$ A B C
A $$\{\text{car}\}$$ $$\{\text{train}\}$$ $$\{\text{car},\text{train}\}$$
B $$\{\text{train}\}$$ $$\varnothing$$ $$\{\text{foot}\}$$
C $$\{\text{boat},\text{car}\}$$ $$\{\text{boat},\text{train}\}$$ $$\{\text{car}\}$$
3. The interpretation does not hold for any two points $$\in \text{Ob}(\mathcal{C})$$, as any mode of transportation brings a person from $$B$$ to $$B$$: just stay at $$B$$. Instead, the interpretation holds for at least three points $$a, b, c$$ where $$c \neq a$$.

Created: 2020-01-22 Wed 18:39