Skip to the Main Content

Note:These pages make extensive use of the latest XHTML and CSS Standards. They ought to look great in any standards-compliant modern browser. Unfortunately, they will probably look horrible in older browsers, like Netscape 4.x and IE 4.x. Moreover, many posts use MathML, which is, currently only supported in Mozilla. My best suggestion (and you will thank me when surfing an ever-increasing number of sites on the web which have been crafted to use the new standards) is to upgrade to the latest version of your browser. If that's not possible, consider moving to the Standards-compliant and open-source Mozilla browser.

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][0,1]\to \mathbb{R}, where μ\mu means the Lebesgue measure:

d (f,g)μ{x[0,1]f(x)>g(x)}.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)μ{x[0,1]f(x)g(x)}.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 1\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(𝒞)Ob(\mathcal{C}) and the following data. (Although I don’t think this would have been anyone’s first guess!)

  • For every pair a,bOb(𝒞)a,b\in Ob(\mathcal{C}) there is a set with structure 𝒞(a,b)Ob(𝒱)\mathcal{C}(a,b)\in Ob(\mathcal{V}).
  • For every triple a,b,cOb(𝒞)a,b,c\in Ob(\mathcal{C}) there is a morphism in 𝒱\mathcal{V} giving composition: 𝒞(b,c)𝒞(a,b)𝒞(a,c)\mathcal{C}(b,c)\otimes \mathcal{C}(a,b)\to \mathcal{C}(a,c).
  • For each object aOb(𝒞)a\in Ob(\mathcal{C}) there is an identity given by a morphism in 𝒱\mathcal{V} from the unit object: 1𝒞(a,a)\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 𝒞(a,b)\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 ( +,+,0)(\mathbb{R}_{+}, +, 0) which has the extended non-negative real numbers [0,][0,\infty] as its set of objects and a single morphism from aa to bb if aba\ge b (so this is [0,][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 00.

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

Y(b,c)+Y(a,b)Y(a,c)and0Y(a,a).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)=0Y(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)Y(a,b) being the distance between aa and bb.

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

  • The “distances” Y(a,b)Y(a,b) can be infinite.
  • Symmetry is not imposed, so we could have Y(a,b)Y(b,a)Y(a,b)\ne Y(b,a).
  • There can be zero “distance” between different points, so Y(a,b)=0Y(a,b)=0 does not necessarily imply a=ba=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)Y(a,b) could be the minimum time, or the minimum cost required to travel from aa to bb.

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 XX is set. Let \mathcal{M} be some set of subsets of XX 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 XX contained in \mathcal{M} and where there is a morphism ABA\to B if ABA\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 X\mathcal{M}_X, is when we take all subsets of XX. This is very well behaved when XX 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 X\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 XX.

Example 1a

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

Z X(f,g){xXf(x)g(x)}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 ff and gg represent two strands of DNA with XX being the set of sites and ZZ being the set of nucleotides {G,T,C,A}\{G, T, C, A\}.)

This “has composition”

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

because if f(x)h(x)f(x)\neq h(x) then either f(x)g(x)f(x)\neq g(x) or g(x)h(x)g(x)\neq h(x). This is the contrapositve of, and hence equivalent to, the usual transitivity of equality: if f(x)=g(x)f(x) = g(x) and g(x)=h(x)g(x) = h(x) then f(x)=h(x)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)Z^X(a,b) and a morphism in Z X(b,c)Z^X(b,c) you get a morphism in Z X(a,c)Z^X(a,c), it says that given a morphism in the latter, Z X(a,c)Z^X(a,c) it must be in one of the former, namely Z X(a,b)Z^X(a,b) or Z X(b,c)Z^X(b,c).

The ‘existence of an identity’ for ff is

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

which just says that ff agrees with itself everywhere.

Example 1b

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

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

We have C [0,1](f,g)Ob( meas)C_{[0,1]}(f,g)\in Ob(\mathcal{M}_{meas}) because as ff and gg 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 ¯ X sym\overline\mathcal{M}^{sym}_X which will have the same set of objects as X\mathcal{M}_X, i.e., the set of all subsets of XX and the hom-object between subsets AXA\subset X and BXB\subset X is defined to be their symmetric difference:

¯ X sym(A,B)(AB)(AB).\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 ZZ 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 X\mathcal{M}_X the set of all subsets of XX into a category enriched over itself. That’s a slightly confusing to say – how can ¯ X\overline\mathcal{M}_X be an ordinary category and an X\mathcal{M}_X-enriched category? – but it what folks say. To try to reduce confusion I’ll use ¯ X\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.

