8.2: Solutions for Chapter 2

Exercise 2.5

The expert is right! The proposal violates property (a) when x\(_{1}\) = −1, x\(_{2}\) = 0, y\(_{1}\) = −1, and y\(_{2}\) = 1.

Indeed −1 ≤ −1 and 0 ≤ 1, but −1 ∗ 0 = 0 \(\nleq\) −1 = −1 ∗ 1.

Exercise 2.8

To check that (Disc(M), =, ∗, e) is a symmetric monoidal preorder, we need to check our proposed data obeys conditions (a)-(d) of Definition 2.2. Condition (a) just states the tautology that x\(_{1}\) ⊗ x\(_{2}\) = x\(_{1}\) ⊗ x\(_{2}\), conditions (b) and (c) are precisely the equations Eq. (2.7), and (d) is the commutativity condition. So we’re done. We leave it to you to decide whether we were telling the truth when we said it was easy.

Exercise 2.20

1. Here is a line by line proof, where we write the reason for each step in parentheses on the right.

Recall we call the properties (a) and (c) in Definition 2.2 monotonicity and associativity respectively.

t + u ≤ (v + w) + u (monotonicity, t ≤ v + w, u ≤ u)

= v + (w + u) (associativity)

≤ v+(x+z) (monotonicity,v ≤ v,w+u ≤ x+v)

= (v + x) + z (associativitiy)

≤ y + z. (monotonicity, v + x ≤ y, z ≤ z)

2. We use reflexivity when we assert that u ≤ u, v ≤ v and z ≤ z, and use transitivity to assert that the above sequence of inequalities implies the single inequality t + u ≤ y + z.
3. We know that the symmetry axiom is not necessary because no pair of wires cross.

Exercise 2.21

Condition (a), monotonicity, says that if x → y and z → w are reactions, then x + z → y + w is a reaction. Condition (b), unitality, holds as 0 represents having no material, and adding no material to some other material does not change it. Condition (c), associativity, says that when combining three collections x, y, and z of molecules it doesn’t matter whether you combine x and y and then z, or combine x with y already combined with z. Condition (d), symmetry, says that combining x with y is the same as combining y with x. All these are true in our model of chemistry, so (Mat, →, 0, +) forms a symmetric monoidal preorder.

Exercise 2.29

The monoidal unit must be false. The symmetric monoidal preorder does satisfy the rest of the conditions; this can be verified just by checking all cases.

Exercise 2.31

The monoidal unit is the natural number 1. Since we know that (\(\mathbb{N}\), ≤) is a preorder, we just need to check that ∗ is monotonic, associative, unital with 1, and symmetric. These are all familiar facts from arithmetic.

Exercise 2.33

This proposal is not monotonic: we have 1|1 and 1|2, but (1 + 1) \(\not |\) (1 + 2).

Exercise 2.34

1.

2. We need to show that (a) if x ≤ y and z ≤ w, then min(x, z) ≤ min(y, w), (b) min(x, yes) = x = min(yes, x), (c) min(min(x, y), z) = min(x, min(y, z)), and (d) min(x, y) = min(y, z). The most straightforward way is to just check all cases.

Exercise 2.35

Yes, (P(S ), ≤, S, ∩) is a symmetric monoidal preorder.

Exercise 2.36

Depending on your mood, you might come up with either of the following. First, we could take the monoidal unit to be some statement true that is true for all natural numbers, such as “n is a natural number.”

We can pair this unit with the monoidal product \(\land\), which takes statements P and Q and makes the statement P \(\land\) Q, where (P \(\land\) Q)(n) is true if P(n) and Q(n) are true, and false otherwise. Then (Prop\(^{\mathbb{N}}\), ≤, true, \(\land\)) forms a symmetric monoidal preorder.
Another option is to take define false to be some statement that is false for all natural numbers, such as “n + 10 ≤ 1” or “n is made of cheese.”

