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.

November 23, 2009

Equipments

Posted by Mike Shulman

I mentioned in my intro that as wonderful as nn-categories are, they’re really just one (important) part of the zoo of “higher categorical structures” out there. Today I want to tell you about another inhabitant of that zoo: a wonderful gadget called a proarrow equipment (or just an equipment), which lets us do what I call “formal category theory.” Equipments don’t seem to be very well-known, especially in the northern hemisphere (even though their inventor, R.J. Wood, is a Canadian at Dalhousie), but there are some indications that they’re gaining ground, so I’m doing my best to help them along.

This post will be a lightning-fast introduction to formal category theory in equipments. But I’m going to present the definition in a nonstandard way, because it turns out that an equipment is basically the same as what I’ve called a framed bicategory, and I find that way of thinking about it more natural—and also easier to generalize (but that’s another post). Some of it may go by a little quickly, but I think it’s the sort of thing that’s really quite fun to work out yourself once you’ve been pointed in the right direction.

What do I mean by formal category theory? This is an analogy to the way in which category theory can be called “formal mathematics.” That is, we see ourselves doing the same thing all the time in mathematics (limits, colimits, adjoints, universal constructions) and we write down category theory in order to do all those things formally, once and for all in abstract generality. But nowadays there are actually lots of kinds of category theory too: ordinary category theory, enriched category theory, internal category theory, fibered category theory, etc. After a while, one starts to get the feeling of “doing the same thing all the time” again: defining limits and colimits, proving adjoint functor and monadicity theorems, etc. So, can we “formalize” the essential aspects of category theory in an analogous way, and if so, how?

You might expect the answer to be “yes, with 2-categories.” Perhaps surprisingly, however, 2-categories don’t always suffice. We can do a lot of category theory in a 2-category: we can define adjunctions, construct Eilenberg-Moore and Kleisli objects for monads (the “formal theory of monads”), and talk about Kan extensions, comma objects, fibrations, and so on. But some things are missing, and some of the general notions are not always quite right. For instance, the most obvious 2-categorical analogue of a limit is a Kan extension, since in ordinary category theory limits can be identified with Kan extensions along functors to the terminal category. However, in enriched category theory this is insufficient; not all weighted limits arise in that way. Moreover, the “internal” notion of Kan extension in a 2-category gives the “weak” notion rather than the more important “pointwise” one.

The central observation is that what’s missing from the 2-category CatCat is hom-functors, and more generally profunctors. Recall that a profunctor (aka “distributor” or “(bi)module”) CDC \nrightarrow D is a functor D op×CSetD^{op}\times C \to Set (or to D opCVD^{op}\otimes C\to V, if CC and DD are VV-enriched). Including profunctors in our “structure for formal category theory” will allow us to talk about their representability, which is the essential ingredient for limits, pointwise Kan extensions, and all the other things that are missing from a 2-category.

So what kind of formal structure includes categories, functors, and profunctors? There are several different answers, but to me, the most obvious and natural-looking answer is a double category. Specifically, there’s a double category Prof̲\underline{Prof} whose objects are small categories, whose vertical arrows (which we’ll just call “arrows”) are functors, whose horizontal arrows (which we’ll call “proarrows”) are profunctors, and whose squares A H B f g C K D\array{A & \overset{H}{\nrightarrow} & B\\ ^f\downarrow & \Downarrow & \downarrow^g\\ C& \underset{K}{\nrightarrow} & D} are transformations H(b,a)K(gb,fa)H(b,a) \to K(g b,f a) natural in aa and bb. Composition of profunctors is by a coend: (HK)(c,a)= bBH(b,a)K(c,b)(H\odot K)(c,a) = \int^{b\in B} H(b,a) \otimes K(c,b) (note that I’m writing it in diagrammatic order) and the identity profunctor of CC is its hom-profunctor U C=Hom C:C op×CSetU_C=Hom_C\colon C^{op}\times C\to Set. The 2-categories CatCat and ProfProf can be recovered from Prof̲\underline{Prof} as its vertical and horizontal 2-categories, respectively, which I’ll write as Cat=𝒱(Prof̲)Cat = \mathcal{V}(\underline{Prof}) and Prof=(Prof̲)Prof = \mathcal{H}(\underline{Prof}). (For ProfProf, this is basically by definition; for CatCat, it’s a nice exercise in the Yoneda lemma.)

Similar double categories exist for all the other kinds of category theory (enriched, internal, fibered, etc.). Moreover, all these double categories have an additional very important property: given any “niche” A B f g C K D\array{A & & B\\ ^f\downarrow & & \downarrow^g\\ C& \underset{K}{\nrightarrow} & D} there exists a “universal” or “cartesian” filler square A K(g,f) B f g C K D\array{A & \overset{K(g,f)}{\to} & B\\ ^f\downarrow & \Downarrow & \downarrow^g\\ C& \underset{K}{\nrightarrow} & D} with the property that any other square X Y fh gk C K D\array{X & \nrightarrow & Y\\ ^{f h}\downarrow & \Downarrow & \downarrow^{g k}\\ C& \underset{K}{\nrightarrow} & D} factors through the universal one uniquely: X Y h ! k A K(g,f) B f g C K D\array{X & \nrightarrow & Y\\ ^{h}\downarrow & \exists! \Downarrow & \downarrow^{k}\\ A & \overset{K(g,f)}{\to} & B\\ ^f\downarrow & \Downarrow & \downarrow^g\\ C& \underset{K}{\nrightarrow} & D} The profunctor K(g,f)K(g,f) is of course just K(g,f):B op×ASetK(g-,f-)\colon B^{op}\times A\to Set. We say that a double category X̲\underline{X} having this property equips the 2-category 𝒱(X̲)\mathcal{V}(\underline{X}) with proarrows, and speak of the whole double category as a proarrow equipment, or just an equipment.

Of particular importance in an equipment are the proarrows B(1,f)=U B(id B,f)B(1,f)=U_B(id_B,f) and B(f,1)=U B(f,id B)B(f,1) = U_B(f,id_B), which exist for any arrow f:ABf\colon A\to B. By factoring the identity square A U A A f U f f B U B B\array{A & \overset{U_A}{\to} & A\\ ^f\downarrow & ^{U_f}\Downarrow & \downarrow^f\\ B & \underset{U_B}{\to} & B} through the universal fillers A B(1,f) B f id B U B BandB B(f,1) A id f B U B B\array{A & \overset{B(1,f)}{\to} & B\\ ^f\downarrow &\Downarrow & \downarrow^{id}\\ B & \underset{U_B}{\to} & B} \qquad\text{and}\qquad \array{B & \overset{B(f,1)}{\to} & A\\ ^{id}\downarrow &\Downarrow & \downarrow^{f}\\ B & \underset{U_B}{\to} & B} that define B(1,f)B(1,f) and B(f,1)B(f,1), we obtain additional squares A U A A f id B B(f,1) AandA U A A id f A B(1,f) B\array{A & \overset{U_A}{\to} & A\\ ^f\downarrow &\Downarrow & \downarrow^{id}\\ B & \underset{B(f,1)}{\to} & A} \qquad\text{and}\qquad \array{A & \overset{U_A}{\to} & A\\ ^{id}\downarrow &\Downarrow & \downarrow^{f}\\ A & \underset{B(1,f)}{\to} & B} such that the composites A U A A f id B B(f,1) A id f B U B BandA U A A id f A B(1,f) B f id B U B B\array{A & \overset{U_A}{\to} & A\\ ^{f}\downarrow &\Downarrow & \downarrow^{id}\\ B & \overset{B(f,1)}{\to} & A\\ ^{id}\downarrow &\Downarrow & \downarrow^{f}\\ B & \underset{U_B}{\to} & B} \qquad\text{and}\quad \array{A & \overset{U_A}{\to} & A\\ ^{id}\downarrow &\Downarrow & \downarrow^{f}\\ A & \underset{B(1,f)}{\to} & B\\ ^f\downarrow &\Downarrow & \downarrow^{id}\\ B & \underset{U_B}{\to} & B} are both equal to U fU_f. And using the uniqueness of factorization through the universal squares, we can conclude moreover that the composites A U A A B(1,f) A id f id A B(1,f) B U B BandB B(f,1) A U A A id f id B U B B B(f,1) A\array{A & \overset{U_A}{\to} & A & \overset{B(1,f)}{\to} & A\\ ^{id}\downarrow &\Downarrow & \downarrow^{f} & \Downarrow & \downarrow^{id}\\ A & \underset{B(1,f)}{\to} & B & \underset{U_B}{\to} & B} \qquad\text{and}\qquad \array{B & \overset{B(f,1)}{\to} & A & \overset{U_A}{\to} & A\\ ^{id}\downarrow &\Downarrow & \downarrow^{f} & \Downarrow & \downarrow^{id}\\ B & \underset{U_B}{\to} & B & \underset{B(f,1)}{\to} & A} are equal to the identity squares of B(1,f)B(1,f) and B(f,1)B(f,1) respectively. In double-category lingo which I adopted from Dawson, Paré, and Pronk, this says that B(1,f)B(1,f) is a companion of ff and B(f,1)B(f,1) is a conjoint of ff. It follows, in particular, that B(1,f)B(1,f) and B(f,1)B(f,1) are adjoint in (X̲)\mathcal{H}(\underline{X}).

Now the central lemma about these companions and conjoints is the following: there is a natural bijection between squares of the form A 0 H B 0 f 1 g 1 A 1 B 1 f 2 g 2 A 2 B 2 f 3 g 3 A 3 K B 3\array{A_0 & \overset{H}{\to} & B_0\\ ^{f_1}\downarrow && \downarrow^{g_1}\\ A_1 && B_1\\ ^{f_2}\downarrow & \Downarrow & \downarrow^{g_2}\\ A_2 && B_2\\ ^{f_3}\downarrow && \downarrow^{g_3}\\ A_3 & \underset{K}{\to} & B_3 } and squares of the form A 1 A 1(f 1,1) A 0 H B 0 B 1(1,g 1) B 1 f 2 g 2 A 2 A 3(1,f 3) A 3 K B 3 B 3(g 3,1) B 2.\array{A_1 & \overset{A_1(f_1 ,1)}{\to} & A_0 & \overset{H}{\to} & B_0 & \overset{B_1(1,g_1)}{\to} & B_1\\ ^{f_2}\downarrow && &\Downarrow & && \downarrow^{g_2}\\ A_2 & \underset{A_3(1,f_3)}{\to} & A_3 & \underset{K}{\to} & B_3 & \underset{B_3(g_3 ,1)}{\to} & B_2.} I like to think of this as saying that vertical arrows can be “slid around corners” to become horizontal arrows, turning them into the “representable proarrows” B(1,f)B(1,f) or B(f,1)B(f,1) (depending on whether you slid them “backwards” or “forwards” to get around the corner). The bijection is just given by composing with the four special squares defined above. In particular, by a Yoneda argument, for any f:ACf\colon A\to C, g:BDg\colon B\to D, and K:CDK\colon C\nrightarrow D we have

(1)K(g,f)C(1,f)KD(g,1)K(g,f) \cong C(1,f) \odot K \odot D(g,1)

so the companions and conjoints determine the rest of the cartesian squares. Note that this is an equipment-version of Yoneda reduction, aka the co-Yoneda lemma. Also, we have a bijection between 2-cells fgf\to g in 𝒱(X̲)\mathcal{V}(\underline{X}) and 2-cells B(1,f)B(1,g)B(1,f)\to B(1,g) in (X̲)\mathcal{H}(\underline{X}). It follows that the functor 𝒱(X̲)(X̲)\mathcal{V}(\underline{X})\to \mathcal{H}(\underline{X}) sending ff to B(1,f)B(1,f) is locally fully faithful.

Wood’s original definition of an equipment was a functor KMK\to M between (weak) 2-categories which is bijective on objects, locally fully faithful, and such that the image of each arrow of KK has a right adjoint in MM. Thus, our definition implies his. The converse is not too hard either, so the two are equivalent. However, I find that the double-category way of thinking makes the structure look much more natural; Wood’s definition looks very ad-hoc to me. The double-categorical approach also (a) automatically gives you a good 2- or 3-category of equipments, which is tricky to do with Wood’s definition (I believe this was first realized by Verity in his thesis), and (b) generalizes better to situations in which the coends that define profunctor composition may not exist. But those are for another day.

Now let me try to convince you that we do formal category theory in an equipment. Let’s start with this: two (vertical) arrows f:ABf\colon A\to B and g:BAg\colon B\to A are adjoint (in 𝒱(X̲)\mathcal{V}(\underline{X})) if and only if we have an isomorphism B(f,1)A(1,g)B(f,1)\cong A(1,g). Why? Well, an adjunction fgf\dashv g comes with a unit and a counit, which (expressed in X̲\underline{X}) are of the form A U A A f B η id g A U A AandB U B B g id ε A f B U B B.\array{A & \overset{U_A}{\to} & A\\ ^f\downarrow && \downarrow\\ B & \overset{\eta}{\Leftarrow} & \downarrow^{id} \\ ^g\downarrow && \downarrow\\ A& \underset{U_A}{\to} & A} \qquad\text{and}\qquad \array{B & \overset{U_B}{\to} & B\\ \downarrow && \downarrow^g\\ ^{id}\downarrow & \overset{\varepsilon}{\Leftarrow} & A \\ \downarrow && \downarrow^f\\ B& \underset{U_B}{\to} & B.} Applying the bijection of the central lemma, we see that η\eta corresponds to a map B(f,1)A(1,g)B(f,1) \to A(1,g), and likewise ε\varepsilon corresponds to a map A(1,g)B(f,1)A(1,g)\to B(f,1). The triangle identities for η\eta and ε\varepsilon are then equivalent to saying that these two maps are inverse isomorphisms. So we’ve recovered the classical equivalence between the “diagrammatic” and isomorphism-of-hom-sets definitions of an adjunction, in a purely formal way.

