Category Theory
Zulip Server
Archive

You're reading the public-facing archive of the Category Theory Zulip server.
To join the server you need an invite. Anybody can get an invite by contacting Matteo Capucci at name dot surname at gmail dot com.
For all things related to this archive refer to the same person.

Stream: theory: category theory

Topic: double profunctors

Matteo Capucci (he/him) (Oct 14 2022 at 21:10):

Hello,
I'm having to deal with [[double profunctors]] recently and it's not clear to me what are the problems with their composition. There's very limited sources on the topic, so I thought to ask here.
The nLab says double profunctors cannot be composed as their composition involves commuting colimits and pullbacks in Cat, which we know doesn't work in general since non every functor is exponentiable. More precisely, the composition of two double profunctors can be defined but the resulting composition operation doesn't seem to be associative.
Now, recently I've been talking with @Brandon Shapiro who explained to me that the definition of profunctors as barrels (which are nothing but functors into the walking arrow) can be generalized to the case of double categories. In this way we recover three kinds of double profunctors: horizontal double profunctors are double functors into the walking horizontal arrow, vertical double profunctors are double functors into the walking vertical arrow, and finally 'square' double profunctors are double functors into the walking square.
I didn't check explicitly but Brandon's claim seems very plausible to me. Take the case of a horizontal double profunctor $P$ between $\mathbb A$ and $\mathbb B$ is embodied by a double functor $\mathbb AP\mathbb B \to h\bf 2$ whose fibers are, respectively $\mathbb A$ and $\mathbb B$. The data and functoriality of $P$ correspond to that of the hom-set of $\mathbb AP\mathbb B$.
Now one can compose double profunctors represented in this way in the same exact way one composes profunctors represented in this way, which is represented by this diagram (this is composition of profunctors in Cat):
image.png
Here $1$ is the walking object, $2$ is the walking arrow, $3$ is the walking composable pair of arrows, and $comp : 2 \to 3$ maps the only arrow in $2$ to the composite arrow in $3$.
Basically you take a pushout and then pullback the resulting functor $APBQC \to 3$ along $comp$, forgetting about $P$.
When I look at this I see why composition of profunctors is not associative: we are pulling back a pushout, and we are doing it along the archetypal *non-exponentiable* functor, $comp$. Except this I described is composition of profunctors of categories, which is well-defined and associative!
So something is making up for the this lack of commutativity between pushout and pullback here. And it seems that this thing is lacking in the category of double categories and double functors, otherwise we could use the same procedure to define an associative composition of double profunctors (replacing everything in the diagram above suitably).
What is it?

Mike Shulman (Oct 14 2022 at 21:26):

Instead of pulling back along comp, it's better to consider that last step to be factoring the map $A+C \to APBQC$ as an essentially surjective functor followed by a fully faithful one. Then the whole construction is a dual form of the bicategory of relations in a regular category. In a general 2-category, the "cospans that should be collages of profunctors" can be characterized as the two-sided [[codiscrete cofibrations]], and then what you need is a suitable factorization system to do the composition. Now the stability condition that holds in Cat to make this associative is clear: fully faithful functors are closed under pushout (a dual of the fact that regular epimorphisms in a regular category are closed under pullback); on the nLab page [[codiscrete cofibration]] this is called an "equippable factorization system" on a 2-category. I presume this condition is what fails in Dbl, although I haven't written out the details.

Matteo Capucci (he/him) (Oct 14 2022 at 22:01):

Hi Mike, thanks for your reply!
Mike Shulman said:

Instead of pulling back along comp, it's better to consider that last step to be factoring the map $A+C \to APBQC$ as an essentially surjective functor followed by a fully faithful one.

I presume the map $A+C \to APBQC$ is given by the two inclusions, how does the factorization give me a map into $2$?

Mike Shulman (Oct 14 2022 at 22:38):

Just forget about 2. A cospan is the collage of a profunctor just when it's a two-sided codiscrete cofibration.

Mike Shulman (Oct 14 2022 at 22:39):

However, if you really insist, you can use the fact that 1+1 -> 2 -> 3 is an analogous factorization and the factorization system is functorial.

Brandon Shapiro (Oct 14 2022 at 23:12):

Hi Matteo and Mike! I hadn't thought about the factorization perspective on this before, that's really interesting. After thinking about these for a while though I still feel like the composition should be associative, for the reasons below. I figure I'm missing something though, and I'd love to better understand what goes wrong here.

• In the pullback-along-comp version of ordinary profunctor composition, even though comp itself is not exponentiable, the functors APBQC -> 3, APBQCRD -> 4, etc are exponentiable, and this can be used to prove associativity as the pushout Push(2 <- 1 -> 2) = 3 is preserved when pulling back comp_1 : 3 -> 4 along APBQCRD -> 4 to get A(P;Q)CRD. This is used to show that both associations agree with the ternary composite defined this way using comp : 2 -> 4. I don't see why this would be any different when the walking arrows in Cat are replaced by the walking horizontal arrows in DoubleCat (this is admittedly vague, but I'm happy to say more about it when I'm not in transit)

