### Enriching Over a Category of Subsets

#### Posted by Simon Willerton

Several of us here at the Café are fans of Lawvere’s paper on enriched categories:

- Metric spaces, generalized logic, and closed categories, FW Lawvere, Republished in: Reprints in Theory and Applications of Categories, No. 1 (2002) pp 1-37.

What I would like do here is expand on a part of the paper that I haven’t seen mentioned elsewhere, although I haven’t looked very hard, about enriching over a category of subsets of some fixed set. I will show how this leads, for instance, to the following generalized metric on the set of continuous functions $[0,1]\to \mathbb{R}$, where $\mu$ means the Lebesgue measure:

$d^\le(f,g)\coloneqq\mu\{x\in[0,1]\mid f(x)\gt g(x)\}.$

It also leads to the following symmetrized version which is a metric in the classical sense:

$d^=(f,g)\coloneqq\mu\{x\in[0,1]\mid f(x)\neq g(x)\}.$

I would be interested to hear if anyone has any other examples of categories enriched over subsets of some set.

I will start with a brief introduction to enriched categories for those who aren’t so regular round here – the rest of you can skip to the following section.

## Enriched categories and metric spaces

I never realised that enriched categories were so much fun until I read the paper of Lawvere and saw that the enriching category did not have to be concrete. Let me ‘remind’ you what that means.

You can try to imagine discovering enriched category theory after noticing that in many categories the hom-sets have extra structure. For instance, the category of representations of a fixed group has hom-sets which naturally have the structure of vector spaces, the category of abelian groups has hom-sets which naturally have the structure of abelian groups and the category of smooth surfaces and diffeomorphisms has hom-sets which naturally have the structure of topological spaces; furthermore in these cases the composition map respects this extra structure in some sense, so it is a bilinear map, a ‘bilinear’ group homomorphism and a continuous map respectively in the previous three examples. We can say that the hom-sets are ‘enriched’ or indeed that the category is enriched. This leads us to attempt to formalize this situation and we come up with the following.

We suppose that $\mathcal{V}$ is a category of “sets with extra structure” which has a monoidal product $\otimes$ and a monoidal unit $\mathbf{1}$, and that now our “hom-sets” will live in $\mathcal{V}$ rather than in the category of sets. So a “category enriched in $\mathcal{V}$”, which we will call $\mathcal{C}$, will consist of a set of objects $Ob(\mathcal{C})$ and the following data. (Although I don’t think this would have been anyone’s first guess!)

- For every pair $a,b\in Ob(\mathcal{C})$ there is a set with structure $\mathcal{C}(a,b)\in Ob(\mathcal{V})$.
- For every triple $a,b,c\in Ob(\mathcal{C})$ there is a morphism in $\mathcal{V}$ giving composition: $\mathcal{C}(b,c)\otimes \mathcal{C}(a,b)\to \mathcal{C}(a,c)$.
- For each object $a\in Ob(\mathcal{C})$ there is an identity given by a morphism in $\mathcal{V}$ from the unit object: $\mathbf{1}\to \mathcal{C}(a,a)$.

This data has to satisfy appropriate associativity and the identity conditions which I won’t write down, but which you can find at the nlab.

This allows us to talk about categories enriched over vector spaces or abelian groups or topological spaces by choosing $\mathcal{V}$ appropriately. But it also allows us to do much more. The phrase “sets with extra structure” was an absolute red herring. The definition does not mention the *elements* of any hom-set: so we can define categories enriched over an any monoidal category. One potential problem with doing that is that we can no longer talk about morphisms in the enriching category: we can only talk about the $\mathcal{V}$-object $\mathcal{C}(a,b)$ which might not have any elements. Let’s look at a standard example of a non-concrete enriching category.

The classic example, due to Lawvere, is where we consider $\mathcal{V}$ to be the monoidal category $(\mathbb{R}_{+}, +, 0)$ which has the extended non-negative real numbers $[0,\infty]$ as its set of objects and a single morphism from $a$ to $b$ if $a\ge b$ (so this is $[0,\infty]$ with the opposite of the usual poset structure considered by category theorists). The monoidal product is the sum $+$ of real numbers and thus the monoidal unit is $0$.

Unpacking the definition, a category $Y$ enriched over $\mathbb{R}_+$ consists of a set $Ob(Y)$ with a number $Y(a,b)\in [0,\infty]$ associated to each pair $(a,b)$ of objects. The existence of composition and identity morphisms means precisely that there are inequalities

