#### Howdy, Stranger!

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

Options

# Exercise 8 - Chapter 2

edited May 22

Exercise 2.8. The string of inequalities in Eq. (2.9) is not quite a proof, because technically there is no such thing as $$v + w + u$$, for example. Instead, there is (v+w)+u and v+(w+u), and so on.

1. Formally prove, using only the rules of symmetric monoidal preorders (Definition 2.1), that given the assertions in Eq. (2.7), the conclusion in Eq. (2.8) follows.
2. Reflexivity and transitivity should show up in your proof. Make sure you are explicit about where they do.
3. How can you look at the wiring diagram Eq. (2.6) and know that the commutative axiom (Definition 2.1 d.) does not need to be invoked?

Eq 2.9 $$t + u \le v + w + u \le v + x + z \le y + z$$

Eq 2.8 $$t + u \le y + z$$

Eq 2.7 $$t \le v + w$$ and $$w + u \le x + z$$ and $$v + x \le y$$

Definition 2.1. A symmetric monoidal structure on a preorder $$(X, \le)$$ consists of two constituents:

(i) an element $$I \in X$$, called the monoidal unit, and

(ii) a function $$\otimes : X \times X \rightarrow X$$, called the monoidal product.

These constituents must satisfy the following properties:

(a) $$\text{ for all } x_1 , x_2 , y_1 , y_2 \in X, \text{ if } x_1 \le y_1 \text{ and } x_2 \le y_2 , \text{ then } x_1 \otimes x_2 \le y_1 \otimes y_2$$ ,

(b) $$\text{ for all } x \in X, \text{ the equations } I \otimes x = x \text{ and } x \otimes I = x \text{ hold }$$,

(c) $$\text{ for all } x, y, z \in X, \text{ the equation } (x \otimes y) \otimes z = x \otimes (y \otimes z) \text{ holds }$$, and

(d) $$\text{ for all } x, y \in X, \text{ the equivalence } x \otimes y \cong y \otimes x \text{ holds }$$ .

A preorder equipped with a symmetric monoidal structure, $$(X, \le, I, \otimes)$$, is called a symmetric monoidal preorder.

• Options
1.

I tried to sketch a proof, but I don't know if it is correct. Let us start from the first assertion of (2.7), that is, $$t \le (v+w)$$. We can write $$(v+w) \le (v+w)+u$$, that is more rich.' By part (c) of Definition 2.1, we can write $$(v+w)+u = v + (w+u)$$. Using the second assertion in (2.7), we have: $$v + (w+u) \le v + (x+z)$$. By (c), we get $$v + (x+z)=(v+x)+z$$. Considering the third assertion, we can write $$(v+x)+z\le y +z$$. Let us go back to the first assertion: $$t \le (v+w)$$; this implies $$(t + u)\le (v+w)+u$$. But $$(v+w)+u\le y +z$$, and thus, by transitivity, $$(t + u)\le (y+z)$$.

I have been thinking of other solutions. Wire $$t$$ in diagram 2.4 branches into $$v+w$$. I'm wondering if we might re-write $$t \le v + w$$ as $$t+0 \le v+w$$. I'm also wondering if we can consider this as the combination of $$t \le v$$ and $$0 \le w$$, reversing' point (a) of Definition 2.1. In the same way, we can find $$w \le x$$, $$u \le z$$, as well as $$v \le y$$ and $$x \le 0$$. We have $$t \le v \le y$$ and, by transitivity, $$t \le y$$. Let us now just consider $$t \le y$$ and $$u \le z$$. By point (a), we get $$t+u \le y+z$$, that is Eq. 2.8.

If we look at the wiring diagram, I guess that we do not need part (d) of Def. 2.1 because the wires do not twist.

