#### Howdy, Stranger!

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

Options

# Exercise 99 - Chapter 2

edited June 2018

Let $$\mathcal{V} = (V, \le, I, \otimes)$$ be a quantale. Use Eq. (2.97) and Proposition 2.84 to prove the following.

1. Show that for any sets $$X$$ and $$Y$$ and $$V$$-matrix $$M : X \times Y \rightarrow V$$, one has $$I_X * M = M$$.

2. Prove the associative law: for any matrices $$M : W \times X \rightarrow V, N : X \times Y \rightarrow V$$, and $$P : Y \times Z \rightarrow V$$, one has $$(M * N) * P = M * (N * P)$$.

Equation 2.97

$$( M * N )(x, z) := \bigvee_{y \in Y} M(x, y) \otimes N(y, z)$$ Proposition 2.84

Suppose $$\mathcal{V} = (V, \le, I, \otimes)$$ is a symmetric monoidal preorder, and that it is closed. Then

1) For every $$v \in V$$, the monotone map $$− \otimes v : (V, \le) \rightarrow (V, \le)$$ is left adjoint to $$v \multimap − : (V, \le) \rightarrow (V, \le)$$.

2) For any element $$v \in V$$ and set of elements $$A \subseteq V$$, we have $$\left( v \otimes \bigvee_{a \in A} a \right) \cong \bigvee_{a \in A} ( v \otimes a )$$ 3) For any $$v, w \in V$$, we have $$v \otimes (v \multimap w) \le w$$.

4) For any $$v \in V$$, we have $$v \cong (I \multimap v)$$.

5) For any $$u, v, w \in V$$, we have $$(u \multimap v) \otimes (v \multimap w) \le (u \multimap w)$$.

