## August 30, 2010

### 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:

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…

Posted at August 30, 2010 5:21 PM UTC

TrackBack URL for this Entry:   http://golem.ph.utexas.edu/cgi-bin/MT-3.0/dxy-tb.fcgi/2265

### 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.

Posted by: Mark Meckes on August 30, 2010 6:27 PM | Permalink | Reply to this

### Re: Enriching Over a Category of Subsets

Taking your last point first, I was aware of the Hamming metric (but had forgotten that that is what it’s called), as I’d come across it in areas like error-correcting codes, and I sort of hinted at it in my reference to DNA sequences. Originally I was going to make a big point about how enriching over subsets gives a refinement of the Hamming metric but as I was writing I discovered the more interesting (?) poset and continuous versions so forgot to make that point.

Your second point nicely illustrates my ignorance in the field of measure theory! I did not know what a measurable function was until I looked it up on wikipedia just now. It is now clear that “functions for which the preimage of an open set is measurable” is the kind of class of functions that I was trying to put my finger on and the class of measurable functions certainly fits the bill. I’m guessing that non-measurable functions on $[0,1]$ are pretty rare in the sense that I’m not likely to bump into them in my mathematical life very often.

Posted by: Simon Willerton on August 31, 2010 3:07 PM | Permalink | Reply to this

### Re: Enriching Over a Category of Subsets

I’m guessing that non-measurable functions on $[0,1]$ are pretty rare in the sense that I’m not likely to bump into them in my mathematical life very often.

Indeed. There’s a famous result (but not so famous that I haven’t forgotten who proved it) that there’s a model of ZF in which every subset of $[0,1]$ is Lebesgue measurable, and thus every real-valued function on $[0,1]$ is Lebesgue measurable. (That you can’t replace “Lebesgue” with “Borel” here follows from cardinality considerations, I think.) So non-Lebesgue measurable functions appear to be inherently nonconstructive beasts.

Here’s what I think is a nice way of thinking of your $d^\leq$. Think of the metric space as a state space. The metric measures how much “effort” it takes to change from one state to another. (I’m using “effort” instead of “work” to make it clear I don’t want to take any analogies with physics seriously.) I’ve heard this interpretation used to argue that the symmetry axiom for metric spaces is too restrictive: we all know empirically that it takes more effort to go up a hill than to come back down.*

The classical Hamming distance $d^=$ says that it takes a unit of effort to change the value of $f$ at an individual $x \in \Omega$, so the amount of effort to change $f$ into $g$ is just the number $x$s where $f$ and $g$ differ; if $\Omega$ is not discrete it’s standard to replace counting $x$s with a more general measure. Your $d^\leq$ says that to raise the value of $f(x)$ takes a unit of effort, but to let it fall down takes no effort at all.

Now from this viewpoint, it’s natural to say, wouldn’t a better model for many purposes take into account how much you change $f(x)$? Then you’re led to thinking about $d_1^\leq (f,g) = \int_\Omega \max \{ f(x)-g(x), 0 \} d\mu(x),$ whose symmetric version is just the $L^1(\Omega, \mu)$ metric. Turning this back around, does something like $d_1^\leq$ fit nicely into the enriched category framework?

*Come to think of it, the other aspects of Lawvere’s more general metric spaces are also natural from this point of view. If a distance is infinite, that means “you can’t get there from here”. If a distance is zero, that means you can effortlessly slip from one state to the other.

Posted by: Mark Meckes on August 31, 2010 3:53 PM | Permalink | Reply to this

### Re: Enriching Over a Category of Subsets

Somehow I overlooked this line in the original post:

For instance $Y(a,b)$ could be the minimum time, or the minimum cost required to travel from $a$ to $b$.

This of course already contains most of the philosophy in my comment above.

Posted by: Mark Meckes on August 31, 2010 4:02 PM | Permalink | Reply to this

### Re: Enriching Over a Category of Subsets

I wonder to what extent the types of enrichment being discussed here allow for forms of matrix mechanics. This requires a rig or perhaps rig category to let you ‘multiply’ along paths and ‘add’ across them. Shortest path/least action type situations come from having a rig where ‘add’ is taking the minimum. But you have genuine addition going on in quantum mechanics with $\mathbb{C}$.

I suppose in Hamming metric situations (example 1a) you take the union of sites of change as you transform one strand of DNA to another in a specific way, then you take the intersection of all such unions to find the least set of sites which need to be changed.

