8.6: Solutions for Chapter6

Exercise 6.3

Let A = {a, b}, and consider the preorders shown here: \(\begin{array}{l} a \\ \bullet \end{array}\) \(\begin{array}{l} b \\ \bullet \end{array}\), \(\begin{array}{l} a \\ \bullet \end{array}\) → \(\begin{array}{l} b \\ \bullet \end{array}\), \(\begin{array}{l} a \\ \bullet \end{array}\) \(\leftrightarrows\) \(\begin{array}{l} b \\ \bullet \end{array}\).

1. The left-most (the discrete preorder on A) has no initial object, because a \(nleq\) b and b \(nleq\) a.
2. The middle one has one initial object, namely a.
3. The right-most (the co-discrete preorder on A) has two initial objects.

Exercise 6.6

Recall that the objects of a free category on a graph are the vertices of the graph, and the morphisms are paths. Thus the free category on a graph G has an initial object if there exists a vertex v that has a unique path to every object. In 1. and 2., the vertex a has this property, so the free categories on graphs 1. and 2. have initial objects. In graph 3., neither a nor b have a path to each other, and so there is no initial object. In graph 4., the vertex a has many paths to itself, and hence its free category does not have an initial object either.

Exercise 6.7

1. The remaining conditions are that f (1\(_{R}\)) = 1\(_{S}\), and that f (r1 ∗\(_{R}\) r2) = f (r1) ∗\(_{S}\) f (r2).

2. The initial object in the category Rig is the natural numbers rig (\(\mathbb{N}\), 0, +, 1, ∗).

The fact that is initial means that for any other rig R = (R, 0\(_{R}\), +\(_{R}\), 1\(_{R}\), ∗\(_{R}\)), there is a unique rig homomorphism f : \(\mathbb{N}\) → R.

What is this homomorphism? Well, to be a rig homomorphism, f must send 0 to 0\(_{R}\), 1 to 1\(_{R}\). Furthermore, we must also have f (m + n) = f (m) +\(_{R}\) f (n), and hence

So if there is a rig homomorphism f : \(\mathbb{N}\) → R, it must be given by the above formula. But does this formula work correctly for multiplication?
It remains to check f (m ∗ n) = f (m) ∗\(_{R}\) f (n), and this will follow from distributivity. Noting that f (m ∗ n) is equal to the sum of m n copies of 1\(_{R}\), we have

Thus (\(\mathbb{N}\), 0, +, 1, ∗) is the initial object in Rig.

Exercise 6.8

In Definition 6.1, it is the initial object Ø \(\in\) C that is universal. In this case, all objects c \(\in\) C are ‘comparable objects’. So the universal property of the initial object is that to any object c \(\in\) C, there is a unique map Ø → c coming from the initial object.

Exercise 6.10

If c\(_{1}\) is initial then by the universal property, for any c there is a unique morphism c\(_{1}\) → c; in particular, there is a unique morphism c\(_{1}\) → c\(_{2}\), call it f . Similarly, if c\(_{2}\) is initial then there is a unique morphism c\(_{2}\) → c\(_{1}\), call it g. But how do we know that f and g are mutually inverse? Well since c\(_{1}\) is initial there is a unique morphism c\(_{1}\) → c\(_{1}\). But we can think of two: idc1 and f ; g. Thus they must be equal. Similarly for c\(_{2}\), so we have f ; g = id\(_{c_{1}}\) and g ; f = id\(_{c_{2}}\), which is the definition of f and g being mutually inverse.

Exercise 6.13

Let (P, ≤) be a preorder, and p, q \(\in\) P. Recall that a preorder is a category with at most one morphism, denoted ≤, between any two objects. Also recall that all diagrams in a preorder commute, since this means any two morphisms with the same domain and codomain are equal.
Translating Definition 6.11 to this case, a coproduct p + q is P is an element of P such that p ≤ p + q and q ≤ p + q, and such that for all elements x \(\in\) P with maps p ≤ x and q ≤ x, we have p + q ≤ x. But this says exactly that p + q is a join: it is a least element above both p and q. Thus coproducts in preorders are exactly the same as joins.

Exercise 6.16

The function [f , g] is defined by

[f , g] : A ⊔ B \(\longrightarrow\) T

apple1 \(\mapsto\) a

banana1 \(\mapsto\) b

pear1 \(\mapsto\) p

cherry1 \(\mapsto\) c

orange1 \(\mapsto\) o

apple2 \(\mapsto\) e

tomato2 \(\mapsto\) o

mango2 \(\mapsto\) o.

Exercise 6.17

1. The equation ι\(_{A}\) ; [f , g] = f is the commutativity of the left hand triangle in the commutative diagram (6.12) defining [f , g].