Now let’s define limits. I’m not sure who first realized that limits can be defined in the following way, but Ross Street is a good guess. The notion of limit we end up with is actually more general than what you’re probably used to, but this extra generality turns out to be useful. Let d:DCd\colon D\to C be an arrow and let J:DAJ\colon D\nrightarrow A be a proarrow; we’re going to define what it means for an arrow :AC\ell\colon A\to C to be the JJ-weighted limit of dd. In the equipment V-Prof̲\underline{V\text{-}Prof} of VV-enriched categories, if AA is the unit VV-category II, then this will recover the usual notion of weighted limit. Of course, in a general equipment we may not have a “unit object,” so that extra generality is unavoidable; it’s like using generalized elements in ordinary category theory.

To make things easier, let’s assume that X̲\underline{X} is closed, in the sense that composition of proarrows has adjoints in each variable (X̲)(HK,L)(X̲)(H,KL)(X̲)(K,LH). \mathcal{H}(\underline{X})(H\odot K,L) \cong \mathcal{H}(\underline{X})(H,K\rhd L) \cong \mathcal{H}(\underline{X})(K,L\lhd H). The central lemma implies that analogously to (1), we have

(2)K(g,f)D(1,g)KC(f,1).K(g,f) \cong D(1,g)\rhd K \lhd C(f,1).

In V-ProfV\text{-}Prof, the adjoints are given by the ends (KL)(b,a)= cC[K(c,b),L(c,a)] (K\rhd L)(b,a) = \int_{c\in C} [K(c,b), L(c,a)] and (LH)(c,b)= aA[H(b,a),L(c,a)]. (L \lhd H)(c,b) = \int_{a\in A} [H(b,a), L(c,a)]. Therefore, (2) is an abstract form of the Yoneda lemma, just as (1) is an abstract form of the co-Yoneda lemma.

Now recall that for VV-categories DD and CC, an object C\ell\in C is a JJ-weighted limit of d:DCd\colon D\to C if we have an isomorphism C(,) [D,V](J,C(,x)) = xD[J(x),C(,d(x))]. \begin{aligned} C(-,\ell) &\cong [D,V](J, C(-,x))\\ &= \int_{x\in D} [J(x), C(-,d(x))]. \end{aligned} Thus it makes sense to define, in a closed equipment, an arrow :AC\ell\colon A\to C to be the JJ-weighted limit of dd if we have an isomorphism C(1,)C(1,d)J. C(1,\ell) \cong C(1,d) \lhd J. (If our equipment is not closed, we simply assert that C(1,)C(1,\ell) has the universal property that C(1,d)JC(1,d) \lhd J would have if it existed.) In particular, when AA is the unit VV-category, this recovers the classical notion. But even in V-Prof̲\underline{V\text{-}Prof} there are interesting examples for other values of AA. If we take J=D(j,1)J = D(j,1) for some functor j:ADj\colon A\to D, then (1) and (2) imply that C(1,d)J =C(1,d)D(j,1) j *C(1,d) D(1,j)C(1,d) C(1,dj) \begin{aligned} C(1,d) \lhd J &= C(1,d) \lhd D(j,1)\\ & \cong j^\ast C(1,d)\\ & \cong D(1,j) \odot C(1,d)\\ & \cong C(1,d j) \end{aligned} so that =dj\ell = d j is the JJ-weighted limit of dd. That is, D(j,1)D(j,1)-weighted limits are just given by composition with jj. But more interestingly, one can show that if J=D(1,k)J = D(1,k) for some k:DAk\colon D\to A, then JJ-weighted limits specialize to pointwise right Kan extensions along kk. That is, the extra data in an equipment lets us define the good notion of Kan extension (even in the enriched case) as a special case of a general notion of limit.

Amazingly, a huge amount of category theory can be done at this level of generality. I’ll give just one more example (for now): the theorem that right adjoints preserve limits. Suppose that :AC\ell\colon A\to C is a JJ-weighted limit of d:DCd\colon D\to C in the above sense, and let g:CBg\colon C\to B be an arrow with a left adjoint f:BCf\colon B\to C. We want to show that gg\ell is a JJ-weighted limit of gdg d. But we have B(1,g) C(1,)B(1,g) (C(1,d)J)C(f,1) C(1,f)(C(1,d)J) (C(1,f)C(1,d))J (C(1,d)C(f,1))J (C(1,d)B(1,g))J B(1,gd)J. \begin{aligned} B(1,g\ell) &\cong C(1,\ell) \odot B(1,g)\\ &\cong \big(C(1,d) \lhd J\big) \odot C(f,1)\\ &\cong C(1,f) \rhd \big(C(1,d) \lhd J\big)\\ &\cong \big(C(1,f) \rhd C(1,d)\big) \lhd J\\ &\cong \big(C(1,d) \odot C(f,1)\big) \lhd J\\ &\cong \big(C(1,d) \odot B(1,g)\big) \lhd J\\ &\cong B(1,g d) \lhd J. \end{aligned} which is what we want.

Finally, in the interests of full disclosure, I should say that equipments are not the only way to do formal category theory. A sort-of equivalent approach, due to Street and Walters, is a “Yoneda structure,” which equips a 2-category with “presheaf objects” so that profunctors can be recovered as functors APBA\to P B. (It’s only “sort-of” equivalent due to differences in how size is dealt with.) Alternately, one can start from a well-behaved 2-category, such as a 2-topos, and construct an equipment or Yoneda structure, in one of several ways, and if one likes one can work only with those constructions without ever saying “equipment” or “Yoneda structure.” But I think that isolating the “proarrow structure” that enables us to do formal category theory is helpful, and can provide useful insights even if we only care about one particular kind of category theory—just like knowing some ordinary category theory can be helpful even if we only care about one particular category.

Posted at November 23, 2009 5:11 AM UTC

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

97 Comments & 3 Trackbacks

Re: Equipments

You know me, so I'm trying to understand equipments by first figuring out what they are a categorification of. Your introductory paragraphs imply that they're a categorification of categories, but I don't buy it. Let me decategorify paragraph 4 (where the first paragraph is paragraph 0):

The central observation is that what’s missing from the category SetSet is equality relations, and more general relations. Recall that a (binary) relation CDC \nrightarrow D is a function D×C𝟚D \times C \to \mathbb{2}. Including relations in our “structure for formal mathematics” will allow us to talk about their representability, which is presumably the essential ingredient for things that are missing from a category.

So maybe an equipment is a categorification of something like an allegory?

Except that we usually don't think of relations as missing from ordinary category theory. We can define an internal relation CDC \nrightarrow D in any category to be an object RR with morphisms p:RCp\colon R \to C and q:RDq\colon R \to D that satisfy a joint monicity condition. So why can't we define an internal profunctor CDC \nrightarrow D in any 22-category to be an object RR with morphisms p:RCp\colon R \to C and q:RDq\colon R \to D equipped with a joint monicity structure?

Trying to write down that structure, I see that already this is not possible even when dealing with posets as categories enriched over 𝟚\mathbb{2}. Of course, that means that there is an interesting decategorification of the notion of equipment which serves as a universe in which to do order theory. (This is an example of how categorification directly takes us from posets to categories or from categories to groupoids, while it is laxification that takes us from sets to posets or from groupoids to categories, and these are separate operations.) Has anybody studied that?

Conversely, I would hope that, as an unlaxified categorification of our ability to study relations internal to an arbitrary category, we can also study profunctors internal to an arbitrary (2,1)(2,1)-category. Do we have a theorem about that, that any locally groupoidal 22-category naturally has the structure of an equipment?

I think that I may have talked with you about this already on your personal web, Mike, but I can't check it now since the Ruby on Rails application is down. (In principle, I could check my backups, but that's not very convenient.) Sorry if you already explained all of this and it didn't stick the first time.

Posted by: Toby Bartels on November 23, 2009 7:31 AM | Permalink | Reply to this

Re: Equipments

The way I think about it, equipments are an attempt to generalize the theory of profunctors from Cat to other 2-categories. Personally I think it’s hopeless to understand equipments without first understanding profunctors and why they’re so great.

But if ‘profunctor’ sounds scary, how about such buzzwords as ‘presheaf category’, ‘Yoneda embedding’, ‘colimit-preserving functor’, and ‘coend’? All these ideas are built into the technology of profunctors, and generalized in the theory of equipments.

But if all this is still too scary…

Personally, I think of all this technology as a categorification of linear algebra. It brings the power of linear algebra to our work on category theory!

The analogy is loose — it’s the analogy between ‘vector space’ and ‘cocomplete category’, and between ‘linear map’ and ‘cocontinuous functor’. But it’s a very useful one, and it can be made more precise by replacing the ‘field of coefficients’ in your vector space by something more closely analogous to the category of sets. For example, the set of truth values!

So, profunctors are also a categorification of relations.

Except that we usually don’t think of relations as missing from ordinary category theory.

Relations would be missing from ordinary set theory if our concept of set theory was merely the category of sets and functions, without any extra bells and whistles.

To overcome this, we can treat Set as an allegory.

Similarly, it’s good to treat Cat not as a mere 2-category, but as a 2-category with an ‘equipment’. We in fact do this implicitly when we talk about such things as ‘presheaf categories’, ‘the Yoneda embedding’, ‘colimit-preserving functors’, and ‘coends’.

And so, 2-categories or bicategories with equipments are a good thing!

Posted by: John Baez on November 23, 2009 10:04 PM | Permalink | Reply to this

Re: Equipments

I think one of the reasons equipments aren’t more widely accepted is that they aren’t an obvious categorification of anything familiar. Of course, profunctors do decategorify naturally to relations. So the decategorified analogue of Prof̲\underline{Prof} would be the equipment Rel̲\underline{Rel} with objects = sets, arrows = functions, and proarrows = relations. If we take the default prefix of “equipment” to be “2-” (since we regard it as structure supplied to a 2-category) we might call Rel̲\underline{Rel} a “1-equipment.”

As you say, however, the 1-equipment Rel̲\underline{Rel} is not commonly studied directly, because it can be constructed easily from either the category 𝒱(Rel̲)=Set\mathcal{V}(\underline{Rel}) = Set of sets and functions, or from the allegory (Rel̲)=Rel\mathcal{H}(\underline{Rel}) = Rel of sets and relations. In SetSet you can define internal relations and their composites, while in RelRel you can look at the (pro)arrows with right adjoints to recover the functions. I would argue that the 1-equipment Rel̲\underline{Rel} is implicitly present, but because it’s so easy to recover SetSet and RelRel from each other, it is never made explicit. (SetSet can of course be replaced here by any other category: nothing is necessary to define relations, but it should be regular if you want to assemble them into RelRel. Likewise RelRel can be replaced by any allegory.)

Actually, an analogous construction is possible for (2-)equipments; I alluded to this in my final paragraph. However, the passage back and forth between CatCat and ProfProf is much more complicated, sometimes loses information, and requires more stringent completeness hypotheses. These are some of the reasons I believe equipments are a valuable framework, despite the fact that with enough work, they can often be constructed from 2-categories. But since you’ve provided the opening, let me summarize how these constructions go.

Starting from the 2-category CatCat, you can reconstruct the 2-category ProfProf (and hence the equipment Prof̲\underline{Prof}) by looking at two-sided discrete fibrations internal to CatCat. (Two-sided discrete fibrations are what I would call the graph of a profunctor; note that they can be defined without a notion of “op” in your 2-category.) Thus, if you want to, you can avoid equipments by working with two-sided discrete fibrations in a 2-category like CatCat, just as you can work with internal relations in a 1-category like SetSet. Cf. for instance Street-Walters, “Fibrations and Yoneda’s lemma in a 2-category,” Street’s paper “Fibrational cosmoi,” and Weber’s work on 2-toposes. However, it turns out to be very fiddly to get the correct conditions on a 2-category so that internal two-sided discrete fibrations can be composed associatively; the appropriate notion of “regularity” is somewhat subtle and quite strong (it’s not the same as the one I’ve been working on).

The first catch is that this doesn’t work for enriched things: two-sided discrete fibrations in VV-CatCat don’t give you the right notion of VV-profunctor. Street (“Fibrations in bicategories”) realized that the right thing to do is switch from graphs to cographs of profunctors, which (coincidentally?) can be characterized as the two-sided discrete fibrations in VV-Cat opCat^{op}, i.e. two-sided discrete cofibrations in VV-CatCat. Then Carboni, Johnson, Street, and Verity (“Modulated bicategories”) gave axioms on a 2-category enabling the reconstruction of an equipment via two-sided discrete cofibrations. I don’t know whether this has been decategorified; is the “1-equipment” of relations enriched over a quantale interesting?

The second catch is that you can’t reconstruct CatCat from ProfProf. You can look at the profunctors having right adjoints, but not all of those are representable by functors. They “almost” all are, though: profunctors CDC\nrightarrow D with right adjoints are equivalent to functors CD¯C\to \overline{D}, where D¯\overline{D} is the Cauchy completion of DD. So if you start from any 2-category MM, you can build an equipment with MM as the proarrows and the left-adjoint-proarrows as the arrows, but from VV-ProfProf this will only reconstruct the equipment of Cauchy complete VV-categories. This is not usually a large loss, but it is a loss. Lots of people talk about Cauchy completeness as a “mild” completeness condition; I say that it is often mild, but sometimes not! For instance, there exist monoidal categories VV, such as the category SupSup of suplattices, such that no small VV-category is Cauchy complete.

