Benabou on Spans and Profunctors/Distributors

May 18, 2011

Benabou on Spans and Profunctors/Distributors

Posted by Jeffrey Morton under category theory, spans, talks
[12] Comments

So I recently got back from a trip to the UK – most of the time was spent in Cardiff, at a workshop on TQFT and categorification at the University of Cardiff. There were two days of talks, which had a fair amount of overlap with our workshop in Lisbon, so, being a little worn out on the topic, I’ll refrain from summarizing them all, except to mention a really nice one by Jeff Giansiracusa (who hadn’t been in Lisbon) which related (open/closed) TQFT’s and cohomology theories via a discussion of how categories of cobordisms with various kinds of structure correspond to various sorts of operads. For example, the “little disks” operad, which describes the structure of how to compose disks with little holes, by pasting new disks into the holes of the old ones, corresponds to the usual cobordism category.

This workshop was part of a semester-long program they’ve been having, sponsored by an EU network on noncommutative geometry. After the workshop was done, Tim Porter and I stayed on for the rest of the week to give some informal seminars and talk to the various grad students who were visiting at the time. The seminars started off being directed by questions, but ended up talking about TQFT’s and their relations to various kinds of algebras and higher categorical structures, via classifying spaces. We also had some interesting discussions outside these, for example with Jennifer Maier, who’s been working with Thomas Nicklaus on equivariant Dijkgraaf-Witten theory; with Grace Kennedy, about planar algebras and their relationships to TQFT‘s. I’d also like to give some credit to Makoto Yamashita, who’s interested in noncommutative geometry (viz) and pointed out to me a paper of Alain Connes which gives an account of integration on groupoids, and what corresponds to measures in that setting, which thankfully agrees with what little of it I’d been able to work out on my own.

However, what I’d like to take the time to write up was from the earlier part of my trip, where I visited with Jamie Vicary at Oxford. While I was there, I gave a little lunch seminar about the bicategory $Span(Gpd)$ (actually a tricategory), and some of the physics- and TQFT-related uses for it. That turned out to be very apropos, because they also had another visitor at the same time, namely Jean Benabou, the fellow who invented bicategories, and introduced the idea of bicategories of spans as one of the first examples. He gave a talk while I was there which was about the relationship between spans and what he calls “distributors” (which are often called “profunctors“, but since he was anyway the one who introduced them and gave them that name in the first place, and since he has since decided that “profunctors” should refer to only a special class of these entities, I’ll follow his terminology).

(Edit: Thanks to Thomas Streicher for passing on a reference to lecture notes he prepared from lecture by Benabou on the same general topic.)

The question to answer is: what is the relation between spans of categories and distributors?

This is related to a slightly lower-grade question about the relationship between spans of sets, and relations, although the answer turns out to be more complicated. So, remember that a span from a set $A$ to a set $B$ is just a diagram like this: $A \leftarrow X \rightarrow B$ . They can be composed together – so that given a span from $A$ to $B$ , and from $B$ to $C$ , we can take fibre products over $B$ and get a span from $A$ to $C$ , consisting of pairs of elements from the $X$ sets which map down to the same $b \in B$ . We can do the same thing in any category with pullbacks, not just ${Sets}$ .

A span $A \leftarrow S \rightarrow B$ is a relation if the pair of arrows is “jointly monic”, which is to say that as a map $S \rightarrow A \times B$ , it is a monomorphism – which, since we’re talking about sets, essentially means “a subset”. That is, up to isomorphism of spans, $S$ just picks out a bunch of pairs $(a,b) \in A \times B$ , which are the “related” pairs in this relation. So there is an inclusion ${Rel} \hookrightarrow Span({Sets})$ . What’s more the inclusion has a left adjoin, which turns a span into a corresponding relation. It follows from the fact that $Sets$ has an “epi-mono factorization”: namely, the map $f: S \rightarrow A \times B$ that comes from the span (and the definition of product) will factor through the image. That is, it is the composite $S \rightarrow Im(f) \rightarrow A \times B$ , where the first part is surjective, and the second part is injective. Then the inclusion $r(f) : Im(f) \hookrightarrow A \times B$ is a relation. So we say the inclusion of $Rel$ into $Span(Set)$ is a reflection. (This is a slightly misleading term: there’s an adjoint to the inclusion, but it’s not an adjoint equivalence. “Reflecting” twice may not get you back where you started, or anywhere isomorphic to it.)

