8.4: Solutions for Chapter 4

Exercise 4.4

1. The Hasse diagram for Xop × Y is shown here (ignore the colors):

2. There is a profunctor \(\land\) : X → Y, i.e. a functor X\(^{op}\) × Y → B, such that, in the picture above, blue is sent to true and black is sent to false, i.e.

\(\land\)(monoid, nothing) = \(\land\)(monoid, this book)
= \(\land\)(preorder, this book) = \(\land\)(category, this book) = true

\(\land\)(preorder, nothing) = \(\land\)(category, nothing) = false.

The preorder X\(^{op}\) × Y describes tasks in decreasing difficulty. For example, (we hope) it is easier for my aunt to explain a monoid given this book than for her to explain a monoid without this book. The profunctor \(\land\) describes possible states of knowledge for my aunt: she can describe monoids without help, categories with help from the book, etc. It is an upper set because we assume that if she can do a task, she can also do any easier task.

Exercise 4.7

We’ve done this one before! We hope you remembered how to do it. If not, see Exercise 2.84.

Exercise 4.9

Recall from Definition 2.41 that a V-functor Φ: X\(^{op}\) × Y → V is a function Φ: Ob(X\(^{op}\) × Y) → Ob(V) such that for all (x, y) and (x′, y′) in X\(^{op}\) ×Y we have

(X\(^{op}\) ×Y)((x, y),(x', y')) ≤ V (Φ(x, y), Φ(x', y')).

Using the definitions of product V-category (Definition 2.74) and opposite V-category (Exercise 2.73) on the left hand side, and using Remark 2.89, which describes how we are viewing the quantale V as enriched over itself, on the right hand side, this unpacks to

X(x′, x) ⊗ Y(y, y′) ≤ Φ(x, y) -o Φ(x′, y′)

Using symmetry of ⊗ and the definition of hom-element, Eq. (2.80), we see that Φ is a profunctor if and only if

X(x′, x) ⊗ Φ(x, y) ⊗ Y(y, y′) ≤ Φ(x′, y′).

Exercise 4.10

Yes, since a Bool-functor is exactly the same as a monotone map, the definition of Bool-profunctor and that of feasibility relation line up perfectly!

Exercise 4.12

The feasibility matrix for Φ is

Exercise 4.15

The Cost-matrix for Φ is

Exercise 4.17

\(\begin{aligned}
\Phi=M_{X}^{3} * M_{\Phi} * M_{Y}^{2} &=\left(\begin{array}{cccc}
0 & 6 & 3 & 11 \\
2 & 0 & 5 & 5 \\
5 & 3 & 0 & 8 \\
11 & 9 & 6 & 0
\end{array}\right)\left(\begin{array}{ccc}
\infty & \infty & \infty \\
11 & \infty & \infty \\
\infty & \infty & \infty \\
\infty & 9 & \infty
\end{array}\right)\left(\begin{array}{ccc}
0 & 4 & 3 \\
3 & 0 & 6 \\
7 & 4 & 0
\end{array}\right) \\
&=\left(\begin{array}{ccc}
17 & 20 & \infty \\
11 & 14 & \infty \\
14 & 17 & \infty \\
20 & 9 & \infty
\end{array}\right)\left(\begin{array}{lll}
0 & 4 & 3 \\
3 & 0 & 6 \\
7 & 4 & 0
\end{array}\right) \\
&=\left(\begin{array}{ccc}
17 & 20 & 20 \\
11 & 14 & 14 \\
14 & 17 & 17 \\
12 & 9 & 15
\end{array}\right)
\end{aligned}\)

Exercise 4.18

Yes, this is valid: it just means that the profunctor Φ: (T × E) → $ does not relate (good-natured, funny) to any element of $. More formally, it means that Φ((good-natured, funny), p) = false for all p \(\in\) $ = {$100K, $500K, $1M}. We can interpret this to mean that it is not feasible to produce a good-natured, funny movie for any of the cost options presented—so at least not for less than a million dollars.

Exercise 4.22

There are a number of methods that can be used to get the correct answer. One way that works well for this example is to search for the shortest paths on the diagram: it so happens that all the shortest paths go through the bridges from D to y and y to r, so in this case (Φ ; Ψ)(−, −) = X(−, D) + 9 + Z(r, −). This gives:

A more methodical way is to use matrix multiplication. Here’s one way you might do the multiplication, using a few tricks.