We can also define \(\lor\) such that (P \(\lor\) Q)(n) is true if and only if at least one of P(n) and Q(n) is true. Then (Prop\(^{\mathbb{N}}\), ≤, false, \(\lor\)) forms a symmetric monoidal preorder.

Exercise 2.39

Unitality and associativity have nothing to do with the order in X\(^{op}\): they simply state that I ⊗ x = x = x ⊗ I, and (x ⊗ y) ⊗ z = x ⊗ (y ⊗ z). Since these are true in X, they are true in X\(^{op}\). Symmetryis slightly trickier, since in only asks that x ⊗ y is equivalent to y ⊗ x. Nonetheless, this is still true in X\(^{op}\) because it is true in X. Indeed the fact that (x ⊗ y) \(\cong\) (y ⊗ x) in X means that (x ⊗ y) ≤ (y ⊗ x) and (y ⊗ x) ≤ (x ⊗ y) in X, which respectively imply that (y ⊗ x) ≤ (x ⊗ y) and (x ⊗ y) ≤ (y ⊗ x) in X\(^{op}\), and hence that (x ⊗ y) \(\cong\) (y ⊗ x) in X\(^{op}\) too.

Exercise 2.40

1. The preorder Cost\(^{op}\) has underlying set [0, ∞], and the usual increasing order on real numbers ≤ as its order.
2. Its monoidal unit is 0.
3. Its monoidal product is +.

Exercise 2.43

1. The map g is monotonic as g(false) = ∞ ≥ 0 = g(true), satisfies condition (a) since 0 ≥ 0 = g(true), and satisfies condition (b) since

2. Since all the inequalities regarding (a) and (b) above are in fact equalities, g is a strict monoidal monotone.

Exercise 2.44

The answer to all these questions is yes: d and u are both strict monoidal monotones. Here is one way to interpret this. The function d asks ‘is x ��= 0?’. This is monotonic, 0 is 0, and the sum of two elements of [0, ∞] is 0 if and only if they are both 0. The function u asks ‘is x finite?’. Similarly, this is monotonic, 0 is finite, and the sum of x and y is finite if and only if x and y are both finite.

Exercise 2.45

1. Yes, multiplication is monotonic in ≤, unital with respect to 1, associative, and symmetric, so (\(\mathbb{N}\), ≤, 1, ∗) is a monoidal preorder. We also met this preorder in Exercise 2.31.
2. The map f (n) = 1 for all n \(\in\) \(\mathbb{N}\) defines a monoidal monotone f : (\(\mathbb{N}\), ≤, 0, +) → (\(\mathbb{N}\), ≤, 1, ∗). (In fact, it is unique! Why?)
3. (\(\mathbb{Z}\), ≤, ∗, 1) is not a monoidal preorder because ∗ is not monotone. Indeed −1 ≤ 0 but (−1 ∗ −1) \(\nleq\) (0 ∗ 0).

Exercise 2.50

1. Let (P, ≤) be a preorder. How is this a Bool-category? Following Example 2.47, we can construct a Bool-category X\(_{P}\) with P as its set of objects, and with X\(_{P}\)(p, q) := true if p ≤ q, and X\(_{P}\)(p, q) := false otherwise. How do we turn this back into a preorder? Following the proof of Theorem 2.49, we construct a preorder with underlying set Ob(X\(_{P}\)) = P, and with p ≤ q if and only if X\(_{P}\)(p, q) = true. This is precisely the preorder (P, ≤)!
2. Let X be a Bool-category. By the proof of Theorem 2.49, we construct a preorder (Ob(X), ≤), where x ≤ y if and only if X(x, y) = true. Then, following our generalization of Example 2.47 in 1., we construct a Bool-category X′ whose set of objects is Ob(X), and such that X′(x, y) = true if and only if x ≤ y in (Ob(X), ≤). But by construction, this means X′(x, y) = X(x, y). So we get back the Bool-category we started with.

Exercise 2.52

