2.3: Enrichment

In this section we will introduce V-categories, where V is a symmetric monoidal preorder. We will see that Bool categories are preorders, and that Cost categories are a nice generalization of the notion of metric space.

V-categories

While V-categories can be defined even when V is not symmetric, i.e. just obeys conditions (a)–(c) of Definition 2.2, certain things don’t work quite right. For example, we will see later in Exercise 2.75 that the symmetry condition is necessary in order for products of V-categories to exist. Anyway, here’s the definition.

Definition: 2.46.

Let V = (V, ≤, I, ⊗) be a symmetric monoidal preorder. A V-category X consists of two constituents, satisfying two properties. To specify X,

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

(ii) for every two objects x, y, one specifies an element X(x, y) \(\in\) V, called the hom-object.\(^{2}\)

The above constituents are required to satisfy two properties:

(a) for every object x \(\in\) Ob(X) we have I ≤ X(x, x), and

(b) for every three objects x, y, z \(\in\) Ob(X), we have X(x, y) ⊗ X(y, z) ≤ X(x, z). We call V the base of the enrichment for X or say that X is enriched in V.

Example 2.47.

As we shall see in the next subsection, from every preorder we can construct a Bool-category, and vice versa. So, to get a feel for V-categories, let us consider the preorder generated by the Hasse diagram:

How does this correspond to a Bool-category X? Well, the objects of X are simply the elements of the preorder, i.e. Ob(X) = {p, q, r, s, t}. Next, for every pair of objects (x, y) we need an element of \(\mathbb{B}\) = {false, true}: simply take true if x ≤ y, and false if otherwise. So for example, since s ≤ t and t \(\nleq\) s, we have X(s, t) = true and X(t, s) = false. Recalling from Example 2.27 that the monoidal unit I of Bool is true, it’s straightforward to check that this obeys both (a) and (b), so we have a Bool-category.

In general, it’s sometimes convenient to represent a V-category X with a square matrix. The rows and columns of the matrix correspond to the objects of X, and the (x, y)th entry is simply the hom-object X(x, y). So, for example, the above preorder in Eq. (2.48) can be represented by the matrix

Preorders as Bool-categories

Our colleague Peter Gates has called category theory “a primordial ooze,” because so much of it can be defined in terms of other parts of it. There is nowhere to rightly call the beginning, because that beginning can be defined in terms of something else. So be it; this is part of the fun.

Theorm 2.49.

There is a one-to-one correspondence between preorders and Bool-categories.

Here we find ourselves in the ooze, because we are saying that preorders are the same as Bool-categories, whereas Bool is itself a preorder. “So then Bool is like... enriched in itself?” Yes, every preorder, including Bool, is enriched in Bool, as we will now see. Proof of Theorem 2.49. Let’s check that we can construct a preorder from any Bool- category. Since \(\mathbb{B}\) = {false, true}, Definition 2.46 says a Bool-category consists of two things:

(i) a set Ob(X), and

(ii) for every x, y \(\in\) Ob(X) an element X(x, y) \(\in\) B, i.e. either X(x, y) = true or X(x, y) = false.

We will use these two things to begin forming a preorder whose elements are the objects of X. So let’s call the preorder (X, ≤), and let X = Ob(X). For the ≤ relation, let’s declare x ≤ y iff X(x, y) = true. We have the makings of a preorder, but for it to work, the ≤ relation must be reflexive and transitive. Let’s see if we get these from the properties guaranteed by Definition 2.46:

(a) for every element x \(\in\) X we have true ≤ X(x, x),

(b) for every three elements x, y, z \(\in\) X we have X(x, y) \(\wedge\) X(y, z) ≤ X(x, z).
For b \(\in\) Bool, if true ≤ b then b = true, so the first statement says X(x, x) = true, which means x ≤ x. For the second statement, one can consult Eq. (2.28). Since false ≤ b for all b \(\in\) B, the only way statement (b) has any force is if X(x, y) = true and X(y, z) = true, in which case it forces X(x, z) = true. This condition exactly translates as saying that x ≤ y and y ≤ z implies x ≤ z. Thus we have obtained reflexivity and transitivity from the two axioms of Bool-categories.

In Example 2.47, we constructed a Bool-category from a preorder. We leave it to the reader to generalize this example and show that the two constructions are inverses; see Exercise 2.50.

Example 2.50.

1. Start with a preorder (P, ≤), and use it to define a Bool-category as we did in Example 2.47. In the proof of Theorem 2.49 we showed how to turn that Bool-category back into a preorder. Show that doing so, you get the preorder you started with.
2. Similarly, show that if you turn a Bool-category into a preorder using the above proof, and then turn the preorder back into a Bool-category using your method, you get the Bool-category you started with. ♦