\(\begin{aligned}
\Phi_{9}^{\circ} \Psi &=\left(M_{X}^{3} * M_{\Phi} * M_{Y}^{2}\right) *\left(M_{Y}^{2} * M_{\Psi} * M_{Z}^{3}\right) \\
&=M_{X}^{3} * M_{\Phi} * M_{Y}^{4} * M_{\Psi} * M_{Z}^{3} \\
&=\left(M_{X}^{3} * M_{\Phi} * M_{Y}^{2}\right) * M_{\Psi} * M_{Z}^{3} \\
&=\Phi * M_{\Psi} * M_{Z}^{3} \\
&=\left(\begin{array}{lll}
17 & 20 & 20 \\
11 & 14 & 14 \\
14 & 17 & 17 \\
12 & 9 & 15
\end{array}\right)\left(\begin{array}{llll}
\infty & \infty & \infty & \infty \\
\infty & \infty & 0 & \infty \\
4 & \infty & \infty & 4
\end{array}\right)\left(\begin{array}{llll}
0 & 2 & 4 & 5 \\
4 & 0 & 2 & 3 \\
2 & 4 & 0 & 1 \\
1 & 3 & 5 & 0
\end{array}\right) \\
&=\left(\begin{array}{lll}
17 & 20 & 20 \\
11 & 14 & 14 \\
14 & 17 & 17 \\
12 & 9 & 15
\end{array}\right)\left(\begin{array}{llll}
\infty & \infty & \infty & \infty \\
2 & 4 & 0 & 1 \\
4 & 6 & 8 & 4
\end{array}\right) \\
\left(\begin{array}{llll}
22 & 24 & 20 & 21 \\
16 & 18 & 14 & 15 \\
19 & 21 & 17 & 18 \\
11 & 13 & 9 & 10
\end{array}\right)
\end{aligned}\)

Exercise 4.26

We choose the Cost-category X from Eq. (2.56). The unit profunctor U\(_{X}\) on X is described by the bridge diagram

Exercise 4.30

1. The first equality is the unitality of V (Definition 2.2(b)).

The second step uses the monotonicity of ⊗ (Definition 2.2(a)) applied to the inequalities I ≤ P(p, p) (the identity law for P at p, Definition 2.46(a)) and Φ(p, q) ≤ Φ(p, q) (reflexivity of preorder V, Definition 1.30(a)). The third step uses the definition of join: for all x and y, since any x ≤ x, we have x ≤ x \(\lor\) y. The final equality is just the definition of profunctor composition, Definition 4.21.

2. Note that in Bool, I = true.

Since the identity law at p says true ≤ P(p, p), and true is the largest element of the preorder Bool, we thus have P(p, p) = true for all p. This shows that the first inequality in Eq. (4.28) is an equality.
The second inequality is more involved. Note that by the above, we can assume the left hand side of the inequality is equal to Φ(p, q). We split into two cases. Suppose Φ(p, q) = true. Then, again since true is the largest element of \(\mathbb{B}\), we must have equality.

Next, suppose Φ(p, q) = false. Note that since Φ is a monotone map P\(^{op}\) × Q → Bool, if p ≤ p in P, then Φ(p1, q) ≤ Φ(p, q) in Bool.

Thus if P(p, p1) = true then Φ(p\(_{1}\), q) = Φ(p, q) = false.

This implies that for all p1 \(\in\) P, we have either P(p, p\(_{1}\)) = false or Φ(p\(_{1}\), q) = false, and hence = \(\bigvee\)\(_{p_{1} \in\ P}\) P(p, p\(_{1}\)) \(\land\) Φ(p\(_{1}\), q) = \(\bigvee\)\(_{p_{1} \in\ P}\) false = false.

Thus, in either case, we see that Φ(p, q) = \(\bigvee\)\(_{p_{1} \in\ P}\) P(p, p\(_{1}\)) \(\land\) Φ(p\(_{1}\), q), as required.

3. The first equation is unitality in monoidal categories, v ⊗ I = v for any v \(\in\) V. The second is that I ≤ Q(q, q) by unitality of enriched categories, see Definition 2.46, together with monotonicity of monoidal product: v\(_{1}\) ≤ v\(_{2}\) implies v ⊗ v\(_{1}\) ≤ v ⊗ v\(_{2}\). The third was shown in Exercise 4.9.

Exercise 4.32

This is very similar to Exercise 2.104: we exploit the associativity of ⊗. Note, however, we also require V to be symmetric monoidal closed, since this implies the distributivity of ⊗ over \(\lor\) (Proposition 2.87 2), and V to be skeletal, so we can turn equivalences into equalities.

\(\begin{aligned}
((\Phi \text { ; } \Psi) \text { ; } \Upsilon)(p, s) &=\bigvee_{r \in \mathcal{R}}\left(\bigvee_{q \in \mathbb{Q}} \Phi(p, q) \otimes \Psi(q, r)\right) \otimes \Upsilon(r, s) \\
&=\bigvee_{r \in \mathcal{R}, q \in \mathbb{Q}} \Phi(p, q) \otimes \Psi(q, r) \otimes \Upsilon(r, s) \\
&=\bigvee_{q \in \mathbb{Q}} \Phi(p, q) \otimes \bigvee_{r \in \mathcal{R}}(\Psi(q, r) \otimes \Upsilon(r, s)) \\
&=(\Phi \text { ; }(\Psi \text { ; } \Upsilon))(p, s)
\end{aligned}\)

