8.3: Solutions for Chapter 3

Exercise 3.3

There are five non-ID columns in Eq. (3.1)and five arrows in Eq. (3.2). This is not a coincidence: there is always one arrow for every non-ID column.

Exercise 3.9

To do this precisely, we should define concatenation technically.

If G = (V, A, s, t) is a graph, define a path in G to be a tuple of the form (v, a\(_{1}\), . . . , a\(_{n}\)) where v \(\in\) V is a vertex, s(a\(_{1}\)) = v, and t(a\(_{i}\)) = s(a\(_{i+1}\)) for all i \(\in\) {1, . . . , n − 1}; the length of this path is n, and this definition makes sense for any n \(\in\) \(\mathbb{N}\). We say that the source of p is s(p) := v and the target of p is defined to be

Two paths p = (v, a\(_{1}\), . . . , a\(_{m}\)) and q = (w, b\(_{1}\), . . . , b\(_{n}\)) can be concatenated if t(p) = s(q), in which case the concatenated path p ; q is defined to be

(p ; q) := (v, a\(_{1}\), . . . , a\(_{m}\), b\(_{1}\), . . . , b\(_{n}\)).

We are now ready to check unitality and associativity. A path p is an identity in Free(G) iff p = (v) for some v \(\in\) V.

It is easy to see from the above that (v) and (w, b\(_{1}\), ..., b\(_{n}\)) can be concatenated iff v = w, in which case the result is (w,b\(_{1}\), ..., b\(_{n}\)). Similarly(v, a\(_{1}\), ..., a\(_{m}\)) and (w) can be concatenated iff w = t(a\(_{m}\)), in which case the result is (v, a\(_{1}\), . . . , a\(_{m}\)). Finally, for associativity with p and q as above and r = (x, c\(_{1}\), . . . , co), the formula readily reads that whichever way they are concatenated, (p ; q) ; r or p ; (q ; r), the result is

(v, a\(_{1}\), ..., a\(_{m}\), b\(_{1}\), ..., b\(_{n}\), c\(_{1}\), ..., c\(_{o}\)).

Exercise 3.10

We often like to name identity morphisms by the objects they’re on, and we do that here: v\(_{2}\) means id\(_{v2}\). We write ☒ when the composite does not make sense (i.e. when the target of the first morphism does not agree with the source of the second).

Exercise 3.12

1. The category 1 has one object v\(_{1}\) and one morphism, the identity id\(_{v1}\).

2. The category 0 is empty; it has no objects and nomorphisms.

3. The pattern for number of morphisms in 0, 1, 2, 3 is 0, 1, 3, 6; does this pattern look familiar? These are the first few ‘triangle numbers,’ so we could guess that the number of morphisms in n, the free category on the following graph

is 1 + 2 + · · · + n. This makes sense because (and the proof strategy would be to verify that) the above graph has n paths of length 0, it has n − 1 paths of length 1, and so on : it has n − i paths of length i for every 0 ≤ i ≤ n.

Exercise 3.15

The correspondence was given by sending a path to its length.

Concatenating a path of length m with a path of length n results in a path of length m + n.

Exercise 3.16

1. The ten paths are as follows

A, A ; f, A ; g, A ; f ; h, A ; g ; i, B, B ; h, C, C ; i, D

2. A ; f ; h is parallel to A ; g ; i, in that they both have the same domain and both have the same codomain.

3. A is not parallel to any of the other nine paths.

Exercise 3.17

The morphisms in the given diagram are as follows:

A, A ; f, A ; g, A ; j, B, B ; h, C, C ; i, D

Note that A ; f ; h = j = A ; g ; i.

Exercise 3.19

There are four morphisms in D, shown below, namely z, s, s ; s, and s ; s ; s:

Exercise 3.21

The equations that make the graphs into preorders are shown below

Exercise 3.22

The preorder reflection of a category C has the same objects and either one morphism or none between two objects, depending on whether or not a morphism between them exists in C. So the preorder reflection of \(\mathbb{N}\) has one object and one morphism from it to itself, which must be the identity. In other words, the preorder reflection of \(\mathbb{N}\) is 1.

Exercise 3.25

A function f : \(\underline{2}\) → \(\underline{3}\) can be described as an ordered pair (f (1), f (2)). The nine such functions are given by the following ordered pairs, which we arrange into a 2-dimensional grid with 3 entries in each dimension, just for “funzies”:\(^{1}\)

(1, 1) (2, 1) (3, 1)

(1, 2) (2, 2) (3, 2)

(1, 3) (2, 3) (3, 3)