$Y(b,c)+Y(a,b)\ge Y(a,c)\qquad and \qquad 0\ge Y(a,a).$

The first inequality is the triangle inequality and the second is more simply written as $Y(a,a)=0$. The associativity and identity conditions turn out to be vacuous in this case.

This means that any classical metric space gives rise to such an $\mathbb{R}_+$-enriched category with the objects being the points of the space and $Y(a,b)$ being the distance between $a$ and $b$.

However, not every $\mathbb{R}_+$-enriched category arises from a classical metric space because there are three differences.

- The “distances” $Y(a,b)$ can be infinite.
- Symmetry is not imposed, so we could have $Y(a,b)\ne Y(b,a)$.
- There can be zero “distance” between different points, so $Y(a,b)=0$ does not necessarily imply $a=b$.

None-the-less, it is not difficult to come up with examples which show that this more general notion of metric space is very natural. For instance $Y(a,b)$ could be the minimum time, or the minimum cost required to travel from $a$ to $b$.

This means that the theory of metric spaces is to some extent subsumed by the theory of enriched categories. Read on for some more examples.

## Enriching over a set of subsets

Now another class of examples of monoidal categories to enrich over that Lawvere gives is the following. Suppose that $X$ is set. Let $\mathcal{M}$ be some set of subsets of $X$ which contains the empty set and is closed under disjoint union: put the order on $\mathcal{M}$ which is given by supersets. So we get a category whose objects are subsets of $X$ contained in $\mathcal{M}$ and where there is a morphism $A\to B$ if $A\supseteq B$ (this is the opposite of the usual poset structure on the set of subsets of a set). The monoidal product of two subsets is defined to be their union and the unit of the monoidal structure is therefore the empty set.

One example, which we will call $\mathcal{M}_X$, is when we take *all* subsets of $X$. This is very well behaved when $X$ is finite, for larger sets, with extra structure such as a topology or a measure, we could consider the set of open sets or the set of measurable sets.

## Examples

The only example of a category enriched over such a category of subsets that Lawvere gives is Example 3 below – and this is the category $\mathcal{M}_X$ enriched over itself – so I thought I would try to come up with some other examples. I would be interested to hear of any other examples, in particular categories that are not based on the set of functions on $X$.

### Example 1a

This is the first example that sprang to mind. For $X$ a set, $\mathcal{M}_X$ the category of all subsets of $X$ and $Z$, a set define the $\mathcal{M}_X$-enriched category $Z^X$ to have as its objects the set of functions $X\to Z$ and to have as the hom-object (or the difference, or the distance) between functions $f\colon X\to Z$ and $g\colon X\to Z$ the set of points in $X$ at which $f$ and $g$ differ:

$Z^X(f,g)\coloneqq \{x\in X \mid f(x)\neq g(x)\}$

(For some reason, the example that comes to mind here is when $f$ and $g$ represent two strands of DNA with $X$ being the set of sites and $Z$ being the set of nucleotides $\{G, T, C, A\}$.)

This “has composition”

$Z^X(g,h) \,\cup\, Z^X(f,g)\supseteq Z^X(f,h)$

because if $f(x)\neq h(x)$ then either $f(x)\neq g(x)$ or $g(x)\neq h(x)$. This is the contrapositve of, and hence equivalent to, the usual transitivity of equality: if $f(x) = g(x)$ and $g(x) = h(x)$ then $f(x)=h(x)$. Actually in this case it might be better to call this *decomposition* rather than composition, because rather than saying given a morphism in $Z^X(a,b)$ and a morphism in $Z^X(b,c)$ you get a morphism in $Z^X(a,c)$, it says that given a morphism in the latter, $Z^X(a,c)$ it must be in one of the former, namely $Z^X(a,b)$ or $Z^X(b,c)$.

The ‘existence of an identity’ for $f$ is

$Z^X(f,f)=\emptyset$

which just says that $f$ agrees with itself everywhere.

### Example 1b

In this slight modification of the above example we can take $X$ to be the interval $[0,1]$ and consider the category $\mathcal{M}_{meas}$ consisting of *Lebesgue measurable* subsets of $[0,1]$. Then we can define $C_{[0,1]}$ to be the $M_{meas}$-enriched category where the objects are the *continuous* functions $[0,1]\to \mathbb{R}$ and the distance from $f$ to $g$ is given by the set of points at which they differ.

$C_{[0,1]}(f,g)\coloneqq \{x\in [0,1] \mid f(x)\neq g(x)\}$