Posted by: David Corfield on September 1, 2010 8:35 AM | Permalink | Reply to this

### Re: Enriching Over a Category of Subsets

I don’t know the answer to your question David, but let me point out one difference between the category of extended non-negative reals $\mathbb{R}_+$ and the category of subsets $\mathcal{M}_X$.

The former, $\mathbb{R}_+$, has sum $+$ as the tensor product, minimum as the categorical coproduct and maximum as the categorical product. So this is not cartesian: the tensor product is not the categorical product.

The latter, $\mathcal{M}_X$, has union as the tensor product, intersection as the categorical coproduct and union (again) as the categorical product. So this is cartesian.

In this respect, at least, $\mathcal{M}_X$ seems to be more like $\mathbb{R}_{max}$ which is the category which ultra-metric spaces are enriched over – it’s the same as $\mathbb{R}_+$ except we take the tensor product to be the maximum.

Following this random train of thought, I don’t know if there are many useful lax monoidal functors $m\colon\mathcal{M}_X\to \mathbb{R}_+$ which would mean associating a non-negative real number to each subset of $X$ which satisfies

(1)$max(m(A),m(B))\ge m(A\union B).$

The class of examples that spring to mind are of the following form. If $f\colon X\to [0,\infty]$ is a function then define $m_f\colon\mathcal{M}_X\to \mathbb{R}_+$ by

$m_f(A)\coloneqq sup_{a\in A}(f(a)).$

This actually satisfies equality in (1).

Posted by: Simon Willerton on September 1, 2010 10:07 AM | Permalink | Reply to this

### Re: Enriching Over a Category of Subsets

If you were allowed some kind of average of $f$ over a set, then you could avoid equality.

Posted by: David Corfield on September 1, 2010 11:11 AM | Permalink | Reply to this

### Re: Enriching Over a Category of Subsets

I said

Then we can form a monoidal category $\mathcal{V}^X$ ([…] in fact this must be a standard construction)

In fact I guess it’s the same as the $V^X$ alluded to by Mike at the beginning of his recent monoidal fibrations post.

Posted by: Simon Willerton on September 1, 2010 11:05 PM | Permalink | Reply to this

### Re: Enriching Over a Category of Subsets

Then we can form a monoidal category $\mathcal{V}^X$ ([…] in fact this must be a standard construction)

It is a special case of the lax internal hom in $2Cat$:

think of the monoidal category $\mathcal{V}$ equivalently in tems of its (pointed) delooping 2-category $\mathbf{B}\mathcal{V}$. Then what you write $\mathcal{V}^X$ is given by

$\mathbf{B} (\mathcal{V}^X) = [X,\mathbf{B}\mathcal{V}] \,,$

where $[-,-]$ is the internal hom in $2Cat$ and where we regard the set $X$ as a discrete 2-category.

In fact I guess it’s the same as the $\mathcal{V}^X$ alluded to by Mike at the beginning of his recent monoidal fibrations post.

Looks like there he considers essentially the 2-Grothendieck construction of the 2-functor

$[-,\mathbf{B}\mathcal{V}] : Set^{op} \to 2Cat \,.$

Posted by: Urs Schreiber on September 2, 2010 10:33 AM | Permalink | Reply to this

### Re: Enriching Over a Category of Subsets

Actually, I find it more taxing to walk down the hill than up; you have to dissipate all that extra energy, and it’s not really clear how we’re supposed to do that! A NatGeog story about Mt. Everest climbers remarked that they have to budget at most a third of their energy (=> food and oxygen) for the ascent, or else they’re in trouble on the way down.

Posted by: some guy on the street on September 3, 2010 2:59 AM | Permalink | Reply to this

### Re: Enriching Over a Category of Subsets

Turning this back around, does something like $d^{\le}_1$ fit nicely into the enriched category framework?

Yes, I think it does. The key is to decide what structure on the codomain $\mathbb{R}$ we want to take into account.

1. We might want to think of it as just a set, so we only know if two points are equal. This is a certain kind of poset, so can be thought of as a category enriched over $\{0\le 1\}$.
2. We might want to think of it as an ordered set so we know when one point is less than or equal to another. Again this is a poset, so can be thought of as a category enriched over $\{0\le 1\}$.
3. We might want to think of it as a classical metric space with metric $d(a,b)=|b-a|$. This can be thought of as a category enriched over $\mathbb{R}_+$.
4. We might want to combine the order relation (2.) and the metric (3.), and the standard way to do this is to give it the asymmetric metric $D(a,b)\coloneqq max(b-a,0)$. [Aside: this gives the internal hom on $\mathbb{R}_+$.] Again this can be thought of as a category enriched over $\mathbb{R}_+$.