For all of these reasons, I think it is better to regard these as various ways of constructing equipments, while the equipments themselves are the (or at least “a”) natural home for formal category theory.

Finally, most of this does decategorify to the (1,2) and the (2,1) case. I haven’t thought deeply about all the ways of constructing equipments and whether they work for posets and groupoids, but probably most of them do.

Posted by: Mike Shulman on November 24, 2009 2:15 AM | Permalink | PGP Sig | Reply to this

Re: Equipments

If we take the default prefix of “equipment” to be “2-” (since we regard it as structure supplied to a 2-category) we might call Rel̲\underline{Rel} a “1-equipment.”

Well, I would never do such a thing, but I won't worry about that now.

Thanks, your explanation helps. In principle, we don't need to use equipments at all, at least if our 22-category has sufficient regularity properties. But really, this should be seen as only presenting the equipment. That makes sense.

Does saying that categorified mathematics should really be done internal to an equipment make you want to say that ordinary mathematics should really be done internal to an allegory? (or whatever a 00-equipment, aka “1-equipment”, really is: a 𝟚\mathbb{2}-enriched equipment or whatever). Certainly much of ordinary mathematics uses relations (not just functions) rather heavily.

Posted by: Toby Bartels on November 24, 2009 6:47 AM | Permalink | Reply to this

Re: Equipments

Does saying that categorified mathematics should really be done internal to an equipment make you want to say that ordinary mathematics should really be done internal to an allegory?

I don’t think I would necessarily go that far, although there might be important insights to be gained from such an approach. But I’ve never really felt the need for such a structure in doing “ordinary” mathematics.

BTW, you’re probably aware of this, but the usual definition of an “allegory” contains an extra “cartesianness” constraint (the “modular law”) which won’t hold in an arbitrary 𝟚\mathbb{2}-enriched equipment.

Posted by: Mike Shulman on November 24, 2009 10:27 PM | Permalink | PGP Sig | Reply to this

Re: Equipments

I’ve actually never really been comfortable with the notion of allegory. The “modular law” always seemed kind of obscure and ad hoc. Also the allegorical notion of “tabulation” seems to me to be crying out to be replaced by a double-categorical universal property.

Apparently I’m not the only one who feels this way. In response to this post, Bob Walters has pointed me to his blog where he argues that the notion of bicategory of relations defined by him and Carboni (a decategorified cartesian bicategory) is a more natural notion. He also sketches a proof that the axioms of a bicategory of relations imply the modular law.

In the spirit of this post, let me add one further potential replacement for allegories: decategorified equipments! I haven’t checked all the details, but I believe that the main attribute of a “1-category equipment” that makes it correspond to an allegory/bicategory-of-relations is that it is a cartesian object in the 2-category of equipments. I suspect that this categorifies to say something about arbitrary cartesian bicategories and cartesian (2-category) equipments, possibly extending to some sort of equivalence. (Anyone want to help check the details?) I find this a very natural condition, and further evidence in favor of the equipment point of view.

Of course, the extra arrows included in an equipment are intentionally excluded from allegories and bicategories-of-relations, since in some cases it is more natural to construct the relations and derive the functions from those. But as I said above, one can always consider, for any bicategory MM, the equipment Map̲(M)\underline{Map}(M) whose proarrows are the morphisms of MM and whose arrows are the morphisms with right adjoints. Saying that Map̲(M)\underline{Map}(M) is a cartesian equipment is then a natural “cartesianness” condition to impose on MM.

Posted by: Mike Shulman on November 25, 2009 9:39 PM | Permalink | PGP Sig | Reply to this

Re: Equipments

I have to go now, but I'll come back tonight to help you work out the details.

“1-category equipment”

But in the meantime, I'll comment on terminology, since that's easier. I've made my peace with ‘11-equipment’, at least if it is regarded as simply an abbreviation of ‘11-category equipment’ as above.

If we take the terminological view that an ‘equipment’ is a thing in itself (like a ‘rig’ or a ‘category’), then a ‘22-equipment’ should be one level higher (like a ‘22-rig’ or a ‘22-category’ —notice that these are all on different levels) and one level lower should be a ‘00-equipment’.

But if we take the terminological view that an ‘equipment’ is something applied to a 22-category (which seems to make more linguistic sense) with any differing grammar being simply an abbreviation, then the standard concept is a ‘22-category equipment’, with the decategorified version being a ‘11-category equipment’ as you say above.

Posted by: Toby Bartels on November 25, 2009 10:16 PM | Permalink | Reply to this

Re: Equipments

But in the meantime, I’ll comment on terminology, since that’s easier. I’ve made my peace with ‘1-equipment’, at least if it is regarded as simply an abbreviation of ‘1-category equipment’ as above.

I haven’t made my peace yet. Just complained a bit here.

Posted by: Urs Schreiber on November 26, 2009 12:53 AM | Permalink | Reply to this

Re: Equipments

I believe that the main attribute of a “1-category equipment” that makes it correspond to an allegory/bicategory-of-relations is that it is a cartesian object in the 2-category of equipments.

Bob Walters points out that a result along these lines can be found in the paper

  • Carboni, Kelly, Wood, “A 2-categorical approach to change of base and geometric morphisms, I” (PDF)

They construct a 2-category of equipments and prove that the cartesian objects in it are precisely the cartesian bicategories of Carboni-Walters. (A “bicategory of relations” is a cartesian object satisfying some additional conditions.)

Posted by: Mike Shulman on November 28, 2009 1:42 AM | Permalink | PGP Sig | Reply to this

Re: Equipments

Starting from the 2-category Cat, you can reconstruct the 2-category Prof (and hence the equipment Prof̲) by looking at two-sided discrete fibrations internal to Cat. (Two-sided discrete fibrations are what I would call the graph of a profunctor;

I can see from your discussion above and from your article why you like the framed bicategory description of equipments, but I find the characterization in terms of spans of functors arising as graphs of functors, or cographs of functors, conceptually very pleasing.

I take your word that it is fiddly to make composition of graphs of functors as spans well defined, but at least this is an obvious notion that i’ll acept right away as clearly useful. And, not unimportant, that clearly generalizes (maybe up to fiddly technical details, but certainly conceptally) to (even) higher categories.

A question on this: you seem to be saying that if using co-graphs instead of graphs there is no such problem. Is that right? I’d be quite happy with cographs instead of graphs, not the least since there is a well developed and useful theory of cographs of (,1)(\infty,1)-functors.

And a remark on this: concerning your italicized I: it seems I have no problem following you in your suggestion of thinking of the graph of a functor as a bifibration, I just replied to that in the query box at graph of a functor: to me it seemed that the differences to the other descriptions are too minor to be worth spending many words about.

But now I understand from the discussion here that you want a formulation that does not need to make use of the notion of opposite category. I see the point of that. We should write this into the nLab entry on graphs of functors, accordingly.

Anyway, thanks for this nice post on equipments. Certainly a useful reference. You should copy the entry code over to equipment.

Do we speak of “equipping a 2-category with an equipment”, by the way? I could imagine that “equipment” isn’t the most descriptive term that was available for this concept, when it was conceived.

Posted by: Urs Schreiber on November 24, 2009 8:54 AM | Permalink | Reply to this

Re: Equipments

I find the characterization in terms of spans of functors arising as graphs of functors, or cographs of functors, conceptually very pleasing.

Or graphs/cographs of profunctors as well, I assume you mean. I think graphs and cographs are a great way to think about profunctors, although there are of course also other good ways.

A question on this: you seem to be saying that if using co-graphs instead of graphs there is no such problem. Is that right?

Well, I think showing that you can compose them is just as fiddly, if that’s the problem you’re referring to.

There are several main reasons that I prefer equipments to just working with graphs or co-graphs. Here are some:

  1. The equipment abstracts away the important features, so you don’t have to worry about exactly how your proarrows were constructed.

  2. There’s a good 2- or 3-category of equipments. It’s not clear to me how functorial the constructions of graphs and cographs are, although I haven’t thought about it deeply.

  3. It’s not clear that every interesting equipment arises from graphs or cographs in a 2-category. (There are completeness properties you can impose on an equipment to ensure that it does so arise, but it’s not clear to me that every interesting equipment satisfies those properties.)

  4. Equipments can be generalized to situations where the proarrows can’t necessarily be composed, such as VV-ProfProf when VV is an arbitrary monoidal category (or even an arbitrary multicategory), or the Kleisli construction for an equipment-monad, or even the equipment of large VV-categories when VV is complete and cocomplete. I don’t know how to produce this sort of generalized equipment, which Geoff and I call a “virtual equipment,” from graphs or cographs.

Posted by: Mike Shulman on November 24, 2009 7:24 PM | Permalink | PGP Sig | Reply to this

Re: Equipments

You should copy the entry code over to equipment.

I’m planning to, but I like to wait a little bit after posting here in case the comments and resulting discussion shows up ways in which the original post can be improved before copying it over.

Do we speak of “equipping a 2-category with an equipment”, by the way?

I think Wood originally spoke of “equipping a 2-category with proarrows,” so that the structure put on the 2-category is a “proarrow equipment” or “equipment of proarrows.” But the “proarrow” in front of “equipment” tends to get dropped. Perhaps that is a bad thing.

Posted by: Mike Shulman on November 24, 2009 7:29 PM | Permalink | PGP Sig | Reply to this

Re: Equipments

Richard Wood has reminded me by email of the following unusual-looking example of a proarrow equipment:

(I think there’s a bit of dualization that has to happen somewhere, but this is the idea). Amazingly (or amusingly?) this equipment can be constructed starting from the 2-category of toposes and geometric morphisms and applying the construction of two-sided codiscrete cofibrations. Moreover, certain topos-theoretic constructions, such as “gluing” two toposes along a left-exact functor, fit naturally into this equipment.

I don’t really feel like I understand what this example is trying to say, but there it is.

Posted by: Mike Shulman on November 24, 2009 4:23 AM | Permalink | PGP Sig | Reply to this

gluing of catgeories vs cographs of functors

such as “gluing” two toposes along a left-exact functor

I am hoping the result of “gluing two categories along a functor” is nothing but the cograph of the functor that you already mentioned above?

In section 4.1 of Schemes over F 1F_1 and zeta-functions Alain Connes and Caterina Consani discuss a concept they call “gluing of two categories along a functor” (with adjoint in their case) and sure enough this is nothing but the notion of cograph of a functor.

(But they can be excused, I supposed, as the nnLab entry on cographs didn’t exist yet at the beginning of this year, when they wrote their article.)

Posted by: Urs Schreiber on November 24, 2009 8:22 AM | Permalink | Reply to this

Re: gluing of catgeories vs cographs of functors

Urs, I reckon it’s not the same gluing. My guess is that it’s the Artin gluing. Given any old functor T:ABT: A \to B, define the Artin gluing to be the comma category BTB \downarrow T, in which an object is a triple (aA,bB,f:bTa)(a \in A, b \in B, f: b \to Ta).

If I remember correctly, it’s a theorem (due to Wraith?) that if AA and BB are toposes and TT preserves pullbacks then BTB \downarrow T is a topos. A similar theorem (due to Carboni and Johnstone) says that if AA and BB are presheaf toposes and TT preserves connected limits then BTB \downarrow T is a presheaf topos.

I haven’t got time to do this now, but it might be worth thinking about what happens when A=Set CA = Set^C and B=Set DB = Set^D are presheaf toposes and TT is composition along some functor DCD \to C. Carboni and Johnstone’s theorem says that BTB \downarrow T is a presheaf topos Set ESet^E; and perhaps this category EE is the gluing of CC and DD that you were expecting.

Posted by: Tom Leinster on November 24, 2009 2:07 PM | Permalink | Reply to this

Re: gluing of catgeories vs cographs of functors

Yes, I’m pretty sure that the Artin gluing is what people always mean when they talk about gluing of toposes.

Posted by: Mike Shulman on November 24, 2009 5:09 PM | Permalink | PGP Sig | Reply to this

Re: gluing of catgeories vs cographs of functors

Given any old functor T:ABT:A\to B, define the Artin gluing to be the comma category BTB\downarrow T, in which an object is a triple (aA,bB,f:bTa)(a\in A,b\in B,f:b\to Ta).

Now I would call that a graph of the functor. Although comparing it to that page, I get the feeling that the comma object there is backwards.

Posted by: Toby Bartels on November 24, 2009 8:22 PM | Permalink | Reply to this

Re: gluing of catgeories vs cographs of functors

Given any old functor T:ABT\colon A\to B, define the Artin gluing to be the comma category BTB\downarrow T, in which an object is a triple (aA,bB,f:bTa)(a\in A,b\in B,f\colon b\to T a).

Now I would call that a graph of the functor.

So would I; in fact it’s the two-sided fibration which is precisely what I wanted to call the graph.

I’m fine with using “graph” also for all the other versions too, but this one feels to me like the most important (since it’s a two-sided fibration and can be defined in CatCat without using “op”) and most analogous to the usual notion of graph (since, in particular, it comes with functors to AA and BB, which the other versions don’t).

Posted by: Mike Shulman on November 24, 2009 10:18 PM | Permalink | PGP Sig | Reply to this

Re: gluing of catgeories vs cographs of functors

Now I would call that a graph of the functor.

So would I;

Yup. So in conclusion we find that

- what Jonstone/Artin call gluing along a functor is the graph of that functor

- what Connes calls gluing along a functor is the cograph of that functor.

in fact it’s the two-sided fibration which is precisely what I wanted to call the graph.

I’m fine with using “graph” also for all the other versions too, but this one feels to me like the most important

All right. Feel free to edit the entry, it’s fine with me.

Posted by: Urs Schreiber on November 24, 2009 10:52 PM | Permalink | Reply to this

Re: gluing of catgeories vs cographs of functors

Tom Leinster wrote:

“If I remember correctly, it’s a theorem (due to Wraith?) that if A and B are toposes and T preserves pullbacks then B glued along T is a topos.”

Hm, I did not find any references online, but - just in case you need a reference of some sort - Johnstone introduces the “Arting glueing” in Example 2.1.12 in his book “Sketches of an Elephant”, calls it just “the glueing construction”, states that it is exactly the same as the comma category (but does not explain why this gadget should have two names, or even three), and states the theorem you mentioned without any reference to Wraith (it does not even have a number!).

Posted by: Tim vB on November 24, 2009 10:32 PM | Permalink | Reply to this

Re: gluing of catgeories vs cographs of functors

what Jonstone/Artin call gluing along a functor is the graph of that functor

I feel obliged to point out why I think this construction is called “gluing” in the topos-theoretic context. If XX is a topological space, with UXU\subset X an open set and K=XUK = X \setminus U its complementary closed set, then there is a canonically defined left-exact functor F:Sh(U)Sh(K)F\colon Sh(U)\to Sh(K) such that Sh(X)Sh(X) is equivalent to the “gluing construction” Gl(F)=(Sh(K)F)Gl(F) = (Sh(K) \downarrow F). That is, we obtain XX by “gluing together” UU and KK along “gluing data” specified by the functor FF. This is true more generally for complementary open and closed subtoposes of any topos; see A4.5.6 in the Elephant (and the discussion preceeding it).

Posted by: Mike Shulman on November 25, 2009 3:23 AM | Permalink | PGP Sig | Reply to this

Re: Equipments

I’d like to get some idea of what equipments are about. (I’m not sure why, of all the things I know nothing about, it’s equipments I now want to understand. Maybe it’s Mike’s comment that they don’t appear to be a categorification of anything else, which makes them seem truly new.)

But I got stuck on profunctors, which I’ve never had the need to understand. Could someone give a key example of a profunctor? Why would anyone care enough about them to want to generalize them to other 2-categories?

Another way in for me would be to think about Richard Wood’s example above, which appears accessible to me. But I also don’t understand that. Would someone be willing to unpack the statement that his example is an equipment. Actually, doing that for fibered categories would also be great. For that matter, so would doing it for anything that comes from geometry.

Posted by: James on November 24, 2009 11:37 AM | Permalink | Reply to this

Re: Equipments

James, you might feel less stuck on profunctors if you simply call them by one of their other names: bimodules. :-)