(Edit: Actually, this is a bit wrong. See the comments below. What’s true is that the hom-categories of $Rel$ have reflective inclusions into the hom-categories of $Span(Set)$ . Here, we think of $Rel$ as a 2-category because it’s naturally enriched in posets. Then these reflective inclusions of hom-categories can be used to build a lax functor from $Span(Set)$ to $Rel$ – but not an actual functor.)

So a slightly more general question is: if $\mathbb{V}$ is a monoidal category, and $\mathbb{V}' \subset \mathbb{V}$ is a “reflective subcategory“, can we make $\mathbb{V}'$ into a monoidal category just by defining $A' \otimes ' B'$ (the product in $\mathbb{V}'$ ) to be the reflection $r(A' \otimes B')$ of the original product? This is the one-object version of a question about bicategories. Namely, say that $\mathbb{S}$ is a bicategory, and $\mathbb{S}'$ is a sub-bicategory such that every pair of objects gives a reflective subcategory: $\mathbb{S}' (A,B) \subset \mathbb{S}(A,B)$ has a reflection. Then can we “pull” the composition of morphisms in $\mathbb{S}$ back to $\mathbb{S}'$ ?

The answer is no: this just doesn’t work in general. For spans of sets, and relations, it works: composing spans essentially “counts paths” which relate elements $A$ and $B$ , whereas composing relations only keeps track of whether or not there is a path. However, composing spans which come from relations, and then squashing them back down to relations again, agrees with the composite in $Rel$ (the squashing just tells whether the set of paths from $A$ to $B$ by a sequence of relations is empty or not). But in the case of $Span(Cat)$ and some reflective subcategory – among other possible examples – associativity and unit axioms will break, unless the reflections $r_{A,B}$ are specially tuned. This isn’t to say that we can’t make $\mathbb{V}'$ a monoidal category (or $\mathbb{S}'$ a bicategory). It just means that pulling back $\otimes$ or $\circ$ along the reflection won’t work. But there is a theorem that says we can always promote such an inclusion into one where this works.

So what’s an instance of all this? A distributor (again, often called “profunctor”) $\Phi : \mathbb{A} \nrightarrow \mathbb{B}$ from a category $\mathbb{A}$ to $\mathbb{B}$ is actually a functor $\phi : \mathbb{B}^{op} \times \mathbb{A} \rightarrow Sets$ . Then there’s a bicategory $Dist$ , where for each objects there’s a category $Dist(\mathbb{A},\mathbb{B})$ . Distributors represent, in some sense, a categorification of relations. (This observation follows the periodic table of category theory, in which a 1-category is a category, a 0-category is a set, and a (-1)-category is a truth value. There’s a 1-category of relations, with hom-sets $Rel(A,B)$ , and each one is a map from $B \times A$ into truth values, specifying whether a pair $(b,a)$ is related.)

The most elementary example of a distributor is the “hom-set” construction, where $\Phi (\mathbb{A},\mathbb{B}) = hom(\mathbb{A},\mathbb{B})$ , which is indeed covariant in $\mathbb{A}$ and contravariant in $\mathbb{B}$ . A way to see the general case in that $\Phi$ obviously determines a functor from $\mathbb{A}$ into presheaves on $\mathbb{B}$ : $\Phi : \mathbb{A} \rightarrow \hat{\mathbb{B}}$ , where $\hat{\mathbb{B}} = Psh(\mathbb{B})$ is the category $hom(\mathbb{B},Sets)$ .

In fact, given a functor $F : \mathbb{A} \rightarrow \mathbb{B}$ , we can define two different distributors:

$\Phi^F : \mathbb{B} \nrightarrow \mathbb{A}$ with $\Phi^F(A,B) = Hom_{\mathbb{B}}(FA,B)$

and

$\Phi_F : \mathbb{A} \nrightarrow \mathbb{B}$ with $\Phi_F(B,A) = Hom_{\mathbb{B}}(B,FA)$