We can then do something along the following lines.

Suppose that $\mathcal{V}$ is a monoidal category and $X$ is a set. Then we can form a monoidal category $\mathcal{V}^X$ (maybe I’m over-using this notation and $\prod_X \mathcal{V}$ might be better, in fact this must be a standard construction) which has as objects the functions $X\to Ob(\mathcal{V})$ and the hom-sets are defined by

$\mathcal{V}^X(s,t)= \prod_X \mathcal{V}(s(x),t(x)).$

Composition and the tensor product are defined point-wise:

$\mathcal{V}^X(s,t)\times \mathcal{V}^X(t,r)\to \mathcal{V}^X(s,r)$

is the product of the maps

$\mathcal{V}(s(x),t(x))\times \mathcal{V}(t(x),r(x))\to \mathcal{V}(s(x),r(x));$

and if $s,t\colon X\to Ob(\mathcal{V})$ then $s\otimes t\colon X\to Ob(\mathcal{V})$ is defined by

$s\otimes t (x)\coloneqq s(x)\otimes t(x).$

In particular, if we take $\mathcal{V}=\{0\le 1\}$ then $\{0\le 1\}^X\cong \mathcal{M}_X$. (I think. I haven’t checked that all of my inequalities go the right way.) If we take $\mathcal{V}=\mathbb{R}_+$ then $(\mathbb{R}_+)^X$ is the poset of functions $X\to [0,\infty]$ ordered by $f\le g$ if and only if $f(x)\le g(x)$ for all $x$, together with the monoidal product being point-wise sum of functions.

Now if $Z$ is a $\mathcal{V}$-enriched category and $X$ is a set then there is $\mathcal{V}^X$-enriched category $Z^X$ whose objects are functions $X\to Ob(Z)$ and where the hom-objects are just done point-wise. The hom-object between functions $f,g:X\to Ob(Z)$ is supposed to be a function $X\to Ob(\mathcal{V})$, you take the “obvious” thing:

$Z^X(f,g)(x)\coloneqq Z(f(x),g(x)).$

So to make $Z^X$ into a metric space we need a lax monoidal functor $m\colon\mathcal{V}^X\to \mathbb{R}_+$. If $X$ is ‘big’ then we might want to restrict to some ‘measurable’ bits of $\mathcal{V}^X$ in order to define $m$.

If $X=[0,1]$ and $\mathcal{V}=\{0\le 1\}$ we can use the Lebesgue measure for our $m$ and for $X=[0,1]$ and $\mathcal{V}=\mathbb{R}_+$ we can use Lebesgue integration. From the four ways of considering $\mathbb{R}$ mentioned at the beginning we get the following four generalized metrics on the space of measurable functions $[0,1]\to \mathbb{R}$.

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

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

3. $d_1^{=}(f,g) = \int_{[0,1]} \mid g(x)-f(x)\mid\, d x$

4. $d_1^{\le}(f,g) = \int_{[0,1]} max\{g(x)-f(x),\,0\}\, d x$

I might have got the signs wrong in places.

Posted by: Simon Willerton on September 1, 2010 6:37 PM | Permalink | Reply to this

### Re: Enriching Over a Category of Subsets

Very nice, thanks. You seem to be using some font that I never got around to installing, and that hasn’t previously been used much in things I wanted to read. I’ll have to go sort that out now.

I wonder if there’s also a nice category-theoretic way to motivate the (or rather, a) $L^0(\Omega, \mu)$ metric. $L^0(\Omega, \mu)$ is the space of all measurable functions $f:\Omega \to \mathbb{R}$, with the topology of “convergence in measure”. This topology is generated, for example, by the metric $d_0(f,g) = \int_\Omega min(1,|f(x)-g(x)|) d\mu(x),$ though there may be other metrics which work better in this setting and generate the same topology.

(Note that the above discussion has elided the usual practice of only considering the $L^1$ metric, which we’re calling $d_1^=$, between measurable functions such that $\int |f| d\mu$ is finite. I guess since we’re allowing infinite distances there’s no need to do that in this setting, so that $L^0$ and $L^1$ are the same set for us, but with different topologies.)