This is part of an analogy between rings and categories. A ring is a one-object Ab\mathbf{Ab}-enriched category. Thus, enriched categories provide a common generalization of rings and categories.

So, for any concept of ring theory, you can try to generalize it to a concept of enriched category theory. Then, if you’re not too keen on enriched category theory, specialize back down to ordinary category theory.

Left modules are an example. A left module over a ring AA can be described as an Ab\mathbf{Ab}-enriched functor AAbA \to \mathbf{Ab}. Generalizing in the obvious way, a left module over a V\mathbf{V}-enriched category can be defined as a V\mathbf{V}-enriched functor AVA \to \mathbf{V}. In particular, a left module over an ordinary category AA is just a functor ASetA \to \mathbf{Set}.

The same story can be told for bimodules. Thus, given V\mathbf{V}-categories AA and BB, an (A,B)(A, B)-bimodule is defined to be a V\mathbf{V}-enriched functor M:B op×AVM: B^{op} \times A \to \mathbf{V}.

People sometimes write (A,B)(A, B)-bimodules MM as M:B+>AM: B -+-> A or M:A+>BM: A -+-> B. (Those are supposed to be crossed arrows. Different people have different conventions on which way round it goes.) You can ‘compose’ such arrows. When V=Ab\mathbf{V} = \mathbf{Ab} and AA and BB are rings, this is the ordinary tensor product of bimodules. When V=Set\mathbf{V} = \mathbf{Set}, it’s a similar kind of tensor product, defined as a certain colimit. (That’s Mike’s coend.)

You asked for examples. I’ll just give one: for any category AA, there is an (A,A)(A, A)-bimodule HomHom defined by taking Hom(a,b)Hom(a, b) to be the usual hom-set (a,bAa, b \in A). This is, in fact, the unit for the tensor product (composition) of bimodules that I just mentioned.

Posted by: Tom Leinster on November 24, 2009 2:01 PM | Permalink | Reply to this

Re: Equipments

James, I think of you as some kind of geometer, so the following might be more up your street.

[Sorry, this is written in haste, I can expand tomorrow if necessary.]

Tom gave the algebraic example where you have algebras, bimodules and bimodule maps. (Actually he said rings, but I’m simple minded and tend to work with the category of vector spaces rather than abelian groups.) So in the Wood picture you have KK the (2-)category of (unital, associative) algebras and (unital) algebra morphisms (+ some two morphisms you can figure out, or I can tell you) mapping to MM consisting algebras, bimodules and bimodule morphisms, where a morphism f:ABf:A\to B gets sent to the bimodule which is BB as a vector space acted on by BB on the left and AA on the right.

One can jazz that up slightly and have MM being the 2-category for which the hom-category from AA to BB is the derived category of AA-BB-bimodules D(A opB)D(A^{op}\otimes B).

There is a geometric analogue of this in which you have KK with objects, say, smooth complex projective varieties, with morphisms smooth maps and perhaps identity two morphisms. Then for MM you would have the 2-category with objects smooth complex varieties and morphisms are integral transforms. So the hom-category from XX to YY would be the derived category D(X×Y)D(X\times Y).

So profunctors are to functors as integral transforms are to functions.

Posted by: Simon Willerton on November 24, 2009 5:46 PM | Permalink | Reply to this

Re: Equipments

Hmmm. Thanks, Tom and Simon.

The examples from module theory are good in that they make it clear that profunctors are familiar in certain special cases. I especially like the integral transform.

But I guess I don’t yet see why someone would bother writing down the definition of profunctor, i.e. why it’s a good concept to isolate in the abstract. Maybe what I’d really like to see are the simplest examples which (i) are natural and (ii) can’t be expressed well using simpler concepts. For a comparison, what really brought home the point of monads for me was an interesting monad on the category of rings (the one responsible for lambda-rings) which didn’t come from an action by a group, a Lie algebra, or anything already familiar to me. (Like everyone else, once I got the point, I started seeing them everywhere.)

It’s probably the same with Simon’s examples of equipments, I don’t see yet why these functors KMK\to M are interesting enough that we’d want to consider their properties in the abstract, but maybe I should not worry about that till I get my head around profunctors.

Finally, can someone explain what to add to Mike’s sketch of Wood’s topos-theoretic example to make it precise, rather than just “the idea” of something precise? The 2-category of toposes seems promising here because it can’t, as far as I know, be explained in simpler language.

Posted by: James on November 25, 2009 1:02 AM | Permalink | Reply to this

Re: Equipments

James wrote:

But I guess I don’t yet see why someone would bother writing down the definition of profunctor, i.e. why it’s a good concept to isolate in the abstract.

As I mentioned before, profunctors are to category theory as linear algebra is to set theory. Just as Burnside had to admit that some problems about actions of finite groups were best solved by ‘linearizing’ and thinking about group representations, category theorists have realized that some problems in category theory are best solved by ‘linearizing’ and working with profunctors.

One early hint of this is the Yoneda embedding theorem, which gives a nice functor

CC^ C \to \widehat{C}

where C^\widehat{C} is the category of presheaves on CC. C^\widehat{C} should be thought of as a ‘linearized version’ of CC, because it’s closed under addition — that is, colimits. Indeed, it’s the free category with colimits on CC, and thus analogous to the free vector space on a set.

Very often when we wish we had an object of DD, we start out knowing we have an object of D^\hat{D}. We then wonder if it came from an object of DD: that is, if it’s ‘representable’.

More generally, very often when we wish we had a functor

CD, C \to D ,

we start out knowing we have a functor

CD^ C \to \widehat{D}

A functor

CD^ C \to \hat{D}

is called a ‘profunctor’. It’s the same as a functor

C^D^ \hat{C} \to \hat{D}

that’s ‘linear’ — by which I mean colimit-preserving.

In situations like this, nature is pushing us towards working with profunctors, and only asking later if they come from functors.

Posted by: John Baez on November 25, 2009 2:03 AM | Permalink | Reply to this

Re: Equipments

C^\hat{C} should be thought of as a ‘linearized version’ of CC, because it’s closed under addition — that is, colimits.

A functor CD^C\to\hat{D} is called a ‘profunctor’. It’s the same as a functor C^D^\hat{C}\to\hat{D} that’s ‘linear’ — by which I mean colimit-preserving.

There’s a lot more to say about this analogy. For instance, if CC, DD, and EE are sets and k[C]k[C], k[D]k[D], and k[E]k[E] are the free kk-vector spaces they generate, then a linear map F:k[C]k[D]F\colon k[C]\to k[D] is determined by its matrix, i.e. elements F c dkF^d_c \in k for cCc\in C and dDd\in D, and the composite of FF with a linear map G:k[D]k[E]G\colon k[D]\to k[E] is represented by the matrix with entries (GF) c e= dDG d eF e d. (G\circ F)^e_c = \sum_{d\in D} G^e_d F^d_e. Likewise, if CC, DD, and EE are categories and PCP C, PDP D, and PEP E are their presheaf categories (I find the hat very hard to see in MathML), then a colimit-preserving functor F:PCPDF\colon P C \to P D is determined by the sets F(d,c)SetF(d,c) \in Set for cCc\in C and dDd\in D (together with action by the arrows of CC and DD)—this is just the third description of a profunctor as a functor D op×CSetD^{op}\times C\to Set. And if G:PDPEG\colon P D \to P E is another colimit-preserving functor, their composite is represented by the “matrix elements” (GF)(e,c)= dDG(e,d)×F(d,c) (G\circ F)(e,c) = \int^{d\in D} G(e,d)\times F(d,c)

We can also go on to multilinear algebra. We might call a functor C×DE^C\times D \to \hat{E} a “two-variable profunctor”, which is the same as a functor C^×D^E^\hat{C}\times\hat{D}\to \hat{E} that is “bilinear”, i.e. colimit-preserving in each variable separately. It is, of course, determined by its components F(e;c,d)SetF(e;c,d)\in Set. Now in the ordinary linear world, an algebra is a vector space together with a bilinear map F:V×VVF\colon V\times V\to V that is associative and unital. In components, associativity means vF xy vF vw u= vF yw vF xv u \sum_{v} F_{x y}^v F_{v w}^u = \sum_{v} F_{y w}^v F_{x v}^u If we translate this into profunctors, we get the notion of a category CC with a functor F:C op×C op×CSetF\colon C^{op}\times C^{op}\times C\to Set together with isomorphisms such as vF(v;x,y)×F(u;v,w)= vF(v;y,w)×F(u;x,v). \int^{v} F(v;x,y) \times F(u;v,w) = \int^{v} F(v;y,w)\times F(u;x,v). This is the notion of a promonoidal category, which is unsurprisingly the same thing as a category CC together with a closed monoidal structure on PCP C. If CC itself has a monoidal structure, then PCP C obtains a monoidal structure in a canonical way by Day convolution; analogously if GG is a monoid, then the vector space k[G]k[G] is naturally an algebra, namely the monoid algebra.

At an abstract level, what’s happening in the multilinear world is that Vect f.dimVect_{f.dim} is a compact closed category, while ProfProf is a compact closed bicategory. As far as I know, no one has formally incorporated this level of structure into equipments, although it really should exist (and it’s needed for some parts of formal category theory).

One can also imagine using an Einstein summation convention for profunctors and their “multilinear relatives”, although I’ve never seen anyone actually make use of this. Likewise, one can imagine using an abstract index notation for proarrows in an arbitrary equipment to make them look more like “familiar” profunctors.

Posted by: Mike Shulman on November 25, 2009 3:15 AM | Permalink | PGP Sig | Reply to this

Re: Equipments

Posted by: David Corfield on November 25, 2009 11:09 AM | Permalink | Reply to this

Re: Equipments

And then Penrose graphical notation?

Yes, clearly! Although that, actually, I think some people have used to a certain degree. Some of the Australian papers on monoidal bicategories, I think, make some nods in that direction.

Posted by: Mike Shulman on November 25, 2009 2:21 PM | Permalink | PGP Sig | Reply to this

Re: Equipments

John said, “As I mentioned before, profunctors are to category theory as linear algebra is to set theory. … C^\hat{C} should be thought of as a ‘linearized version’ of CC, because it’s closed under addition — that is, colimits. Indeed, it’s the free category with colimits on C, and thus analogous to the free vector space on a set.”

Great! Thanks.

So now I have a good analogy to hold onto. I can also say that the ideal of looking at functors between the presheaf categories of two given categories is formally very natural. Further, it’s not surprising to me that this is applicable — presheaf categories are examples of toposes and you can have important maps at the topos level that don’t come from maps of sites (not to mention algebraic varieties, if that’s what you’re looking at).

I think the only thing left to ask for is to see profunctors in action, something that I want to do that is done much better with profunctors than without. Are there any good examples?

Posted by: James on November 25, 2009 5:22 AM | Permalink | Reply to this

Re: Equipments

James wrote:

I think the only thing left to ask for is to see profunctors in action, something that I want to do that is done much better with profunctors than without. Are there any good examples?

Unfortunately I don’t know any examples of things you want to do that are better done with profunctors. There probably are some, but I don’t know ‘em. All I know is examples of things I want to do that are better done with profunctors.