The distance d(US, Spain) is bigger: the distance from, for example, San Diego to anywhere is Spain is bigger than the distance from anywhere in Spain to New York City.

Exercise 2.55

The difference between a Lawvere metric space that is, a category enriched over ([0, ∞], ≥, 0, +) and a category enriched over (\(\mathbb{R}_{≥0}\), ≥, 0, +) is that in the latter, infinite distances are not allowed between points. You might thus call the latter a finite-distance Lawvere metric space.

Exercise 2.58

The table of distances for X is

Exercise 2.60

The matrix of edge weights of X is

Exercise 2.61

A NMY-category X is a set X together with, for all pairs of elements x, y in X, a value X(x, y) equal to no, maybe, or yes. Moreover, we must have X(x, x) = yes and min(X(x, y), X(y, z)) ≤ X(x, z) for all x, y, z. So a NMY-category can be thought of as set of points together with an statement—no, maybe, or yes—of whether it is possible to get from one point to another. In particular, it’s always possible to get to a point if you’re already there, and it’s as least as possible to get from x to z as it is to get from x to y and then y to z.

Exercise 2.62

Here is one way to do this task.

1.

2. The corresponding M-category, call it X, has hom-objects:

For example, to compute the hom-object X(C, D), we notice that there are two paths: C → A → B → D and C → D. For the first path, the intersection is the set {boat}. For the second path, the intersection in the set {foot, car}. Their union, and thus the hom-object X(C, D), is the entire set M.

This computation contains the key for why X is a M-category: by taking the union over all paths, we ensure that X(x, y) ∩ X(y, z) \(\subseteq\) X(x, z) for all x, y, z.

3. The person’s interpretation looks right to us.

Exercise 2.63

1.

2. The matrix M with (x, y)\(^{th}\) entry equal to the maximum, taken over all paths p from x to y, of the minimum edge label in p is

3. This is a matrix of hom-objects for a W-category since the diagonal values are all equal to the monoidal unit ∞, and because min(M(x, y), M(y, z)) ≤ M(x, y) for all x, y, z \(\in\) {A, B, C}.

4. One interpretation is as a weight limit (not to be confused with ‘weighted limit,’ a more advanced categorical notion), for example for trucking cargo between cities. The hom-object indexed by a pair of points (x, y) describes the maximum cargo weight allowed on that route. There is no weight limit on cargo that remains at some point x, so the hom-object from x to x is always infinite. The maximum weight that can be trucked from x to z is always at least the minimum of that that can be trucked from x to y and then y to z. (It is ‘at least’ this much because there may be some other, better route that does not pass through y.)

Exercise 2.67

This preorder describes the ‘is a part of’ relation. That is, x ≤ y when d(x, y) = 0, which happens when x is a part of y. So Boston is a part of the US, and Spain is a part of Spain, but the US is not a part of Boston.

Exercise 2.68

1. Recall the monoidal monotones d and u from Exercise 2.44. The function f is equal to d; let g be equal to u.
2. Let X be the Lawvere metric space with two objects A and B, such that d(A, B) = d(B, A) = 5. Then we have X\(_{f}\) = \(\begin{array}{l} A \\\bullet\end{array}\)\(\begin{array}{l} B \\\bullet\end{array}\) while X\(_{g}\) = \(\begin{array}{l} A \\\bullet\end{array}\)\(\begin{array}{l} B \\\bullet\end{array}\).

Exercise 2.73

1. An extended metric space is a Lawvere metric space that obeys in addition the properties (b) if d(x, y) = 0 then x = y, and (c) d(x, y) = d(y, x) of Definition 2.51. Let’s consider the dagger condition first. It says that the identity function to the opposite Cost-category is a functor, and so for all x, y we must have d(x, y) ≤ d(y, x). But this means also that d(y, x) ≤ d(x, y), and so d(x, y) = d(y, x). This is exactly property (c). Now let’s consider the skeletality condition. This says that if d(x, y) = 0 and d(y, x) = 0, then x = y. Thus when we have property (c), d(x, y) = d(y, x), this is equivalent to property (b). Thus skeletal dagger Cost-categories are the same as extended metric spaces!
2. Recall from Exercise 1.73 that skeletal dagger preorders are sets. The analogy “preorders are to sets as Lawvere metric spaces are to extended metric spaces” is thus the observation that just as extended metric spaces are skeletal dagger Cost-categories, sets are skeletal dagger Bool- categories.