Posted by: Mark Meckes on September 2, 2010 3:05 PM | Permalink | Reply to this

### Re: Enriching Over a Category of Subsets

the category of groups has hom-sets which naturally have the structure of groups

this is not true: it is true for abelian groups, but $Grp$ is enriched over groupoids.

Posted by: David Roberts on August 31, 2010 1:18 AM | Permalink | Reply to this

### Re: Enriching Over a Category of Subsets

I was going to say that, too. As David beat me to it, I’ll add a different typo:

… transitivity of equality: if $f(x)=g(x)$ or $g(x)=h(x)$ then $f(x)=h(x)$.

I think you mean “and”.

Posted by: Andrew Stacey on August 31, 2010 12:17 PM | Permalink | Reply to this

### Re: Enriching Over a Category of Subsets

Indeed, thanks. I had intended to alter that example to find a good example that wasn’t just something enriched over itself. But just mucked it up. Fixed now.

Actually there’s various subtleties there that I didn’t quite want to go into as I thought the post was getting long, but maybe I should have done.

• For the category of groups the hom-sets do form groups (unless I’m being stupid) and similarly for abelian groups.
• If you use the obvious cartesian product of groups or abelian groups then composition is not a group homomorphism in either case.
• If you use the tensor product of abelian groups then composition is a group homomorphism and the category of abelian group is enriched over itself.

This does lead to the question “Can anyone think of any categories enriched over (abelian) groups with the cartesian product?”

David, as I’m feeling slow today, could you give a hint as to how you enrich groups over groupoids?

Posted by: Simon Willerton on August 31, 2010 2:28 PM | Permalink | Reply to this

### Re: Enriching Over a Category of Subsets

For the category of groups the hom-sets do form groups

The problem in the nonabelian case is that what you’d like to be the inverse of a homomorphism $G \to H$ is actually a homomorphism $G \to H^{op}$ (unless you have a nonobvious multiplication $hom(G,H)$ in mind).

Posted by: Mark Meckes on August 31, 2010 3:59 PM | Permalink | Reply to this

### Re: Enriching Over a Category of Subsets

For the category of groups the hom-sets do form groups

The problem in the nonabelian case is that what you’d like to be the inverse of a homomorphism $G \to H$ is actually a homomorphism $G \to H^{op}$

That may not be the only problem, since the hom-sets for the category of monoids fail to be monoids.

It’s a question of interchange. If monoid homomorphisms $f, g: M \to N$ are multiplied using the pointwise definition,

$(f \cdot g)(x) = f(x)g(x),$

then $(f \cdot g)(x y) = f(x y)g(x y) = f(x)f(y)g(x)g(y)$, whereas $(f \cdot g)(x)(f \cdot g)(y) = f(x)g(x)f(y)g(y)$.

In particular, if $M$ is the free monoid on two generators, we can cook up $f$ and $g$ so that $f(x) = 1 = g(y)$ and $f(y)$, $g(x)$ are any two elements $a$, $b$ in $N$. If $f \cdot g$ is to be monoid homomorphism, we infer $a b = b a$ so that $N$ must be commutative for this to work.

Posted by: Todd Trimble on August 31, 2010 4:53 PM | Permalink | Reply to this

### Re: Enriching Over a Category of Subsets

Just to prove that my deductive powers are not completely off-kilter today, let me observe that what I wrote was completely correct.

For the category of groups the hom-sets do form groups (unless I’m being stupid)

Unfortunately, of the two alternatives, it was the “I’m being stupid” one that was true. Ooops. Thank you for the corrections.

Posted by: Simon Willerton on August 31, 2010 5:16 PM | Permalink | Reply to this

### Re: Enriching Over a Category of Subsets

could you give a hint as to how you enrich groups over groupoids?

Think of groups as connected groupoids.

Posted by: Urs Schreiber on August 31, 2010 4:35 PM | Permalink | Reply to this

### Re: Enriching Over a Category of Subsets

Take groups to be 1-element groupoids, and then functors between these groupoids are in bijection with homomorphisms. Then the arrows are given by elements of $G$ which act by conjugation: $k: g \mapsto k g k^{-1}$. This is just taking natural transformations between the groupoids and so this is secretly the usual enrichment of groupoids over themselves.

Posted by: David Roberts on August 31, 2010 10:37 PM | Permalink | Reply to this

### Re: Enriching Over a Category of Subsets