2. The equation ι\(_{B}\) ; [f , g] = g is the commutativity of the right hand triangle in the commutative diagram (6.12) defining [f , g].

3. The equation [f , g] ; h = [f ; h, g ; h] follows from the universal property of the coproduct. Indeed, the diagram

commutes, and the universal property says there is a unique map [f ; h, g ; h]: A + B → D for which this occurs.

Hence we must have [f , g] ; h = [f ; h, g ; h]. 4. Similarly, to show [ι\(_{A}\), ι\(_{B}\)] = id\(_{A + B}\), observe that the diagram

trivially commutes. Hence by the uniqueness in (6.12), [ι\(_{A}\) , ι\(_{B}\)] = id\(_{A + B}\).

Exercise 6.18

This exercise is about showing that coproducts and an initial object give a symmetric monoidal category. Since all we have are coproducts and an initial object, and since these are defined by their universal properties, the solution is to use these universal properties over and over, to prove that all the data of Definition 4.45 can be constructed.

1. To define a functor + : C × C → C we must define its action on objects and morphisms. In both cases, we just take the coproduct. If (A, B) is an object of C × C, its image A + B is, as usual, the coproduct of the two objects of C.

If (f, g): (A, B) → (C, D) is a morphism, then we can form a morphism f + g = [f ; ι\(_{C}\) , g ; ι\(_{D}\)] : A + B → C + D, where ι\(_{C}\) : C → C + D and ι\(_{D}\) : D → C + D are the canonical morphisms given by the definition of the coproduct A + B.

Note that this construction sends identity morphisms to identity morphisms, since by Exercise 6.17 4 we have

id\(_{A}\) + id\(_{B}\) = [id\(_{A}\) ; ι\(_{A}\), id\(_{B}\) ; ι\(_{B}\)] = [ι\(_{A}\), ι\(_{B}\)] = id\(_{A + B}\).

To show that + is a functor, we need to also show it preserves composition. Suppose we also have amorphism(h, k): (C, D) → (E, F) in C × C. We need to show that (f + g) ; (h + k) = (f ; h) + (g ; k). This is a slightly more complicated version of the argument in Exercise 6.17 3. It follows from the fact the diagram below commutes:

Indeed, we again use the uniqueness of the copairing in (6.12), this time to show that (f ; h) + (g ; k) = [f ; h ; ι\(_{E}\), k ; ι\(_{F}\)] = (f + g) ; (h + k), as required.

2. Recall the universal property of the initial object gives a unique map !\(_{A}\) : Ø → A. Then the copairing [id\(_{A}\), !\(_{A}\)] is a map A + Ø → A. Moreover, it is an isomorphism with inverse ι\(_{A}\) : A → A + Ø.

Indeed, using the properties in Exercise 6.17 and the universal property of the initial object, we have ι\(_{A}\) ; [id\(_{A}\), !\(_{A}\)] = id\(_{A}\), and

[id\(_{A}\), !\(_{A}\)] ; ι\(_{A}\) = [id\(_{A}\) ; ι\(_{A}\), !\(_{A}\) ; ι\(_{A}\)] = [ι\(_{A}\), !\(_{A + Ø}\)] = [ι\(_{A}\), ι\(_{Ø}\)] = id\(_{A + Ø}\).

An analogous argument shows [!\(_{A}\) , id\(_{A}\)] : Ø + A → A is an isomorphism.

3. We’ll just write down the maps and their inverses; we leave it to you, if you like, to check that they indeed are inverses

a) The map [id\(_{A + ι_{B},ι_{C}}\)] = [[ι\(_{A}\), ι\(_{B}\) ; ι\(_{B + C}\)], ι\(_{C}\) ; ι\(_{B + C}\)]: (A + B) + C → A + (B + C) is an isomorphism, with inverse [ι\(_{A}\), ι\(_{B}\) + id\(_{C}\)]: A + (B + C) → (A + B) + C.

b) The map [ι\(_{A}\), ι\(_{B}\)]: A + B → B + A is an isomorphism.

Note our notation here is slightly confusing: there are two maps named ι\(_{A}\),(i) ι\(_{A}\): A → A + B, and (ii) ι\(_{A}\): A → B + A, and similarly for ι\(_{B}\). In the above we mean the map (ii). It has inverse [ι\(_{A}\), ι\(_{B}\)]: B + A → A + B, where in this case we mean the map (i).

Exercise 6.24

1. Suppose given an arbitrary diagram of the form B ← A → C in Disc\(_{S}\); we need to show that it has a pushout. The only morphisms in Disc\(_{S}\) are identities, so in particular A = B = C, and the square consisting of all identities is its pushout.

2. Suppose Disc\(_{S}\) has an initial object s. Then S cannot be empty! But it also cannot have more than one object, because if s′ is another object then there is a morphism s → s′, but the only morphisms in S are identities so s = s′. Hence the set S must consist of exactly one element.