Exercise 3.30

1. The inverse to f (a) = 2, f (b) = 1, f (c) = 3 is given by

f \(^{−1}\)(1) = b, f \(^{−1}\)2) = a, f \(^{−1}\)(3) = c.

2. There are 6 distinct isomorphisms. In general, if A and B are sets, each with n elements, then the number of isomorphisms between them is n factorial, often denoted n!. So for example there are 5 ∗ 4 ∗ 3 ∗ 2 ∗ 1 = 120 isomorphisms between {1, 2, 3, 4, 5} and {a, b, c, d, e}.

Exercise 3.31

We have to show that for any object c \(\in\) C, the identity idc has an inverse, i.e. a morphism f : c → c such that f ; id\(_{c}\) = id\(_{c}\) and id\(_{c}\) ; f = id\(_{c}\). Take f = id\(_{c}\); this works.

Exercise 3.32

1. The monoid in Example 3.13 is not a group, because the morphism s has no inverse.

Indeed each morphism is of the form s\(^{n}\) for some n \(\in\) \(\mathbb{N}\) and composing it with s gives s\(^{n+1}\), which is never s\(^{0}\).p

2. C from Example 3.18 is a group: the identity is always an isomorphism, and the other morphism s has inverse s.

Exercise 3.33

You may have found a person whose mathematical claims you can trust! Whenever you compose two morphisms in Free(G), their lengths add, and the identities are exactly those morphisms whose length is 0. In order forp to be an isomorphism, there must be some q such that p ; q = id and q ; p = id, in which case the length of p (or q) must be 0.

Exercise 3.37

The other three functors 2 → 3 are shown here:

Exercise 3.39

There are nine morphisms in F; as usual we denote identities by the object they’re on. These morphisms are sent to the following morphisms in C:

A' \(\longmapsto\) A, f' \(\longmapsto\) f, g' \(\longmapsto\) g, f' ; h' \(\longmapsto\) f ; h, g' ; i' \(\longmapsto\) f ; h,

B′ \(\longmapsto\) B, h′ \(\longmapsto\) h, C ′ \(\longmapsto\) C, i′ \(\longmapsto\) i, D′ \(\longmapsto\) D.

If one of these seems different from the rest, it’s probably g' ; i ' \(\longmapsto\) f ; h.

But note that in fact also g' ; i '\(\longmapsto\) g ; i because g ; i = f ; h, so it’s not an outlier after all.

Exercise 3.40

We need to give two functors F, G from \(\stackrel{a}{\bullet} \stackrel{f}{\longrightarrow} \stackrel{b}{\bullet}\) to \(\stackrel{a'}{\bullet} \underset{f_{2}}{\stackrel{f_{1}}{\longrightarrow}} \stackrel{b'}{\bullet}\) whose on-objects parts are the same and whose on-morphisms parts are different. There are only two ways to do this, and we choose one of them:

F(a) := a′, G(a) := a′, F(b) := b′, G(b) := b′, F (f ) := f\(_{1}\), and G (f ) := f\(_{2}\).

The other way reverses f\(_{1}\) and f\(_{2}\).

Exercise 3.43

1. Let C be a category.

Then defining id\(_{C}\) : C → C by id\(_{C}\)(x) = x for every object and morphism in C is a functor because it preserves identities id\(_{C}\)(id\(_{c}\)) = id\(_{c}\) = id\(_{id_{C}}\)(c) for each object c \(\in\) Ob(C), and it preserves composition id\(_{C}\)(f ; g) = f ; g = id\(_{C}\)(f) ; id\(_{C}\)(\(_{g}\)) for each pair of composable morphisms f , g in C.

2. Given functors F : C → D and G : D → E, we need to show that F ; G is a functor, i.e. that it preserves preserves identities and compositions. If c \(\in\) C is an object then (F ; G)(id\(_{c}\)) = G(F(id\(_{c}\))) = G(id\(_{F(c)}\)) = id\(_{G(F(c)}\)) because F and G preserve identities. If f, g are composable morphisms in C then

(F ; G)(f ; g) = G(F(f ) ; F(g)) = G(F(f )) ; G(F(g))

because F and G preserve composition

3. We have proposed objects, morphisms, identities, and a composition formula for a category Cat: they are categories, functors, and the identities and compositions given above. We need to check that the two properties, unitality and associativity, hold. So suppose F: C → D is a functor and we pre-compose it as above with id\(_{C}\); it is easy to see that the result will again be F, and similarly if we post-compose F with id\(_{D}\). This gives unitality, and associativity is just as easy, though more wordy. Given F as above and G : D → \(\mathcal{E}\) and H : \(\mathcal{E}\) → F, we need to show that (F ; G) ; H = F ; (G ; H). It’s a simple application of the definition: for any x \(\in\) C, be it an object or morphism, we have