• In terms of factorizations, it seems relevant here that the pushouts we're considering don't add any new vertical composites. When gluing together P and Q along B, we add in horizontal composites of the heteromorphisms and heterosquares, but on both objects and vertical morphisms the pushout is simply a pushout of inclusions of sets. Maybe this is the most short and intuitive reason why I feel like horizontal double profunctors should compose just as nicely as ordinary profunctors.

Nathanael Arkor (Oct 14 2022 at 23:15):

@Matteo Capucci (he/him): have you looked at Paré's papers Yoneda theory for double categories and Composition of modules for lax functors? These discuss the topic of double profunctors quite extensively.

Mike Shulman (Oct 14 2022 at 23:32):

@Nathanael Arkor I don't think Paré's "modules" are the same as the double profunctors we're talking about here. His are a kind of transformation between two parallel lax double functors.

Nathanael Arkor (Oct 14 2022 at 23:35):

Oh whoops, you're right! He just calls them profunctors, and his modules are something else. Thanks for pointing that out; I should have double-checked.

Mike Shulman (Oct 14 2022 at 23:49):

Brandon Shapiro said:

In terms of factorizations, it seems relevant here that the pushouts we're considering don't add any new vertical composites. When gluing together P and Q along B, we add in horizontal composites of the heteromorphisms and heterosquares, but on both objects and vertical morphisms the pushout is simply a pushout of inclusions of sets.

I don't think this is true. The quotienting that happens on heteromorphisms means that some heterosquares that were not previously composable will become so, and thus new vertical composites of heterosquares appear. Here is a sketch of how this gives rise to non-associativity.

Matteo Capucci (he/him) (Oct 15 2022 at 00:19):

Instead of pulling back along comp, it's better to consider that last step to be factoring the map $A+C \to APBQC$ as an essentially surjective functor followed by a fully faithful one. Then the whole construction is a dual form of the bicategory of relations in a regular category. In a general 2-category, the "cospans that should be collages of profunctors" can be characterized as the two-sided [[codiscrete cofibrations]], and then what you need is a suitable factorization system to do the composition. Now the stability condition that holds in Cat to make this associative is clear: fully faithful functors are closed under pushout (a dual of the fact that regular epimorphisms in a regular category are closed under pullback); on the nLab page [[codiscrete cofibration]] this is called an "equippable factorization system" on a 2-category. I presume this condition is what fails in Dbl, although I haven't written out the details.

Ok I should have read the nLab page you linked before, I now see what you mean here.

Matteo Capucci (he/him) (Oct 15 2022 at 00:19):

Brandon Shapiro said:

In terms of factorizations, it seems relevant here that the pushouts we're considering don't add any new vertical composites. When gluing together P and Q along B, we add in horizontal composites of the heteromorphisms and heterosquares, but on both objects and vertical morphisms the pushout is simply a pushout of inclusions of sets.

I don't think this is true. The quotienting that happens on heteromorphisms means that some heterosquares that were not previously composable will become so, and thus new vertical composites of heterosquares appear. Here is a sketch of how this gives rise to non-associativity.

But any way, this really nails it! :exploding_head:

Brandon Shapiro (Oct 15 2022 at 00:29):

Mike Shulman said:

I don't think this is true. The quotienting that happens on heteromorphisms means that some heterosquares that were not previously composable will become so, and thus new vertical composites of heterosquares appear. Here is a sketch of how this gives rise to non-associativity.

I see, that makes it very clear where the problem is. Thanks!

Christian Williams (Oct 15 2022 at 20:37):

Hm, this sketch is interesting. For fibrant double categories, we can compose $\gamma$ with $1_b\circ cart_{v_o}\circ \delta$, the identity of $b$ composed with "bending" of the left vertical arrow of $\delta$ (the cartesian cell of its companion) composed with $\delta$. So these zig-zags are not obstructions to associative composition of profunctors of FDCs.

Christian Williams (Oct 15 2022 at 20:49):

prof-comp-assoc-issue.png

Mike Shulman (Oct 15 2022 at 22:23):

Yes, that's true.

Christian Williams (Oct 16 2022 at 19:42):

So, this seems to be a serious limitation of non-fibrant double categories. What notions of profunctor have been used? I'll search around.

Christian Williams (Oct 16 2022 at 19:50):

it's not easy to find much online; I'm only seeing nLab: double profunctor

Christian Williams (Oct 16 2022 at 20:00):

yeah, I'm not even seeing double profunctors in those references of Pare. but I'm pretty sure I've seen some from Shulman.

Nathanael Arkor (Oct 16 2022 at 22:27):

Christian Williams said:

yeah, I'm not even seeing double profunctors in those references of Pare. but I'm pretty sure I've seen some from Shulman.

They're simply defined to be (lax) double functors $\mathbb B^{\text{op}} \times \mathbb A \to \mathbb S\mathrm{et}$ in the paper. He doesn't use the terminology "double profunctor".

Matteo Capucci (he/him) (Oct 18 2022 at 19:44):

Christian Williams said:

it's not easy to find much online; I'm only seeing nLab: double profunctor

yeah there's pretty much nothing

Mike Shulman (Oct 19 2022 at 23:14):

I added the counterexample to associativity to the nLab page [[double profunctor]].