In fact, I’m writing papers with Paul-André Melliés and Mike Stay that use profunctors to study questions coming from computer science. As you’ve probably heard, theoretical computer scientists like cartesian closed categories. By now we’re ready to study more general ‘cartesian closed gizmos’. To do this, we’d like to replace the 2-category CatCat by some other 2-category of gizmos, and transfer the definition of ‘cartesian closed category’ to this new context.

But there’s a tricky thing about cartesian closed categories. Their definition involves both covariant and contravariant functors! Indeed, if CC is a cartesian closed category, it has an ‘internal hom’

C op×CC C^{op} \times C \to C

This functor sends any pair of objects X,YCX,Y \in C to the ‘object of maps from XX to YY’, often written as Y XY^X. It’s covariant in YY and contravariant in XX.

Because of this, cartesian closed categories are not creatures that we can define using merely the 2-category structure of CatCat, where the morphisms are covariant functors and the 2-morphisms are natural transformations. We’re using some extra features of CatCat… so to define cartesian closed gizmos, our 2-category of gizmos will need to have those extra features.

What are those extra features?

At first, you might think it’s enough to note that every object of CatCat has an ‘opposite’. But the trouble runs deeper. After all, every cartesian closed category comes with an ‘evaluation’ map

ev X,Y:Y X×XY ev_{X,Y}: Y^X \times X \to Y

and this is natural in some vague sense… but it’s not a natural transformation in the technical sense, because XX appears both covariantly and contravariantly on the left here, and not at all on the right!

In fact this evaluation map is something called a dinatural transformation.

Dinatural transformations are a bit scary at first. But the ones we need can be tamed, and understood, using profunctors.

After pondering this for a while, and reading some stuff by Ross Street, it became clear that we should think about CatCat as a gadget with two kinds of morphisms: functors and profunctors!

So, it’s very interesting to read Mike Shulman write:

So what kind of formal structure includes categories, functors, and profunctors? There are several different answers, but to me, the most obvious and natural-looking answer is a double category.

This is indeed the conclusion that Paul-André and I had arrived at, starting with some questions about computer science!

Posted by: John Baez on November 26, 2009 6:03 PM | Permalink | Reply to this

Re: Equipments

Hooray! The double-category revolution continues. Defining fancy natural transformations is another great thing to use profunctors for.

I’m a little confused about the terms used for these fancy natural transformations, though. I had thought a dinatural transformation has components like F(c,c)G(c,c)F(c,c)\to G(c,c) such that some hexagon commutes, while if GG or FF is constant so that the hexagon reduces to a “wedge” (which is the situation that seems to occur most frequently) then it’s called extraordinary natural. Of course there can be extra parameters as well in either case. But the nLab page dinatural transformation seemingly uses “extranatural” to mean a transformation that is dinatural in some variables and ordinary-natural in some others. Is that common?

Posted by: Mike Shulman on November 28, 2009 12:21 AM | Permalink | PGP Sig | Reply to this

Re: Equipments

I assumed it was common! It’s in fact the original meaning as given by Eilenberg and Kelly back in 1966 when they were inventing this stuff. See for example the discussion in Kelly’s Basic Concepts in Enriched Category Theory, 17 ff. (page 23 of 143).

Posted by: Todd Trimble on November 28, 2009 1:59 AM | Permalink | Reply to this

Re: Equipments

Blast it. My memory is probably playing tricks on me again. Quite likely you’re right, and the more general things involving a mix of ordinary and extraordinary natural transformations are called generalized natural transformations. Sorry about that.

Posted by: Todd Trimble on November 28, 2009 2:15 AM | Permalink | Reply to this

Re: Equipments

Mike wrote:

I had thought a dinatural transformation has components like F(c,c)G(c,c)F(c,c) \to G(c,c) such that some hexagon commutes, while if GG or FF is constant so that the hexagon reduces to a “wedge” (which is the situation that seems to occur most frequently) then it’s called extraordinary natural.

Yes, Paul-André Melliès confirms this. And extraordinary natural transformations are also called extranatural.

Posted by: John Baez on December 13, 2009 8:30 PM | Permalink | Reply to this

geometric function theory

I think the only thing left to ask for is to see profunctors in action, something that I want to do that is done much better with profunctors than without. Are there any good examples?

Yes, there is a grand story developing from this point, which captures a wealth of classical structrues, explains a bunch of classical conjectures, and then goes on into previously uncharted territory:

it’c called geometric \infty-function theory.

Above it was explained how presheaf categories play a bit the role of vector spaces and colimit perserving maps between them, aka profunctors on the underlying sites, the role of linear maps.

But the category of presheaves over the point is just the cat of sets, which plays the role of the 1-dimensional “vector space over \mathbb{N}”. That’s a bit too puny to be of fully good use if we really want to talk about linear algebra.

The solutuiion is to pass from sets to \infty-groupoids. Via their groupoid cardinality passing to these is like passing from \mathbb{N} at least to \mathbb{Q}, but really beyond.

So what we really want to be doing is consider \infty-groupoid valued presheaf categories and colimit preserving functors between them, i.e. \infty-profunctors. In fact, we should allow yet more slight generalization and notice that we can just as well include all reflective subcategories of \infty-presheaf categories in this game.

The collection of these gadgets:

- reflective subcategories of \infty-presheaf categories

- with colimit preserving functors between them (\infty-profunctors)

organizes itself into the symmetric monoidal (,1)(\infty,1)-category of presentable (,1)(\infty,1)-categories, and denoted Pr LPr^L.

This is like a big version of VectVect, a context for lineat algebra, just much more natural.

So we can do linear algebra in Pr LPr^L and see what comes out. A good deal of what comes out has been studied by David ben-Zvi, John Francis and David Nadler in Integral Transforms and Drinfeld Centers in Derived Algebraic Geometry.

This unifies things like Fourier-Mukai transformations as higher linear algebra and serves to prove large parts of the Deligne and Kontsevich conjectures on Hochschild cohomology.

The followup article The character theory of a complex group describes more concrete applications in representation theory, with some insights on Langlands duality.

That’s one thing that profunctors, regarded as generalized linear maps, are good for.

Posted by: Urs Schreiber on November 26, 2009 7:06 PM | Permalink | Reply to this

Re: Equipments

John wrote:

Just as Burnside had to admit that some problems about actions of finite groups were best solved by ‘linearizing’ and thinking about group representations, category theorists have realized that some problems in category theory are best solved by ‘linearizing’ and working with profunctors.

But haven’t you been trying to tell us that Burnside needn’t have bothered?

Hmm, in that comment you talk of the waving a magic wand to get Perm(G)Perm(G) from Rep(G)Rep(G) by splitting idempotents. So that’s about forming the Karoubi envelope?

Posted by: David Corfield on November 25, 2009 8:54 AM | Permalink | Reply to this

Re: Equipments

Just as Burnside had to admit that some problems about actions of finite groups were best solved by ‘linearizing’ and thinking about group representations, category theorists have realized that some problems in category theory are best solved by ‘linearizing’ and working with profunctors.

But haven’t you been trying to tell us that Burnside needn’t have bothered?

Passing to profunctors is indeed more like “groupoidified linearization”/geometrization than true linearization. The graph of a profunctor is a span of categories and the composition of profunctors is composition of these spans, as Mike indicated above.

Posted by: Urs Schreiber on November 25, 2009 1:02 PM | Permalink | Reply to this

Re: Equipments

David wrote:

But haven’t you been trying to tell us that Burnside needn’t have bothered?

I was trying to tell you that instead of ‘artificially’ linearizing the category of GG-sets by choosing your favorite field and looking at the category of representations of GG on vector spaces over that field, it’s nice to ‘naturally’ linearize it by looking at the weak 2-category of

  • GG-sets
  • spans of GG-sets
  • maps of spans of GG-sets

and various other ‘spanish’ nn-categories. And as Urs pointed out, a span is a lot like a profunctor. For example, a span of groupoids

XSY X \leftarrow S \rightarrow Y

is secretly the same as a map

X×YGpd X \times Y \to Gpd

while a profunctor

XY^ X \to \hat{Y}

is the same as a map

X×YSet X \times Y \to Set

So, a span of groupoids is a generalization of a profunctor between groupoids.

Posted by: John Baez on November 25, 2009 5:58 PM | Permalink | Reply to this

Re: Equipments

Another way in for me would be to think about Richard Wood’s example above, which appears accessible to me. But I also don’t understand that. Would someone be willing to unpack the statement that his example is an equipment.

Actually, that example is an equipment for fairly boring reasons. (The surprising thing is that it’s useful to think of it that way, and that it can be constructed from cographs in the same way as many other toposes.)

It’s probably easiest to see with Wood’s definition: a 2-category KK is equipped with proarrows when we have a functor KMK\to M which is bijective on objects, locally fully faithful (i.e. induces isomorphisms on 2-cells), and such that each 1-cell in its image has a right adjoint in MM. Now let MM be any 2-category and let KK be the subcategory of MM consisting of all the objects, only the 1-cells that have right adjoints, and all the 2-cells between those. Then the inclusion KMK\to M is obviously an equipment. Wood’s example arises in this way where MM is the 2-category of toposes and left-exact functors, since a geometric morphism is just a left-exact functor having a right adjoint. (The dualization bit happens because a geometric morphism is considered to point in the direction of its right adjoint, rather than its left.)

Posted by: Mike Shulman on November 25, 2009 3:31 AM | Permalink | PGP Sig | Reply to this

Re: Equipments

When you say

zoo of “higher categorical structures”

is that using ‘zoo’ as they do in physics when they say Particle zoo? So there’s a variety of types of thing which haven’t been given equal amounts of attention, but there might be a systematic account of all of them?

Posted by: David Corfield on November 24, 2009 11:06 PM | Permalink | Reply to this

Re: Equipments

So there’s a variety of types of thing which haven’t been given equal amounts of attention, but there might be a systematic account of all of them?

I think that’s a reasonable approximation of how I feel. Some of the unequal attention is of course justified; I do think nn-categories are almost certainly the most important higher categorical structure. I just think there are others that merit more attention than they sometimes get.

Posted by: Mike Shulman on November 25, 2009 2:50 AM | Permalink | PGP Sig | Reply to this

Metric space profunctors

Carrying on with the examples of profunctors, does anyone know of any examples in analysis where profunctors/bimodules between metric spaces naturally crop up?

Let me ‘remind’ people what that means rather briefly. We can consider the monoidal category [0,][0,\infty] whose set of objects is 0\mathbb{R}_{\ge 0}\cup \infty with a morphism from xx to yy precisely when xyx\ge y, and the monoidal product on objects is just addition xyx+yx\otimes y \coloneqq x+y. We can now do enriched category theory over [0,][0,\infty], and, unpacking the definition, a [0,][0,\infty]-category is a set XX with a function d:X×X[0,]d:X\times X\to [0,\infty] which is like a metric in that it satisfies the triangle inequality and has d(a,a)=0d(a,a)=0 for all aXa\in X, but for which

  • the ‘metric’ dd is not necessarily symmetric,
  • d(a,b)=0d(a,b)=0 does not imply that a=ba=b,
  • the distance between two points might be infinite.

In particular, any metric space can be considered as a [0,][0,\infty]-category. So we can ask what the standards notions of enriched category theory translate to in metric space language.

  • A functor between metric spaces XX and YY is precisely the same as a distance non-increasing function XYX\to Y: this is pretty natural from a metric space perspective.
  • A presheaf on a metric space XX is then a non-negative function X 0X\to\mathbb{R}_{\ge 0} which doesn’t increase the distance (or else is the constant map to \infty).
  • The presheaf space X^\hat X or PXPX is the set of such non-negative functions with the metric d(f,g)sup x(f(x),g(x)).d(f,g)\coloneqq sup_x(f(x),g(x)). Actually this fails to be a metric space in the classical sense because we might need infinite distances, but that’s not too drastic.
  • The Yoneda embedding is the distance preserving function XPXX\to PX which sends a point xx to the distance-from-xx function.
  • A profunctor or bimodule is then a distance non-increasing function K:X×Y 0K\colon X\times Y\to \mathbb{R}_{\ge 0} which should be should of as a kernel, convolution (see below) with which sends non-negative, distance non-increasing functions on YY to the same kind of thing on XX.
  • The convolution K¯(ϕ):X 0\bar{K}(\phi):X\to \mathbb{R}_{\ge 0} of a function ϕ:Y 0\phi:Y\to \mathbb{R}_{\ge 0} with a function K:X×Y 0K:X\times Y \to \mathbb{R}_{\ge 0} here is here defined by K¯(ϕ)(x)inf yY{K(x,y)+ϕ(y)}forxX.\bar{K}(\phi)(x)\coloneqq inf_{y\in Y}\big\{K(x,y)+\phi(y)\big\}\quad for x\in X.

So my question is “Do these kinds of kernels crop up in metric space theory?”

Posted by: Simon Willerton on November 25, 2009 6:50 PM | Permalink | Reply to this

Re: Metric space profunctors

Cool! Being too ignorant to explain any details, I can only remark that the “profunctors” are Chu spaces over 0\mathbb{R}_{\geq 0} (what about their morphisms?), and the convolution map is kind of a Legendre transform and also appears in optimal transport theory, e.g. eq. (5.5) here.

Posted by: Tobias Fritz on November 25, 2009 9:30 PM | Permalink | Reply to this

Re: Metric space profunctors

Well, I don’t know if it goes without saying, but trying to explain this to us is one way of becoming less ignorant…

Posted by: Simon Willerton on November 26, 2009 12:14 PM | Permalink | Reply to this

Re: Metric space profunctors