We now discuss a beautiful application of the notion of enriched categories: metric spaces.

Lawvere metric spaces

Metric spaces offer a precise way to describe spaces of points, each pair of which is separated by some distance. Here is the usual definition:

Definition: 2.51.

A metric space (X, d) consists of:

(i) a set X, elements of which are called points, and

(ii) a function d : X × X → \(\mathbb{R}\)\(_≥0\), where d(x, y) is called the distance between x and y

These constituents must satisfy four properties:

(a) for every x \(\in\) X, we have d(x,x) = 0,
(b) for every x, y \(\in\) X, if d(x,y) = 0 then x = y,

(c) for every x, y \(\in\) X, we have d(x,y) = d(y,x),and
(d) for every x, y, z \(\in\) X, we have d(x,y)+d(y,z) ≥ d(x,z).

The fourth property is called the triangle inequality.
If we ask instead in (ii) for a function d : X × X → [0, ∞] = \(\mathbb{R}\)\(_{≥0}\) \(\cup\) {∞}, we call (X, d) an extended metric space.

The triangle inequality says that when plotting a route from x to z, the distance is always at most what you get by choosing an intermediate point y and going

x → y → z.

It can be invoked three different ways in the above picture: 3 + 5 ≥ 7.2, but also 5 + 7.2 ≥ 3 and 3 + 7.2 ≥ 5. Oh yeah, and 5 + 3 ≥ 7.2, 7.2 + 5 ≥ 3 and 7.2 + 3 ≥ 5.

The triangle inequality wonderfully captures something about distance, as does the fact that d(x, x) = 0 for any x. However, the other two conditions are not quite as general as we would like. Indeed, there are many examples of things that “should” be metric spaces, but which do not satisfy conditions (b) or (c) of Definition 2.51.

For example, what if we take X to be places in your neighborhood, but instead of measuring distance, you want d(x, y) to measure effort to get from x to y. Then if there are any hills, the symmetry axiom, d(x, y) =\(^{?}\) d(y, x), fails: it’s easier to get from x downhill to y then to go from y uphill to x.

Another way to find a model that breaks the symmetry axiom is to imagine that the elements of X are not points, but whole regions such as the US, Spain, and Boston. Say that the distance from region A to region B is understood using the setup “I will put you in an arbitrary part of A and you just have to get anywhere in B; what is the distance in the worst-case scenario?” So d(US, Spain) is the distance from somewhere in the western US to the western tip of Spain: you just have to get into Spain, but you start in the worst possible part of the US for doing so.

Example 2.52.

Which distance is bigger under the above description, d(Spain, US) or d(US, Spain)? ♦

This notion of distance, which is strongly related to something called Hausdorff distance,\(^{3}\) will again satisfy the triangle inequality, but it violates the symmetry condition. It also violates another condition, because d(Boston, US) = 0. No matter where you are in Boston, the distance to the nearest point of the US is 0. On the other hand, d(US, Boston) \(\neq\) 0.

Finally, one can imagine a use for distances that are not finite. In terms of my effort, the distance from here to Pluto is ∞, and it would not be any better if Pluto was still a planet. Similarly, in terms of Hausdorff distance, discussed above, the distance between two regions is often infinite, e.g. the distance between {r \(\in\) \(\mathbb{R}\) | r < 0} and {0} as subsets of (\(\mathbb{R}\), d) is infinite.

When we drop conditions (b) and (c) and allow for infinite distances, we get the fol- lowing relaxed notion of metric space, first proposed by Lawvere. Recall the symmetric monoidal preorder Cost = ([0, ∞], ≥, 0, +) from Example 2.37.

Definition: 2.53.

A Lawvere metric space is a Cost-category.

This is a very compact definition, but it packs a punch. Let’s work out what it means,

by relating it to the usual definition of metric space. By Definition 2.46, a Cost-category X consists of:

(i) a set Ob(X),
(ii) for every x, y \(\in\) Ob(X) an element X(x, y) \(\in\) [0, ∞].

Here the set Ob(X) is playing the role of the set of points, and X(x, y) \(\in\) [0, ∞] is playing the role of distance, so let’s write a little translator:

X := Ob(X) d(x, y) := X(x, y).

The properties of a category enriched in Cost are: (a) 0 ≥ d(x,x) for all x \(\in\) X, and
(b) d(x,y) + d(y,z) ≥ d(x,z) for all x, y, z \(\in\) X.