Exercise 4.36

This is very straightforward. We wish to check \(\widehat{id}\): P → P has the formula \(\widehat{id}\)(p,q) = P(p,q). By Definition 4.34, \(\widehat{id}\)(p, q) := P(id(p), q) = P(p, q). So they’re the same.

Exercise 4.38

The conjoint \(\check{+}\) : \(\mathbb{R}\) → \(\mathbb{R}\) × \(\mathbb{R}\) × \(\mathbb{R}\) sends (a, b, c, d) to \(\mathbb{R}\)(a, b + c + d), which is true if a ≤ b + c + d, and false otherwise.

Exercise 4.41

1. By Definition 4.34, \(\widehat{F}\)(p, q)= Q(F(p), q) and \(\check{G}\)(p, q) = Q(p, G(q)). Since V is skeletal, F and G are V adjoints if and only if Q(F(p), q) = Q(p, G(q)). Thus F and G are adjoints if and only if \(\widehat{F}\) = \(\check{G}\).

2. Note that id: P → P is V-adjoint to itself, since both sides of Eq. (4.40) then equal P(p, q). Thus \(\widehat{id}\) = \(\check{id}\).

Exercise 4.44

The Hasse diagram for the collage of the given profunctor is quite simply this:

Exercise 4.48

Since we only have a rough definition, we can only roughly check this: we won’t bother with the notion of well-behaved. Nonetheless, we can still compare Definition 2.2 with Definition 4.45.
First, recall from Section 3.2.3 that a preorder is a category P such that for every p, q \(\in\) P, the set P(p, q) has at most one element.
On the surface, all looks promising: both definitions have two constituents and four properties. In constituent (i), both Definition 2.2 and Definition 4.45 call for the same: an element, or object, of the preorder P. So far so good. Constituent (ii), however, is where it gets interesting: Definition 2.2 calls for merely a function ⊗ : P × P → P, while Definition 4.45 calls for a functor.

Recall from Example 3.42 that functors between preorders are exactly monotone maps. So we need for the function ⊗ in Definition 2.2 to be a monotone map. This is exactly property (a) of Definition 2.2: it says that if (x\(_{1}\), x\(_{2}\)) ≤ (y\(_{1}\), y\(_{2}\)) in P ⊗ P, then we must have x\(_{1}\) ⊗ x\(_{2}\) ≤ y\(_{1}\) ⊗ y\(_{2}\) in P. So it is also the case that in Definition 2.2 that ⊗ is a functor.
The remaining properties compare easily, taking the natural isomorphisms to be equality or equivalence in P. Indeed, property (b) of Definition 2.2 corresponds to both properties (a) and (b) of Definition 4.45, and then the respective properties (c) and (d) similarly correspond.

Exercise 4.50

1. \(_{gE}\)(5, 3) = false, \(_{gF}\)(5, 3) = 2.
2. \(_{gE}\)(3, 5) = true, \(_{gF}\)(3, 5) = −2.
3. h(5, true) = 5.
4. h(−5, true) = −5.
5. h(−5, false) = 6.
6. \(_{qG}\)(−2, 3) = 2, \(_{qF}\)(−2, 3) = −13.
7. \(_{qG}\)(2, 3) = −1, \(_{qF}\)(2, 3) = 7.

Exercise 4.52

Yes, the rough definition roughly agrees: plain old categories are Set-categories! In detail, we need to compare Definition 4.51 when V = (Set, {1}, ×) with Definition 3.6. In both cases, we see that (i) asks for a collection of objects and (ii) asks for, for all pairs of objects x, y, a set C(x, y) of morphisms. Moreover, recall that the monoidal unit I is the one element set {1}.

This means a morphism id\(_{x}\) : I → C(x, x) is a function id\(_{x}\) : {1} → C(x, x). This is the same data as simply an element id\(_{x}\) = id\(_{x}\)(1) \(\in\) C(x, x); we call this data the identity morphism on x. Finally, a morphism ; : C(x, y) ⊗ C(y, z) → C(x, z) is a function ; : C(x, y) × C(y, z) → C(x, z); this is exactly the composite required in Definition 3.6 (iv).

So in both cases the data agrees. In Definition 3.6 we also require this data to satify two conditions, unitality and associativity. This is what is meant by the last sentence of Definition 4.51.

Exercise 4.54

An identity element in a Cost-category X is a morphism I → X(x, x) in Cost = ([0, ∞], ≥, 0, +), and hence the condition that 0 ≥ X(x, x). This implies that X(x, x) = 0. In terms of distances, we interpret this to mean that the distance from any point to itself is equal to 0. We think this is a pretty sensible condition for a notion of distance to obey.