There seems to be such a thing as a cc-transform, which for XX and YY Polish spaces, lower semicontinuous c:X×Y[0,){+}c: X \times Y \to [0, \infty) \cup \{+\infty\} and ϕ:Y{}\phi: Y \to \mathbb{R} \cup \{-\infty\}, is defined as

ϕ c(x)=inf{c(x,y)ϕ(y):yY}. \phi^c(x) = inf \{c(x, y) - \phi(y): y \in Y \}.

It’s mention on p. 7 here. Not exactly what you want, but not too far either.

Posted by: David Corfield on November 26, 2009 1:10 PM | Permalink | Reply to this

Re: Metric space profunctors

Note that lower semicontinuous functions to [0,][0,\infty] are simply continuous functions to the quasimetric space [0,],(x,ymax{0,yx})[0,\infty], (x,y \mapsto \max\{0,y - x\}), which is the natural closed monoidal structure on [0,][0,\infty] as a Lawvere metric space.

So we really should not be surprised to see them showing up, even if we might prefer that they be short maps.

Posted by: Toby Bartels on November 26, 2009 8:41 PM | Permalink | Reply to this

Re: Metric space profunctors

Speaking of continuous functions, is there any slick categorial description of continuous functions between Lawvere metric spaces?

Posted by: Toby Bartels on November 29, 2009 6:41 PM | Permalink | Reply to this

Re: Metric space profunctors

And when are you going to give an enriched category-theoretic version of Hodge Theory on Metric Spaces?

Posted by: David Corfield on December 3, 2009 11:10 PM | Permalink | Reply to this

Re: Metric space profunctors

The paper that David links to — by Bartholdi, Schick, Smale and Smale — looks amazing! And something in the abstract got me going:

This motivates us to develop a version of Hodge theory on metric spaces with a probability measure.

(Why did it get me going? Because of this, which is all about probability metric spaces.)

Unfortunately, I think I’d need months or possibly years to understand this paper… And from a brief skim, I really have no idea what it’s about. Does anyone else? David?

Posted by: Tom Leinster on December 3, 2009 11:59 PM | Permalink | Reply to this

Re: Metric space profunctors

The book Tobias referred to is available on google books: Optimal transport: old and new by Cédric Villani. Chapter 5 on cyclical monotonicity and Kantorovich duality seem to be the relevant bit. It looks to be of a decidedly profunctorial nature. I wonder if Kantorovich duality (whatever that might be) can be translated into enriched category theory…

Posted by: Simon Willerton on November 26, 2009 4:48 PM | Permalink | Reply to this

Re: Metric space profunctors

So let me try to explain my current vey basic understanding of this.

Optimal transport is about the following: imagine you have a pile of sand distributed on a (Polish?) space XX; mathematically, a pile of sand is a probability measure on XX. Now given such a pile of sand, how much effort does it take to transport the sand around such that one ends up with another given pile? The information one has is that of the cost function c(x,y)c(x,y). It specifies the effort needed to transport a unit of sand from xx to yy. This is the basic problem of optimal transport theory. In principle, yy can lie in a different space YY.

There are two ways to make the phrase “transport the sand around” precise. In the first, one considers (continuous?) functions f:XYf:X\rightarrow Y; specifying such a function means saying that all the sand which is originally at xx will be moved to f(x)f(x). The second possibility considers probability measures on X×YX\times Y, which have the given measures on XX and YY as marginals; in this setting, one can take the sand at xx and redistribute it arbitrarily over all of YY. Under the right technical assumptions, these two yield the same optimal cost, although it’s only an infimum in the first setting, and a proper minimum in the second.

The second setting is also more natural from a theoretical point of view. The problem then turns into an infinite-dimensional linear program. And if I get this right, Kantorovich duality then is morally nothing but linear programming duality in this special case. There is a more intuitive explanation of Kantorovich duality in the book chapter I mentioned, but I’m still busy with trying to grasp that.

Posted by: Tobias Fritz on November 26, 2009 11:17 PM | Permalink | Reply to this

Re: Metric space profunctors

Thanks for that Tobias. Do you have any idea what the reason for doing this with Polish spaces is? I have absolutely no feeling for what a Polish space is.

Posted by: Simon Willerton on December 2, 2009 10:44 AM | Permalink | Reply to this

Re: Metric space profunctors

All answers to be added to nLab.

Posted by: David Corfield on December 2, 2009 11:20 AM | Permalink | Reply to this

Polish spaces

Simon wrote:

I have absolutely no feeling for what a Polish space is.

Don’t be scared!

A Polish space is just a slightly nice sort of topological space: one that’s homeomorphic to a complete separable metric space. Unless you’re a glutton for punishment, the topological spaces you like best are probably Polish spaces. So you don’t need to have any particular feeling for them, except a warm and fuzzy feeling: these are the topological spaces you like.

But what really matters — usually, and apparently here! — is the measurable space you get from taking a Polish space with its σ\sigma-algebra of Borel sets. This is called a ‘standard Borel space’. Standard Borel spaces are often the right context in which to do measure theory.

So I think Tobias really meant ‘standard Borel space’… but people often say ‘Polish space’, because they’re a bit careless about which category they’re thinking about: topological spaces or measurable spaces.

On the one hand, you’d have to be a real fiend to think of a measure space that’s not a standard Borel space. But on the other, there’s an incredibly beautiful classification of standard Borel spaces. I explained it in week272.

They’re classified by their cardinality! — which must be finite, countably infinite, or the cardinality of the continuum.

If you start wanting a nice category of measurable spaces, you’ll inevitably be led to standard Borel spaces, and thus Polish spaces. It happened to me, it happened to David Corfield, and if you’re not careful it could happen to you. Luckily they are very nice when you get to know them!

Posted by: John Baez on December 3, 2009 11:48 PM | Permalink | Reply to this

Re: Polish spaces

Jolly good!

Posted by: Simon Willerton on December 4, 2009 12:30 AM | Permalink | Reply to this

Re: Polish spaces

Sorry for not following this more closely. The internet is a great place for scientific collaboration, but it’s also a huge timesink.

Well, to be honest I didn’t mean anything precise in my previous post, since I don’t know the technical assumptions required for proving that the two optimization problems I described have the same optimal values. But at least the optimal transport problem makes good sense in the second formulation for any pair of measurable spaces XX and YY, and I wonder whether one can then prove the existence of an optimal transportation plan in a setting where the cost function c(x,y)c(x,y) is any measurable function taking real non-negative values. On the other hand, optimizing over functions XYX\rightarrow Y fails even in the case where XX is finite, since generically there is no function mapping the given measure on XX to the given measure on YY.

In any case, Simon’s observations are very intriguing, indeed!

My own motivation for starting to look into optimal transport was different: it originated from trying to contemplate a version of noncommutative geometry that doesn’t use function algebras as the basic objects, but spaces of probability measures (e.g. as convex spaces); the starting point is the paper

Francesco D’Andrea, Pierre Martinetti: A view on transport theory from noncommutative geometry.

Finally, one might have something like the following: suppose we have a Chu space over 0\mathbb{R}_{\geq 0},

ev:X×Y 0ev: X\times\Y\longrightarrow\mathbb{R}_{\geq 0}

Morally, XX is a set of probability measures over some non-existing space, while YY encodes the geometry as being the set of Lipschitz functions with Lipschitz constant 11 on that space. The map evev sends a measure and a function to the expectation value of that function under that measure. One now obtains a pseudometric on XX with values in {}\mathbb{R}\cup\{\infty\} by setting

d(x 1,x 2)=sup yY|ev(x 1,y)ev(x 2,y)|d(x_1,x_2) =\sup_{y\in Y}|ev(x_1,y)-ev(x_2,y)|

Has anyone studied metric geometry of Chu spaces in this sense? E.g. dimension or curvature properties? I suspect that metrics of this kind crop up very frequently; another example besides noncommutative geometry and optimal transport is the diamond norm between quantum channels.

Posted by: Tobias Fritz on December 4, 2009 1:11 PM | Permalink | Reply to this

Re: Metric space profunctors

The most naive problem described in Chapter 5 of the book definitely fits in to the enriched category framework – I’ll give my understanding of it below. What I find interesting is that we have metric spaces with probability measures cropping up again very close to category theoretic ideas: we saw this before as a way of modeling ecosystems in Tom’s diversity measure work.