Exercise 6.26

The pushout is the set \(\underline{4}\), as depicted in the top right in the diagram below, equipped also with the depicted functions:

We want to see that this checks out with the description from Example 6.25, i.e. that it is the set of equivalence classes in \(\underline{5}\) ⊔ 3 generated by the relation {f (a) ∼ g(a) | a \(\in\) \(\underline{4}\)}. If we denote elements of 5 as {1, ..., 5} and those of \(\underline{3}\) as {1′, 2′, 3′}, we can redraw the functions f, g:

which says we take the equivalence relation on \(\underline{5}\) ⊔ \(\underline{3}\) generated by: 1 ∼ 1′, , 3 ∼ 1′, 5 ∼ 2′, and 5 ∼ 3′. The equivalence classes are {1, 1′, 3}, {2}, {4}, and {5, 2′, 3′}. These four are exactly the four elements in the set labeled ‘pushout’ in Eq. (A.1).

Exercise 6.28

1. The diagram to the left commutes because Ø is initial, and so has a unique map Ø → X + Y. This implies we must have f ; ι\(_{X}\) = g ; ι\(_{Y}\).

2. There is a unique map X + Y → T making the diagram in (6.21) commutes imply by the universal property of the coproduct (6.12) applied to the maps x : X → T and y : Y → T.

3. Suppose X + \(_{Ø}\)Y exists. By the universal property of Ø, given any pair of arrows x : X → T and y : Y → T, the diagram

commutes. This means, by the universal property of the pushout X + \(_{Ø}\)Y, there exists a unique map t : X + \(_{Ø}\)Y → T such that ι\(_{X}\) ; t = x and ι\(_{Y}\) ; t = y.

Thus X + \(_{Ø}\)Y is the coproduct X + Y.

Exercise 6.35

We have to check that the colimit of the diagram shown left really is given by taking three pushouts as shown right:

That is, we need to show that S, together with the maps from A, B, X, Y, and Z, has the required universal property. So suppose given an object T with two commuting diagrams as shown:

We need to show there is a unique map S → T making everything commute. Since Q is a pushout of X ← A → Y, there is a unique map Q → T making a commutative triangle with Y, and since R is the pushout of Y ← B → Z, there is a unique map R → T making a commutative triangle with Y. This implies that there is a commuting (Y, Q, R, T) square, and hence a unique map S → T from its pushout making everything commute. This is what we wanted to show.

Exercise 6.41

The formula in Theorem 6.37 says that the pushout X +\(_{N}\) Y is given by the set of equivalence classes of X ⊔ N ⊔ Y under the equivalence relation generated by x ∼ n if x = f (n), and y ∼ n if y(n), where x \(\in\) X, y \(\in\) Y, n \(\in\) N. Since for every n \(\in\) N there exists an x \(\in\) X such that x = f (n), this set is equal to the set of equivalence classes of X ⊔ Y under the equivalence relation generated by x ∼ y if there exists n such that x = f (n) and y = g(n). This is exactly the description of Example 6.25.

Exercise 6.48

The monoidal product is

Exercise 6.49

Let x and y be composable cospans in Cospan\(_{FinSet}\). In terms of wires and connected components, the composition rule in Cospan\(_{FinSet}\) says that (i) the composite cospan has a unique element in the apex for every connected component of the concatenation of the wire diagrams x and y, and (ii) in the wire diagram for x ; y, each element of the feet is connected by a wire to the element representing the connected component to which it belongs.

Exercise 6.57

Morphisms 1, 4, and 6 are equal, and morphisms 3 and 5 are equal. Morphism 3 is not equal to any other depicted morphism. This is an immediate consequence of Theorem 6.55.

Exercise 6.59

1. The input to h should be labelled B.
2. The output of g should be labelled D, since we know from the labels in the top right that h is a morphism B → D ⊗ D.
3. The fourth output wire of the composite should be labelled D too!

Exercise 6.62

We draw the function depictions above, and the wiring depictions below. Note that we depict the empty set with blank space.

Exercise 6.63

The special law says that the composite of cospans

is the identity. This comes down to checking that the square

is a pushout square. It is trivial to see that the square commutes. Suppose now that we have maps f : X → Y and g : X → Y such that

Write ι\(_{1}\) : X → X + X for the map into the first copy of X in X + X, given by the definition of coproduct. Then, using the fact that ι\(_{1}\) ; [id, id] = id from Exercise 6.17 1, and the commutativity of the above square, we have f = ι\(_{1}\) ; [id, id] ; f = ι\(_{1}\) ; [id, id] ; g = g. This means that f : X → T is the unique map such that

commutes, and so (A.2) is a pushout square.

Exercise 6.67

The missing diagram is

Exercise 6.70