One thing I notice is that all the categories you are enriching over are Boolean algebras. So you might as well take complements, which turns all the joins into meets and removes all the negations from the definitions of the hom-objects.

Posted by: Richard Garner on September 1, 2010 2:38 PM | Permalink | Reply to this

### Re: Enriching Over a Category of Subsets

Which reminds me of another famous example of a category enriched in subsets of some given set: a presheaf or sheaf on a space $X$. In fact you need to be a bit more subtle to say this properly. You don’t have a single monoidal category of subsets that you are enriching over, but a whole indexed family of them over some base category $\mathcal{B}$.

More precisely, an indexed monoidal category over $\mathcal{B}$ is a pseudofunctor $\mathbf{V} \colon \mathcal{B}^{op} \to \mathbf{MonCat}$, where $\mathbf{MonCat}$ denotes the $2$-category of monoidal categories and lax monoidal functors. Recall that any lax monoidal functor $F \colon \mathcal{V} \to \mathcal{W}$ induces a functor $F_\ast \colon \mathcal{V}$-$\mathbf{Cat} \to \mathcal{W}$-$\mathbf{Cat}$.

Now a $\mathbf{V}$-enriched category $\mathbf{C}$ is given by a $\mathbf{V}(b)$-enriched category $\mathbf{C}_b$ for each $b \in \mathcal{B}$; a $\mathbf{V}(b)$-enriched functor $\mathbf{C}_f \colon \mathbf{V}(f)_{\ast}(\mathbf{C}_c) \to \mathbf{C}_b$ for each $f \colon b \to c$ in $\mathcal{B}$; and some $\mathbf{V}(b)$-natural isomorphisms expressing that the assignation $f \mapsto \mathbf{C}_f$ is pseudo-functorial in $f$.

So suppose we are given a space $X$. From it we define an indexed monoidal category as follows. Its base category $\mathcal{B}$ is $\mathcal{O}(X)$. The fibre $\mathbf{V}(U)$ is the monoidal category of open subsets of $U$, ordered by inclusion, and with intersection as the monoidal structure. At an morphism $i \colon U' \to U$ of $\mathcal{O}(X)$—which is just an inclusion—the functor $\mathbf{V}(i) \colon \mathbf{V}(U) \to \mathbf{V}(U')$ is given by $W \mapsto U' \cap W$.

Now any presheaf $F$ on $X$ gives a $\mathbf{V}$-enriched category $\mathbf{C}$. For $U \in \mathcal{O}(X)$, the $\mathbf{V}(U)$-category $\mathbf{C}_U$ has as objects, the elements of $F U$; and as hom-objects $\mathbf{C}_U(x,y)$, the largest $V \subset U$ for which $x \mid_V = y \mid_V$. At a morphism $i \colon U' \to U$ in $\mathcal{O}(X)$, the reindexing functor $\mathbf{V}(i)_{\ast}(\mathbf{C}_U) \to \mathbf{C}_{U'}$ sends $x \in \mathrm{ob } \mathbf{C}_U = F U$ to $x \mid_{U'} \in \mathrm{ob } \mathbf{C}_{U'} = F U'$. This presheaf is actually a sheaf precisely if it is Cauchy complete as a $\mathbf{V}$-enriched category.

This general approach to sheaves is also called the theory of $\mathcal{O}(X)$-valued sets, developed by Grayson and Fourman I think; it’s in the Elephant. The last point—concerning the Cauchy-complete things being the sheaves—is due to Bob Walters.

Posted by: Richard Garner on September 1, 2010 10:19 PM | Permalink | Reply to this

### Re: Enriching Over a Category of Subsets

That’s interesting. What’s the relationship between this construction and Walters’, where $\mathbf{C}$ is enriched over a bicategory built out of the underlying site?

Posted by: Finn Lawler on September 2, 2010 11:37 AM | Permalink | Reply to this

### Re: Enriching Over a Category of Subsets

Walters’ bicategory is actually a double category, and it is the result of a general construction that produces double categories from indexed monoidal categories (= monoidal fibrations), as here, applied to the indexed monoidal category that Richard described.