((F ; G) ; H)(c) = H ((F ; G))(c)) = H (G (F (c))) = (G ; H)(F (c)) = (F ; (G ; H))(c).

Exercise 3.45

Let S \(\in\) Set be a set. Define F\(\_{S}\): 1 → Set by F\(\_{S}\)(1) = S and F\(\_{S}\)(id\(\_{1}\)) = id\(\_{S}\). With this definition, F\(\_{S}\) preserves identities and compositions (the only compositions in 1 is the composite of the identity with itself), so F\(\_{S}\) is a functor with F\(\_{S}\)(1) = S as desired.

Exercise 3.48

We are asked what sort of data “makes sense” for the schemas below?

This is a subjective question, so we propose an answer for your consideration.
1. Data on this schema, i.e. a set-valued functor, assigns a set D(z) and a function D(s): D(z) → D(z), such that applying that function twice is the identity. This sort of function is called an involution

of the set Dz:

It’s a do-si-do, a “partner move,” where everyone picks a partner (possibly themselves) and

exchanges with them. One example one could take D to be the set of pixels in a photograph, and take s to be the function sending each pixel to its mirror image across the vertical center line of the photograph.

2. WecouldmakeD(c)thesetofpeopleata“secretSanta”Christmasparty,where everyone gives a gift to someone, possibly themselves. Take D(b) to be the set of gifts, g the giver function (each gift is given by a person), and h the receiver function (each gift is received by a person), D(a) is the set of people who give a gift to themselves, and d( f ) : D(a) → D(b) is the inclusion.

Exercise 3.5

1. The expert packs so much information in so little space! Suppose given three objects F, G, H \(\in\) D\(^{C}\); these are functors F, G, H : C → D. Morphisms α: F → G and β: G → H are natural transfor- mations. Most beginners seem to think about a natural transformation in terms of its naturality squares, but the main thing to keep in mind is its components; the naturality squares constitute a check that comes later.

So for each c \(\in\) C, α has a component α\(_{c}\) : F(c) → G(c) and β has a component β\(_{c}\) : G(c) → H(c) in D. The expert has told us to define (α ; β)\(_{c}\) := (α\(_{c}\) ; β\(_{c}\)), and indeed that is a morphism F(c) → H(c).
Now we do the check. For any f : c → c′ in C, the inner squares of the following diagram commute because α and β are natural; hence the outer rectangle does too:

2. We propose that the identity natural transformation id\(_{F}\) on a functor F : C → D has as its c-component the morphism (id\(_{F}\))\(_{c}\) := id\(_{F}\)(\(_{c}\)) in D, for any c. The naturality square

obviously commutes for any f : c → c′. And it is unital: post-composing idF with any β : F → G (and similarly for precomposing with any α : E → F) results in a natural transformation id\(_{F}\) ; β with components (id\(_{F}\))\(_{c}\) ; β\(_{c}\) = (id\(_{F}\)(\(_{c}\)) ; β\(_{c}\)) = β\(_{c}\), and this is just β as desired.

Exercise 3.58

We have a category C and a preorder P, considered as a category.
1. Suppose that F, G : C → P are functors and α, β : F → G are natural transformations; we need to show that α = β.

It suffices to check that αc\(_{c}\) = β\(_{c}\) for each object c \(\in\) Ob(C). But α\(_{c}\) and β\(_{c}\) are morphisms F(c) → G(c) in P, which is a preorder, and the definition of a preorder considered as a category is that it has at most one morphism between any two objects. Thus α\(_{c}\) = β\(_{c}\), as desired.

2. This is false. Let P := 1, let C := \(\stackrel{a}{\bullet} \frac{f_{1}}{f_{2}} \text { b }\), let F(1) := a, let G(1) := b, let α\(_{1}\) := f\(_{1}\), and let β\(_{1}\) := g\(_{2}\).

Exercise 3.62

We need to write down the following

as a Gr-instance, as in Eq. (3.61). The answer is as follows:

Exercise 3.64

Let G, H be the following graphs:

and let’s believe the authors that there is a unique graph homomorphism α: G → H for which α\(_{Arrow}\)(a) = d.