(Remember, these $\Phi$ are functors from the product into $Sets$ : so they are just taking hom-sets here in $\mathbb{B}$ in one direction or the other.) This much is a tautology: putting a value in $\mathbb{A}$ in leaves a free variable, but the point is that $\hat{\mathbb{B}}$ can be interpreted as a category of “big objects of $\mathbb{B}$ “. This is since the Yoneda embedding $Y : B \hookrightarrow \mathbb{B}$ embeds $\mathbb{B}$ by taking each object $b \in B$ to the presentable presheaf $hom_B(-,b)$ which assigns each object the set of morphisms into $b$ , so $\hat{\mathbb{B}}$ has “extended” objects of $\mathbb{B}$ .

So distributors like $\Phi$ are “generalized functors” into $\mathbb{B}$ – and the idea is that this is in roughly the same way that “distributions” are to be seen as “generalized functions”, hence the name. (Benabou now prefers to use the name “profunctor” to refer only to those distributors which map to “pro-objects” in $\hat{\mathbb{B}}$ , which are just special presheaves, namely the “flat” ones.)

Now we have an idea that there is a bicategory $Dist$ , whose hom-categories $Dist(\mathbb{A},\mathbb{B})$ consist of distributors (and natural transformations), and that the usual functors (which can be seen as distributors which only happen to land in the image of $\mathbb{B}$ under the Yoneda embedding) form a sub-bicategory: that is, post-composition with $Y$ turns a functor into a distributor.

But moreover, this operation has an adjoint: functors out of $\mathbb{B}$ can be “lifted” to functors out of $\hat{\mathbb{B}}$ , just by taking the Kan extension of a functor $G : \mathbb{B} \rightarrow \mathbb{X}$ along $Y$ . This will work (pointwise, even), as long as $\mathbb{X}$ is cocomplete, so that we can basically “add up” contributions from the objects of $\mathbb{B}$ by taking colimits. In the special case where $\mathbb{X} = \hat{\mathbb{C}}$ for some other category $\mathbb{C}$ , then this tells us how to get composition of distributors $Dist(\mathbb{A},\mathbb{B}) \times Dist(\mathbb{B},\mathbb{C})\rightarrow Dist(\mathbb{A},\mathbb{C})$ .

Now, for a functor $F$ , there are straightforward unit and counit natural transformations which makes $\Phi^F$ (the image of $F$ under the embedding of $Cat$ into $Dist$ ) a left adjoint for $\Phi_F$ . So we’ve embedded $Cat$ into $Dist$ in such a way that every functor has a right adjoint. What about $Span(Cat)$ ? In general, given a bicategory $B$ , we can construe $Span(B)$ as a tricategory, which contains $B$ , in such a way that every morphism of $B$ has an ambidextrous adjoint (both left and right adjoint). (There’s work on this by Toby Kenney and Dorette Pronk, and Alex Hoffnung has also been looking at this recently.) So how does $Span(Cat)$ relate to $Dist$ ?

One statement is that a distributor $\Phi : \mathbb{A} \nrightarrow \mathbb{B}$ can be seen as a special kind of span, namely:

$\mathbb{A} \stackrel{q}{\longleftarrow} Elt(\Phi) \stackrel{p}{\longrightarrow} \mathbb{B}$

where $Elt(\Phi)$ consists of all the “elements of $\Phi$ ” (in particular, pasting together all the images in $Sets$ of pairs $(A,B)$ and the set maps that come from morphisms between them in $\mathbb{B}^{op} \times \mathbb{A}$ ). (As an aside: Benabou also explained how a cospan, $\mathbb{A} \rightarrow C(\Phi) \leftarrow \mathbb{B}$ can be got from a distributor. The objects of $C(\Phi)$ are just the disjoint union of those from $\mathbb{A}$ and $\mathbb{B}$ , and the hom-sets are just taken from either $\mathbb{A}$ , or $\mathbb{B}$ , or as the sets given by $\Phi$ , depending on the situation. Then the span we just described completes a pullback square opposite this cospan – it’s a comma category.)

