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


view this post on Zulip 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}\{A,B\}

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

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

{(A,A),(B,B),(idA,idA),(idB,idB)}\{ (A,A), (B,B), (id_A,id_A), (id_B, id_B) \}

In other words, CC relates everything in AA to itself except for ff.

Now, what I can't see is how we can express this subcategory as a profunctor P:Aop×ASetP: 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){} (A,A) \mapsto \{\ast\}
(B,B){} (B,B) \mapsto \{\ast\}
And you can map the non-reflexive pairs to the empty set to express non-relation .
(A,B) (A,B) \mapsto \emptyset
(B,A) (B,A) \mapsto \emptyset

However, if we consider how to map the pair of morphisms (fop,f):(B,A)(A,B)(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 fopf^{op} is unrelated to ff?

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

  3. Assuming it does make sense to inter-translate

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

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

view this post on Zulip 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.

view this post on Zulip 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 (mop,m)f(m^{op}, m') \mapsto f?

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

view this post on Zulip 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 -> {} }

view this post on Zulip 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 RA×AR \subseteq A \times A will give a functor f:Aop×ASetf: 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×ASetf: A \times A \to \mathsf{Set}. After all, there's no "op" in your definition of relator.

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

view this post on Zulip 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×ASetF: A \times A \to Set then the problem is that we are forced by functor laws to map (f,f)!:{}{}(f,f) \mapsto !: \{\ast\} \to \{\ast\}. So I don't see how this can represent the subcategory of A×AA \times A which leaves out (f,f)(f,f).

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

view this post on Zulip Kevin Carlson (Mar 09 2025 at 19:49):

The profunctor associated to the diagonal relation on AA that I suggested goes like this: you add a heteromorphism, as you did, aa,bba\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 Aop×A,A^\mathrm{op}\times A, if you like.

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

view this post on Zulip 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.

view this post on Zulip 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 AA and BB so you might as well make AA act on the left and BB on the right!

view this post on Zulip 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.

view this post on Zulip 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×ASetF: A \times A \to Set then the problem is that we are forced by functor laws to map (f,f)!:{}{}(f,f) \mapsto !: \{\ast\} \to \{\ast\}. So I don't see how this can represent the subcategory of A×AA \times A which leaves out (f,f)(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×B|A|\times |B|, where entry (a,b)(a,b) is 1 if (a,b) are related, and 0 otherwise. It's either "yes, aRb" or "no, ¬(aRb)\lnot(aRb)".

A profunctor is essentially the same, up to the crucial fact that you (must) have a whole set of ways in which aRbaRb, 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 aa.

view this post on Zulip 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.

view this post on Zulip 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!

view this post on Zulip 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.

view this post on Zulip 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

view this post on Zulip Kevin Carlson (Mar 09 2025 at 20:40):

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

view this post on Zulip 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.

view this post on Zulip 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?

view this post on Zulip 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.

view this post on Zulip 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 Cat\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.

view this post on Zulip 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

view this post on Zulip 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.

view this post on Zulip Kevin Carlson (Mar 09 2025 at 20:57):

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

view this post on Zulip 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.

view this post on Zulip 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.

view this post on Zulip 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?"

view this post on Zulip 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.

view this post on Zulip John Baez (Mar 09 2025 at 21:44):

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

view this post on Zulip 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 CC and DD as a subcategory of C×DC \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×DC \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.

view this post on Zulip Avi Craimer (Mar 09 2025 at 22:17):

Kevin Carlson said:

The profunctor associated to the diagonal relation on AA that I suggested goes like this: you add a heteromorphism, as you did, aa,bba\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 Aop×A,A^\mathrm{op}\times A, if you like.

The profunctor freely generated by those two heteromorphisms then is empty over (b,a)(b,a) but has two elements over (a,b)(a,b) coming from the two generating heteromorphisms, acted on by (f,id)(f,id) and (id,f)(id,f) respectively. There are no relations to impose in this case; they’d have to come from generating heteromorphisms at (b,a)(b,a) acted on by (f,f)(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".

view this post on Zulip 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 ABA\nrightarrow B" as a subcategory of Aop×B,A^\mathrm{op}\times B, much like we think of sesquilinear rather than bilinear maps for complex vector spaces.

view this post on Zulip Kevin Carlson (Mar 09 2025 at 22:56):

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

view this post on Zulip Kevin Carlson (Mar 09 2025 at 22:57):

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

view this post on Zulip Kevin Carlson (Mar 09 2025 at 22:57):

In our case this becomes i!u(a,b)=colimf:aa,g:bb,aRb1,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 π0(R(a,b))\pi_0(R\downarrow (a,b)) of the category of related pairs above (a,b)(a,b) in Aop×B.A^{\mathrm{op}}\times B.

view this post on Zulip 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)(a,b)(a,b):(f,g)(f,g):(a',b')\to (a,b)\leftarrow (a'',b''):(f',g') from related pairs aRb,aRba' R b', a'' R b'' as "the same" when there's a map (f,g):(a,b)(a,b)(f'',g''):(a',b')\to (a'',b'') with fRgf''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)aRbA(a,a)×B(b,b),(a,b)\mapsto \sum_{a' R b'} A(a',a)\times B(b',b), quotienting by which produces H.H.

view this post on Zulip Kevin Carlson (Mar 09 2025 at 23:02):

As a side note, "left Kan extensions of the terminal functor into Set\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 π:HA×B,\pi:\int H\to A\times B, then i:RA×Bi: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.

view this post on Zulip 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.

view this post on Zulip 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.