1. We have α\(_{Arrow}\)(b) = e and α\(_{Vertex}\)(1) = 4, α\(_{Vertex}\)(2) = 5, and α\(_{Vertex}\)(3) = 5.
2. We roughly copy the tables and then draw the lines (shown in black; ignore the dashed lines for now):

3. It works! One example of the naturality is shown with the help of dashed blue lines above. See how both paths starting at a end at 5?

Exercise 3.67

We just need to write out the composite of the following functors

in the form of a database, and then draw the graph. The results are given below.

Exercise 3.73

We are interested in how the functors − × B and (−)\(^{B}\) should act on morphisms for a given set B.

We didn’t specify this in the text—we only specified − × B and (−)\(^{B}\) on objects so in some sense this exercise is open: you can make up anything you want, under the condition that it is functorial. However, the authors cannot think of any such answers except the one we give below.

1. Given an arbitrary function f : X → Y, we need a function X × B → Y × B. We suggest the function which might be denoted f × B; it sends (x, b) to ( f (x), b). This assignment is functorial: applied to id\(_{X}\) it returns id\(_{X x B}\) and it preserves composition.

2. Given a function f : X → Y, we need a function X\(^{B}\) → Y\(^{B}\). The canonical function would be denoted f\(^{B}\); it sends a function g : B → X to the composite (g ; f ) :B → X → Y. This is functorial: applied to id\(_{X}\) it sends g to g, i.e. f\(^{B}\)(id\(_{X}\)) = id\(_{X}\)\(^{B}\), and applied to the composite (f\(_{1}\) ; f\(_{2}\)): X → Y → Z, we have

(f\(_{1}\) ; f\(_{2}\))\(^{B}\)(g) = g ; (f\(_{1}\) ; f\(_{2}\)) = (g ; f\(_{1}\)) ; f\(_{2}\) = (f\(_{1}\)\(^{B}\) ; f\(_{2}\)\(^{B}\))(g)

for any g \(\in\) X\(^{B}\).

3. If p : \(\mathbb{N}\) → \(\mathbb{N}\)\(^{\mathbb{N}}\) is the result of currying +: \(\mathbb{N}\)×\(\mathbb{N}\) → \(\mathbb{N}\), then p(3) is an element of \(\mathbb{N}\)\(^{\mathbb{N}}\), i.e. we have p(3): \(\mathbb{N}\) → \(\mathbb{N}\) what function is it? It is the function that adds three. That is p(3)(n) := n + 3.

Exercise 3.76

The functor !: C → 1 from Eq. (3.75) sends each object c \(\in\) C to the unique object 1 \(\in\) 1 and sends each morphism f : c → d in C to the unique morphism id\(_{1}\) : 1 → 1 in 1.

Exercise 3.78

We want to draw the graph corresponding to the instance I : G → Set shown below:

Here it is, with names and emails shortened (e.g. B=Bob, 3=Em_3):

Exercise 3.81

An object z is terminal in some category C if, for every c \(\in\) C there exists a unique morphism c → z. When C is the category underlying a preorder, there is at most one morphism between any two objects, so the condition simplifies: an object z is terminal iff, for every c \(\in\) C there exists a morphism c → z. The morphisms in a preorder are written with ≤ signs, so z is terminal iff, for every c \(\in\) P we have c ≤ z, and this is the definition of top element.

Exercise 3.82

The terminal object in Cat is 1 because by Exercise 3.76 there is a unique morphism (functor) C → 1 for any object (category) C \(\in\) Cat.

Exercise 3.83

Consider the graph 2V := • • with two vertices and no arrows, and let C = Free(2V); it has two objects and two morphisms (the identities). This category does not have a terminal object because it does not have any morphisms from one object to the other.

Exercise 3.88

A product of x and y in P is an object z \(\in\) P equipped with maps z → x and z → y such that for any other object z′ and maps z′ → x and z′ → y, there is a unique morphism z′ → z making the evident triangles commute. But in a preorder, the maps are denoted ≤, they are unique if they exist, and all diagrams commute. Thus the above becomes: a product of x and y in P is an object z with z ≤ x and z ≤ y such that for any other z′, if z′ ≤ x and z′ ≤ y then z′ ≤ z. This is exactly the definition of meet, z = x \(\land\) y.

Exercise 3.90

1. The identity morphism on the object (c, d) in the product category C × D is (id\(_{c}\), id(_{d}\)).

2. Suppose given three composable morphisms in C × D

\((c\(_{1}\), d\(_{1}\)) \stackrel{(f\(_{1}\), g\(_{1}\)})}{\rightarrow} (c\(_{2}\), d\(_{2}\) \stackrel{(f\(_{2}\), g\(_{2}\)})}{\rightarrow} (c\(_{3}\), d\(_{3}\) \stackrel{(f\(_{3}\), g\(_{3}\)})}{\rightarrow} (c\(_{4}\), d\(_{4}\)\)