These spans $(Elt(\Phi),p,q)$ end up having some special properties that result from how they’re constructed. In particular, $p$ will be an op-fibration and $q$ will be a fibration (this, for instance, is alifting property that let one lift morphisms – since the morphisms are found as the images of the original distributor, this makes sense). Also, the fibres of $(p,q)$ are discrete (these are by definition the images of identity morphisms, so naturally they’re discrete categories). Finally, these properties (fibration, op-fibration, and discrete fibres) are enough to guarantee that a given span is (isomorphic to) one that comes from a distributor. So we have an embedding $i : Dist \rightarrow Span(Cat)$ .

What’s more, it’s a reflective embedding, because we can always mangle any span to get a new one where these properties hold: it’s enough to force fibres to be discrete by taking their $\pi_0$ – the connected components. The other properties will then follow. But notice that this is a very nontrivial thing to do: in general, the fibres of $(p,q)$ could be any sort of category, and this operation turns them into sets (of isomorphism classes). So there’s an adjunction between $i$ and $\pi_0$ , and $Dist$ is a reflective sub-bicategory of $Span(Cat)$ . But the severity of $\pi_0$ ends up meaning that this doesn’t get along well with composition – the composition of distributors (described above) is not related to composition of spans (which works by weak pullback) via this reflection in a naive way. However, the theorem mentioned above means that there will be SOME reflecction that makes the compositions get along. It just may not be as nice as this one.

This is kind of surprising, and the ideal punchline to go here would be to say what that reflection is like, but I don’t know the answer to that question just now. Anyone else know?

Thanks to Bob Coecke, here are some pictures of me, a few of the people from ComLab, and Jean Benabou at dinner at the Oxford University Club, with a variety of dopey expressions as Bob snapped the pictures unexpectedly. Thanks Bob.

12 Responses to “Benabou on Spans and Profunctors/Distributors”

Thomas Streicher Says:

May 21, 2011 at 6:53 pm
Dear Jeffrey,

you might want to have a look at Thm. 6.6 of “Distributors at Work” available from my homepage
but also via nLab I guess.
There the reflection of a span (p,q) is \phi^p * \phi_q.

Best, Thomas

Reply
1. Jeffrey Morton Says:
  
  May 23, 2011 at 11:42 am
  Hi Thomas:
  
  That’s a nice reference (in case anyone else stumbles on this, here it is). The theorem seems to be saying roughly what I expect: the are functors $\mathbb{C}$ and $\mathbb{S}$ which reflect distributors into cospans and spans of categories, respectively. It does elaborate that the cospan representation has a right adjoint, and the span one has a left adjoint, which you mention. It’s not so clear to me at the moment if this answers Benabou’s observation that this reflection might not respect composition (at least strictly). Maybe some further perusal will make that come clearer.
  
  Thanks!
  
  Jeff
  
  Reply
John Baez Says:

June 4, 2011 at 4:48 pm
You say there an inclusion of Rel in Span(Set). In what sense is this true?

I can think of any relation as a jointly monic span. But suppose I take two relations, think of them as spans this way, and then compose them as spans. Alternatively, suppose I compose them as relations and then think of the result as a span. The resulting spans are not in general isomorphic.

Why not? The first span is always a relation, but the second one is not. For example, think of the relation “friend of”. If we interpret this as as a span and then square it, the resulting span does not come from the relation “friend of a friend of”, because I could be a friend of a friend of yours in more than one way!

(In fact I am.)

I believe that there is a lax 2-functor from Rel to Span(Set). If F(f) is the span corresponding to a relation f, there’s a map of spans from F(f)F(g) to F(fg).

However, it’s a bit odd to call a lax 2-functor an “inclusion”.