BTW, I think you can say something about the non-Cauchy complete objects, too, if you’re sufficiently careful. IIRC the 2-category of Cauchy-complete V-enriched categories is equivalent to the 1-category of sheaves on X, but the 2-category of not-necessarily-Cauchy-complete V-enriched categories is equivalent, not to the 1-category of presheaves, but to the 1-category of separated presheaves. However, to get the correct morphisms between non-Cauchy-complete objects you need to use enrichment over either an indexed monoidal category or over a double category (the two being equivalent when the double category is constructed from the indexed monoidal category) – mere enrichment over a bicategory doesn’t contain enough data.

It’s worth noting that this approach also generalizes to sheaves on arbitrary sites.

Posted by: Mike Shulman on September 3, 2010 8:43 AM | Permalink | Reply to this

### Re: Enriching Over a Category of Subsets

Cool, thanks. I remember wondering if Walters’s bicategory was actually a framed bicategory, as it’s built from spans, but I never got around to working it out. Do you know if this has been written up anywhere?

Posted by: Finn Lawler on September 3, 2010 6:28 PM | Permalink | Reply to this

### Re: Enriching Over a Category of Subsets

I think the original reference for comparing the span version with the indexed monoidal version is

On completeness of locally-internal categories

by Betti and Walters. (The indexed enriched categories have as a special case the “locally internal categories”, which are such categories where the indexed monoidal category one is enriching over is the codomain fibration of some category, equipped with the cartesian monoidal structure: such is in particular what we have in the sheaves example.)

Posted by: Richard Garner on September 4, 2010 10:11 AM | Permalink | Reply to this

### Re: Enriching Over a Category of Subsets

But I don’t know anywhere that the version for sheaves is written down. IIRC Betti+Walters only talk about the codomain fibration and spans, not general enrichment over indexed monoidal categories.

Posted by: Mike Shulman on September 4, 2010 11:07 PM | Permalink | Reply to this

### Re: Enriching Over a Category of Subsets

Actually, it occurs to me that there is yet another way of seeing sheaves on a space as things enriched over a category of subsets. Before I described how you can do this by being slightly subtle about what “enriched” should mean. Now I’ll describe how you can do it by being slightly subtle about what “set” means.

Suppose we’re given a space $X$, and consider the category $[\mathcal{O}(X)^{op}, \mathbf{Set}]$ of presheaves over $X$. This category is a topos, so we can think of its objects as sets. Because a topos has power objects, some of its objects we can think of as sets of subsets of other ones. So we can look at internal categories of subsets in $[\mathcal{O}(X)^{op}, \mathbf{Set}]$, and try and enrich over those.

It turns out that there is a particular internal category of subsets $\mathcal{V}$ in $[\mathcal{O}(X)^{op}, \mathbf{Set}]$ for which Cauchy-complete enriched categories are sheaves on $X$. The object of objects of this internal category is $\Omega_j \colon \mathcal{O}(X)^{op} \to \mathbf{Set}$, where $\Omega_j(U)$ is the set of all open subsets of $U$. It’s really an internal poset of course, and in fact a sub-poset of $\Omega = \mathcal{P}1$, the set of all subsets of $1$ in $[\mathcal{O}(X)^{op}, \mathbf{Set}]$. So we’re enriching over a category of subsets of $1$!

What is a category enriched over $\Omega_j$? Well, it’s a presheaf $X$ together with a map $X \times X \to \Omega_j$ which is going to send a pair $(x,y) \in X U$ to the largest $V \in \Omega_j(U)$ for which $x \mid_V = y \mid_V$, which you can see is already quite similar to the data I described above in the indexed-enriched setting. Again, the 2-category of (symmetric) $\Omega_j$-enriched categories in $[\mathcal{O}(X)^{op},\mathbf{Set}]$ will turn out to be equivalent to the category of separated presheaves on $X$.

The nice thing now is that (symmetric) Cauchy-complete $\Omega_j$-categories are once again the sheaves on $X$. Moreover, sheafification is visibly the same as Cauchy-completion: given an enriched category $X \times X \to \Omega_j$, you get the corresponding sheaf by considering the embedding $X \to \Omega_j^X$ (which is the Yoneda embedding) and then closing the image of $X$ in $\Omega_j^X$ under absolute colimits: in the internal logic, you look at the subobject of $\Omega_j^X$ comprising all those elements which the topos thinks are singletons.

(Note that all of this works in much greater generality than I’ve described here. $j$ can be any local operator on any topos, and $\Omega_j$ the corresponding closed subobject classifier; see A4.4 in the Elephant).

Posted by: Richard Garner on September 4, 2010 10:46 AM | Permalink | Reply to this

Post a New Comment