4.4: Categorification

Here we switch gears, to discuss a general concept called categorification. We will begin again with the basics, categorifying several of the notions we’ve encountered already. The goal is to define compact closed categories and their feedback-style wiring diagrams. At that point we will return to the story of co-design, and V-profunctors in general, and show that they do in fact form a compact closed category, and thus interpret the diagrams we’ve been drawing since Eq. (4.1).

The basic idea of categorification

The general idea of categorification is that we take a thing we know and add structure to it, so that what were formerly properties become structures. We do this in such a way that we can recover the thing we categorified by forgetting this new structure. This is rather vague; let’s give an example. Basic arithmetic concerns properties of the natural numbers N, such as the fact that 5 + 3 = 8. One way to categorify N is to use the category FinSet of finite sets and functions. To obtain a categorification, we replace the brute 5, 3, and 8 with sets of that many elements, say \(\underline{5}\) = {apple,banana,cherry,dragonfruit,elephant}, \(\underline{3}\) = {apple, tomato, cantaloupe}, and \(\underline{8}\) = {Ali, Bob, Carl, Deb, Eli, Fritz, Gem, Helen} respectively. We also replace + with disjoint union of sets ⊔, and the brute property of equality with the structure of an isomorphism. What makes this a good categorification is that, having made these replacements, the analogue of 5 + 3 = 8 is still true: \(\underline{5}\) ⊔ \(\underline{3}\) \(\cong\) \(\underline{8}\).

In this categorified world, we have more structure available to talk about the relation- ships between objects, so we can be more precise about how they relate to each other. Thus it’s not the case that \(\underline{5}\) ⊔ \(\underline{3}\) is equal to our chosen eight-element set 8, but more precisely that there exists an invertible function comparing the two, showing that they are isomorphic in the category FinSet.

Note that in the above construction we made a number of choices; here we must beware. Choosing a good categorification—like designing a good algebraic structure such as that of preorders or quantales—is part of the art of mathematics. There is no prescribed way to categorify, and the success of a chosen categorification is often empirical: its richer structure should allow us more insights into the subject we want to model.

As another example, an empirically pleasing way to categorify preorders is to cat- egorify them as, well, categories. In this case, rather than the brute property “there exists a morphism a → b,” denoted a ≤ b or P(a, b) = true, we instead say “here is a set of morphisms a → b.” We get a hom-set rather than a hom-Boolean. In fact—to state this in a way straight out of the primordial ooze—just as preorders are Bool-categories, ordinary categories are actually Set-categories.

reflection on wiring diagrams

Suppose we have a preorder. We introduced a very simple sort of wiring diagram in Section 2.2.2. These allowed us to draw a box

whenever x\(_{0}\) ≤ x\(_{1}\). Chaining these together, we could prove facts in our preorder. For example

provides a proof that x\(_{0}\) ≤ x\(_{3}\) (the exterior box) using three facts (the interior boxes), x\(_{0}\) ≤ x\(_{1}\), x\(_{1}\) ≤ x\(_{2}\), and x\(_{2}\) ≤ x\(_{3}\).

As categorified preorders, categories have basically the same sort of wiring diagram as preorders—namely sequences of boxes inside a box. But since we have replaced the fact that x\(_{0}\) ≤ x\(_{1}\) with the structure of a set of morphisms, we need to be able to label our boxes with morphism names:

Suppose given additional morphisms g : B → C, and h : C → D. Representing these each as boxes like we did for f , we might be tempted to stick them together to form a new box:

Ideally this would also be a morphism in our category: after all, we have said that we can represent morphisms with boxes with one input and one output. But wait, you say! We don’t know which morphism it is. Is it f ; (g ; h)? Or (f ; g) ; h? It’s good that you are so careful. Luckily, we are saved by the properties that a category must have.

Associativity says f ; (g ; h) = (f ; g) ; h, so it doesn’t matter which way we chose to try to decode the box.

Similarly, the identity morphism on an object x is drawn as on the left below, but we will see that it is not harmful to draw id\(_{x}\) in any of the following three ways:

By Definition 3.6 the morphisms in a category satisfy two properties, called the unitality property and the associativity property.

The unitality says that id\(_{x}\) ; f = f = f = id\(_{y}\) for any f : x → y. In terms of diagrams this would say

This means you can insert or discard any identity morphism you see in a wiring diagram. From this perspective, the coherence laws of a category that is, the associativity law and the unitality law are precisely what are needed to ensure we can lengthen and shorten wires without ambiguity.

In Section 2.2.2, we also saw wiring diagrams for monoidal preorders. Here we were allowed to draw boxes which can have multiple typed inputs and outputs, but with no choice of label (always ≤):

If we combine these ideas, we will obtain a categorification of symmetric monoidal preorders: symmetric monoidal categories. A symmetric monoidal category is an algebraic structure in which we have labelled boxes with multiple typed inputs and outputs:

Furthermore, a symmetric monoidal category has a composition rule and a monoidal product, which permit us to combine these boxes to interpret diagrams like this:

Finally, this structure must obey coherence laws, analogous to associativity and unitality in categories, that allow such diagrams to be unambiguously interpreted. In the next section we will be a bit more formal, but it is useful to keep in mind that, when we say our data must be “well behaved,” this is all we mean.

Monoidal categories

We defined V-categories, for a symmetric monoidal preorder V in Definition 2.46. Just like preorders turned out to be special kinds of categories (see Section 3.2.3), monoidal preorders are special kinds of monoidal categories. And just like we can consider V-categories for a monoidal preorder, we can also consider V-categories when V is a monoidal category. This is another sort of categorification.

We will soon meet the monoidal category (Set, {1}, ×). The monoidal product will take two sets, S and T, and return the set S × T = {(s, t) | s \(\in\) S, t \(\in\) T}. But whereas for monoidal preorders we had the brute associative property (p ⊗ q) ⊗ r = p ⊗ (q ⊗ r), the corresponding idea in Set is not quite true:

\(\begin{aligned}
& S \times(T \times U):=\{(s,(t, u)) \mid s \in S, t \in T, u \in U\} \\
=? &(S \times T) \times U:=\{((s, t), u) \mid s \in S, t \in T, u \in U\}
\end{aligned}\)

They are slightly different sets: the first contains pairs consisting of an elements in S and an element in T × U, while the second contains pairs consisting of an element in S × T and an element in U. The sets are not equal, but they are clearly isomorphic, i.e. the difference between them is “just a matter of bookkeeping.” We thus need a structure a bookkeeping isomorphism to keep track of the associativity:

\(\alpha_{s, t, u}:\{(s,(t, u)) \mid s \in S, t \in T, u \in U\} \stackrel{\cong}{\rightarrow}\{((s, t), u) \mid s \in S, t \in T, u \in U\}\)

There are a couple things to mention before we dive into these ideas. First, just because you replace brute things and properties with structures, it does not mean that you no longer have brute things and properties: new ones emerge! Not only that, but second, the new brute stuff tends to be more complex than what you started with. For example, above we replaced the associativity equation with an isomorphism αs,t,u, but now we need a more complex property to ensure that all these α’s behave reasonably! The only way out of this morass is to add infinitely much structure, which leads one to “∞-categories,” but we will not discuss that here.

Instead, we will continue with our categorification of monoidal preorders, starting with a rough definition of symmetric monoidal categories. It’s rough in the sense that we suppress the technical bookkeeping, hiding it under the name “well behaved.”

Rough Definition: 4.45.

Let C be a category. A symmetric monoidal structure on C consists of the following constituents:

(i) an object I \(\in\) Ob(C) called the monoidal unit, and

(ii) a functor ⊗ : C × C → C, called the monoidal product

subject to well-behaved, natural isomorphisms

(a) λ\(_{c}\) : I ⊗ c \(\cong\) c for every c \(\in\) Ob(C),

(b) ρ\(_{c}\) :c ⊗ I \(\cong\) c for every c \(\in\) Ob(C),

(c) α\(_{c,d,e}\) :(c ⊗ d) ⊗e \(\cong\) c ⊗ (d ⊗ e) for every c, d, e \(\in\) Ob(C),and

(d) σ\(_{c,d}\) :c ⊗ d \(\cong\) d ⊗c for every c, d \(\in\) Ob(C), called the swap map, such that σ ◦ σ = id.

A category equipped with a symmetric monoidal structure is called a symmetric monoidal category.

Remark 4.46. If the isomorphisms in (a), (b), and (c)—but not (d)—are replaced by equalities, then we say that the monoidal structure is strict, and this is a complete (non-rough) definition of symmetric strict monoidal category. In fact, symmetric strict monoidal categories are almost the same thing as symmetric monoidal categories, via a result known as Mac Lane’s coherence theorem. An upshot of this theorem is that we can, when useful to us, pretend that our monoidal categories are strict: for example, we implicitly do this when we draw wiring diagrams. Ask your friendly neighborhood category theorist to explain how!

Remark 4.47. For those yet to find a friendly expert category theorist, we make the following remark. A complete (non-rough) definition of symmetric monoidal category is that a symmetric monoidal category is a category equipped with an equivalence to (the underlying category of) a symmetric strict monoidal category. This can be unpacked, using Remark 4.46 and our comment about equivalence of categories in Remark 3.59, but we don’t expect you to do so. Instead, we hope this gives you more incentive to ask a friendly expert category theorist!

Exercise 4.48.

Check that monoidal categories indeed generalize monoidal preorders: a monoidal preorder is a monoidal category (P, I, ⊗) where,

for every p, q \(\in\) P, the set P(p, q) has at most one element. ♦

Example 4.49.

As we said above, there is a monoidal structure on Set where the monoidal unit is some choice of singleton set, say I := {1}, and the monoidal product is ⊗ := ×. What it means that × is a functor is that:

• For any pair of objects, i.e. sets, (S, T) \(\in\) Ob(Set × Set), one obtains a set (S × T) \(\in\) Ob(Set). We know what it is: the set of pairs {(s, t) | s \(\in\) S, t \(\in\) T}.
• For any pair of morphisms, i.e. functions, f : S → S′ and g :T → T′, one obtains a function (f ×g): (S×T) → (S′×T′). It works pointwise: (f ×g)(s, t) := (f (s), g(t)).
• These should preserve identities: id\(_{S}\) × id\(_{T}\) = id\(_{S×T}\) for any sets S, T.
• These should preserve composition: for any functions \(S \stackrel{f}{\rightarrow} S^{\prime} \stackrel{f^{\prime}}{\rightarrow} S^{\prime \prime} \text { and } T \stackrel{g}{\rightarrow} T^{\prime} \stackrel{g^{\prime}}{\rightarrow} T^{\prime \prime}\), one has

(f ×g) ; (f ' ×g' ) = (f ; g) × (f ' ; g').

The four conditions, (a), (b), (c), and (d) give isomorphisms {1} × S \(\cong\) S, etc.

These maps are obvious in the case of Set, e.g. the function {(1, s) | s \(\in\) S} → S sending (1, s) to s. We have been calling such things bookkeeping.

Exercise 4.50.

Consider the monoidal category (Set, 1, ×), together with the diagram

Suppose that A = B = C = D = F = G = Z and E = \(\mathbb{B}\) = {true,false}, and suppose that f\(_{C}\)(a) = |a|, f\(_{D}\)(a) = a ∗ 5, g\(_{E}\)(d, b) = “d ≤ b,” g\(_{F}\)(d, b) = d − b, and h(c, e) = if e then c else 1 − c.

1. What are g\(_{E}\)(5,3) and g\(_{F}\)(5,3)?

2. What are g\(_{E}\)(3,5) and g\(_{F}\)(3,5)?

3. What is h(5, true)?

4. What is h(−5, true)?

5. What is h(−5, false)?

The whole diagram now defines a function A × B → G × F; call it q.

6. What are q\(_{G}\)(−2, 3) and q\(_{F}\)(−2, 3)?

7. What are q\(_{G}\)(2, 3) and q\(_{F}\)(2, 3)?

We will see more monoidal categories throughout the remainder of this book. ♦

Categories enriched in a symmetric monoidal category

We will not need this again, but we once promised to explain why V-categories, where V is a symmetric monoidal preorder, deserve to be seen as types of categories. The reason, as we have hinted, is that categories should really be called Set-categories. But wait, Set is not a preorder! We’ll have to generalize—categorify—V-categories.

We now give a rough definition of categories enriched in a symmetric monoidal category V. As in Definition 4.45, we suppress some technical parts in this sketch, hiding them under the name “usual associative and unital laws.”

Rough Definition: 4.51.

Let V be a symmetric monoidal category, as in Definition 4.45. To specify a category enriched in V, or a V-category, denoted X,

(i) one specifies a collection Ob(X), elements of which are called objects;

(ii) for every pair x, y \(\in\) Ob(X), one specifies an object X(x, y) \(\in\) V, called the hom-object for x, y;

(iii) for every x \(\in\) Ob(X), one specifies a morphism id\(_{x}\) : I → X(x, x) in V, called the identity element;

(iv) for each x, y, z \(\in\) Ob(X), one specifies a morphism ; : X(x, y) ⊗ X(y, z) → X(x, z), called the composition morphism.

These constituents are required to satisfy the usual associative and unital laws.

The precise, non-rough, definition can be found in other sources, e.g. [nLa18], [Wik18], [Kel05].

Exercise 4.52.

Recall from Example 4.49 that V = (Set, {1}, ×) is a symmetric monoidal category. This means we can apply Definition 4.51. Does the (rough) definition roughly agree with the definition of category given in Definition 3.6? Or is there a subtle difference? ♦

Remark 4.53. We first defined V-categories in Definition 2.46, where V was required to be a monoidal preorder. To check we’re not abusing our terms, it’s a good idea to make sure that V-categories as per Definition 2.46 are still V-categories as per Definition 4.51.

The first thing to observe is that every symmetric monoidal preorder is a symmetric monoidal category (Exercise 4.48). So given a symmetric monoidal preorder V, we can apply Definition 4.51. The required data (i) and (ii) then get us off to a good start: both definitions of V-category require objects and hom-objects, and they are specified in the same way. On the other hand, Definition 4.51 requires two additional pieces of data: (iii) identity elements and (iv) composition morphisms. Where do these come from?

In the case of preorders, there is at most one morphism between any two objects, so we do not need to choose an identity element and a composition morphism. Instead, we just need to make sure that an identity element and a composition morphism exist. This is exactly what properties (a) and (b) of Definition 2.46 say.

For example, the requirement (iii) that a V-category X has a chosen identity element idx : I → X(x, x) for the object x simply becomes the requirement (a) that I ≤ X(x, x) is true in V. This is typical of the story of categorification: what were mere properties in Definition 2.46 have become structures in Definition 4.51.

Exercise 4.54.

What are identity elements in Lawvere metric spaces (that is, Cost-categories)? How do we interpret this in terms of distances? ♦