Reply
1. Jeffrey Morton Says:
  
  June 5, 2011 at 10:51 am
  This is a good point, which gets at exactly the point of Benabou’s talk. You’re right that “inclusion” is a funny word here. Let me go back and see how to put this better.
  
  Benabou began by talking about an inclusion of monoidal categories (not bicategories) $\mathbb{V}' \subset \mathbb{V}$ , which is not assumed to be a monoidal inclusion, which I would probably write as $(\mathbb{V}', \otimes ') \subset (\mathbb{V}, \otimes)$ . The interesting case is precisely when it’s not.
  
  Then if the inclusion is reflective, with $r : \mathbb{V} \rightarrow \mathbb{V}'$ adjoint to the inclusion, we can as if it’s possible to recover the monoidal structure on the subcategory from the large category. That is, whether $v'_1 \otimes' v'_2 = r(v'_1 \otimes v'_2)$ , where I’m implicitly using the inclusion map on the right hand side but not the left.
  
  The monoidal category case is that of a bicategory with one object $\star$ , whose morphisms are the objects of the $\mathbb{V}$ , and whose composition is the monoidal product, so that $\mathbb{V} = Hom(\star,\star)$ . So I guess I should re-paraphrase Benabou as follows:
  
  Suppose we have two bicategories $\mathbb{B}'$ and $\mathbb{B}$ , which in this case I suppose are $Rel$ thought of as a bicategory with only identity 2-morphisms, and $Span(Set)$ , respectively. And suppose furthermore that they have the same objects (one could probably weaken this assumption, but I doubt it would make the example any clearer), and that for any pair of objects $(X,Y)$ , there’s a are reflective inclusion $i_{X,Y} : Hom_{\mathbb{B}'}(X,Y) \rightarrow Hom_{\mathbb{B}}(X,Y)$ , with reflection going the other way $r_{X,Y} : Hom_{\mathbb{B}'}(X,Y) \rightarrow Hom_{\mathbb{B}}(X,Y)$ .
  
  Then the question is whether we can reconstruct the composition of $\mathbb{B}'$ from that of $\mathbb{B}$ in the following way: given $f : X \rightarrow Y$ and $g : Y \rightarrow Z$ in $\mathbb{B}'$ , take $f \circ ' g = r_{X,Z} ( i_{Y,Z}(g) \circ i_{X,Y}(f))$ . In general, the answer is no, but in the case of $Rel$ and $Span(Sets)$ , the answer is yes.
  
  Specifically, for $Rel$ and $Span(Sets)$ , given sets $X$ and $Y$ , the map $i_{X,Y}$ takes a relation to some choice of span which represents it – let’s say to the actual subset of “the” product $S \subset X \times Y$ and the projection maps to $X$ and $Y$ . The reflection maps $r_{X,Y}$ takes any span $X \leftarrow S \rightarrow Y$ to another span, with middle object $S'$ , which is the subset of $X \times Y$ which has either zero or one element over $(x,y)$ depending on whether the corresponding subset of $S$ is empty or nonempty. Since the span factors through a map into the product, this is just the image of this map, together with its usual projections.
  
  The thing you describe, then is, exactly the reconstruction of the composition structure of $Rel$ using all these reflections. But you’re right – there’s no inclusion functor, because in general the composite of the image of two relations in $Span(Sets)$ isn’t a relation. Only its image under the appropriate $r_{X,Z}$ is (the image of) a relation.
  
  To summarize, you’re right that there’s not an inclusion *2-functor* from $Rel$ (as a discrete 2-category) to $Span(Sets)$ . Rather, there are a bunch of (reflective) inclusion functors of the hom-categories. This setup needn’t be a functor, just like that reflective inclusion of the monoidal subcategory $\mathbb{V}'$ into $\mathbb{V}$ needn’t be monoidal. The lax (2-)functor you mention has those reflections $r_{X,Z}$ of the hom-category inclusions as components of the natural transformation that defines its lax structure.
  
  One thing that occurs to me is that when we squash $Span(Sets)$ into a category by taking spans up to isomorphism, we don’t notice the adjunction between the $i$ and $r$ maps.
  
  Reply
  1. Jeffrey Morton Says:
    
    June 6, 2011 at 12:49 pm
    Alex Hoffnung pointed out a problem with what I said here by email. It essentially boils down to the fact that, if you think of $Rel(X,Y)$ as a discrete category, it doesn’t have enough morphisms for the reflection functor $r_{X,Y}$ which I described to be well defined.
    
    After thinking about it a bit, I realize that $Rel$ is already naturally a 2-category. Since relations can be written as matrices of zeroes and ones, $(0,1)$ is an ordered set, hence a category, then the set of matrices in $(0,1)$ is also a category, with component-wise maps. You need all of these to be present for $r_{X,Y}$ to be well-defined.
    
    In particular, given a span map, which breaks down into a bunch of set maps between the sets lying over each pair $(x,y)$ , we need to have an image 2-cell in $Rel$ . This is OK if we have all the componentwise maps of 0’s and 1’s I just mentioned. For instance, if two spans both have nonempty preimage lying over $(x,y)$ , then the corresponding relations both have 1 in the $(x,y)$ component. Any span map between them will have a function from one nonempty set to another in this component, which will be sent to the unique morphism $1 \rightarrow 1$ in that component.
    
    The fact that there’s no morphism from 1 to 0 in the ordered set $(0,1)$ reflects the fact that there’s no set map from a nonempty set to an empty set. This means there’s no 2-morphism in $Rel$ from a “bigger” relation to a “smaller” relation (partially ordered with the componentwise order on ${0,1}$ ). So in fact, what we have here is the natural enrichment of $Rel$ in posets.
2. David Roberts Says:
  
  June 8, 2011 at 11:12 pm
  Hi John,
  
  here is a (possibly misguided) categorified analogy, which may or may not help. Consider the bicategory of categories and anafunctors and transformations. There is a ‘subbicategory’ where the 1-arrows are _saturated_ anafunctors (these are essentially representable disrtributors) and the 2-arrows are maps of spans (no 2-arrows involved!). Now the composition of the latter is by a ‘tensor product’ (analogous to extending the structure group of a bundle), whereas the composition of the former is as spans, namely pullback. So the inclusion map is weak in this respect.
  
  But then one runs into trouble slightly because for inverible 2-arrows in the first bicategory, these correspond precisely to the 2-arrows in the second bicategory, but for non-invertible 2-arrows, they don’t! If you are interested in groupoids, then this isn’t a problem, and indeed people use the bicategory of e.g. Lie groupoids with Hilsum-Skandalis morphisms/right principal bibundles as maps instead of the (equivalent) bicategory of anafunctors. But if one is interested in the general setup, things aren’t so clean.
  
  Reply
Jamie Vicary Says:

September 8, 2011 at 10:31 am
Hi Jeff. So let me get this straight: there is no 2-functor $Span(Cat) \rightarrow Prof$ that sends $A \stackrel{F}{\rightarrow} X \stackrel{G}{\leftarrow} B$ to $G^* \circ F_* : A \rightarrow B$ . Is that right?

Reply
1. Jeffrey Morton Says:
  
  September 8, 2011 at 1:58 pm
  I’ve cleaned up the markup on that comment – if I changed your intended meaning, let me know. (BTW: to use math LaTeX on WordPress, just do as usual, but put “latex” after the opening dollar sign.)
  
  I’m not sure I understand what you’re asking – I’m reading your notation $F_*$ and $G^*$ as functors between presheaf categories $PSh(A)$ , $PSh(X)$ and $PSh(B)$ , yes? Granted, there are inclusions by the Yoneda embeddings, like $y : A \rightarrow PSh(A)$ , but I wouldn’t expect the image of $A$ under $G^* \circ F_*$ to be contained in the image of $B$ under the Yoneda embedding. So, no, it doesn’t look like that would work.
  
  Reply
2. Jamie Vicary Says:
  
  September 8, 2011 at 2:02 pm
  By $(-)_*$ , I mean the covariant inclusion 2-functor Cat $\to$ Prof, and by $(-)^*$ I mean the contravariant inclusion 2-functor.
  
  Thanks for the $\LaTeX$ tips!
  
  Reply
  1. Jeffrey Morton Says:
    
    September 8, 2011 at 3:20 pm
    Ah, right – so as far as I recall, the moral of the story was that the process you described ends up not being 2-functorial, because composition of spans and of profunctors don’t commute with that correspondence, though it does behave nicely on the hom-categories. I would have to think about it again some more to remember the details…
  2. Jamie Vicary Says:
    
    September 8, 2011 at 4:01 pm
    Yes, that’s the message I got too. It’s a pain!
    
    It would be good to have a simple example which makes this clear… it’s easy enough for Rel vs Span(Set), after all. Maybe a good project for the plane ride back home!
2-Erlangen Program; Manifold Calculus talk (Pedro Brito) « Theoretical Atlas Says:

September 26, 2011 at 2:22 pm
[…] inclusion of sheaves into presheaves (see some discussion about reflective inclusions, also in an earlier post). Any sheaf is a contravariant functor – this is the inclusion of into $latex PSh( […]

Reply