Exercise 4.62

1. Here is a picture of the unit corelation Ø → \(\underline{3}\) ⊔ \(\underline{3}\), where we have drawn the empty set with an empty dotted rectangle on the left:

2. Here is a picture of the counit corelation \(\underline{3}\) ⊔ \(\underline{3}\) → Ø:

3. Here is a picture of the snake equation on the left of Eq. (4.59).

Exercise 4.64

Given two resource preorders X and Y, the preorder X × Y represents the set of all pairs of resources, x \(\in\) X and y \(\in\) Y, with (x, y) ≤ (x′, y′) iff x ≤ x′ and y ≤ y′. That is, if x is available given x′ and y is available given y′, then (x, y) is available given (x′, y′).
Given two profunctors Φ: X\(_{1}\) → X\(_{2}\) and Ψ: Y\(_{1}\) → Y\(_{2}\), the profunctor Φ × Ψ represents their conjunction, i.e. AND. In other words, if y\(_{1}\) can be obtained given x\(_{1}\) AND y\(_{2}\) can be obtained given x\(_{2}\), then (y\(_{1}\), y\(_{2}\)) can be obtained given (x\(_{1}\), x\(_{2}\)).

Exercise 4.65

The profunctor X × 1 → X defined by the functor α : (X × 1)\(^{op}\) × X → V that maps α((x, 1), y) := X(x, y) is an isomorphism. It has inverse α\(^{-1}\) : X → X × 1 defined by α\(^{-1}\)(x, (y, 1)) := X(x, y). To see that α\(^{-1}\) ; α = U\(_{x}\), note first that the unit law for X at z and the definition of join imply

X(x, z) = X(x, z) ⊗ I ≤ X(x, z) ⊗ X(z, z) ≤ \(\bigvee_{y \in X}\) X(x, y) ⊗ X(y, z),

while composition says X(x, y) ⊗ X(y, z) ≤ X(x, z) and hence

\(\bigvee_{y \in X}\) X(x, y) ⊗ X(y, z) ≤ \(\bigvee_{y \in X}\) X(x, z) ⊗ X(y, z)

Thus, unpacking the definition of composition of profunctor, we have

(α\(^{-1}\) ; α)(x, z) = \(\bigvee_{(y,1) \in Xx1}\) α(x, (y, 1)) ⊗ α\(^{-1}\)((y, 1), z) = \(\bigvee_{y \in X}\) X(x, y) ⊗ X(y, z) = X(x, z).

Similarly we can show α ; α\(^{−1}\) = U\(_{X×1}\), and hence that α is an isomorphism X × 1 → X. Moreover, we can similarly show that β((1, x), y) := X(x, y) defines an isomorphism β : 1 × X → X.

Exercise 4.66

We check the first snake equation, the one on the left hand side of Eq. (4.59). The proof of the one on the right hand side is analogous. We must show that the composite Φ of profunctors

\(X \stackrel{a^{-1}}{\rightarrow} X x 1 \stackrel{U_{x} x n_{x}}{\longrightarrow} X x X^{op} x X \stackrel{\mathcal{E}_{x} x U_{x}} {\longrightarrow} 1 x X \stackrel{a}{\rightarrow} X\)

is itself the identity (ie. the unit profunctor on X), where α and α\(^{−1}\) are the isomorphisms defined in the solution to Exercise 4.65 above.
Freely using the distributivity of ⊗ over \(\land\), the value Φ(x, y) of this composite at (x, y) \(\in\) X\(^{op}\) × X is given by

\(\begin{aligned}
& \bigvee_{x} \alpha^{-1}(x,(a, 1)) \otimes(\mathrm{U} x \times \eta x)((a, 1),(b, c, d)) \\
& a, b, c, d, e \in X & \otimes(\epsilon x \times \mathrm{U} x)((b, c, d),(1, e)) \otimes \alpha((1, e), y) \\
=& \bigvee_{\alpha}^{-1}(x,(a, 1)) \otimes \mathrm{U} x(a, b) \otimes \eta x(1, c, d) \\
& a, b, c, d, e \in \mathcal{X} \quad \otimes \epsilon x(b, c, 1) \otimes \mathrm{U} x(d, e) \otimes \alpha((1, e), y) \\
=& \bigvee_{a, b, c, d, e \in X} \\
=& x(x, y)
\end{aligned}\)

where in the final step we repeatedly use the argument the Lemma 4.27 that shows that composing with the unit profunctor U\(_{X}\)(a, b) = X(a, b) is the identity. This shows that Φ(x, y) is the identity profunctor, and hence shows the first snake equation holds. Again, checking the other snake equation is analogous.