¯ X(A,B)BA\overline\mathcal{M}_X(A,B)\coloneqq B\setminus A

So you can think that to get from AA to BB you have to pick an element of BB that you don’t already have in AA.

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

X(AB,C)= X(A,CB),\mathcal{M}_X(A\cup B,C)=\mathcal{M}_X(A,C\setminus B),

or, in other words,

ABCACB.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 ¯ X\overline\mathcal{M}_X is the ordinary category X\mathcal{M}_X.

Example 4a

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

P X(f,g){xXf(x)g(x)}.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)P X(g,h)P X(f,h)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 ZZ, by which I mean the preorder \le is precisely equality ==. Example 3 is obtained by taking the preorder {01}\{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 [0,1] C^\le_{[0,1]}, enriched over meas\mathcal{M}_{meas}, the measurable subsets of the interval [0,1][0,1], whose objects are continuous functions f:[0,1]f\colon [0,1]\to \mathbb{R} and whose distances are given by

C [0,1] (f,g){x[0,1]f(x)>g(x)}.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][0,1], thus Lebesgue measurable and hence objects in meas\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 aa to bb is, perhaps not unsurprisingly, α𝒞(a,b)\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 aa and bb

α(a)α(b)α(ab);1 𝒱α(1 𝒱)\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 Γ:𝒱Set\Gamma\colon \mathcal{V}\to Set which is the “global elements” or “sections” functor

Γ()𝒱(1,)\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 aba\le b if and only if d(a,b)=0d(a,b)=0; similarly in the case of a category enriched over X\mathcal{M}_X the underlying category is a preorder on the objects of the enriched category and the preorder is defined by aba\le b if and only if 𝒞(a,b)=\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 XX in \mathcal{M} which satisfies

m(A)+m(B)m(AB)and0m()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 XX, or at least on the subsets of XX which lie in \mathcal{M}.

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

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

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

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

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

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

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

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

and

d =(f,g)μ{x[0,1]f(x)g(x)}.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

28 Comments & 0 Trackbacks

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:Ωf:\Omega \to \mathbb{R}, with respect to the Borel σ\sigma-algebra on \mathbb{R}, is preserved by linear combinations, and so {xΩf(x)g(x)}={xΩf(x)g(x)0} \{ 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)=μ{xΩf(x)g(x)} 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 nS_n. I bet d 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][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][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][0,1] is Lebesgue measurable, and thus every real-valued function on [0,1][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 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 =d^= says that it takes a unit of effort to change the value of ff at an individual xΩx \in \Omega, so the amount of effort to change ff into gg is just the number xxs where ff and gg differ; if Ω\Omega is not discrete it’s standard to replace counting xxs with a more general measure. Your d d^\leq says that to raise the value of f(x)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)f(x)? Then you’re led to thinking about d 1 (f,g)= Ωmax{f(x)g(x),0}dμ(x), d_1^\leq (f,g) = \int_\Omega \max \{ f(x)-g(x), 0 \} d\mu(x), whose symmetric version is just the L 1(Ω,μ)L^1(\Omega, \mu) metric. Turning this back around, does something like d 1 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)Y(a,b) could be the minimum time, or the minimum cost required to travel from aa to bb.

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 X\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, X\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, X\mathcal{M}_X seems to be more like max\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: X +m\colon\mathcal{M}_X\to \mathbb{R}_+ which would mean associating a non-negative real number to each subset of XX which satisfies

(1)max(m(A),m(B))m(AB).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:X[0,]f\colon X\to [0,\infty] is a function then define m f: X +m_f\colon\mathcal{M}_X\to \mathbb{R}_+ by

m f(A)sup aA(f(a)).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 ff 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 𝒱 X\mathcal{V}^X ([…] in fact this must be a standard construction)

In fact I guess it’s the same as the V XV^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 𝒱 X\mathcal{V}^X ([…] in fact this must be a standard construction)

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

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

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

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

In fact I guess it’s the same as the 𝒱 X\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