Since d(x, x) \(\in\) [0, ∞], if 0 ≥ d(x, x) then d(x, x) = 0. So the first condition is equivalent to the first condition from Definition 2.51, namely d(x, x) = 0. The second condition is the triangle inequality.

Example 2.54.

The set \(\mathbb{R}\) of real numbers can be given a metric space structure, and hence a Lawvere metric space structure. Namely d(x, y) := |y − x|, the absolute value of the difference. So d(3, 7) = 4.

Exercise 2.55.

Consider the symmetric monoidal preorder (\(\mathbb{R}_{≥0}\), ≥, 0, +), which is almost the same as Cost, except it does not include ∞. How would you characterize the difference between a Lawvere metric space and a (\(\mathbb{R}_{≥0}\), ≥, 0, +)-category in the sense of Definition 2.46?♦

Presenting metric spaces with weighted graphs Just as one can convert a Hasse diagram into a preorder, one can convert any weighted graph a graph whose edges are labeled with numbers w ≥ 0 into a Lawvere metric space. In fact, we shall consider these as graphs labelled with elements of [0, ∞], and more precisely call them Cost-weighted graphs.\(^{4}\)

One might think of a Cost-weighted graph as describing a city with some one-way roads (a two-way road is modeled as two one-way roads), each having some effort-to- traverse, which for simplicity we just call length. For example, consider the following weighted graphs:

Given a weighted graph, one forms a metric \(d_{X}\) on its set X of vertices by setting d(p, q) to be the length of the shortest path from p to q. For example, here is the the table of distances for Y

Exercise 2.58.

Fill out the following table of distances in the weighted graph X from Eq. (2.56)

Above we converted a weighted graph G, e.g. as shown in Eq. (2.56), into a table of distances, but this takes a bit of thinking. There is a more direct construction for taking G and getting a square matrix MG, whose rows and columns are indexed by the vertices of G. To do so, set MG to be 0 along the diagonal, to be ∞ wherever an edge is missing, and to be the edge weight if there is an edge.

For example, the matrix associated to Y in Eq. (2.56) would be

As soon as you see how we did this, you’ll understand that it takes no thinking to turn a weighted graph G into a matrix MG in this way. We will see later in Section 2.5.3 that the more difficult “distance matrices” dY, such as Eq. (2.57), can be obtained from the easy graph matrices MY, such as Eq. (2.59), by repeating a certain sort of “matrix multiplication.”

Exercise 2.60.

Fill out the matrix MX associated to the graph X in Eq. (2.56):

V-variations on preorders and metric spaces

We have told the story of Bool and Cost. But in Section 2.2.4 we gave examples of many other monoidal preorders, and each one serves as the base of enrichment for a kind of enriched category. Which of them are useful? Something only becomes useful when someone finds a use for it. We will find uses for some and not others, though we encourage readers to think about what it would mean to enrich in the various monoidal categories discussed above; maybe they can find a use we have not explored.

Exercise 2.61.

Recall the monoidal preorder NMY := (P, ≤, yes, min) from Exercise 2.34. Interpret what a NMY-category is ♦

next two exercises, we use V-weighted graphs to construct V-categories. This is possible because we will use preorders that, like Bool and Cost, have joins.

Exercise 2.62.

Let M be a set and let M := (P(M), \(\subseteq\), M, \(\cap\)) be the monoidal preorder whose elements are subsets of M.

Someone gives the following interpretation, “for any set M, imagine it as the set of modes of transportation (e.g. car, boat, foot). Then an M-category X tells you all the modes that will get you from a all the way to b, for any two points a, b \(\in\) Ob(X).”

1. Draw a graph with four vertices and four or five edges, each labeled with a subset of M = {car, boat, foot}.
2. From this graph is it possible to construct an M-category, where the hom-object from x to y is computed as follows: for each path p from x to y, take the intersection of the sets labelling the edges in p. Then, take the union of the these sets over all paths p from x to y. Write out the corresponding four-by-four matrix of hom-objects, and convince yourself that this is indeed an M-category.
3. Does the person’s interpretation look right, or is it subtly mistaken somehow? ♦

Exercise 2.63.

Consider the monoidal preorder W := (\(\mathbb{N}\) \(\cup\) {∞}, ≤, ∞, min).

1. Draw a small graph labeled by elements of N \(\cup\) {∞}.
2. Write out the matrix whose rows and columns are indexed by the nodes in the
3. graph, and whose (x, y)th entry is given by the maximum over all paths p from x
4. to y of the minimum edge label in p.
5. Prove that this matrix is the matrix of hom-objects for a W-category. This will
6. give you a feel for how W works.
7. Make up an interpretation, like that in Exercise 2.62, for how to imagine enrichment in W. ♦