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: learning: questions

Topic: profunctors and tensor-hom adjunctions

David Egolf (May 02 2025 at 21:18):

I'm interested in understanding how "tensor-hom" adjunctions arise, and when such an adjunction is in fact a geometric morphism. I'm specifically interested in understanding how tensor-hom adjunctions can arise from profunctors, and I'd like to try this out with a few examples. It could also be interesting to note some common patterns that can be used to construct profunctors. Along the way, I want to learn how to compose profunctors - and to use this as a chance to learn a little bit about coends.

I'm hoping to structure this thread around specific questions and specific exercises. I'm not sure quite yet which specific question or exercise I'd like to start with, but I wanted to get this thread started! Going forward, I'm currently planning to reference discussion and exercises from "Sheaves in Geometry and Logic" (by Mac Lane and Moerdijk) and/or "Coend calculus" (by Fosco Loregian).

If anyone has any initial thoughts or suggestions at the start of this thread, please feel free to share those! Otherwise, I will plan to create a second post in this thread once I have a specific first exercise or discussion topic in mind.

Ryan Wisnesky (May 02 2025 at 21:30):

This paper https://arxiv.org/abs/2404.01406 talks about how different notions of pro functor presentation lead to failure or success of composition of presentations. If you need to compose specific finitely presented pro functors, the algorithms in that paper are implemented at http://categoricaldata.net

David Egolf (May 04 2025 at 15:18):

Thanks for your comment @Ryan Wisnesky. I hadn't heard about "presentations" of profunctors before. I'll keep that paper in mind in case I want to learn more about that, at some point.

David Egolf (May 04 2025 at 15:25):

Here's the first specific question I'd like to explore in this thread: What are some examples of profunctors?

David Egolf (May 04 2025 at 15:25):

The nLab informs me that if $V$ is a symmetric closed monoidal category $V$ (such as the category of sets), and $C$ and $D$ are categories enriched over $V$, then a profunctor from $C$ to $D$ is a $V$-functor $:D^{\mathrm{op}} \otimes C \to V$.

David Egolf (May 04 2025 at 15:27):

I don't know what this $\otimes$ is doing, yet - I guess there is some notion of tensor product between $V$-enriched categories. However, in the case that $V = \mathsf{Set}$, I do know that a profunctor from a category $C$ to a category $D$ is just a functor $:D^{\mathrm{op}} \times C \to \mathsf{Set}$.

John Baez (May 04 2025 at 15:49):

Puzzle. Guess what the tensor product of $V$-enriched categories $C$ and $D$ might be. For starters figure out the set of objects of $C \otimes D$, and then for any pair of objects in $C \otimes D$ their hom-object, which is an object in $V$.

Hint: copy the product of ordinary categories, replacing the cartesian product of sets by the tensor product of objects in $V$ whenever called for (and not otherwise).

A lot of basic enriched category theory is straightforward generalization of ordinary category theory, so it's good to get used to doing those generalizations without breaking a sweat. This lets you focus on the really novel aspects, like how limits and colimits get replaced by [[weighted limits]] and [[weighted colimits]]. These are connected to ends and coends, so they may become important when composing [[enriched profunctors]].

Kevin Carlson (May 04 2025 at 17:05):

David Egolf said:

Here's the first specific question I'd like to explore in this thread: What are some examples of profunctors?

The most important profunctor is $\mathrm{Hom}: C^{\mathrm{op}}\otimes C\to \mathcal V.$ If you have functors $f,g: D,E\to C$ then there’s the restricted hom $\mathrm{Hom}(f(-),g(-)):D^{\mathrm{op}}\otimes E\to \mathcal V.$ If $f$ or $g$ picks out a single object then this restricted hom is a representable presheaf or copresheaf in the familiar sense! So one things profunctors do immediately is generalize representability to a concept that can vary in both variables at once.

Kevin Carlson (May 04 2025 at 17:07):

A very different feel of example comes from drawing any category you like over the partial order $0<1.$ The inverse image of $0$ becomes the domain of a profunctor and the inverse image of $1$, the codomain, while the arrows over the nontrivial arrow in $0<1$ becomes the values. You might like to try to flesh out this sketch to show these things really do give profunctors, but it could also be useful just to draw some tiny examples in this way.

David Egolf (May 05 2025 at 19:22):

Thanks to both of you! Both of your responses will be interesting to work through.

To begin with, I think the puzzle @John Baez provided would be a great place to start. So let me see if I can guess what the tensor product of two $V$-enriched categories $C$ and $D$ might be.

David Egolf (May 05 2025 at 19:24):

If we assume that $C$ and $D$ are small, they each have a set of objects. So it seems reasonable to try setting the objects of $C \otimes D$ to be the cartesian product of the set of objects of $C$ with the set of objects of $D$.

(I suppose that if $C$ or $D$ were categories internal to some category, then they might not have a set of objects, and we might want to do something fancier to form our new "object of objects".)

David Egolf (May 05 2025 at 19:27):

Next, we'd like to find the hom-object for any ordered pair of objects in $C \otimes D$. So, let's try to figure out the hom-object from $(c,d)$ to $(c',d')$.

David Egolf (May 05 2025 at 19:29):

I expect this to be something in the spirit of the "product" of the morphisms $:c \to c'$ in $C$ with the morphisms $:d \to d'$ in $D$. So, maybe we can try setting this hom object $(C \otimes D)((c,d), (c',d'))$ to be $C(c,c') \otimes D(d,d')$.

John Baez (May 05 2025 at 19:29):

Great! There is really nothing else you could have done.

John Baez (May 05 2025 at 19:30):

Of course you're not done yet, but you are following the tao of mathematics, like swimming downstream in a fast current.

I'm alluding to Chapter 19 of the Chuang-Tzu:

Confucius was looking at the cataract near the gorge of Lü, which fell a height of 240 cubits, and the spray of which floated a distance of forty lî, (producing a turbulence) in which no tortoise, gavial, fish, or turtle could play. He saw, however, an old man swimming about in it, as if he had sustained some great calamity, and wished to end his life.

Confucius made his disciples hasten along the stream to rescue the man; and by the time they had gone several hundred paces, he was walking along singing, with his hair dishevelled, and enjoying himself at the foot of the embankment. Confucius followed and asked him, saying, 'I thought you were a sprite; but, when I look closely at you, I see that you are a man. Let me ask if you have any particular way of treading the water.'