Definition of identity $$V$$-matrix (page 65 (75 of the pdf) of Seven Sketches):$I_x(x,y)=\begin{cases}I\quad\mathrm{if}\,x=y\\0\quad\textrm{if}\,x\neq y\end{cases}$
1. By equation 2.97, $$(I_X* M)(x_2,y):=\bigvee_{x_1\in X}I_X(x_2,x_1)\otimes M(x_1,y)$$. By the definition of identity, $$\bigvee_{x_1\in X}I_X(x_2,x_1)\otimes M(x_1,y)=I\otimes M(x_2,y)\bigvee_{x_1\in X\\x_1\neq x_2}0\otimes M(x_1,y)$$ $$=I\otimes M(x_2,y)\vee0$$ $$=I\otimes M(x_2,y)$$ $$=M(x_2,y)$$. Thus, $$(I_X* M)(x_2,y)=M(x_2,y)$$. Since this equation holds for all $$x_2\in X$$ and $$y\in Y$$, one can conclude $$I_X* M=M$$. (Note that $$0\otimes a=0$$ by Prop. 2.84 2) and symmetry.)
2. By equation 2.97, $$((M* N)* P)(w,z)=\bigvee_{y\in Y}(M* N)(w,y)\otimes P(y,z)$$ $$=\bigvee_{y\in Y}\left(\bigvee_{x\in X}M(w,x)\otimes N(x,y)\right)\otimes P(y,z)$$. By Prop. 2.84 2) and associativity of $$\otimes$$, $$\bigvee_{y\in Y}\left(\bigvee_{x\in X}M(w,x)\otimes N(x,y)\right)\otimes P(y,z)$$ $$=\bigvee_{y\in Y}\bigvee_{x\in X}M(w,x)\otimes N(x,y)\otimes P(y,z)$$. Setting $$v=\bigvee_{b\in B}b$$, one can use Prop. 2.84 2) to prove that suprema commute. By commutativity of suprema, $$\bigvee_{y\in Y}\bigvee_{x\in X}M(w,x)\otimes N(x,y)\otimes P(y,z)$$ $$=\bigvee_{x\in X}\bigvee_{y\in Y}M(w,x)\otimes N(x,y)\otimes P(y,z)$$. By Prop. 2.84 2) and associativity of $$\otimes$$, $$\bigvee_{x\in X}\bigvee_{y\in Y}M(w,x)\otimes N(x,y)\otimes P(y,z)$$ $$=\bigvee_{x\in X}M(w,x)\left(\bigvee_{y\in Y}N(x,y)\otimes P(y,z)\right)$$. By equation 2.97, $$\bigvee_{x\in X}M(w,x)\left(\bigvee_{y\in Y}N(x,y)\otimes P(y,z)\right)$$ $$=\bigvee_{x\in X}M(w,x)\otimes(N* P)(x,z)$$ $$=(M* (N* P))(w,z)$$. So, $$((M* N)* P)(w,z)=(M* (N* P))(w,z)$$. Since this equation holds for all $$w\in W$$ and $$z\in Z$$, one can conclude that $$(M* N)* P=M* (N* P)$$.
Comment Source:Definition of identity \$$V\$$-matrix (page 65 (75 of the pdf) of Seven Sketches):\$I_x(x,y)=\begin{cases}I\quad\mathrm{if}\,x=y\\\\0\quad\textrm{if}\,x\neq y\end{cases}\$ 1. By equation 2.97, \$$(I_X* M)(x_2,y):=\bigvee_{x_1\in X}I_X(x_2,x_1)\otimes M(x_1,y)\$$. By the definition of identity, \$$\bigvee_{x_1\in X}I_X(x_2,x_1)\otimes M(x_1,y)=I\otimes M(x_2,y)\bigvee_{x_1\in X\\\\x_1\neq x_2}0\otimes M(x_1,y)\$$ \$$=I\otimes M(x_2,y)\vee0\$$ \$$=I\otimes M(x_2,y)\$$ \$$=M(x_2,y)\$$. Thus, \$$(I_X* M)(x_2,y)=M(x_2,y)\$$. Since this equation holds for all \$$x_2\in X\$$ and \$$y\in Y\$$, one can conclude \$$I_X* M=M\$$. (Note that \$$0\otimes a=0\$$ by Prop. 2.84 2) and symmetry.) 2. By equation 2.97, \$$((M* N)* P)(w,z)=\bigvee_{y\in Y}(M* N)(w,y)\otimes P(y,z)\$$ \$$=\bigvee_{y\in Y}\left(\bigvee_{x\in X}M(w,x)\otimes N(x,y)\right)\otimes P(y,z)\$$. By Prop. 2.84 2) and associativity of \$$\otimes\$$, \$$\bigvee_{y\in Y}\left(\bigvee_{x\in X}M(w,x)\otimes N(x,y)\right)\otimes P(y,z)\$$ \$$=\bigvee_{y\in Y}\bigvee_{x\in X}M(w,x)\otimes N(x,y)\otimes P(y,z)\$$. Setting \$$v=\bigvee_{b\in B}b\$$, one can use Prop. 2.84 2) to prove that suprema commute. By commutativity of suprema, \$$\bigvee_{y\in Y}\bigvee_{x\in X}M(w,x)\otimes N(x,y)\otimes P(y,z)\$$ \$$=\bigvee_{x\in X}\bigvee_{y\in Y}M(w,x)\otimes N(x,y)\otimes P(y,z)\$$. By Prop. 2.84 2) and associativity of \$$\otimes\$$, \$$\bigvee_{x\in X}\bigvee_{y\in Y}M(w,x)\otimes N(x,y)\otimes P(y,z)\$$ \$$=\bigvee_{x\in X}M(w,x)\left(\bigvee_{y\in Y}N(x,y)\otimes P(y,z)\right)\$$. By equation 2.97, \$$\bigvee_{x\in X}M(w,x)\left(\bigvee_{y\in Y}N(x,y)\otimes P(y,z)\right)\$$ \$$=\bigvee_{x\in X}M(w,x)\otimes(N* P)(x,z)\$$ \$$=(M* (N* P))(w,z)\$$. So, \$$((M* N)* P)(w,z)=(M* (N* P))(w,z)\$$. Since this equation holds for all \$$w\in W\$$ and \$$z\in Z\$$, one can conclude that \$$(M* N)* P=M* (N* P)\$$.