In what sense are profunctors a generalization of relations?

Question

In the wikipedia page on profunctors it states that

In category theory, a branch of mathematics, profunctors are a generalization of relations and also of bimodules.

However, I cannot see from the definiton of profunctor that it is a generalization of a relation. Maybe I'm looking for something more complicated than I should.

Answer 1

I've personally always found this a weird thing to say about profunctors, but Borceux (calling them "distributors") has the most to say in justifying the analogy. His explanation goes like this:

For a relation $R\subset A\times B$, one way we can represent the relation is as a directed multigraph with exactly one edge from vertex $a$ to vertex $b$ when $aRb$. The idea is generalized by thinking of, for a profunctor $Q:\mathbf{A}\to\mathbf B$, the set $Q(A,B)$ as a set of "formal arrows" $A\to B$ that are acted on by $f:A'\to A$ and $g:B\to B'$ through a kind of "formal composition" $$A'\overset{f}{\dashrightarrow} A\to B\overset{g}{\dashrightarrow} B'.$$ Then, if $\mathbf{A},\mathbf{B}$ are discrete, and the set of "formal arrows" at most a singleton, this gives us back essentially a relation on a pair of sets again.

Why this particular generalization? Well, that I've never been clear on. I've seen profunctors used to prove some helpful results, but their "relation-like" status has never shone through these proofs, for me. The best notion I've heard to make this a little more natural is that $\mathbf{Set}^{\mathbf{B}^{op}}$ is in some sense like the "power set" of $\mathbf{B}$, and one way to represent a relation on $A,B$ is as a function $A\to\mathcal{P}(B)$; and the transpose of $\mathbf{A}\to\mathbf{Set}^{\mathbf{B}^{op}}$ is a bifunctor to $\mathbf{B}^{op}\times\mathbf{A}\to\mathbf{Set}$. I don't know if this is totally satisfactory as an intuition, but at least it tempers the oddness for me.

Answer 2

As with many things in category theory, it can become much clearer by considering the $(0,1)$-category analogue (and also $0$-groupoids). This can also be thought of as $\mathbf 2$-enriched category theory where I'm using $\mathbf 2$ as the interval category (which forms a complete Boolean algebra and is thus a cosmos)¹.

So what does a $(0,1)$-profunctor look like? First, our $(0,1)$-categories are essentially posets, and $(0,1)$-functors are monotonic functions. A $(0,1)$-profunctor would then be a monotonic function from $P:\mathcal D^{op}\times\mathcal C\to\mathbf 2$. The object part of this is just a (binary) relation on the underlying sets of the posets in the normal set theoretic sense. In the case where $\mathcal D$ and $\mathcal C$ are discrete, this is the whole story. If they're not discrete, then we get the property that if $d'\leq_{\mathcal D} d$ and $c\leq_{\mathcal C} c'$ then $P(d,c)\implies P(d',c')$.

Let's stick to the discrete (i.e. $0$-groupoid) case for a bit. The identity profunctor normally is simply the $\mathsf{Hom}$ functor on the appropriate category. For a discrete poset, this is the equality relation. Composition of profunctors is given by the coend formula $(Q\circ P)(e,c)=\int^{d:\mathcal D}Q(e,d)\times P(d,c)$. If $\mathcal D$ is discrete, this becomes $(Q\circ P)(e,c)=\exists d\in\mathcal D.Q(e,d)\land P(d,c)$ which is exactly relational composition. In this sense, profunctors on groupoids would be a direct "groupoidification" of relations. If we allow arbitrary posets, very little changes. The identity $(0,1)$-profunctor becomes the ordering of the poset. Composition is unchanged. The decategorification of the notion of a profunctor can thus be viewed as a relation on posets that respects the ordering of the posets in the appropriate way. In the case of discrete posets, that ordering is trivial and profunctors on discrete categories are a categorification of $\mathbf{Rel}$.

¹ $\mathbf 2$ can also be thought of as (equivalent to) the full subcategory of $\mathbf{Set}$ consisting of sets of cardinality at most $1$. The initial object is the empty set, any limit of sets of cardinality at most $1$ has cardinality at most $1$, and the coequalizer of any two functions into sets of cardinality at most $1$ has cardinality at most $1$. However, the coproduct of sets of cardinality at most $1$ can have cardinality greater than $1$. It is easy to show, though, that the $I$-indexed coproduct in this subcategory is essentially the existential quantifier. We could write it as $\coprod_{i\in I}S_i = \{1\mid\exists i\in I.S_i\neq\varnothing\}$.