Exercise 2.75

1. Let (x, y) \(\in\) X × Y. Since X and Y are V-categories, we have I ≤ X(x, x) and I ≤ Y(y, y). Thus I = I ⊗ I ≤ X(x, x) ⊗ Y(y, y) = (X × Y)((x, y), (x, y)).
2. Using the definition of product hom-objects, and the symmetry and monotonicity of ⊗ we have

(X × Y)((x\(_{1}\), y\(_{1}\)), (x\(_{2}\), y\(_{2}\))) ⊗ (X × Y)((x\(_{2}\), y\(_{2}\)), (x\(_{3}\), y\(_{3}\)))

= X(x\(_{1}\), x\(_{2}\)) ⊗ Y(y\(_{1}\), y\(_{2}\)) ⊗ X(x\(_{2}\), x\(_{3}\)) ⊗ Y(y\(_{2}\), y\(_{3}\))

= X(x\(_{1}\), x\(_{2}\)) ⊗ X(x\(_{2}\), x\(_{3}\)) ⊗ Y(y\(_{1}\), y\(_{2}\)) ⊗ Y(y\(_{2}\), y\(_{3}\))

≤ X(x\(_{1}\), x\(_{3}\)) ⊗ Y(y\(_{1}\), y\(_{3}\))

= (X × Y)((x\(_{1}\), y\(_{1}\)), (x\(_{3}\), y\(_{3}\))) .

3. In particular, we use the symmetry, to conclude that Y(y\(_{1}\), y\(_{2}\)) ⊗ X(x\(_{2}\), x\(_{3}\)) = X(x\(_{2}\), x\(_{3}\)) ⊗ Y(y\(_{1}\), y\(_{2}\)).

Exercise 2.78

We just apply Definition 2.74(ii): (\(\mathbb{R}\) × \(\mathbb{R}\))((5, 6), (−1, 4)) = \(\mathbb{R}\)(5, −1) + \(\mathbb{R}\)(6, 4) = 6 + 2 = 8.

Exercise 2.82

1. The function−⊗v :V → V is monotone, because if u ≤ u′ then u ⊗ v ≤ u′ ⊗ v by the monotonicity condition (a) in Definition 2.2.
2. Let a := (v -o w) in Eq.(2.80). The right hand side is thus (v -o w) ≤ (v -o w), which is true by reflexivity. Thus the left hand side is true too. This gives ((v -o w) ⊗ v) ≤ w.
3. Let u ≤ u′. Then, using 2., (v -o u) ⊗ v ≤ u ≤ u′. Applying Eq.(2.80), we thus have (v -o u) ≤ (v -o u′). This shows that the map (v -o −): V → V is monotone.
4. Eq.(2.80) is exactly the adjointness condition from Definition 1.95, except for the fact that we do not know (− ⊗ v) and (v -o −) are monotone maps. We proved this, however, in items 1 and 3 above.

Exercise 2.84

We need to find the hom-element. This is given by implication. That is, define the function x ⇒ y by the table

Then (a \(\land\) v) ≤ w if and only if a ≤ (v ⇒ w). Indeed, if v = false then a \(\land\) false = false, and so the left hand side is always true.

But (false ⇒ w) = true, so the right hand side is always true too. If v = true, then a \(\land\) true = a so the left hand side says a ≤ w.

But (true ⇒ w) = w, so the right hand side is the same. Thus ⇒ defines a hom-element as per Eq. (2.80).

Exercise 2.93