[,B𝒱]:Set op2Cat. [-,\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

Mark Meckes asked

Turning this back around, does something like d 1 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 {01}\{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 {01}\{0\le 1\}.
  3. We might want to think of it as a classical metric space with metric d(a,b)=|ba|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)max(ba,0)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 XX is a set. Then we can form a monoidal category 𝒱 X\mathcal{V}^X (maybe I’m over-using this notation and X𝒱\prod_X \mathcal{V} might be better, in fact this must be a standard construction) which has as objects the functions XOb(𝒱)X\to Ob(\mathcal{V}) and the hom-sets are defined by

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

Composition and the tensor product are defined point-wise:

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

is the product of the maps

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

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

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

In particular, if we take 𝒱={01}\mathcal{V}=\{0\le 1\} then {01} X X\{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 ( +) X(\mathbb{R}_+)^X is the poset of functions X[0,]X\to [0,\infty] ordered by fgf\le g if and only if f(x)g(x)f(x)\le g(x) for all xx, together with the monoidal product being point-wise sum of functions.

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

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

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

If X=[0,1]X=[0,1] and 𝒱={01}\mathcal{V}=\{0\le 1\} we can use the Lebesgue measure for our mm and for X=[0,1]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][0,1]\to \mathbb{R}.

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

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

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

  4. d 1 (f,g)= [0,1]max{g(x)f(x),0}dxd_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(Ω,μ)L^0(\Omega, \mu) metric. L 0(Ω,μ)L^0(\Omega, \mu) is the space of all measurable functions f:Ω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)= Ωmin(1,|f(x)g(x)|)dμ(x), 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 1L^1 metric, which we’re calling d 1 =d_1^=, between measurable functions such that |f|dμ\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 0L^0 and L 1L^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 GrpGrp 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)f(x)=g(x) or g(x)=h(x)g(x)=h(x) then f(x)=h(x)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 GHG \to H is actually a homomorphism GH opG \to H^{op} (unless you have a nonobvious multiplication hom(G,H)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 GHG \to H is actually a homomorphism GH opG \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:MNf, g: M \to N are multiplied using the pointwise definition,

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

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

In particular, if MM is the free monoid on two generators, we can cook up ff and gg so that f(x)=1=g(y)f(x) = 1 = g(y) and f(y)f(y), g(x)g(x) are any two elements aa, bb in NN. If fgf \cdot g is to be monoid homomorphism, we infer ab=baa b = b a so that NN 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 GG which act by conjugation: k:gkgk 1k: 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 XX. 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 V: opMonCat\mathbf{V} \colon \mathcal{B}^{op} \to \mathbf{MonCat}, where MonCat\mathbf{MonCat} denotes the 22-category of monoidal categories and lax monoidal functors. Recall that any lax monoidal functor F:𝒱𝒲F \colon \mathcal{V} \to \mathcal{W} induces a functor F *:𝒱F_\ast \colon \mathcal{V}-Cat𝒲\mathbf{Cat} \to \mathcal{W}-Cat\mathbf{Cat}.

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

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

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

This general approach to sheaves is also called the theory of 𝒪(X)\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 C\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 XX, and consider the category [𝒪(X) op,Set][\mathcal{O}(X)^{op}, \mathbf{Set}] of presheaves over XX. 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 [𝒪(X) op,Set][\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 [𝒪(X) op,Set][\mathcal{O}(X)^{op}, \mathbf{Set}] for which Cauchy-complete enriched categories are sheaves on XX. The object of objects of this internal category is Ω j:𝒪(X) opSet\Omega_j \colon \mathcal{O}(X)^{op} \to \mathbf{Set}, where Ω j(U)\Omega_j(U) is the set of all open subsets of UU. It’s really an internal poset of course, and in fact a sub-poset of Ω=𝒫1\Omega = \mathcal{P}1, the set of all subsets of 11 in [𝒪(X) op,Set][\mathcal{O}(X)^{op}, \mathbf{Set}]. So we’re enriching over a category of subsets of 11!

What is a category enriched over Ω j\Omega_j? Well, it’s a presheaf XX together with a map X×XΩ jX \times X \to \Omega_j which is going to send a pair (x,y)XU(x,y) \in X U to the largest VΩ j(U)V \in \Omega_j(U) for which x V=y Vx \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) Ω j\Omega_j-enriched categories in [𝒪(X) op,Set][\mathcal{O}(X)^{op},\mathbf{Set}] will turn out to be equivalent to the category of separated presheaves on XX.

The nice thing now is that (symmetric) Cauchy-complete Ω j\Omega_j-categories are once again the sheaves on XX. Moreover, sheafification is visibly the same as Cauchy-completion: given an enriched category X×XΩ jX \times X \to \Omega_j, you get the corresponding sheaf by considering the embedding XΩ j XX \to \Omega_j^X (which is the Yoneda embedding) and then closing the image of XX in Ω j X\Omega_j^X under absolute colimits: in the internal logic, you look at the subobject of Ω j X\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. jj can be any local operator on any topos, and Ω j\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