The naive problem, involving no probability measures, is the following. Suppose we have a consortium consisting of some bakeries and some shops. Let BB be the set of bakeries and equip this with the metric dd where d(b,b)d(b,b') is the cost of transporting one loaf of bread from bakery bb to bakery bb'. If ϕ(b) 0\phi(b)\in \mathbb{R}_{\ge 0} is the cost of producing a loaf of bread at bakery bb, then ϕ\phi had better be a presheaf on BB (i.e., a distance non-increasing function) otherwise that would mean there were bakeries, say Hovis and Warburtons, with ϕ(Hovis)>ϕ(Warburtons)+d(Warburtons,Hovis)\phi(Hovis)\gt \phi(Warburtons)+d(Warburtons,Hovis) so it would be cheaper to bake a loaf at the Warburtons bakery and ship it to the Hovis bakery than it would be to bake it at the Hovis bakery, and so, assuming the bakeries can bake arbitrarily large amounts of bread, it would be uneconomic to keep open the Hovis bakery.

Similarly we have a set CC of cafes which will sell the bread to the public. This also has a metric dd with d(c,c)d(c,c') being the price of transporting a loaf of bread from cafe cc to cafe cc'. The price at which these cafes sell bread should be a presheaf on CC for the same economic reasons described above.

We wish to transport bread from bakeries to cafes. We have the cost K(b,c) 0K(b,c)\in\mathbb{R}_{\ge 0} of transporting one loaf of bread from bakery bb to cafe cc. We know the cost of transporting bread between bakeries and between cafes as these cost are given by the two metrics. This function transport KK should be a bimodule/profunctor as otherwise you could get a cheaper transport cost by diverting via a different cafe or bakery. What you possibly have in your mind now is the picture of a collage as described by Tom Leinster below; namely a “metric” on the union BCB\cup C of bakeries and cafes, extending the individual metrics, but which is not symmetric between cafes and bakeries – you can go from bakeries to cafes but not vice versa.

The cost of baking a loaf at bakery bb and transporting to cafe cc is ϕ(b)+K(b,c)\phi(b)+K(b,c), so the least cost of getting a loaf to cafe cc is inf b{ϕ(b)+K(b,c)}.\inf_b\{\phi(b)+K(b,c)\}. This is precisely the definition of the evaluation at cc of the convolution of the bimodule KK with the presheaf ϕ\phi. I wrote this convolution as K¯(ϕ)\bar{K}(\phi) in the above post, but can write it as ϕK\phi\otimes K if I’m thinking in the bimodule language. So whatever price ψ(c)\psi(c) you sell the bread at at cafe cc it had better be at least the above amount (otherwise you won’t make any profit). This means we need ψ(c)(ϕK)(c)c\psi(c)\ge (\phi\otimes K )(c)\quad \forall c which means in the category theory language that a pricing ψ\psi of loafs in the cafes is economic if it comes with a presheaf map ψϕK.\psi\to \phi\otimes K. Hmmm. I don’t know if that’s made it clear to anyone. I also don’t know how much further the translation to enriched category theory will go. I note that the “dual” problems involve suprema rather than infima and that for [0,][0,\infty]-categories inf\inf is the coproduct and sup\sup is the product (see Lawvere’s classic paper).

Posted by: Simon Willerton on November 27, 2009 10:21 AM | Permalink | Reply to this

Re: Metric space profunctors

I guess I’ve confused the notation somehow, by simultaneously thinking about kernels and bimodules, so I should probably have said either

there is a morphism of presheaves over CC ψK¯(ϕ)\psi\to \bar{K}(\phi)

or, equivalently, in a different language

there is a map of right CC-modules ψϕ BK\psi\to \phi\otimes_B K

If I’m talking about profunctors as being bimodules then I should talk about presheafs being right (or left) modules.

Posted by: Simon Willerton on November 27, 2009 12:25 PM | Permalink | Reply to this

Re: Metric space profunctors

Hmmm. I don’t know if that’s made it clear to anyone.

Yes, that makes great sense, and you even justified it in the category of short maps instead of continuous maps like the other references had. It even made sense when you wrote

a presheaf map ψϕK \psi \to \phi \otimes K

By the way, when you write

a “metric” […] which is not symmetric

the standard term for such a “metric” is ‘quasimetric’.

Posted by: Toby Bartels on November 27, 2009 2:41 PM | Permalink | Reply to this

Re: Metric space profunctors

Thanks very much for writing this up - this is an excellent example! I’m currently doing an informal seminar series on enriched categories, internal categories, and other such things for non-category theorists. This will be a great example to discuss the use of enriched profunctors (if you don’t mind me using it).

Posted by: Geoff Cruttwell on November 27, 2009 4:48 PM | Permalink | Reply to this

Re: Metric space profunctors

Geoff, it would be a bit silly of me to post this on a public forum if I minded you using it! I would to happy to hear if you extended this example any further.

Posted by: Simon Willerton on November 29, 2009 5:58 PM | Permalink | Reply to this

Re: Metric space profunctors

Tobias, is this the kind of thing you think about in general? I never cease to be amazed by the variety of things that Café partrons work on.

Posted by: Simon Willerton on November 27, 2009 10:38 AM | Permalink | Reply to this

Re: Metric space profunctors

I’m sure there’s a snappy slogan to be had here designed to recruit future category theorists, along the lines of “Join the Navy and see the world.” Then we could have quotes from old hands, like Tom:

One reason I went into category theory is that I wanted a subject that would take me to different parts of the mathematical world.

Posted by: David Corfield on November 27, 2009 11:46 AM | Permalink | Reply to this

Re: Metric space profunctors

I don’t really understand what is meant by convexity in all this, nor why it is relevant for the Legendre transform, but a function being KK-convex (whatever that means) seems to be the same as being as the function being an algebra for the monad KK{-}\odot K \lhd K. (My KK is what is called cc in the book.) I’ll try to explain what I mean by this.

The important thing to note is that sup cC(ϕ(c)K(b,c))sup_{c\in C}(\phi(c)-K(b,c)) which crops up has a natural interpretation as, in Mike’s notation, (ϕK)(b)(\phi \lhd K)(b). Here the operation K{-}\lhd K is right adjoint to the operation K{-}\odot K. Let me first remind you what these two operations are in the world of bimodules.

Suppose we have algebras AA, BB and CC; a BB-AA-bimodule BM A{}_B M_A; a CC-BB-module CP B{}_C P_B; and a CC-AA-bimodule CN A{}_C N_A. We can tensor over BB with BM A{}_B M_A to turn PP into a CC-AA-module, this is the composition denoted \odot by Mike: CP B B BM A= CP B BM A.{}_C P_B \otimes_B {}_B M_A ={}_C P_B \odot {}_B M_A.

On the other hand we can turn CN A{}_C N_A into a CC-BB-bimodule by taking the space of right AA-module maps into it, this is the thing denoted \lhd by Mike:

Hom A( BM A, CN A)= CN A BM A.Hom_A({}_B M_A,{}_C N_A) = {}_C N_A \lhd {}_B M_A.

These two operations are adjoint and we have the unit and counit maps:

CP BHom A( BM A, CP B B BM A),p(mpm);{}_C P_B\to Hom_A({}_B M_A,{}_C P_B \otimes_B {}_B M_A), \qquad p\mapsto (m\mapsto p\otimes m); Hom A( BM A, CN A) B BM A CN A,fmf(m).Hom_A({}_B M_A,{}_C N_A) \otimes_B {}_B M_A\to {}_C N_A, \qquad f\otimes m\mapsto f(m).

So via the usual yoga we have a monad

Hom A( BM A,) B BM AorMM.Hom_A({}_B M_A,{-}) \otimes_B {}_B M_A\quad or \quad {-}\odot M \lhd M.

Back in the world of bakeries and the like, we had that K:B×C 0K\colon B\times C\to \mathbb{R}_{\ge 0} was our kernel or bimodule, then the KK-transform (Defn 5.2) of a function ψ:B 0\psi\colon B\to \mathbb{R}_{\ge 0} is ψ K\psi^K (more notation for the same thing!) defined to be ψK\psi\odot K, and the KK-transform (Defn 5.7) of a function ϕ:C ge0\phi\colon C\to \mathbb{R}_{ge 0} is ϕ K\phi^K defined to be ϕK\phi\lhd K. Then a function ψ:B 0\psi\colon B\to \mathbb{R}_{\ge 0} is KK-convex (Prop 5.8) if and only if ψKK=ψ\psi\odot K \lhd K=\psi. But we have the unit map for the monad so we know ψKKψ\psi\odot K \lhd K\le \psi, and so equality is equivalent to ψKKψ\psi\odot K \lhd K\ge \psi which I think suffices for ψ\psi being an algebra for KK{-}\odot K \lhd K.

Actually I haven’t done exactly what is in the book, as they consider functions defined on the whole of \mathbb{R} but I don’t know if that makes any differences. It’s still intriguing, none-the-less.

Posted by: Simon Willerton on November 29, 2009 5:43 PM | Permalink | Reply to this

Re: Metric space profunctors

Following Tobias’ comment that the convolution with a kernel looks like the Legendre transform, I noticed (following a period of googling) that what is going on here is similar to tropical mathematics. I’ve asked a question at mathoverflow to see if anyone knows any formal connection. Tropical mathematics has cropped up here at the Café on several occasions.

Posted by: Simon Willerton on December 2, 2009 10:54 AM | Permalink | Reply to this

Re: Metric space profunctors

A profunctor or bimodule from XX to YY can be thought of as a way of metrizing the disjoint union X+YX + Y of the underlying sets, in such a way that the induced metrics on XX and YY are the original ones, and the distance from any point of YY to any point of XX is \infty.

In the general enriched context, every bimodule MM from A\mathbf{A} to B\mathbf{B} has a collage, which is the enriched category obtained by taking the disjoint union of the categories A\mathbf{A} and B\mathbf{B}, then ‘throwing in arrows from A\mathbf{A} to B\mathbf{B} as dictated by MM’.

E.g. suppose you’re enriching over the two-element totally ordered set {,}\{\bot, \top\}, so that enriched categories are (pre)ordered sets. If MM has constant value \top then its collage is the ordered set A+BA + B in which every element of AA is less than every element of BB. When AA and BB are ordinals, this is their ordinal sum.

Posted by: Tom Leinster on November 26, 2009 12:55 PM | Permalink | Reply to this

Re: Metric space profunctors

In the general enriched context, every bimodule M from A\mathbf{A} to B\mathbf{B} has a collage, which is the enriched category obtained by taking the disjoint union of the categories A\mathbf{A} and B\mathbf{B}, then ‘throwing in arrows from A\mathbf{A} to B\mathbf{B} as dictated by MM’.

That should be the cograph of the profunctor, I suppose.

Posted by: Urs Schreiber on November 26, 2009 2:40 PM | Permalink | Reply to this

Re: Metric space profunctors

Tom, yes. I guess I should have mentioned the collage point of view, if just to say that it doesn’t satisfy me! I wanted to stay in the realm of classical, i.e. symmetric, metric spaces, and the collage is not a metric space in that sense. Whilst I agree that this is sometimes a useful perspective it’s often not how profunctors are thought of in practice – as a rule algebraists don’t think of a bimodules as a two-object category with morphisms going between them in only one direction. (I would very much love an algebraist to pipe in at this point “I do!”)

Posted by: Simon Willerton on November 26, 2009 3:28 PM | Permalink | Reply to this

Re: Metric space profunctors

OK, but there’s a kind of ‘symmetric collage’ construction for metric spaces that might relieve you of some of your dissatisfaction.

This works as follows. Given symmetric metric spaces XX and YY, a profunctor or bimodule from XX to YY can be regarded as a way of symmetrically metrizing the disjoint union X+YX + Y, in such a way that the induced metrics on XX and YY are the original ones.

It’s true that this doesn’t correspond to any common view of bimodules in algebra. But the fact that it’s an insight particular to the context of metric spaces doesn’t stop it being useful.

Posted by: Tom Leinster on November 26, 2009 5:12 PM | Permalink | Reply to this

Re: Metric space profunctors

I find the symmetrization to be a very violent thing to do to a poor, defenceless quasimetric space. If you are going to start going around doing that everywhere then you ought to have better justification for it than just attempting to satisfy me. And whilst I know you’re the kind of chap who likes to see me happy, I also know you’re the kind of chap who would have better, deeper and more cunning justification.

Anyway, I hope you saw that I bumped into an example above of metric spaces which convinced me that the unsymmetrized collage can be a perfectly natural construction.

Posted by: Simon Willerton on November 27, 2009 5:45 PM | Permalink | Reply to this

Re: Metric space profunctors

Simon wrote:

… as a rule algebraists don’t think of a bimodules as a two-object category with morphisms going between them in only one direction.

As a rule no, but when trying to develop the theory of ‘A A_\infty modules of A A_\infty rings’ this perspective can be handy.

Posted by: John Baez on November 26, 2009 8:30 PM | Permalink | Reply to this

Re: Equipments

By the way, your double category setup acts as if profunctors can be composed in a strictly associative way.

That’s not true unless you do a bit of fiddling around, e.g. by treating them as cocontinuous functors between presheaf categories.

But luckily — as you probably know — there’s a general theory of ‘pseudo double categories’ where the arrows in one direction don’t compose in a strictly associative way:

And, the first paper here presents a general theorem (Theorem 7.5) saying that every pseudo double category is equivalent to one of the usual ‘strict’ kind.

(I was going to post a comment asking if such a theorem existed, but then I saw it does! So, I wrote this — and added some information to the nLab article on double categories.)

Posted by: John Baez on December 3, 2009 11:01 PM | Permalink | Reply to this

Re: Equipments

In his framed bicategories paper (the beginning of Section 2) Mike explains that he uses double category to mean what others would call a pseudo double category, and it is very clear from his examples that the associativity morphisms in one direction are not definitely not identities. I guess he’s using the same convention here.

Posted by: Simon Willerton on December 4, 2009 12:01 AM | Permalink | Reply to this

Re: Equipments

Yes, Simon’s right. Just as we say “n-category” around here to mean “weak n-category,” I tend to say “double category” to mean “(possibly) weak double category.” But thanks for pointing that out; I tend to forget that some people used to the strict-by-default terminology might be confused.

Posted by: Mike Shulman on December 4, 2009 4:27 AM | Permalink | PGP Sig | Reply to this

Re: Equipments

Hey Mike — was it you who proved that Wood’s definition of a proarrow equipment is equivalent to this formulation in terms of pseudo double categories, or was it someone else? I want to cite someone in my paper with Melliès.

Quite a lot of gall, using ‘double category’ to mean ‘pseudo double category’ without any explanation! Sounds like something I’d have done — in my youth.

And another question: do know if someone has studied the symmetric monoidal version of equipments? E.g., Cat is a cartesian 2-category and Prof is a symmetric monoidal bicategory, and they get along. We need this stuff. But don’t invent it just ‘cause I asked! You should leave some work for us.

Posted by: John Baez on December 30, 2009 12:15 AM | Permalink | Reply to this

Re: Equipments

John wrote:

Hey Mike — was it you who proved that Wood’s definition of a proarrow equipment is equivalent to this formulation in terms of pseudo double categories, or was it someone else?

If it was Verity, could you point me to chapter and verse? I have his top-secret thesis, but I wasn’t able to find this stuff in there.

Posted by: John Baez on December 30, 2009 1:02 AM | Permalink | Reply to this

Re: Equipments

was it you who proved that Wood’s definition of a proarrow equipment is equivalent to this formulation in terms of pseudo double categories[?]

As far as I know, yes. Verity constructs a double category from an equipment, but as far as I know, I was the first to point out how to characterize the double categories that arise in that way—although very similar ideas do occur in other work on equipments. (Actually, historically I came to it from the other side—I started studying these kinds of double categories and only later realized that they were the same as proarrow equipments.) I gave a talk about it in Sydney (with Verity in the audience) and no one said anything like “actually, that’s in so-and-so’s obscure paper from umpteen years ago.”

Quite a lot of gall, using ‘double category’ to mean ‘pseudo double category’ without any explanation!

Actually, that was just a mistake; I should have explained. (And I do, in formal mathematical writing.) But I tend to forget, when writing informal things like blog posts, that some people are more finicky about using different words for strict things and weak ones.

And while we’re talking about strictness, I should point out that (as you probably know) Wood’s original definition in terms of a functor KMK\to M allowed both KK and MM to be bicategories, not necessarily strict 2-categories, while in the version you get from a pseudo double category, MM is a bicategory but KK is always a strict 2-category. That’s what one most often sees in practice, of course: CatCat is a strict 2-category but ProfProf is only a bicategory. But if you want the full generality of Wood’s definition then you need double categories that are pseudo in both directions, like Verity’s “double bicategories” (which is of course the reason that Verity defined those).

Posted by: Mike Shulman on December 30, 2009 1:50 AM | Permalink | PGP Sig | Reply to this

Re: Equipments

On a more lowbrow note: does anyone know how to draw barred arrows in xymatrix diagrams? They’re not among the arrow shaft styles listed in the User’s Guide.

People who use profunctors need barred arrows!

Posted by: John Baez on December 30, 2009 12:27 AM | Permalink | Reply to this

Re: Equipments

does anyone know how to draw barred arrows in xymatrix diagrams?

This seems like it should be a common question, so I added some information to the nLab page about how to produce barred arrows in various contexts. In Xypic, I use \ar[r]|-@{|} which I think comes out pretty nice. I’d be interested to hear if anyone has other techniques.

Posted by: Mike Shulman on December 30, 2009 2:04 AM | Permalink | PGP Sig | Reply to this

Re: Equipments

Thanks!

Posted by: John Baez on January 3, 2010 5:15 AM | Permalink | Reply to this

Re: Equipments

This is really nifty stuff. I think I’ve found a typo, though: where you say ‘such that the composites… [diagrams] … are both equal to U fU_f’, the diagrams are the same. Maybe you meant one of them to involve the squares for B(f,1)B(f,1).

I have a question too: the nlab entry on equipments mentions internalizing hom-objects and profunctors in a 2-category using comma objects. I can see how Span(C)Span(C) becomes a framed bicategory, by taking the cartesian filler of AACBBA' \to A \leftarrow C \to B \leftarrow B' to be the limit of that diagram, and in particular how the filler of a niche over the identity span is just the pullback of the vertical arrows. Is there a nice way to make this work with comma objects instead of pullbacks? Does it perhaps involve weighted limits (I don’t really understand those yet)?

(I also thought of the 2-sided fibration (dom,cod):AA 2A(dom,cod): A \leftarrow A^{\mathbf{2}} \to A, and of how a comma object (also a 2-sided fibration, I think, via the projections, at least in CatCat) is a strict limit over a diagram involving that, but I don’t think (dom,cod)(dom,cod) is the identity for any sort of composition of spans, so maybe it’s a red herring.)

Posted by: Finn Lawler on January 3, 2010 5:00 AM | Permalink | Reply to this

Re: Equipments

I also thought of the 2-sided fibration (dom,cod):AA 2A(dom,cod):A\leftarrow A^{\mathbf{2}}\to A, and of how a comma object (also a 2-sided fibration, I think, via the projections, at least in CatCat) is a strict limit over a diagram involving that, but I don’t think (dom,cod)(dom,cod) is the identity for any sort of composition of spans, so maybe it’s a red herring.

Actually, that’s exactly right! (dom,cod)(dom,cod) is the identity for the composition, not of spans, but of 2-sided fibrations (which, in CatCat, are equivalent to profunctors). The trick is in defining what you mean by “composition of 2-sided fibrations” in such a way as to reproduce the usual composition of profunctors.

Here’s the neatest almost-definition that I know. Let KK be a strict 2-category with strict finite 2-limits, and enough well-behaved strict colimits that we can construct the proarrow equipment Prof̲(K 0)\underline{Prof}(K_0) of internal categories, functors, and profunctors in its underlying 1-category K 0K_0. If KK is CatCat, then Cat(Cat 0)Cat(Cat_0) consists of strict double categories, strict double functors, and “strict double profunctors.”

Now, for any object AKA\in K, the two projections A 2AA^{\mathbf{2}} \rightrightarrows A are in fact the (source, target) maps of an internal category in K 0K_0, which we call ΦA\Phi A. In CatCat, this means that we regard a category AA as a strict double category whose vertical and horizontal morphisms are both the morphisms of AA, and whose 2-cells are commutative squares in AA. Similarly, any morphism f:ABf\colon A\to B in KK induces an internal functor Φf:ΦAΦB\Phi f\colon \Phi A \to \Phi B in K 0K_0, and any 2-cell in KK induces an internal natural transformation in K 0K_0, so we have a 2-functor from KK to the 2-category Cat(K 0)Cat(K_0) of internal categories in K 0K_0 (which is, of course, the vertical 2-category of Prof̲(K 0)\underline{Prof}(K_0)).

Now a 2-sided discrete fibration H:ABH\colon A⇸B in KK is defined to be an internal profunctor H:ΦAΦBH\colon \Phi A ⇸ \Phi B in K 0K_0 which is representably discrete, as an object of the 2-category K/(A×B)K/(A\times B) (i.e. all hom-categories into it are discrete). You can check that in CatCat this is equivalent to the usual definition. Finally, the proarrow equipment DFib̲(K)\underline{DFib}(K) is the sub-equipment of Prof̲(K 0)\underline{Prof}(K_0) consisting of the objects of the form ΦA\Phi A, arrows of the form Φf\Phi f, proarrows that are 2-sided discrete fibrations, and all 2-cells.

Unfortunately, I’ve been lying through my teeth, because there are basically no 2-categories having colimits that are well-enough behaved to allow internal profunctors in K 0K_0 to be composed (so that the double category Prof̲(K 0)\underline{Prof}(K_0) is well-defined). For this you need K 0K_0 to have coequalizers preserved by pullback, and this is just false even in the 1-category CatCat. (The problem has nothing to do with strictness, either.) There are various remedies, such as observing that colimits do sometimes behave okay when pulled back along internal fibrations, or introducing a suitable factorization system on KK; you can have a look at Street’s “Fibrations in bicategories” or Carboni-Johnson-Street-Verity’s “Modulated bicategories.” I think a cleaner solution, however, is to stop demanding that profunctors can always be composed, i.e. to use instead a “virtual equipment” as defined in this paper. Then all you need is for KK to have finite limits.

The seminal paper about doing category theory with internal 2-sided discrete fibrations is Street’s “Fibrations and Yoneda’s lemma in a 2-category.” It doesn’t use the language of proarrow equipments, but it’s a nice exercise to reformulate everything he does in equipment-language and see that it agrees with the general notions. Also worth reading are Street’s “Elementary cosmoi,” Street and Walters’ “Yoneda structures on 2-categories”, and Weber’s “Yoneda structures from 2-toposes.”

Posted by: Mike Shulman on January 4, 2010 3:28 AM | Permalink | PGP Sig | Reply to this

Re: Equipments

Thanks for this. It’s going to take me a while to understand it all, though!

Let me just think aloud for a bit… Working through this construction for a 1-category CC with finite limits, and Φ:CCat(C)\Phi : C \to Cat(C) the ‘discrete internal category’ functor, gets you Span(C)Span(C) as an equipment, I think, which sounds right. Then it makes sense (to me) to think of A 2AA^{\mathbf{2}} \rightrightarrows A in KK as — roughly — the ‘locally discrete double category’ on AA (which is exactly right in CatCat), with structure maps induced from the obvious ones between 1\mathbf{1}, 2\mathbf{2} and 3\mathbf{3}. A 1-cell ff goes to (f,f 2)(f,f^{\mathbf{2}}). A 2-cell α:fg:AB\alpha : f \Rightarrow g : A \to B is given by a functor α:2K(A,B)\alpha : \mathbf{2} \to K(A,B), which by the universal property of powers gives a unique 1-cell AB 2A \to B^{\mathbf{2}}. Not quite sure about the naturality axioms, but otherwise OK so far, I think.

An internal profunctor will be a span AHBA \leftarrow H \to B, with an action on HH of the arrow-objects of B op×AB^{op} \times A, satisfying some conditions that I can write down but are a bit mystifying in this case.

So this is where I get a bit lost. Although seeing the comma-object version as a kind of categorification of the strict-pullback version is nice.

I’ll keep trying. Thanks for the references, too. I’ll check out the ones I can get at.

Posted by: Finn Lawler on January 7, 2010 8:37 PM | Permalink | Reply to this

Re: Equipments

Would it help to understand the conditions if I point out that a functor BAB\to A is a cloven fibration if and only if it is a pseudo-algebra for the 2-monad on Cat/ACat/A which maps XAX\to A to A 2×XAA^{\mathbf{2}}\times X\to A? A “2-sided” version of this tells you that a span AHBA\leftarrow H \to B is a 2-sided fibration iff it is a Φ(A)\Phi(A)-Φ(B)\Phi(B)-bimodule, and then you just have to add discreteness.

Posted by: Mike Shulman on January 8, 2010 6:58 PM | Permalink | PGP Sig | Reply to this

Re: Equipments

Ah! OK, that makes a lot more sense.

Let’s see — this 2-monad, FF say, should be induced by composition with the monad ΦA\Phi A in Span(Cat)Span(Cat), i.e. internal category in CatCat, and to give F(p:BA)F(p : B \to A) an FF-algebra structure is to make the corresponding span AB1A \leftarrow B \to 1 into a left (or possibly right) ΦA\Phi A-module/algebra. Then it’s not at all surprising that a 2-sided fibration should be a bimodule.

This looks like what Street does in section 3 of ‘Fibrations in Bicategories’, which I’ve been looking at (though largely in vain).

So what’s an FF-algebra κ:Fpp\kappa : F p \to p? Its domain is A 2× ABA^\mathbf{2} \times_A B, the pullback of pp along the ‘target’ map of ΦA\Phi A. In CatCat, an object of this is a morphism apba \to p b of AA for some bBb \in B, and an arrow is a square with one side equal to pϕp \phi for ϕ\phi an arrow of BB. κ\kappa is a morphism over AA, so we must have κp=domπ\kappa \circ p = dom \circ \pi, where π\pi is the projection out of the pullback. In other words, κ\kappa sends apba \to p b to some object in BB over aa, and likewise for squares.

If this is right, then these arrows f:apbf : a \to p b are the ones we want cartesian lifts for, and I’d guess that κ(f)\kappa(f) will be the domain f *bf^* b of the lift of ff. The unit and associativity axioms should (?) impose pseudofunctoriality. But I can’t quite see where the cartesian lifts magically pop out.

Let me muddle on a little further. A morphism in A 2× ABA^\mathbf{2} \times_A B looks like a a f pb pb \array{ a' & \to & a \\ \downarrow & & \downarrow f \\ p b' & \to & p b } where the bottom arrow comes from BB. If the left arrow is an identity then we have a commuting triangle in AA, of the sort that appears when we define cartesianness. The action of κ\kappa on this should give a morphism bf *bb' \to f^* b over aaa' \to a, which should (?) be the factorization through the lift of ff.

Unless that’s hopelessly wrong, I’m almost there. I just don’t see any arrows κ(f)b\kappa(f) \to b that could be cartesian lifts of ff — but then, at this point on a Friday night I’m not usually very quick off the mark.

Sorry to talk your ear off about this, and for being dense, but your help is very much appreciated.

Posted by: Finn Lawler on January 8, 2010 11:55 PM | Permalink | Reply to this

Re: Equipments

This is actually something that’s nice to work through. We should remember to nLabify it when we’re done. You’re exactly right that this is what Street is doing in “fibrations in bicategories,” although he’s doing everything in full bicategorical generality and using clever tricks to avoid talking about coherence axioms, which makes some things easier but also sometimes has the effect of obscuring what’s really going on.

I think the morphism f bbf^* b \to b that you’re looking for is the image under κ\kappa of the morphism a f pb f id pb id pb\array{a & \overset{f}{\to} & p b\\ ^f\downarrow && \downarrow^{id}\\ p b& \underset{id}{\to} & p b} in A 2× ABA^{\mathbf{2}}\times_A B. The image of afpba \overset{f}{\to} p b on the left is f bf^*b, and the image of pbidpbp b \overset{id}{\to} p b on the right is bb (by the unit axiom for an FF-algebra).

There’s something deeper going on here, namely that the 2-monad FF is (co)lax-idempotent, a.k.a. a co-Kock-Zoberlein 2-monad, which means that the structure map FppF p \to p of any FF-algebra is always right adjoint to the unit transformation pFpp \to F p. Unfortunately we don’t yet have an nLab page on lax-idempotence.

Posted by: Mike Shulman on January 9, 2010 3:04 AM | Permalink | PGP Sig | Reply to this

Re: Equipments

Thanks for all this, Mike — it’s beautiful stuff. I’ll start trying to work it out in more detail on nlab.

Posted by: Finn Lawler on January 19, 2010 12:10 AM | Permalink | Reply to this
Read the post Generalized Multicategories
Weblog: The n-Category Café
Excerpt: A brief introduction to generalized multicategories, in honor of a new draft of a paper about them.
Tracked: January 4, 2010 2:20 AM
Read the post Extraordinary 2-Multicategories
Weblog: The n-Category Café
Excerpt: The still-hypothetical notion of "extraordinary 2-multicategory" generalizes a 2-category just enough to include extraordinary natural transformations.
Tracked: March 30, 2010 9:07 PM

Re: Equipments

My friends told me that operations \nabla and Δ\Delta that I introduce in this paper (page 3) can be naturally understood throught proarrow equipments (when defined as a double category). What is your opinion? Is it possible to rewrite my theory using equipments?

Posted by: osman on August 24, 2010 1:54 PM | Permalink | Reply to this

Re: Equipments

Yes, I agree with your friends. What you call an “f-category” looks like essentially the same as a vertically-chaotic double category which is a proarrow equipment / framed bicategory. (I think you probably want an additional axiom saying that the identity 2-cells for vertical composition act as identities for horizontal composition as well. I am also not sure whether your notion of “universal” in the definition of Δ\Delta and \nabla is exactly the same, since you didn’t say exactly what you mean by it.) In particular, this would mean that your Δ\Delta and \nabla can be reconstructed from each other.

Posted by: Mike Shulman on August 25, 2010 7:44 AM | Permalink | Reply to this

Re: Equipments

Thank you very much.

I think this “vertically-chaotic” can be removed. It seems that “vertically-thin double category which is proarrow equipment” is quite good for my applications. Anyway, now I should read your paper closely.

Posted by: osman on August 25, 2010 12:30 PM | Permalink | Reply to this

Re: Equipments

It seems that “vertically-thin double category which is proarrow equipment” is quite good

Absolutely, I agree that that would be better. Actually, your motivation/introduction sounded to me like that’s what you wanted, but then your actual definition of f-category looked chaotic instead.

Posted by: Mike Shulman on August 25, 2010 6:30 PM | Permalink | Reply to this

Re: Equipments

Sorry, I mean “it will be removed in future”. Now it’s of course chaotic in my paper.

Posted by: osman on August 25, 2010 7:06 PM | Permalink | Reply to this

Re: Equipments

It’s funny, I already read this your post, long before writing my article, and even translated little part of it to Russian. But that time I did not understand what proarrow equipment is! (it’s easy to imagine, because I’m not a mathematician, I just like category theory)

Posted by: osman on August 27, 2010 4:43 PM | Permalink | Reply to this

Re: Equipments

You can also feel free to blame it on the less than evocative or memorable terminology. (-: In contexts like yours, I think it is sometimes better to say something like “fibrant double category” instead of “proarrow equipment”.

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

Re: Equipments

Why not just framed bicategory? Actually I would like to reference to your paper and use the theory developed there. As far as I can see it’s quite enough for my goals (except maybe the theory “allegoric” involution).

Posted by: osman on September 3, 2010 1:21 PM | Permalink | Reply to this

Re: Equipments

That would be fine too. I usually say “framed bicategory” when I want to emphasize that one of the directions is of primary interest and the other is more “auxiliary,” and especially when I’m talking to an audience that is at least sort of comfortable with bicategories, but probably not so much with double categories. Possibly either or both of those are the case in your situation.

Posted by: Mike Shulman on September 3, 2010 4:54 PM | Permalink | Reply to this
Read the post Koudenburg on Algebraic Weigthed Colimits
Weblog: The n-Category Café
Excerpt: Read about my student's thesis.
Tracked: April 17, 2013 5:59 PM

Post a New Comment