We showed in Exercise 2.84 that Bool is symmetric monoidal closed, and in Exercise 1.7 and Example 1.88 that the join is given by the OR operation \(\lor\). Thus Bool is a quantale.

Exercise 2.94

Yes, the powerset monoidal preorder (P(S), \(\subseteq\), S, ∩) is a quantale. The hom-object B -o C is given by \(\bar{B}\) \(\bigcup\) C, where \(\bar{B}\) is the complement of B: it contains all elements of S not contained in B.

To see that this satisfies Eq. (2.80), note that if (A ∩ B) \(\subseteq\) C, then

A = (A ∩ \(\bar{B}\)) \(\bigcup\) (A ∩ B) \(\subseteq\) \(\bar{B}\) \(\bigcup\) C.

On the other hand, if A \(\subseteq\) (\(\bar{B}\) \(\bigcup\) C), then

A ∩ B \(\subseteq\) (\(\bar{B}\) \(\bigcup\) C) ∩ B (\(\bar{B}\) ∩ B) \(\bigcup\) (C ∩ B) = C ∩ B \(\subseteq\) C.

So (P(S), \(\subseteq\), S, ∩) is monoidal closed. Furthermore, joins are given by union of subobjects, so it is a quantale.

Exercise 2.92

1a. In Bool, (\(\bigvee\) Ø) = false, the least element.

1b. In Cost, (\(\bigvee\) Ø) = ∞. This is because we use the opposite order ≥ on [0, ∞], so \(\bigvee\) Ø is the greatest element of [0, ∞]. Note that in this case our convention from Definition 2.90, where we denote (\(\bigvee\) Ø) = 0, is a bit confusing! Beware!

2a. In Bool, x (\lor\) y is the usual join, OR.

2b. In Cost, x (\lor\) y is the minimum min(x, y). Again because we use the opposite order on [0, ∞], the join is the greatest number less than or equal to x and y.

Exercise 2.103

The 2 × 2-identity matrices for (\(\mathbb{N}\), ≤, 1, ∗), Bool, and Cost are respectively

Exercise 2.104

1. We first use Proposition 2.87 (2) and symmetry to show that for all v \(\in\) V, 0 ⊗ v = 0.

0 ⊗ v \(\cong\) v ⊗ 0 \(\cong\) (v ⊗ \(\bigvee_{a \in Ø}\)a) = \(\bigvee_{a \in Ø}\)(v ⊗ a) = 0.

Then we may just follow the definition in Eq. (2.101):

\(\begin{aligned}
I_{X} * M(x, y) &=\bigvee_{x^{\prime} \in X} I_{X}\left(x, x^{\prime}\right) \otimes M\left(x^{\prime}, y\right) \\
&=\left(I_{X}(x, x) \otimes M(x, y)\right) \vee\left(\bigvee_{x^{\prime} \in X, x^{\prime} \neq x} I_{X}\left(x, x^{\prime}\right) \otimes M\left(x^{\prime}, y\right)\right) \\
&=(I \otimes M(x, y)) \vee\left(\bigvee_{x^{\prime} \in X, x^{\prime} \neq x} 0 \otimes M\left(x^{\prime}, y\right)\right) \\
&=M(x, y) \vee 0=M(x, y) .
\end{aligned}\)

2. This again follows from Proposition 2.87(2) and symmetry, making use also of the associativity of ⊗:

\(\begin{aligned}
((M * N) * P)(w, z) &=\bigvee_{y \in Y}\left(\bigvee_{x \in X} M(w, x) \otimes N(x, y)\right) \otimes P(y, z) \\
& \cong \bigvee_{y \in Y, x \in X} M(w, x) \otimes N(x, y) \otimes P(y, z) \\
& \cong \bigvee_{x \in X} M(w, x) \otimes\left(\bigvee_{y \in Y} N(x, y) \otimes P(y, z)\right) \\
&=(M *(N * P))(w, z)
\end{aligned}\)

Exercise 2.105

We have the matrices