Let A \(\subseteq\) S and B \(\subseteq\) T. Then

\(\begin{aligned}
\varphi_{S^{\prime}, T^{\prime}}\left(\left(\mathrm{im}_{f} \times \mathrm{im}_{g}\right)(A \times B)\right) &=\varphi_{S^{\prime}, T^{\prime}}(\{f(a) \mid a \in A\} \times\{g(b) \mid b \in B\}) \\
&=\{(f(a), g(b)) \mid a \in A, b \in B\} \\
&=\operatorname{im}_{f \times g}(A \times B) \\
&=\operatorname{im}_{f \times g}\left(\varphi_{S, T}(A, B)\right)
\end{aligned}\)

Thus the required square commutes.

Exercise 6.78

They mean that every category Cospan\(_{C}\) is equal to a category Cospan\(_{F}\), for some well-chosen F. They also tell you how to choose this F: take the functor F : C → Set that sends every object of C to the set {∗}, and every morphism of C to the identity function on {∗}. Of course, you will have to check this functor is a lax symmetric monoidal functor, but in fact this is not hard to do.
To check that Cospan\(_{C}\) is equal to Cospan\(_{F}\) , first observe that they have the same objects: the objects of C. Next, observe that a morphism in Cospan\(_{F}\) is a cospan X ← N → Y in C together with an element of FN = {∗}. But FN also has a unique element, ∗! So there’s no choice here, and we can consider morphisms of Cospan\(_{F}\) just to be cospans in C.

Moreover, composition of morphisms in Cospan\(_{F}\) is simply the usual composition of cospans via pushout, so Cospan\(_{F}\) = Cospan\(_{C}\).
(More technically, we might say that Cospan\(_{C}\) and Cospan\(_{F}\) are isomorphic, where the isomorphism is the identity-on-objects functor Cospan\(_{C}\) → Cospan\(_{F}\) that simply decorates each cospan with ∗, and its inverse is the one that forgets this ∗. But this is close enough to equal that many category theorists, us included, don’t mind saying equal in this case.)

Exercise 6.79

We can represent the circuit in Eq. (6.71) by the tuple (V, A, s, t, l) where V = {ul, ur, dl, dr}, A = {r1, r2, r3, c1, i1}, and s, t, and l are defined by the table

Exercise 6.80

The circuit Circ(f )(c) is

Exercise 6.82

The circuit ψ\(_{\underline{2, 2}}\)(b, s) is the disjoint union of the two labelled graphs b and s :

Exercise 6.83

The cospan is the cospan \(\underline{1} \stackrel{f}{\rightarrow} \underline{2} \stackrel{g}{\leftarrow} \underline{1}\), where f(1) and g(1) = 2. The decoration is the C-ciruit (\(\underline{2}\), {a}, s, t, l), where s(a) = 1, t(a) = 2 and l(a) = battery.

Exercise 6.86

Recall the circuit C = (V, A, s, t, l) from the solution to Exercise 6.79. Then the first decorated cospan is given by the cospan \(\underline{1} \stackrel{f}{\rightarrow} V \stackrel{g}{\leftarrow} \underline{2}\), f (1) = ul, (1) = ur, and g(2) = ur, decorated by circuit C. The second decorated cospan is given by the cospan \(\underline{1} \stackrel{f'}{\rightarrow} V' \stackrel{g'}{\leftarrow} \underline{2}\) and the circuit C′:= (V′, A′, s′, t′, l′), where V′ = {l, r, d}, A′ = {r1′, r2′}, and the functions are given by the tables

To compose these, we first take the pushout of \(V \stackrel{g}{\leftarrow} \underline{2} \stackrel{f'}{\leftarrow} V'\).

This gives the a new apex V ′′ = {ul, dl, dr, m, r} with five elements, and composite cospan \(\underline{1} \stackrel{h}{\rightarrow} V'' \stackrel{k}{\leftarrow} \underline{2}\) given by h(1) = ul, k(1) = r and k(2) = m. The new circuit is given by (V,′′ A + A′, s,′′ t,′′ l′′) where the functions are given by

This is exactly what is depicted in Eq. (6.74).

Exercise 6.88

Composing η and x we have

and composing the result of \(\mathcal{E}\) gives

Exercise 6.96

1. The cospan shown left corresponds to the wiring diagram shown right:

It has two inner circles, each with two ports. One port of the first is wired to a port of the second. One port of the first is wired to the outside circle, and one port of the second is wired to the outside circle. This is exactly what the cospan says to do.

2. The cospan shown left corresponds to the wiring diagram shown right:

3. The composite g ◦\(_{1}\) f has arity (2, 2, 2, 2; 0); there is a depiction on the left:

4. The associated wiring diagram is shown on the right above. One can see that one diagram has been substituted in to a circle of the other.