We want to check that ((f\(_{1}\), g\(_{1}\)) ; (f\(_{2}\), g\(_{2}\)) ; (f\(_{3}\), g\(_{3}\)) = (f\(_{1}\), g\(_{1}\)) ; ((f\(_{2}\), g\(_{2}\)) ; (f\(_{3}\), g\(_{3}\)). But composition in a product category is given component-wise. That means the left-hand side is ((f\(_{1}\) ; f\(_{2}\)) ; f\(_{3}\), (g\(_{1}\) ; g\(_{2}\)) ; g\(_{3}\)), whereas the right-hand side is (f\(_{1}\) ; (f\(_{2}\) ; f\(_{3}\)), g\(_{1}\) ; (g\(_{2}\) ; g\(_{3}\))), and these are equal because both C and D individually have associative composition.

3. The product category 1 × 2 has two objects (1, 1) and (1, 2) and one non-identity morphism (1,1) → (1,2). It is not hard to see that it looks the same as 2. In fact, for any C there is an isomorphism of categories 1 × C \(\cong\) C.

4. Let P and Q be preorders, let X = P × Q be their product preorder as defined in Example 1.56, and let P, Q, and X be the corresponding categories. Then X = P × Q.

Exercise 3.91

A product of X and Y is an object Z equipped with morphisms \(X \stackrel{px}{\leftarrow} Z \stackrel{py}{\rightarrow} Y\) such that for any other object Z' equipped with morphisms \(X \stackrel{p'x}{\leftarrow} Z \stackrel{p'y}{\rightarrow} Y\), there is a unique morphism f : Z → Z making the triangles commute, f ; p\(_{X}\) = p′\(_{X}\) and f ; p\(_{Y}\) = p′\(_{Y}\). But “an object equipped with morphisms to X and Y” is exactly the definition of an object in Cone(X, Y), and a morphism f making the triangles commute is exactly the definition of a morphism in Cone(X, Y). So the definition above becomes: a product of X and Y is an object Z \(\in\) Cone(X, Y) such that for any other object Z′ there is a unique morphism Z′ → Z in Cone(X, Y). This is exactly the definition of Z being terminal in Cone(X, Y).

Exercise 3.97

Suppose J is the graph \(\begin{array}{l} v1 \\ \bullet \end{array}\)\(\begin{array}{l} v2 \\ \bullet \end{array}\) and D : J → Set is given by two sets, D(v\(_{1}\)) = A and D(v\(_{2}\)) = B for sets A, B. The product of these two sets is A × B. Let’s check that the limit formula in Theorem 3.95 gives the same answer. It says

\(\begin{aligned}
&\lim _{g} D:=\left\{\left(d_{1}, \ldots, d_{n}\right) \mid d_{i} \in D\left(v_{i}\right) \text { for all } 1 \leq i \leq n\right. \text { and }\\
&\text { for all } a: v_{i} \rightarrow v_{j} \in A, \text { we have } \left.D(a)\left(d_{i}\right)=d_{j}\right\}
\end{aligned}\)

But in our case n = 2, there are no arrows in the graph, and D(v\(_{1}\)) = A and D(v\(_{2}\)) = B. So the formula reduces to

lim\(_{J}\)D := (d\(_{1}\), d\(_{2}\)) | d\(_{1}\) \(\in\) A and d\(_{2}\) \(\in\) B.

which is exactly the definition of A × B.

Exercise 3.101

Given a functor F : C → D, we define its opposite F\(^{op}\) : C\(^{op}\) → D\(^{op}\) as follows.

For each object c \(\in\) Ob(C\(^{op}\)) = Ob(C), put F\(^{op}\)(c) := F(c). For each morphism f : c\(_{1}\) → c\(_{2}\) in C\(^{op}\), we have a corresponding morphism f′: c\(_{2}\) → c\(_{1}\) in C and thus a morphism F(f′): F(c\(_{2}\)) → F(c\(_{1}\)) in D, and thus a morphism F(f ) : F\(^{op}\)(c\(_{1}\))→F\(^{op}\)(c\(_{2}\)).

Hence we can define F\(^{op}\)(f ) := F(f' )'. Note that the primes (−') are pretty meaningless, we only put them there to differentiate between things that are very closely related. It is easy to check that our definition of Fop is functorial: it sends identities to identities and composites to composites.