We have $C_{[0,1]}(f,g)\in Ob(\mathcal{M}_{meas})$ because as $f$ and $g$ are continuous, the set of points at which they differ is an open set and hence Lebesgue measurable (that’s a basic piece of measure theory that look me a while to figure out). This gives rise to an enriched category for the same reasons as in Example 1a.

There are possibly other classes of functions which would give rise to measurable sets in this way, but my analysis is maybe not up to the job of figuring it out.

### Example 2

Another example is if we take $\overline\mathcal{M}^{sym}_X$ which will have the same set of objects as $\mathcal{M}_X$, i.e., the set of all subsets of $X$ and the hom-object between subsets $A\subset X$ and $B\subset X$ is defined to be their symmetric difference:

$\overline\mathcal{M}^{sym}_X(A,B)\coloneqq(A\cup B)\setminus( A\cap B).$

The astute amongst you will be thinking two things at this point.

- “Ah! That this is just the same as Example 1a where we take $Z$ to be a two element set.”
- “Hmmm. We’re taking the
*symmetric*difference. We know that generalized notions of difference don’t have to be symmetric, and there is clearly a natural non-symmetric way to do this.”

The latter thought leads us to our next example.

### Example 3

We can make $\mathcal{M}_X$ the set of all subsets of $X$ into a category enriched over itself. That’s a slightly confusing to say – how can $\overline\mathcal{M}_X$ be an ordinary category *and* an $\mathcal{M}_X$-enriched category? – but it what folks say. To try to reduce confusion I’ll use $\overline\mathcal{M}_X$ to denote the enriched version. We take the distance, or hom-object between two subsets to be the set-theoretic difference.

$\overline\mathcal{M}_X(A,B)\coloneqq B\setminus A$

So you can think that to get from $A$ to $B$ you have to pick an element of $B$ that you don’t already have in $A$.

The key reason this is a self-enrichment, if you know about such things, is that there is the relation

$\mathcal{M}_X(A\cup B,C)=\mathcal{M}_X(A,C\setminus B),$

or, in other words,

$A\cup B \supseteq C \quad\Longleftrightarrow \quad A\supseteq C\setminus B.$

This means that the underlying category (see below) of the enriched category $\overline\mathcal{M}_X$ is the ordinary category $\mathcal{M}_X$.

### Example 4a

We can now generalize Examples 1a, 2 and 3. Suppose that $(P,{}\le{})$ is a preorder, i.e., $P$ is a set and $\le$ is a transitive and reflexive relation. Define $P^X$ to be the category enriched over $\mathcal{M}_X$ which has the set of functions $\{f \colon X\to P\}$ as its objects and the hom-object, or distance, from $f$ to $g$ is defined to be the set of points where $g$ does not dominate $f$:

$P^X(f,g)\coloneqq \{x\in X \mid f(x)\nleq g(x)\}.$

Just as in Example 1a above, the “composition”

$P^X(f,g) \union P^X(g,h)\supseteq P^X(f,h)$

comes precisely from the contrapositive of the transitivity of the order relation $\le$.

Example 1a is obtained by taking the trivial preorder on $Z$, by which I mean the preorder $\le$ is precisely equality $=$. Example 3 is obtained by taking the preorder $\{0\le1\}$ – you might need to think for a minute why that is true.

### Example 4b

We can do a similar thing to the previous example, but in the vein of Example 1b using the standard order $\le$ on the real numbers $\mathbb{R}$. We obtain a category, which I’ll call $C^\le_{[0,1]}$, enriched over $\mathcal{M}_{meas}$, the measurable subsets of the interval $[0,1]$, whose objects are continuous functions $f\colon [0,1]\to \mathbb{R}$ and whose distances are given by

$C^\le_{[0,1]}(f,g)\coloneqq \{x\in [0,1] \mid f(x)\gt g(x)\}.$

(Note that as we have a linear order $\gt$ is the same as $\nleq$.) Just as in Example 1b these are open subsets of $[0,1]$, thus Lebesgue measurable and hence objects in $\mathcal{M}_{meas}$.

## Lax monoidal functors and change of basis

Now let’s return to another chunk of general enriched category theory. If we have monoidal categories $\mathcal{V}$ and $\mathcal{W}$ and a *lax* monoidal functor (see below) $\alpha\colon \mathcal{V}\to \mathcal{W}$ then we get a way of obtaining a $\mathcal{W}$-category $\alpha\mathcal{C}$ from a $\mathcal{V}$-category $\mathcal{C}$. This has the same set of objects as $\mathcal{C}$ but the hom-object from $a$ to $b$ is, perhaps not unsurprisingly, $\alpha \mathcal{C}(a,b)$.

