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: applied category theory

Topic: Relational version of Cat, Relators, Profunctors

Avi Craimer (Mar 09 2025 at 16:07):

Thanks @Ryan Wisnesky for the paper and thanks @Kevin Carlson for the further explanation.

I'm still kind of scratching my head here. I am thinking of profunctors in a very concrete way. Like as mappings from sets of objects and sets of morphisms. And I still can't figure out how they are supposed to be interpreted to represent relators. I can illustrate this with a specific example.

Suppose I have the walking arrow category A.
I'll call it's objects $\{A,B\}$

It has a single non-identity morphism $f: A \to B$

Now, there exists a subcategory/relator $C \subseteq A \times A$ which contains the following objects and morphisms.

$\{ (A,A), (B,B), (id_A,id_A), (id_B, id_B) \}$

In other words, $C$ relates everything in $A$ to itself except for $f$.

Now, what I can't see is how we can express this subcategory as a profunctor $P: A^{op} \times A \to Set$?

To start with trying to construct such a profunctor you would map the reflexive objects pairs to the singleton set to express the fact of being related:
$(A,A) \mapsto \{\ast\}$
$(B,B) \mapsto \{\ast\}$
And you can map the non-reflexive pairs to the empty set to express non-relation .
$(A,B) \mapsto \emptyset$
$(B,A) \mapsto \emptyset$

However, if we consider how to map the pair of morphisms $(f^{op},f): (B,A) \to (A,B)$. Since (B,A) and (A,B) are each mapped to $\emptyset$ we know the type of the function must be $\emptyset \to \emptyset$.

Ok, here are my initial questions:

1. Since the absurd function of this type can be regarded as an empty function, are we to regard this mapping as saying that $f^{op}$ is unrelated to $f$?

2. How should we interpret the profunctor mapping of $(f^{op},f)$ in terms of the relator mapping of $(f,f)$. Does the op matter here, or are these just different ways of talking about the relations between $f$ and itself? If the op does matter, then on the face of it there is no way for the profunctor to even talk about $f$ relating to itself as it can only say anything about how $f^{op}$ relates to $f$?

3. Assuming it does make sense to inter-translate

$(f^{op},f) \mapsto \text{ absurd with } (f,f) \notin C$

Then would this mean our profunctor can only omit $f$ from self-relation? If so then the problem becomes there is no way for the profunctor to express the full sub-category of $A \times A$. Since this would require sending $(f^{op},f)$ to $!:\{\ast\} \to \{\ast\}$ which is prohibited by the functor laws.

Ryan Wisnesky (Mar 09 2025 at 17:16):

do you speak relational database theory? I've found that for me personally, the most concrete intuition of a pro functor C * D^op -> Set is as family of relational conjunctive queries over C, one for each object in D, along with a morphism of these queries for each morphism in D^op. I've never really been able to master the heteromorphism syntax. Could you write your pro-query that way, in curried form, using SQL code, and then translate back to an uncurried pro functor presentation? In database land, statements such as "every database is a query" turn into statements about how pro functors relate to pre sheaves, etc.

Avi Craimer (Mar 09 2025 at 17:37):

Hi Ryan,

I read some of your papers on CQL years ago, very interesting stuff, but it has been a while. I'm not a database guy myself.

In the simplest possible terms, my question is:

When we are supposed to interpret profunctors as "categorified relations" what is the recipe for reading off the relational interpretation from a mapping of $(m^{op}, m') \mapsto f$?

In other words, how do we translate something like $(m^{op}, m') \mapsto f$ into a statement about how $m$ is related to $m'$? Conversely, how to translate a statement that $m$ is (or is not) related to $m'$ into a profunctorial mapping $(m^{op}, m') \mapsto f$?

Ryan Wisnesky (Mar 09 2025 at 17:52):

I can't quite figure out which CQL syntax would correspond to your desired subcategory, but I can write down the three smallest pro functor presentations on your walking arrow schema A, maybe it is one of those?

schema A = literal : empty {
    entities A B
    foreign_keys f : A -> B }

query Q1 = literal : A -> A {
    entity A -> {from a:A foreign_keys f->{b->f(a)}}
    entity B -> {from b:B} }

query Q2 = literal : A -> A {
    entity A -> {from a:A foreign_keys f->{}}
    entity B -> {} }

query Q3 = literal : A -> A {
    entity A -> {foreign_keys f->{}}
    entity B -> {} }

John Baez (Mar 09 2025 at 17:59):

Avi Craimer said:

I'm still kind of scratching my head here. I am thinking of profunctors in a very concrete way. Like as mappings from sets of objects and sets of morphisms. And I still can't figure out how they are supposed to be interpreted to represent relators. I can illustrate this with a specific example.

I could be wrong, but I think one problem is that you're hoping a relator $R \subseteq A \times A$ will give a functor $f: A^{\text{op}} \times A \to \mathsf{Set}$, but I don't see how that can possibly work. It seems more likely to give a functor $f: A \times A \to \mathsf{Set}$. After all, there's no "op" in your definition of relator.

A functor $f: A^{\text{op}} \times B \to \mathsf{Set}$ is usually called a profunctor from $A$ to $B$, though 48% of mathematicians use the other convention and call it a profunctor from $B$ to $A$. The main point is that the "op" sets up a distinction in roles between $A$ and $B$. A functor $f: A \times A \to \mathsf{Set}$ would thus be called a profunctor from $A^{\text{op}}$ to $A$. But never mind the terminology: see if you can get a functor $f: A \times A \to \mathsf{Set}$ from your relator $R \subseteq A \times A$.

Avi Craimer (Mar 09 2025 at 19:33):

@John Baez Yes, I kind of thought the same thing, but everybody says that profunctors are relations for categories so I was trying to see if they could actually work.

If we go with a regular bifunctor $F: A \times A \to Set$ then the problem is that we are forced by functor laws to map $(f,f) \mapsto !: \{\ast\} \to \{\ast\}$. So I don't see how this can represent the subcategory of $A \times A$ which leaves out $(f,f)$.

I'm just trying to establish that general relations on categories are not purely a special case of profunctors or bifunctors.

Kevin Carlson (Mar 09 2025 at 19:49):

The profunctor associated to the diagonal relation on $A$ that I suggested goes like this: you add a heteromorphism, as you did, $a\to a,b\to b$, realizing the relatedness of those two pairs. Then, I did not say to impose that there are no heteromorphisms between the other pairs! We’re freely generating a profunctor here. You could call it the left Kan extension of the terminal functor out of the two-point category along its diagonal inclusion into $A^\mathrm{op}\times A,$ if you like.

The profunctor freely generated by those two heteromorphisms then is empty over $(b,a)$ but has two elements over $(a,b)$ coming from the two generating heteromorphisms, acted on by $(f,id)$ and $(id,f)$ respectively. There are no relations to impose in this case; they’d have to come from generating heteromorphisms at $(b,a)$ acted on by $(f,f)$, but there are none of those.

John Baez (Mar 09 2025 at 20:27):

@Kevin Carlson - so you're really trying to build a profunctor from A to itself, not to its opposite? You could do either I suppose.

Kevin Carlson (Mar 09 2025 at 20:28):

Yeah, I guess this is a special case of the better known construction of the profunctor generated by a span of categories. You have a bunch of material sitting in between two categories $A$ and $B$ so you might as well make $A$ act on the left and $B$ on the right!

Kevin Carlson (Mar 09 2025 at 20:29):

Having gotten in this far I should now probably try to figure out to what extent you can actually recover a relator from the associated profunctor.

fosco (Mar 09 2025 at 20:34):

Avi Craimer said:

John Baez Yes, I kind of thought the same thing, but everybody says that profunctors are relations for categories so I was trying to see if they could actually work.

If we go with a regular bifunctor $F: A \times A \to Set$ then the problem is that we are forced by functor laws to map $(f,f) \mapsto !: \{\ast\} \to \{\ast\}$. So I don't see how this can represent the subcategory of $A \times A$ which leaves out $(f,f)$.

I'm just trying to establish that general relations on categories are not purely a special case of profunctors or bifunctors.

You have to change what you mean by "relation": a relation can be presented as a matrix of 0s and 1s, of size $|A|\times |B|$, where entry $(a,b)$ is 1 if (a,b) are related, and 0 otherwise. It's either "yes, aRb" or "no, $\lnot(aRb)$".

A profunctor is essentially the same, up to the crucial fact that you (must) have a whole set of ways in which $aRb$, and if your categories are not discrete, you have to take into account the fact that $$(a,b)\maptso R(a,b)$$ varies contravariantly in $a$.

Kevin Carlson (Mar 09 2025 at 20:35):

Avi is quite focused on internal relatjons, Fosco, so that you need to be able to specify related edges too. A Boolean matrix over the objects doesn’t help with that; I’ve been trying to see whether you can fold it into the profunctor formalism.

fosco (Mar 09 2025 at 20:37):

yes, I was trying to dispel the idea that "profunctors are relations for categories" in the sense that a profunctor captures a subcategory. It does not!

Kevin Carlson (Mar 09 2025 at 20:38):

Do you actually know that you can’t embed internal relations into profunctors? Certainly we’re agreed that profunctors are not just internal relations.

fosco (Mar 09 2025 at 20:39):

the mantra "profunctors are relations for categories" (to me) rather means "relations are nothing but profunctors between sets" a relation arises in the same way as Prof, from the Kleisli bicategory of a KZ-monad.

The middle school representation of a function, left potato, right potato, arrows... that's the cospan representation of a profunctor into {0,1}! That's what we should teach kids! /s

Kevin Carlson (Mar 09 2025 at 20:40):

Sure, but none of that’s actually related to the question I asked.

Kevin Carlson (Mar 09 2025 at 20:42):

It’s not very good if the category theorist’s answer to someone saying “I want to study relations between categories” is only “you shouldn’t want that, you should want profunctors”, even though that may well be true in many cases. Much better to understand to what extent you can have both.

fosco (Mar 09 2025 at 20:49):

Kevin Carlson said:

Sure, but none of that’s actually related to the question I asked.

what is the question you asked?

Kevin Carlson (Mar 09 2025 at 20:52):

Kevin Carlson said:

Do you actually know that you can’t embed internal relations into profunctors? Certainly we’re agreed that profunctors are not just internal relations.

fosco (Mar 09 2025 at 20:53):

It’s not very good if the category theorist’s answer to someone saying “I want to study relations between categories” is only “you shouldn’t want that, you should want profunctors”

if the desire to do the second thing is based (as it was) on the incorrect belief that $\bf Cat$ is a regular category, I reserve the right to be blunt and say "well, certainly a relation between categories is an interesting thing, but let's make sure it is indeed what you want to study before diving into something that we know can be a bit pathological". Now, I only rapidly skimmed through the various answers, so this piece of conversation might already have happened. But indeed, I didn't go into the fine details of anything, I just noticed no one made precise in what sense "everybody says that profunctors are relations for categories". I might object on the "everybody" part, and even those who say it, say so in a sense that is not literal. That was my entire point, am I repeating something that has already been cleared? Do you think this is off topic for some reason? There is something I don't get.

fosco (Mar 09 2025 at 20:55):

Do you actually know that you can’t embed internal relations into profunctors?

If by this you mean what I suspect you mean ("there is no functor from Rel(E) to Prof for the category of relation of all regular E's) I was thinking of Sets here. Also, I was writing while you posted the question, I didn't just ignore to answer something else :grinning: I just was busy texting on a different point

Kevin Carlson (Mar 09 2025 at 20:57):

No, I mean internal relations in categories specifically, which is what Avi’s been asking about. And that’s all fair. I think the “usual” story of how profunctors are like relations in that they specialize to relations can be considered handled, yeah.

Kevin Carlson (Mar 09 2025 at 20:57):

And the point that Cat is not regular was also raised early.

John Baez (Mar 09 2025 at 21:02):

Kevin Carlson said:

It’s not very good if the category theorist’s answer to someone saying “I want to study relations between categories” is only “you shouldn’t want that, you should want profunctors”, even though that may well be true in many cases.

Oh, but it's so much fun to say! :upside_down:

It's a bit like the typical response to "how do I do this in [some programming language]?" Namely, "it's better to use [some other language]." It allows the replier to feel superior while sidestepping the hard work of figuring out the answer to the question.

fosco (Mar 09 2025 at 21:08):

Kevin Carlson said:

And the point that Cat is not regular was also raised early.

yes, I saw, and that's indeed why I scrolled down and replied.

fosco (Mar 09 2025 at 21:10):

John Baez said:

Kevin Carlson said:

It’s not very good if the category theorist’s answer to someone saying “I want to study relations between categories” is only “you shouldn’t want that, you should want profunctors”, even though that may well be true in many cases.

Oh, but it's so much fun to say! :upside_down:

It's a bit like the typical response to "how do I do this in [some programming language]?" Namely, "it's better to use [some other language]." It allows the replier to feel superior while sidestepping the hard work of figuring out the answer to the question.

Nah, I never do that. I have no need to feel superior to some, and I am clearly not superior to others.

I think this is a more honest, banal, "ok, you want to do that. Did we make sure you want to do it for the right reason?"

Kevin Carlson (Mar 09 2025 at 21:18):

Well, yes, and Avi says he wants to be able to relate arrows to each other, which seems like a good reason to be nervous about profunctors, which don’t self-evidently permit that. That’s why I started trying to figure out whether they non-self-evidently permit that a couple days ago.

John Baez (Mar 09 2025 at 21:44):

Yes, I think it's a good math problem.

Avi Craimer (Mar 09 2025 at 22:04):

What a good discussion!

Hi @fosco, I miss you! Fosco, I'm interested in the idea of a relation between categories $C$ and $D$ as a subcategory of $C \times D$. I know this may not be a standard notion for Cat, but it is standard for regular categories, and while I've since learned that Cat is not regular, I'm curious whether we can save this intuitive notion of a relation between categories. I proposed the concept of a Relator which take the definition of a functor and swaps in set-relations in place of functions to connect objects and morphisms. It turns out this definition is equivalent to the subcategory of $C \times D$ definition, but in my opinion it is nicer since it suggest more naturally how composition might be defined in the absence of regularity. .

Then as a second branch of the conversation, Kevin and John suggested we consider whether relators are special cases of profunctors/bifunctors. I raised a possible counter-example and Kevin recently responded with an attempt work it in to the profunctor framework. Also, Ryan shared some cool CQL code that might be relevant. I think that's a pretty full summary of the discussion so far.

Avi Craimer (Mar 09 2025 at 22:17):

Kevin Carlson said:

The profunctor associated to the diagonal relation on $A$ that I suggested goes like this: you add a heteromorphism, as you did, $a\to a,b\to b$, realizing the relatedness of those two pairs. Then, I did not say to impose that there are no heteromorphisms between the other pairs! We’re freely generating a profunctor here. You could call it the left Kan extension of the terminal functor out of the two-point category along its diagonal inclusion into $A^\mathrm{op}\times A,$ if you like.

The profunctor freely generated by those two heteromorphisms then is empty over $(b,a)$ but has two elements over $(a,b)$ coming from the two generating heteromorphisms, acted on by $(f,id)$ and $(id,f)$ respectively. There are no relations to impose in this case; they’d have to come from generating heteromorphisms at $(b,a)$ acted on by $(f,f)$, but there are none of those.

@Kevin Carlson Thanks so much for this. I don't know the framework you are using to describe the generation of the profunctors. I also feel as if I'm missing some kind of Rosetta stone for interpreting the mappings in terms of relations. As I said previously, mapping object pairs to sets makes sense to me. We can say that mapping to an empty set means "not related" and mapping to a non-empty set means "related" (possibly in more than one way). But I don't grasp your intuition for how mapping a morphism pair to a function is to be thought of as expressing "related" or "not related".

Kevin Carlson (Mar 09 2025 at 22:56):

Right, so, that image that "not related" means "empty" is very much not what happens here. Let me try to give a closed form for this profunctor, rather than saying how to generate it. I actually think John was right that I need to align the variances first, though...I suspect the right answer to this variance question might be that you should think of a "relator $A\nrightarrow B$" as a subcategory of $A^\mathrm{op}\times B,$ much like we think of sesquilinear rather than bilinear maps for complex vector spaces.

Kevin Carlson (Mar 09 2025 at 22:56):

Anyway, let's first consider a relator $R\hookrightarrow A\times B.$ Then we can construct a profunctor $H:A\times B\to \mathbf{Set}$ as the left Kan extension of the terminal functor $u:R\to \mathbf{Set}$ along the inclusion $i:R\hookrightarrow A\times B.$

Kevin Carlson (Mar 09 2025 at 22:57):

With this simpler (and perhaps less wrong) definition we can compute $H$ pretty explicitly using general lore about Kan extensions. In general, the left Kan extension of $u:C\to E$ along $i:C\to D$ has the formula $i_!u(d)=\mathrm{colim}_{c \in u\downarrow d} u(c),$ if those colimits exist.

Kevin Carlson (Mar 09 2025 at 22:57):

In our case this becomes $i_!u(a,b)=\mathrm{colim}_{f:a'\to a,g:b'\to b, a'Rb'} 1,$ a colimit of a bunch of singleton sets. This kind of colimit can always be simplified to the set of connected components $\pi_0(R\downarrow (a,b))$ of the category of related pairs above $(a,b)$ in $A^{\mathrm{op}}\times B.$

Kevin Carlson (Mar 09 2025 at 22:57):

So, roughly speaking, the profunctor I'm inducing from a relator counts "how many ways" a pair of elements can be mapped to from a related pair. More precisely, "how many" means that I count two mappings $(f,g):(a',b')\to (a,b)\leftarrow (a'',b''):(f',g')$ from related pairs $a' R b', a'' R b''$ as "the same" when there's a map $(f'',g''):(a',b')\to (a'',b'')$ with $f''Rg''$ making the resulting triangle commute. This "existence of a triangle with related top side" relation generates a natural equivalence relation on the values of the free profunctor $(a,b)\mapsto \sum_{a' R b'} A(a',a)\times B(b',b),$ quotienting by which produces $H.$

Kevin Carlson (Mar 09 2025 at 23:02):

As a side note, "left Kan extensions of the terminal functor into $\mathbf{Set}$" like this show up in the construction of the comprehensive factorization system. What this means is that, if you take the Grothendieck construction $\pi:\int H\to A\times B,$ then $i:R\hookrightarrow A\times B$ factors canonically through $\pi$ via an initial functor, while like any Grothendieck construction, $\pi$ is a discrete opfibration.

So, if you're in the know about these words, we could say that the profunctor I've associated to a relator is simply the universal discrete opfibration that relator generates. There's a whole lot known about the mapping from diagrams in a category to discrete opfibrations over that category, much of which is very nicely outlined in Perrone and Tholen's paper from a few years ago on Kan extensions as partial colimits.

Avi Craimer (Mar 09 2025 at 23:04):

Hmmm... I think this may be a step beyond my category theory fu. But it's good to know that there might be a principled way to connect relators to more abstract/normal category theory stuff.

Kevin Carlson (Mar 09 2025 at 23:07):

Yeah, I know that’s kind of a lot, though Kan extensions are a wonderful thing to learn about. All concepts are (in a famous quote) Kan extensions. But for your purposes this construction probably isn’t that important in its own right; it’s more a natural place for me or somebody else to construct an example of two different relators that induce the same profunctor. Based on the general ideas about the comprehensive factorization system, I bet such examples exist, and if somebody provides them then you might be able to use them to reflect on whether relators are really what you care about.