The man said, 'No, I have no particular way. I began (to learn the art) at the very earliest time; as I grew up, it became my nature to practise it; and my success in it is now as sure as fate. I enter and go down with the water in the very centre of its whirl, and come up again with it when it whirls the other way. I follow the way of the water, and do nothing contrary to it of myself;—this is how I tread it.

fosco (May 06 2025 at 05:57):

David Egolf said:

I expect this to be something in the spirit of the "product" of the morphisms $:c \to c'$ in $C$ with the morphisms $:d \to d'$ in $D$. So, maybe we can try setting this hom object $(C \otimes D)((c,d), (c',d'))$ to be $C(c,c') \otimes D(d,d')$.

Note that symmetry is needed to define composition: the only possible definition is

$\big(C(c,c')\otimes D(d,d')\big)\otimes\big(C(c',c'')\otimes D(d',d'')\big) \to ... \to C(c,c'')\otimes D(d,d'')$

James Deikun (May 06 2025 at 07:46):

Wow, so generically categories enriched in a non-symmetric monoidal category don't even have a tensor product? I guess you can get one though if you enrich in the colax product of a [[duoidal category]] $V$ -- then the other (lax) product induces a tensor product on $V$-enriched categories.

Nathanael Arkor (May 06 2025 at 07:56):

Yes, this is Proposition 18 of Garner and López Franco's Commutativity. (See also section 13 of Lucyshyn-Wright's V-graded categories and V-W-bigraded categories.)

John Baez (May 06 2025 at 08:21):

You can define:

• graphs enriched in a category
• categories enriched in a monoidal category
• monoidal categories enriched in a braided monoidal category
• braided monoidal categories enriched in a symmetric monoidal category
• symmetric monoidal categories enriched in a symmetric monoidal category

Note that in the last step it "stabilizes".

I believe all this should generalize to higher columns in the periodic table, e.g. for 2-categories (by which I really mean bicategories, sorry) you should be able to define

• 2-graphs enriched in a 2-category
• 2-categories enriched in a monoidal 2-category
• monoidal 2-categories enriched in a braided monoidal 2-category
• braided monoidal 2-categories enriched in a sylleptic monoidal 2-category
• sylleptic monoidal 2-categories enriched in a symmetric monoidal 2-category
• symmetric monoidal 2-categories enriched in a symmetric monoidal 2-category

James Deikun (May 06 2025 at 08:29):

I assume this means you should be able to define a 2-category (3-category) of these things. What happens if you want a (symmetric/sylleptic/braided) monoidal 2-category of the things, or for that matter if you're content with just a 2-graph of them?

John Baez (May 06 2025 at 08:59):

That's a great question, but maybe you can guess the pattern as well as I can - I haven't thought about this question recently. I think the method of working out a few simple cases and then wildly extrapolating to pose some general conjectures is good here.

Mike Shulman (May 06 2025 at 17:59):

You can also do a [[horizontal categorification]] and define categories enriched in a bicategory, or even a (virtual) double category. In this case, it's straightforward to see that you get a tensor product of enriched categories if you enrich in a monoidal double category, using the tensor product on the double category to tensor hom-objects together (in contrast to how the composition of the double category is used when defining composition in enriched categories).

This "explains" why you need braiding in the case of enrichment over a monoidal category, since a one-object monoidal double category is essentially a category with two interchanging monoidal structures, which by the Eckmann-Hilton argument (the [[delooping hypothesis]]) is the same as a braided monoidal category.

David Egolf (May 06 2025 at 18:19):

Let me see if I can figure out how composition works. For any three objects $(c,d), (c',d'), (c'',d'')$ in $C \otimes D$, we want a "composition" morphism:

• $:(C \otimes D)((c',d'), (c'',d'')) \otimes (C \otimes D)((c,d), (c',d')) \to (C \otimes D)((c,d), (c'',d''))$

We saw just above that $(C \otimes D)((c,d), (c',d')) = C(c,c') \otimes D(d,d')$, and we can use this to rewrite the above expression. Upon doing so, we get:

• $:(C(c',c'') \otimes D(d', d'')) \otimes (C(c,c') \otimes D(d,d')) \to C(c,c'') \otimes D(d,d'')$

If $V$ is a braided monoidal category, then we intuitively have the ability to re-order the left side. There is then a morphism corresponding to our composition morphism of following type:

• $:(C(c',c'') \otimes C(c,c')) \otimes (D(d',d'') \otimes D(d,d')) \to C(c,c'') \otimes D(d,d'')$

There is a morphism of this type that stands out to me. Because $C$ and $D$ are $V$-enriched, we have composition morphisms:

• $\mu_{(c, c', c'')}:C(c',c'') \otimes C(c,c') \to C(c,c'')$
• $\mu_{(d, d', d'')}:D(d',d'') \otimes D(d, d') \to D(d,d'')$

Both of these morphisms are morphisms of $V$, and so we can tensor them together to get a morphism presumably corresponding to our composition morphism.

David Egolf (May 06 2025 at 18:22):

It's not immediately clear to me that $V$ needs to be a symmetric monoidal category. (I think I only ended up using a braiding.) Is that needed so that this composition becomes associative, maybe?

Mike Shulman (May 06 2025 at 18:24):

It's not needed.

Mike Shulman (May 06 2025 at 18:25):

It's just that symmetric monoidal categories are so much more common than merely-braided ones that a lot of people don't bother being careful to check in what cases a braiding suffices.

Fernando Yamauti (May 06 2025 at 20:26):

Is all that story here supposed to generalize further to something like: the (n+1)-cat of V-enriched n-cats for V (k+1)-tuply monoidal is k-tuply monoidal?

John Baez (May 06 2025 at 20:33):

It must. Proving this would be a very nice challenge for higher category theorists: each person with their own approach to higher categories gets to prove their own version!

Fernando Yamauti (May 06 2025 at 21:03):

John Baez said:

It must. Proving this would be a very nice challenge for higher category theorists: each person with their own approach to higher categories gets to prove their own version!

My bad. I've edited my wondering question. But you probably already got what I meant before that.

Anyways, if that's true, it should be somewhere in Lurie's HA for (n,1).

David Egolf (May 07 2025 at 18:00):

It remains to work out what the identity elements are in $C \otimes D$. For any object $(c,d)$ we want an identity element, which is a certain morphism $:I \to (C \otimes D)((c,d), (c,d))$. Here $I$ is the tensor unit object of our enriching monoidal category $V$. Since $(C\otimes D)((c,d),(c,d)) = C(c,c) \otimes D(d,d)$, we are looking for a morphism $:I \to C(c,c) \otimes D(d,d)$.

Since $C$ and $D$ are $V$-categories, we have already identity elements $1_c:I \to C(c,c)$ and $1_d:I \to D(d,d)$. Then we can form $1_c \otimes 1_d:I \otimes I \to C(c,c) \otimes D(d,d)$. Finally, using a unitor isomorphism $I \otimes I \cong I$, we can get our identity element for $C(c,d)$.

David Egolf (May 07 2025 at 18:05):

I think that concludes the exercise of guessing what $C \otimes D$ might be! Going forward, I think knowing how to form $C \otimes D$ will be helpful for finding examples of profunctors.

David Egolf (May 07 2025 at 18:07):

Next, I'll plan to explore this comment:

Kevin Carlson said:

David Egolf said:

Here's the first specific question I'd like to explore in this thread: What are some examples of profunctors?

The most important profunctor is $\mathrm{Hom}: C^{\mathrm{op}}\otimes C\to \mathcal V.$ If you have functors $f,g: D,E\to C$ then there’s the restricted hom $\mathrm{Hom}(f(-),g(-)):D^{\mathrm{op}}\otimes E\to \mathcal V.$ If $f$ or $g$ picks out a single object then this restricted hom is a representable presheaf or copresheaf in the familiar sense! So one things profunctors do immediately is generalize representability to a concept that can vary in both variables at once.

David Egolf (May 12 2025 at 15:46):

I've been thinking about this Hom profunctor! One thing I like about this example is that it gives a profunctor for every $V$-category, where $V$ is a symmetric closed monoidal category. So we get a large source of examples of profunctors.

Another thing I like about the Hom profunctor is that it suggests this intuition: a profunctor assigns to a pair of objects a thing that is "between" them. In this case, we have between $c$ and $c'$ the $V$-object $\mathrm{Hom}(c,c')$. The action of the profunctor on morphisms intuitively I think has to do with "extending" what's between objects, via generalized pre/post composition. I'm hopeful that this intuition will be helpful for learning about composition of profunctors.

David Egolf (May 12 2025 at 15:48):

I am curious as to why we have this profunctor $\mathrm{Hom}$. I think this relates to how functors can induce profunctors, and I want to get to that shortly.

David Egolf (May 12 2025 at 15:50):

Before doing that, I first want to consider the case where we have functors $f:D \to C$ and $g:E \to C$. Can we somehow use these to create a new "restricted hom" profunctor $:D^{\mathrm{op}} \otimes E \to C^{\mathrm{op}} \otimes C \to_{\mathrm{Hom}} V$?

David Egolf (May 12 2025 at 15:55):

If we can form some $f^{\mathrm{op}}:D^{\mathrm{op}} \to C^{\mathrm{op}}$ then we might be in business, as we could maybe form some $V$-functor $f^{\mathrm{op}} \otimes g:D^{\mathrm{op}} \otimes E \to C^{\mathrm{op}} \otimes C$ by "tensoring" somehow. Then, precomposing this $V$-functor before our hom functor I think presumably would give our restricted hom functor.

David Egolf (May 12 2025 at 15:58):

I don't actually know, though, if we can:

1. form the "opposite" of a $V$-functor
2. "tensor" two $V$-functors (although we've discussed already that we can tensor two $V$-categories)

David Egolf (May 12 2025 at 16:06):

It looks like page 12 of "Basic Concepts of Enriched Category Theory" (by Kelly) is relevant to both of these questions!

In short, it sounds like we can do both of these things, and so we can presumably form the restricted hom functor as I outlined above. (It would probably be a good exercise to check (1) and (2) work out in the "obvious" way, but I'm not sure I want to do that right now.)

Mike Shulman (May 12 2025 at 16:36):

You're absolutely right about all of that! And in fact, these restricted hom-profunctors are extremely important. If you want a hint as to one reason why, you could try asking yourself what they might have to do with $V$-adjunctions.

Kevin Carlson (May 12 2025 at 19:07):

You could also focus on the idea of restricting hom in the non-enriched setting; learning about profunctors and learning about enriched category theory are substantially orthogonal goals, although profunctors serve certain more important roles in the enriched theory that don't tend to fully show up in the unenriched case.

Kevin Carlson (May 12 2025 at 19:07):

As for why Hom exists, it's kind of like asking why identity morphisms exist. Hom is fundamental as a profunctor, not derived from anywhere else.

Mike Shulman (May 12 2025 at 19:25):

I don't think it's quite the same as why identity morphisms exist. I would say it's more analogous to why representable functors exist, or why the action of a group on itself exists. Those facts all depend in particular on associativity: a magma (even a unital magma) doesn't act on itself, at least not in the obvious way.

David Egolf (May 14 2025 at 18:24):

Thanks to both of your for your comments!

It probably does make sense to focus on the non-enriched setting, at least to start out with. I wanted to think about the enriched setting at least a little bit though, just to have access to more examples. But maybe now I'll switch focus to the non-enriched setting.

David Egolf (May 14 2025 at 18:26):

Mike Shulman said:

You're absolutely right about all of that! And in fact, these restricted hom-profunctors are extremely important. If you want a hint as to one reason why, you could try asking yourself what they might have to do with $V$-adjunctions.

I do want to understand how profunctors relate to tensor-hom adjunctions, and maybe this is in that spirit. I'm not quite sure where to start with this line of thought, though.

Mike Shulman (May 14 2025 at 18:28):

What sort of relationship between profunctors and tensor-hom adjunctions do you have in mind?

Mike Shulman (May 14 2025 at 18:28):

I mean, did you see someone say that they are related in a particular way and you want to understand that?

David Egolf (May 14 2025 at 18:43):

Mike Shulman said:

What sort of relationship between profunctors and tensor-hom adjunctions do you have in mind?

So, I'm thinking of a profunctor as like a bimodule: something that describes two compatible "actions" on something. That's the kind of thing we need to define a tensor product, I believe. For example, we can tensor a set with two compatible monoid actions against a set with an appropriate monoid action. Or we can tensor a commutative group with two compatible ring actions (a bimodule) against a commutative group with an appropriate ring action (a module).

David Egolf (May 14 2025 at 18:46):

"Sheaves in Geometry and Logic" also introduces a "tensor product" of set-valued functors on p. 353.

Mike Shulman (May 14 2025 at 18:46):

Ah, so you mean tensor products of profunctors.

David Egolf (May 14 2025 at 18:46):

I am hoping that all this tensoring is secretly tensoring of profunctors.

David Egolf (May 14 2025 at 18:48):

So maybe what I want to understand next is how to tensor profunctors, and maybe to see how this gives the appropriate thing in some special cases.

John Baez (May 14 2025 at 18:48):

Your examples sounded to me like examples of what I'd call composing profunctors.

Mike Shulman (May 14 2025 at 18:48):

It's the same thing.

Mike Shulman (May 14 2025 at 18:49):

(I mean, there are also other kinds of tensor products of profunctors, but I think it's reasonable to also call the "composition" of profunctors a "tensor product".)

John Baez (May 14 2025 at 18:50):

Okay. I will call it composition of profunctors, but for some reason I will also call it tensoring of bimodules. I guess it's just a cultural thing.

John Baez (May 14 2025 at 18:52):

When David talked about tensoring profunctors, I imagine taking profunctors $F: A \to B$ and $G: C \to D$ and tensoring them to get $F \otimes G : A \otimes C \to B \otimes D$. But anyway, he's not talking about that.

John Baez (May 14 2025 at 18:52):

I'm just trying to figure out what he's interested in, and I think maybe I know by now, from his examples.

John Baez (May 14 2025 at 18:55):

For example if I have a set $S$ with compatible left and right actions of monoids $M$ and $N$, that's the same as a profunctor from the 1-object category $BM$ to the 1-object category $BN$.

And then if I have a set $T$ with compatible left and right actions of $N$ and $O$, I can "tensor" $S$ and $T$ and get a set $S \otimes_N T$ with compatible left and right actions of $M$ and $O$. And that's an example of composing profunctors.

John Baez (May 14 2025 at 18:56):

(David was looking at an example where one of these actions was trivial so it looked like you had a set with just one monoid acting on it.)

John Baez (May 14 2025 at 19:00):

For some reason I don't know a super-standard name for a set with compatible left and right actions of two monoids; it should be called something like a "biaction". But there's a super-standard name for the same thing in the Ab-enriched world, namely an abelian group with compatible left and right actions of two rings. Everyone calls this is a "bimodule".

So, sometimes the word "bimodule" gets extended to mean "enriched profunctor".

David Egolf (May 14 2025 at 19:05):

Yes, this is all exactly the kind of thing I'm interested in. I'm also keeping in mind the example (hopefully I'm not misremembering and it is actually an example!) of composition of relations. I think this is also a tensoring of profunctors.

David Egolf (May 14 2025 at 19:06):

I would like to build on all this intuition to understand the general definition of compositon/tensoring of profunctors. (And then I'm curious if we can understand how to build a tensor-hom adjunction from a given profunctor. But one step at a time!)

Mike Shulman (May 14 2025 at 19:09):

John Baez said:

For some reason I don't know a super-standard name for a set with compatible left and right actions of two monoids; it should be called something like a "biaction".

I feel like I may have seen this called a "G-H-biset", analogous to "G-set" for a set with a single action.

John Baez (May 14 2025 at 19:12):

David Egolf said:

Yes, this is all exactly the kind of thing I'm interested in. I'm also keeping in mind the example (hopefully I'm not misremembering and it is actually an example!) of composition of relations. I think this is also a tensoring of profunctors.

A relation is an example of a Bool-enriched profunctor, since for each pair of elements in your two sets it's giving you a boolean. (A plain old profunctor gives you, for each pair of objects in your two categories, a set.)

Composing relations can then be seen as composing Bool-enriched profunctors.

James Deikun (May 14 2025 at 19:14):

One thing relations have that general profunctors don't is the converse, because sets are all groupoids. There's a notion of "ordered relation" of posets that doesn't have the converse!

John Baez (May 14 2025 at 19:14):

Bool is like a "baby" or "decategorified" version of Set, so compared to ordinary Set-enriched things, Bool-enriched things tend to be simpler, and the word "enriched" is a bit misleading: I actually feel like saying "impoverished" in this particular case!

David Egolf (May 14 2025 at 19:27):

Thanks everyone! I'll stop here for today as I'm getting tired, but next time I think I'll start to move towards understanding the composition/tensoring of profunctors. This involves a "coend", so this may be a great chance for me to learn a bit about coends!

John Baez (May 15 2025 at 08:55):

Indeed, coends and profunctors go hand in hand!

Each time you've been saying you want to learn about profunctors and hom-tensor adjunctions, I've been scratching my head thinking you should either be saying "I want to learn about profunctors and coends" or "I want to learn about hom-tensor adjunctions and closed categories".

David Egolf (May 16 2025 at 15:30):

John Baez said:

Each time you've been saying you want to learn about profunctors and hom-tensor adjunctions, I've been scratching my head thinking you should either be saying "I want to learn about profunctors and coends" or "I want to learn about hom-tensor adjunctions and closed categories".

At first I had thought I might really be wanting to learn about closed categories. However, in a closed category the "tensor against a fixed object" functor is an endofunctor. By contrast, tensoring against a bimodule/"biaction" takes in a thing of one kind and produces a thing of a different kind.

David Egolf (May 16 2025 at 15:36):

So - how to compose/tensor profunctors? A profunctor $p$ from $A$ to $B$ is a functor $:A^{\mathrm{op}} \times B \to \mathsf{Set}$. I will sometimes view this as a morphism in a category $\mathsf{Prof}$ from $A$ to $B$, and sometimes view this as a functor from $A^{\mathrm{op}} \times B$ to $\mathsf{Set}$.

If we have a profunctor $p:A \to B$ and another $q:B \to C$, the book "Coend calculus" states that we can define their composite $q \circ p:A \to C$ as follows:

• $(q \circ p)(a,c) = \int^{b \in B}p(a,b) \times q(b,c)$

David Egolf (May 16 2025 at 15:38):

...where the right side is apparently a "coend". So it will take some learning to unravel what exactly this definition means.

John Baez (May 16 2025 at 15:39):

When reading that formula, I hope your heart sings out "matrix multiplication".

David Egolf (May 16 2025 at 15:40):

Oh! Thanks for pointing that out! It is indeed a lot like the matrix multiplication formula, although I hadn't noticed that yet.

The intuition I had so far was more from composing relations: a way in which $a$ and $b$ are related, together with a way in which $b$ and $c$ are related - that gives us a way in which $a$ and $c$ are related.

David Egolf (May 16 2025 at 15:48):

I found a set of slides from a talk you gave in 2007, which maybe visualizes the matrix multiplication intuition:

visualization

John Baez (May 16 2025 at 15:48):

Yes, there I was showing how composing spans is a special case of matrix multiplication.

We can work with matrices valued in any [[rig]], since we just need to know how to add and multiply matrix entries in a way that obeys the usual laws. Composing relations is matrix multiplication where the matrices take values in the boolean rig $\mathbb{B} = \{T,F\}$.

Composing spans is a bit more sophisticated because the matrix entries are sets, which are objects in a kind of '2-rig'.

Composing profunctors is like that, but we also need to replace addition by a colimit, as hinted by that integral sign you wrote down.

John Baez (May 16 2025 at 15:50):

So, it's good to think of all these things - relations, matrices, spans and profunctors - as different examples of the same idea. This will allow you to save a lot of work relearning things over and over. Even if you don't know the formal abstraction that captures all these examples, you can still mentally put them all on the same shelf in your mind. It's all "linear algebra", as far as I'm concerned.

David Egolf (May 16 2025 at 15:54):

I think it's very cool when so many ideas can be grouped together helpfully like that! One thing I like about that is this: if you recognize that two ideas are secretly in the same spirit, then intuition or concepts about one have hope to be transferred to intuition or concepts for another. This might not always work out, but probably can lead to surprising and fun questions like "Do we have a notion of an eigenvector for a relation?". This can also probably help one understand new concepts more quickly by analogy.

David Egolf (May 16 2025 at 15:54):

For the profunctor case, I'm wondering if this intuition will be helpful: $p(a,b)$ is like a set of paths from $a$ to $b$.

David Egolf (May 16 2025 at 15:58):

Exploring this idea a little bit - if we have a morphism $f:b \to b'$ in $B$, then $p(1_a, f):p(a,b) \to p(a,b')$ lets us create a path from $a$ to $b'$ given a path from $a$ to $b$, using $f$. That seems intuitively reasonable.

John Baez (May 16 2025 at 15:58):

Yes, that's a good point of view. As you may have seen (maybe in those slides of mine), Heisenberg thought of $p(a,b)$ as the amplitude to get from $a$ to $b$, which is a number. Feynman later computed these amplitudes as an integral over the set of all paths from $a$ to $b$.

So Feynman was doing a kind of decategorification of the idea you are talking about now, where you are imagining $p(a,b)$ as the set of paths from $a$ to $b$. It's decategorification because he was taking a set (an object in a category) and turning it into a number (an element of a set).

(It wasn't just a bare set, of course: to integrate you need a set with a measure on it, and maybe also a function on it. But I'm trying to talk in a broad-brush way here.)

John Baez (May 16 2025 at 16:01):

In short, yes: relations, matrices, spans and profunctors are all about how you can get from $a$ to $b$, or whether you can get from $a$ to $b$, or with what probability or amplitude can you get from $a$ to $b$.

John Baez (May 16 2025 at 16:03):

But you're focusing in on profunctors, and pointing out that if $a \in A$ and $b \in B$ are objects of categories, then we can combine any way to go from $a$ to $b$ with a morphism in $A$ and/or $B$ to get a way to go from $a'$ to $b'$.

John Baez (May 16 2025 at 16:04):

This extra twist doesn't show up for the simplest sort of relations, matrices or spans - it's characteristic of profunctors, simply because profunctors go between categories. It also shows why you want an 'op' in the definition of profunctor.

David Egolf (May 16 2025 at 16:08):

Just to spell that out a bit more: if we have a morphism $g:a \to a'$ in $A$, then we intuitively want a way to convert paths $p(a',b)$ to paths $p(a,b)$ using $g$. So we need an "op" to make this a functor.

David Egolf (May 16 2025 at 16:13):

So if I were to naively guess as to how to compose two profunctors $p$ and $q$, my first guess would be as follows. To find all the paths from $a$ to $c$, we first form the product $p(a,b) \times q(b,c)$ for each $b \in B$. Each such set contains as elements the information needed to describe a path from $a$ to $c$. Then I'd want to take the disjoint union of all these sets.

John Baez (May 16 2025 at 16:14):

Right! Very good. But "disjoint union" is obviously a bit wrong when your category has a bunch of isomorphic objects, or even a bunch of "morphic" objects. So you gotta be a bit more sophisticated.

John Baez (May 16 2025 at 16:18):

And this will lead you to invent coends....

David Egolf (May 16 2025 at 16:18):

Hmm I see! If $b$ and $b'$ are isomorphic, then maybe we don't want to count paths from $a$ to $c$ that pass through either $b$ or $b'$ as really different, for example. So some thought will be needed to properly come up with all the distinct paths.

And yes! I'm hoping that thinking in this direction will help the definition of coend make some intuitive sense. :sweat_smile:

John Baez (May 16 2025 at 16:20):

You'll just automatically reinvent it by trying to straighten out this "redundancy" problem.

John Baez (May 16 2025 at 16:21):

Even if $b$ and $b'$ are just "morphic", i.e. there's a morphism $f: b \to b'$, you don't want to count paths from $a$ to $c$ that pass through either $b$ or $b'$ as completely different.

John Baez (May 16 2025 at 16:22):

This is the redundancy problem.

David Egolf (May 16 2025 at 16:28):

Oh! That's surprising to me. I guess I don't fully understand which paths we want to count then.

David Egolf (May 16 2025 at 16:29):

Or maybe this speaks to some limitation of the "paths" intuition.

David Egolf (May 16 2025 at 16:31):

I'll think about this for a while. :slight_smile:

John Baez (May 16 2025 at 16:33):

You just need to sharpen up your intuition. If you start with categories that are groupoids, you don't have to worry about certain nuances, and you can focus on trying to eliminate redundancies due to isomorphisms. But in a general category, you're not going to want to treat isomorphisms in a completely different way from other morphisms - that's too ugly, you never want to do a "case by case" definition in category theory. So you need a nice thing to do with morphisms that does what you want when they're isomorphisms.

David Egolf (May 16 2025 at 16:57):

I think I was able to visualize the situation:
path redundancy

David Egolf (May 16 2025 at 16:58):

There's a single "path" here, from $a$ to $b'$ to $b$ to $c$. However we can build it up in two ways:

• travel from $a$ to $b'$, and then from $b'$ to $c$ (passing through $b$)
• travel from $a$ to $b$ (passing through $b'$), and then from $b$ to $c$

David Egolf (May 16 2025 at 16:59):

To do this, we made use our ability to travel from $b'$ to $b$, which presumably corresponds to a morphism in $B$ from $b'$ to $b$. So we see that having even just "morphically" related objects can result in multiple ways to build up the same path.

David Egolf (May 16 2025 at 17:02):

(I say "path" but it's more like a "travel route". We're not keeping track of the "speed" at which are traversing from one object to another, and we aren't associating each part of an "interval" to parts of our traversal.)

Kevin Carlson (May 16 2025 at 19:03):

Yes, this is a key idea left in the notion of coend! Maybe you’re ready to start thinking mathematically about what this picture means you ought to do with that disjoint union of products you’d mentioned earlier?

David Egolf (May 21 2025 at 19:15):

I would like to do that! There are some elements of $\coprod_{b} p(a,b) \times q(b,c)$ that correspond to the same routes, as visualized in the image above. So, I am guessing there is a diagram involving the $p(a,b) \times q(b,c)$ (as $b$ varies) such that taking the colimit give us all the distinct routes. I'm not quite sure how to dream up this diagram yet, though.

David Egolf (May 21 2025 at 19:18):

Drawing inspiration from the drawing above, I'm currently thinking of a route from $a$ to $b$ as involving three parts:

1. Some morphism in $A$ with source of $a$
2. Something "between the categories" $A$ and $B$
3. Some morphism in $B$ with target of $b$.

And the thing "between the categories" needs to be compatible with the morphisms in (1) and (3).

David Egolf (May 21 2025 at 19:20):

I suppose in the case of a route from $a$ to $c$ that passes through $B$, the thing "between the categories" $A$ and $C$ includes a few pieces:

• something between $A$ and $B$
• a morphism in $B$
• something between $B$ and $C$.

David Egolf (May 21 2025 at 19:26):

I don't know if trying to express the routes in the picture above using a decomposition like this will be helpful for figuring out an appropriate colimit.

David Egolf (May 21 2025 at 19:49):

Oh, I remembered the term "heteromorphism" - maybe that's relevant when thinking about things "between" objects in different categories.

Intuitively, maybe what I'm trying to understand relates to the idea that some "composition" of heteromorphisms should be associative.

John Baez (May 21 2025 at 20:11):

Following the principle that it's good to draw everything you've got in a diagram, it might be useful to see what maps you have between sets of the form

$p(a,b) \times q(b,c)$

given the fact that $p$ and $q$ are functors, and try to draw these maps in a diagram, and let that guide your thoughts a bit.

David Egolf (May 21 2025 at 20:41):

Thanks for the hint! I am planning to give your hint some thought.

I'm also realizing that we can write a route $A \to B \to C$ in two pieces, say $(f,g)$. Here $f$ is a route that starts in $A$ and ends in $B$, while $g$ is a route that starts in $B$ and ends in $C$. Then we can consider the case where one of these two pieces is given by "extending" some smaller piece, so we have something like $(h \circ f, g)$ or $(f, g \circ h)$. Then extending the first piece "at the end" should give the same route as extending the second piece "at the start".

David Egolf (May 21 2025 at 20:42):

So I think that $(h \circ f,g)$ and $(f, g \circ h)$ should give the same route. Keeping something like this in mind might be helpful as I search for a colimit diagram.

[If we use $\otimes$ instead of $(-,-)$, then we're wanting to view $(h \circ f) \otimes g$ as the same as $f \otimes (g \circ h)$. And if I write $fh$ to mean $h \circ f$, we want to view $(fh) \otimes g$ as the same as $f \otimes (hg)$. This starts to reminds me of the tensor product of modules!]

John Baez (May 21 2025 at 20:52):

David Egolf said:

So I think that $(h \circ f,g)$ and $(f, g \circ h)$ should give the same route. Keeping something like this in mind might be helpful as I search for a colimit diagram.

Yes, this sounds like a crucial observation. You could have gotten it by following my suggestion to just draw all the maps between sets of the form

$p(a,b) \times q(b,c)$

But you got it in a more thoughtful way. My approach is nice for when you're feeling clueless: you just draw all the maps and see when two might be equal and what it would mean for them to be equal.

David Egolf (May 26 2025 at 00:26):

I think I can encode part of what I want in a pushout diagram. If we have an "almost" route that is just missing a middle piece, here are two ways to fill in that missing piece: we can extend the first part of the incomplete route, or we can extend the second part. If we use the same "route segment" to do this, these two approaches should intuitively yield the same route.

pushout diagram

David Egolf (May 26 2025 at 00:28):

(Here, I think of $q(m,1_c):q(b',c) \to q(b,c)$ as in the spirit of "precomposing a route $:b \to c$ with $m:b \to b'$".)

So if we have a route from $a$ to $b$ and a route from $b'$ to $c$, we can make a route from $a$ to $c$ given a morphism $m:b \to b'$ in two ways:

1. (travel from $a$ to $b$, and then to $b'$ using $m$) and then to $c$
2. travel from $a$ to $b$ (and then to $b'$ using $m$, and finally to $c$)

David Egolf (May 26 2025 at 00:29):

I think the pushout will end up being the disjoint union of $p(a,b) \times q(b,c)$ and $p(a,b') \times q(b',c)$, except that we identify two routes if they can both be formed from the same incomplete route in $p(a,b) \times q(b',c)$ using $m$.

David Egolf (May 26 2025 at 00:35):

However, this is not yet what I want! There may be additional elements that I would like to identify between $p(a,b') \times q(b',c)$ and $p(a,b) \times q(b,c)$. In particular, if there is another morphism $n:b \to b'$ from $b$ to $b'$, then I will want to identify additional elements.

David Egolf (May 26 2025 at 00:37):

Beyond this, I also want to do a similar "gluing"/quotienting process as $b$ and $b'$ vary. So there is a lot of "quotienting" that I want to somehow organize tidily!

David Egolf (May 26 2025 at 01:06):

I guess I'm hoping to get a nice clean colimit diagram that gives $(q \circ p)(a,c)$ in terms of $p(a,b)$ and $q(b,c)$ as $b$ varies. But maybe that's hoping for too much?

I may take a look at some references and see how they organize this information. In particular, this might be a good time to look at the definition of a coend - hopefully it relates to the intuition developed in this thread!

David Egolf (May 26 2025 at 01:19):

It would be fantastic if the notion of "coend" cleanly organizes all the quotienting I want to do in the context of composition of profunctors.

John Baez (May 26 2025 at 08:00):

You almost stated the definition of coend just now! The diagram you drew is the key part in the definition of coend, or at least one popular definition. What you wrote will look more like the usual coend if you abstract from the situation at hand, and write

$p(a,b) \times q(b',c) = A(b,b')$

hiding the role of $a$ and $c$, which are fixed in the process you are focused on, and highlighting the role of $b$ and $b'$. Note that $A(b,b')$ is covariant in $b$ and contravariant in $b'$ - or maybe the other way around if I'm confused, but the main point is that they have opposite variances.

John Baez (May 26 2025 at 08:01):

So a coend is a thing you can construct whenever you have a thing like this $A(b,b')$, and you've pretty much explained how to construct it.

David Egolf (May 29 2025 at 18:43):

Thanks for explaining that! I think this is making sense to me.

In this context, let me now write out the definition of a coend (from "Coend Calculus"). I anticipate this will be interesting to compare with the discussion above.

David Egolf (May 29 2025 at 18:52):

Referencing Definition 1.1.6 in Coend Calculus, I think a coend for a functor $P:C^{\mathrm{op}} \times C \to D$ is an "initial cowedge" for $P$.

A "cowedge" for $P:C^{\mathrm{op}} \times C \to D$ is a dinatural transformation $:P \to \Delta_d$, where $\Delta_d:C^{\mathrm{op}} \times C \to D$ is a functor constant at some $d \in D$.

John Baez (May 29 2025 at 18:52):

By the way, I'm right now at a retreat for math grad students at a country house in Scotland, and they loved the 'plane trips and taxi rides' story about composing profunctors, and used it to come up with the definition of coend (with a little nudging from me), and then polished it up into a colimit over a twisted arrow category, and also came up with another approach using the [[collage]] of a profunctor.

David Egolf (May 29 2025 at 18:54):

Nice! I've noted the phrase "twisted arrow category" as well as "collage" for possible future exploration. :slight_smile:

David Egolf (May 29 2025 at 18:57):

I notice that "extranatural transformations" can also be used to define profunctors, instead of "dinatural transformations". But, for the purpose of starting somewhere, I'll stick with dinatural transformations for the moment.

David Egolf (May 29 2025 at 18:58):

So for the definition above to be useful, we need to know what a dinatural transformation is.

John Baez (May 29 2025 at 18:59):

Even those are a bit too fancy for me to have incorporated them into my ways of defining coends, but that's probably just my own fault. I just know how to construct coends, not describe their universal property as an 'initial cowedge'.

David Egolf (May 29 2025 at 19:03):

I see! Well, I'm curious to try and understand this definition from "Coend calculus". If it ends up being a bit too fancy for me to intuitively understand at this point, then that's fine as well. But I'll give it a try!

David Egolf (May 29 2025 at 19:10):

So, here is the notion of "dinatural transformation".

Let $P,Q:C^{\mathrm{op}} \times C \to D$ be functors. A dinatural transformation $\alpha:P \to Q$ is first of all a family of morphisms (in $D$) $\alpha_c:P(c,c) \to Q(c,c)$ indexed by the objects of $C$. We also require that for any $f:c \to c'$ in $C$ the following diagram to commute:
diagram

David Egolf (May 29 2025 at 19:13):

I wonder if we can understand this intuitively in the spirit of the discussion above. Maybe we can think of $P(c',c)$ as in the spirit of a set of "routes" that travel to $c'$, are interrupted, and then pick up again at $c$ (with some fixed but unstated overall starting and ending points).

If we can understand $Q$ in a similar way (as providing potentially "partial" routes), then perhaps we can try to understand a dinatural transformation as describing a way to relate the partial routes of $P$ to the partial routes of $Q$.

David Egolf (May 29 2025 at 19:25):

I guess my current question that I'd like to explore is this: How can we intuitively (possibly through examples) understand the notion of "dinatural transformation"?

David Egolf (May 29 2025 at 19:30):

Actually, I think I specifically want to focus on the case where $Q$ is a constant functor. (This relates closely to cowedges!) Next time, I may start by redrawing the diagram above for that case.

David Egolf (May 30 2025 at 17:10):

Here's what part of a cowedge under $P$ looks like (so $Q$ is a constant functor):
cowedge

This looks very much like the pushout diagram I drew above! However, in this case, we don't require the square to be a pushout diagram.

David Egolf (May 30 2025 at 17:19):

I was thinking that the constant (set) output of $Q$ needs to be a pushout for all such squares simultaneously. But that doesn't make sense: each such square only requires us to identify certain routes. So if we identify too many, we won't get a pushout square.

David Egolf (May 30 2025 at 17:21):

Instead, our set $Q(c,c')$ (which is the same for all $(c,c')$) needs to just make each square commute and then be initial with respect to that property. Each individual square requires that we "glue together" certain routes, and $Q(c,c')$ making each such square commute means that all of the desired routes are glued together.

David Egolf (May 30 2025 at 17:26):

If we think of $P$ as specifying "partial routes" with a fixed start point and end point, then I suspect an initial cowedge under $P$ gives us exactly the unique "completed" routes from that starting point to that end point. Requiring the cowedge to be initial I think means that we avoid identifying too many routes, and avoid introducing new unwanted elements.

David Egolf (May 30 2025 at 17:27):

If this is on the right track, I think I can then begin to see how using a coend makes sense for composition of profunctors!

David Egolf (May 30 2025 at 17:37):

[Perhaps one thing I can take away from this: If one has many diagrams one wants to make commute, sometimes this situation can be organized by using something in the spirit of a natural transformation.]

David Egolf (Jun 03 2025 at 17:39):

I feel pretty happy with the above! Next, I think I would like to work out a special case of profunctor composition.

Specifically, I would like to work out the composition of a profunctor $:1 \to C$ with a profunctor $:C \to D$. And to start with, I'll consider the case where $C$ and $D$ both have a single object.

(By $1$ I mean a terminal category, having a single object and a single morphism.)

David Egolf (Jun 03 2025 at 17:43):

A profunctor $:1 \to C$ is a functor $:C^{\mathrm{op}} \to \mathsf{Set}$. When $C$ has a single object, I think this amounts to a right action of a monoid. A profunctor $:C \to D$ is a functor $:C \times D^{\mathrm{op}} \to \mathsf{Set}$. When $C$ and $D$ have a single object, I think such a profunctor amounts to a set together with a left action of some monoid $C$ on it, compatible with the right action of some monoid $D$ on it. Upon composing these profunctors, we'll get a profunctor $:1 \to D$, which is a right action of the monoid $D$ on some set.

David Egolf (Jun 03 2025 at 17:44):

But how exactly does this work? I'd like to use the discussion above regarding profunctor composition to work this out in some detail.

David Egolf (Jun 03 2025 at 17:55):

So let us imagine we have profunctors $P:1 \to M$ and $Q:M \to N$, where $M$ and $N$ are monoids (thought of as categories with a single object). Then $(Q \circ P):1 \to N$. This corresponds to a functor $1 \times N^{\mathrm{op}} \to \mathsf{Set}$. If we call the single object of $1$ by the name $\ast$, and the single object of $N$ by the name $\ast_N$, then there is a set $(Q \circ P)(\ast, \ast_N)$. What is this set?

David Egolf (Jun 03 2025 at 17:57):

I expect $(Q \circ P)(\ast, \ast_N)$ to be something like a set of "tensors". Let's see what we get!

David Egolf (Jun 03 2025 at 18:07):

Here's a picture to visualize the situation: [EDIT: I ended up creating a second version of this picture and accompanying discussion below, which I think improves on this one]
forming "routes"

David Egolf (Jun 03 2025 at 18:10):

We can start with a partial route, which consists of: the identity morphism in $1$, together with some morphism $n$ in $N$. This is missing just some $m \in M$ to complete the route.

We get two complete routes that we want to consider the same:

1. identity morphism of $\ast$, followed by $m$; then $n$
2. identity morphism of $\ast$; then $m$ followed by $n$

We might write these two routes as follows: $(m \circ 1_\ast, n)$ and $(1_\ast, n \circ m)$.

David Egolf (Jun 03 2025 at 18:27):

I'm getting tired, so I'll stop here for today. Next time, to avoid getting confused, I'm hoping to draw the diagram that describes what a cowedge is in this setting.

John Baez (Jun 03 2025 at 18:30):

One thing you almost but didn't quite do in your previous round of exploring profunctor composition, is to explicitly describe the set $(Q \circ P)(\ast, \ast_n)$, or more generally the sets $(Q \circ P)(a,b)$ for any composite of profunctors (they work exactly like the example you're doing now). So I'm eager to see the explicit description you get out of this cowedge stuff.

David Egolf (Jun 03 2025 at 18:44):

Before stopping for today, I want to adjust the discussion I provided above relating to this picture:

creating routes V2

David Egolf (Jun 03 2025 at 18:46):

I've labelled the black lines this time, which I'm now thinking as being elements of the profunctors involved. So $a$ is a "route" from $\ast_1$ to $\ast_M$, and is an element of $P(\ast_1, \ast_M)$. Similarly, $b$ is an element of $Q(\ast_M, \ast_N)$.

I've also removed $n:N \to N$ from the drawing, as I don't think we need it right now.

David Egolf (Jun 03 2025 at 18:49):

Then we have two things we can do with $m$: (1) we can use $P$ to act on $a$ using $m$ to create a new route $:\ast_1 \to \ast_M$ or (2) we can use $Q$ to act on $b$ to create a new route $:\ast_M \to \ast_N$.

We might intuitively write this as $(a.m,b) = (a,m.b)$. Or perhaps $(am) \otimes b = a \otimes (mb)$.

Next time, I'll try to describe this using a diagram involving cowedges! And hopefully that is then helpful for explicitly describing $(Q \circ P)(\ast,\ast_N)$.

Ryan Wisnesky (Jun 03 2025 at 20:17):

is there an underlying mathematical or philosophical reason why work on profunctors seems to be dominated by considering them as A*B^op->Set rather than A->Set^B^op?

John Baez (Jun 03 2025 at 20:19):

David wrote:

We might intuitively write this as $(a.m,b) = (a,m.b)$. Or perhaps $(am) \otimes b = a \otimes (mb)$.

Okay, now you've come EXTREMELY close to explicitly describing $(Q \circ P)(\ast,\ast_N)$. Let me finish the job, because I can't stand the torture any more. :wink:

Here's the explicit description:

$\displaystyle{ (Q \circ P)(\ast,\ast_N) = \frac{\sum_{m \in M} \text{hom}(\ast, m) \times \text{hom}(m, \ast_N)}{(a.m,b) \sim (a,m.b)} }$

John Baez (Jun 03 2025 at 20:22):

First you're taking the coproduct over all objects $m \in M$ of the product of homsets

$\text{hom}(\ast, m) \times \text{hom}(m, \ast_N)$

Then you're taking a quotient of this by the equivalence relation generated by $(a.m,b) \sim (a,m.b)$.

So, you're first doing a coproduct and then a coequalizer! Since both these are colimits, you're doing a colimit.

There are more elegant ways to write this colimit, but this is perfectly serviceable.

More generally, any coend is a colimit rather similar to this one.

John Baez (Jun 03 2025 at 20:24):

I feel I'm not saying anything you don't know. I'm just making your thoughts more explicit by writing them out as a formula for the composite profunctor $Q \circ P$.