Recall that a functor $\alpha\colon \mathcal{V}\to\mathcal{W}$ between monoidal categories is lax monoidal when there are natural morphisms for each $a$ and $b$

$\alpha(a)\otimes \alpha(b)\to \alpha(a\otimes b); \qquad \mathbf{1}_\mathcal{V}\to \alpha(\mathbf{1}_\mathcal{V})$

satisfying appropriate conditions.

For example, every monoidal category $\mathcal{V}$ comes equipped with a lax monoidal functor $\Gamma\colon \mathcal{V}\to Set$ which is the “global elements” or “sections” functor

$\Gamma({-})\coloneqq \mathcal{V}(\mathbf{1},{-})$

Given a $\mathcal{V}$-category $\mathcal{C}$ the resulting ordinary category $\Gamma\mathcal{C}$ is referred to as the underlying category of $\mathcal{C}$.

In the case of a generalized metric space the underlying category is a preorder structure on the points in the space and the preorder is defined by $a\le b$ if and only if $d(a,b)=0$; similarly in the case of a category enriched over $\mathcal{M}_X$ the underlying category is a preorder on the objects of the enriched category and the preorder is defined by $a\le b$ if and only if $\mathcal{C}(a,b)=\emptyset$.

## Generalized metric spaces from subset-enriched categories

How about changing a $\mathcal{M}$-category into a generalized metric space? Clearly, one way to do this would be to have a lax monoidal functor $\mathcal{M}\to \mathbb{R}_+$ which would mean having an association of a non-negative number to each subset of $X$ in $\mathcal{M}$ which satisfies

$m(A)+m(B)\ge m(A\cup B)\quad and \quad 0\ge m(\emptyset)$

the other conditions turn out to be vacuous. In other words we require an *outer measure* on $X$, or at least on the subsets of $X$ which lie in $\mathcal{M}$.

If $X$ is finite then there is the obvious counting measure or “number of elements”

$\#\colon \mathcal{M}_X\to \mathbb{R}_+$

which, for any set $Z$, gives rise to the metric space structure $\# Z^X$ on the set of function $X\to Z$, given on a pair of functions by counting the number of places at which they differ:

$d(f,g)\coloneqq \#\{x\in X \mid f(x)\neq g(x)\}.$

When $X$ is the interval $[0,1]$ there is the Lebesgue measure

$\mu\colon \mathcal{M}_{meas}\to \mathbb{R}_+.$

By applying this to our two $\mathcal{M}_{meas}$-categories $C_{[0,1]}$ and $C^\le_{[0,1]}$ we get two generalized metric space structures on the set of continuous functions $[0,1]\to \mathbb{R}_+$, namely the two mentioned in the introduction above:

$d^\le(f,g)\coloneqq\mu\{x\in[0,1]\mid f(x)\gt g(x)\}$

and

$d^=(f,g)\coloneqq\mu\{x\in[0,1]\mid f(x)\neq g(x)\}.$

Inadvertently I have managed to combine two themes that Tom has been writing about recently, namely enriched categories and measures. Of course I could also have done this by talking about the magnitude of measure spaces, but that’s another story…

## Re: Enriching Over a Category of Subsets

Regarding Example 1b, you can generalize quite a lot. Suppose $(\Omega, \mathcal{F})$ is any measurable space. Then measurability of functions $f:\Omega \to \mathbb{R}$, with respect to the Borel $\sigma$-algebra on $\mathbb{R}$, is preserved by linear combinations, and so $\{ x \in \Omega \mid f(x) \neq g(x) \} = \{ x \in \Omega \mid f(x)-g(x) \neq 0 \}$ is a measurable set. (Lebesgue measurable functions are measurable with respect to the Lebesgue $\sigma$-algebra on the domain and the

Borel$\sigma$-algebra on the codomain, so your setup really is a special case of this.)Jumping down to the end of the post, when $\Omega$ is a finite set and $\mu$ is the counting measure, the metric $d^= (f,g) = \mu \{ x\in \Omega \mid f(x) \neq g(x) \}$ is often called the

Hamming metric, and is well known in discrete math. It’s used, for example, to metrize the symmetric group $S_n$. I bet $d^\leq$ has been used in the same context as well, maybe in a more or less implicit way, though I can’t think of any examples off the top of my head.