Comment Source: I tried to sketch a proof, but I don't know if it is correct. Let us start from the first assertion of (2.7), that is, \$$t \le (v+w)\$$. We can write \$$(v+w) \le (v+w)+u\$$, that is more rich.' By part (c) of Definition 2.1, we can write \$$(v+w)+u = v + (w+u)\$$. Using the second assertion in (2.7), we have: \$$v + (w+u) \le v + (x+z)\$$. By (c), we get \$$v + (x+z)=(v+x)+z\$$. Considering the third assertion, we can write \$$(v+x)+z\le y +z\$$. Let us go back to the first assertion: \$$t \le (v+w)\$$; this implies \$$(t + u)\le (v+w)+u\$$. But \$$(v+w)+u\le y +z\$$, and thus, by transitivity, \$$(t + u)\le (y+z)\$$. I have been thinking of other solutions. Wire \$$t\$$ in diagram 2.4 branches into \$$v+w\$$. I'm wondering if we might re-write \$$t \le v + w\$$ as \$$t+0 \le v+w\$$. I'm also wondering if we can consider this as the combination of \$$t \le v\$$ and \$$0 \le w\$$, reversing' point (a) of Definition 2.1. In the same way, we can find \$$w \le x\$$, \$$u \le z\$$, as well as \$$v \le y\$$ and \$$x \le 0\$$. We have \$$t \le v \le y\$$ and, by transitivity, \$$t \le y\$$. Let us now just consider \$$t \le y\$$ and \$$u \le z\$$. By point (a), we get \$$t+u \le y+z\$$, that is Eq. 2.8. If we look at the wiring diagram, I guess that we do not need part (d) of Def. 2.1 because the wires do not twist.
• Options
2.
edited May 18

The approach suggested by Eq. 2.9 is that as a "cut line" moves from left to right as each inequality is "cut" a inequality is expressed. Put another way, the application of 2.1.a produces an implication. Throughout the proof $$+ = \otimes$$.

Given $$t + u$$

By 2.1.a $$x_1 = t , x_2 = u, y_1 = v + w , y_2 = u$$ and 2.7.a $$t \le v + w$$ giving $$t + u \le (v + w) + u$$.

Applying 2.1.c we get $$(v + w) + u = v + (w + u)$$.

By 2.1.a $$x_1 = v, x_2 = w + u , y_1 = v, y_2 = x + z$$ and 2.7.b $$w + u \le x + z$$ giving $$v + (w + u) \le v + (x + z)$$.

Applying 2.1.c we get $$v + (x + z) = (v + x) + z$$.

By 2.1.a $$x_1 = v + x, x_2 = z, y_1 = y, y_2 = z$$ and 2.7.c $$v + x \le y$$ giving $$(v + x) + z \le y + z$$.

Comment Source:The approach suggested by Eq. 2.9 is that as a "cut line" moves from left to right as each inequality is "cut" a inequality is expressed. Put another way, the application of 2.1.a produces an implication. Throughout the proof \$$+ = \otimes \$$. Given \$$t + u \$$ By 2.1.a \$$x_1 = t , x_2 = u, y_1 = v + w , y_2 = u \$$ and 2.7.a \$$t \le v + w \$$ giving \$$t + u \le (v + w) + u \$$. Applying 2.1.c we get \$$(v + w) + u = v + (w + u) \$$. By 2.1.a \$$x_1 = v, x_2 = w + u , y_1 = v, y_2 = x + z \$$ and 2.7.b \$$w + u \le x + z \$$ giving \$$v + (w + u) \le v + (x + z) \$$. Applying 2.1.c we get \$$v + (x + z) = (v + x) + z \$$. By 2.1.a \$$x_1 = v + x, x_2 = z, y_1 = y, y_2 = z \$$ and 2.7.c \$$v + x \le y \$$ giving \$$(v + x) + z \le y + z \$$. 
• Options
3.

Thanks! This is very clear. I'm wondering if the first part of my sketch was correct, even if much longer.

Comment Source:Thanks! This is very clear. I'm wondering if the first part of my sketch was correct, even if much longer.