4.3: Categories of Profunctors

There is a category Feas whose objects are preorders and whose morphisms are feasi- bility relations. In order to describe it, we must give the composition formula and the identities, and prove that they satisfy the properties of being a category: unitality and associativity.

Composing profunctors

If feasibility relations are to be morphisms, we need to give a formula for composing two of them in series. Imagine you have cities P, Q, and R and you have bridges and hence feasibility matrices connecting these cities, say Φ : P → Q and Ψ : Q → R.

The feasibility matrices for Φ (in blue) and Ψ (in red) are:

As in Remark 2.95, we personify a quantale as a navigator. So imagine a navigator is trying to give a feasibility matrix Φ ; Ψ for getting from P to R. How should this be done? Basically, for every pair p \(\in\) P and r \(\in\) R, the navigator searches through Q for a way-point q, somewhere both to which we can get from p AND from which we can get to r. It is true that we can navigate from p to r iff there is a way-point q through which to travel; this is a big OR over all possible q. The composition formula is thus:

\(\left(\Phi_{9}^{\circ} \Psi\right)(p, r):=\bigvee_{q \in \mathbb{Q}} \Phi(p, q) \wedge \Psi(q, r)\) (4.20)

But as we said in Eq. (2.101), this can be thought of as matrix multiplication. In our example, the result is

and one can check that this answers the question, “can you get from here to there” in Eq. (4.19): you can’t get from N to x but you can get from N to y.

The formula (4.20) is written in terms of the quantale Bool, but it works for arbitrary (unital commutative) quantales. We give the following definition.

Definition: 4.21.

Let V be a quantale, let X, Y, and Z be V-categories, and let Φ : X → Y and Ψ : Y → Z be V-profunctors.

We define their composite, denoted Φ ; Ψ : X → Z by the formula

\(\left(\Phi_{9} \Psi\right)(p, r)=\bigvee_{q \in Q}(\Phi(p, q) \otimes \Psi(q, r))\)

Exercise 4.22.

Consider the Cost-profunctors Φ : X → Y and Ψ : Y → Z shown below:

Fill in the matrix for the composite profunctor:

The categories V-Prof and Feas

A composition rule suggests a category, and there is indeed a category where the objects are Bool-categories and the morphisms are Bool-profunctors. To make this work more generally, however, we need to add one technical condition.

Recall from Remark 1.35 that a preorder is a skeletal preorder if whenever x ≤ y and y ≤ x, we have x = y. Skeletal preorders are also known as posets. We say a quantale is skeletal if its underlying preorder is skeletal; Bool and Cost are skeletal quantales.

Theorem 4.23.

For any skeletal quantale V, there is a category Prof\(_{V}\) whose objects are V-categories X, whose morphisms are V-profunctors X → Y, and with composition defined as in Definition 4.21.

Definition: 4.24.

We define Feas = Prof\(_{Bool}\).

At this point perhaps you have two questions in mind. What are the identity morphisms? And why did we need to specialize to skeletal quantales? It turns out these two questions are closely related.

Define the unit profunctor U\(_{X}\) : X → X on a V-category X by the formula

U\(_{X}\)(x, y) := X(x, y). (4.25)

How do we interpret this? Recall that, by Definition 2.46, X already assigns to each pair of elements x, y \(\in\) X an hom-object X(x, y) \(\in\) V. The unit profunctor UX just assigns each pair (x, y) that same object.

In the Bool case the unit profunctor on some preorder X can be drawn like this:

Obviously, composing a feasibility relation with with the unit leaves it unchanged; this is the content of Lemma 4.27.

Exercise 4.26.

Choose a not-too-simple Cost-category X. Give a bridge-style diagram for the unit profunctor U\(_{X}\) : X → X. ♦

Lemma 4.27.

Composing any profunctor Φ : P → Q with either unit profunctor, U\(_{P}\) or U\(_{Q}\), returns Φ:

\(\mathrm{U}_{\mathcal{P}} \text { ; } \Phi=\Phi=\Phi_{\text {9 }}^{\circ} \mathrm{U}_{\mathrm{Q}}\)

Proof. We show that U\(_{P}\) ; Φ = Φ holds; proving Φ = Φ ; U\(_{Q}\) is similar. Fix p \(\in\) P and q \(\in\) Q. Since V is skeletal, to prove the equality it’s enough to show Φ ≤ U\(_{P}\) ; Φ and U\(_{P}\) ; Φ ≤ Φ. We have one direction:

\(\Phi(p, q)=I \otimes \Phi(p, q) \leq \mathcal{P}(p, p) \otimes \Phi(p, q) \leq \bigvee_{p_{1} \in P}\left(\mathcal{P}\left(p, p_{1}\right) \otimes \Phi\left(p_{1}, q\right)\right)=\left(\mathrm{U}_{\mathcal{P}} \text { ; } \Phi\right)(p, q)\) (4.28)

For the other direction, we must show \(\bigvee_{p1 \(\in\)P}\) (P(p, p\(_{1}\)) ⊗ Φ(p\(_{1}\), q)) ≤ Φ(p, q).

But by definition of join, this holds iff P(p, p\(_{1}\)) ⊗ Φ(p\(_{1}\), q) ≤ Φ(p, q) is true for each p\(_{1}\) \(\in\) P. This follows from Definitions 2.46 and 4.8:

\(\mathcal{P}\left(p, p_{1}\right) \otimes \Phi\left(p_{1}, q\right)=\mathcal{P}\left(p, p_{1}\right) \otimes \Phi\left(p_{1}, q\right) \otimes I \leq \mathcal{P}\left(p, p_{1}\right) \otimes \Phi\left(p_{1}, q\right) \otimes 2(q, q) \leq \Phi(p, q)\) (4.29) \(\square\)

Exercise 4.30.

1. Justify each of the four steps (=, ≤, ≤, =) in Eq. (4.28).
2. In the case V = Bool, we can directly show each of the four steps in Eq. (4.28) is actually an equality. How?
3. Justify each of the three steps (=, ≤, ≤) in Eq. (4.29). ♦

Composition of profunctors is also associative; we leave the proof to you.

Lemma 4.3.1.

Serial composition of profunctors is associative. That is, given profunctors Φ: P → Q, Ψ: Q → R, and Υ: R → S, we have

(Φ ; Ψ) ; Y = Φ ; (Ψ ; Y)

Exercise 4.3.2.

Prove Lemma 4.31. (Hint: remember to use the fact that V is skeletal.) ♦

So, feasibility relations form a category. Since this is the case, we can describe feasibility relations using wiring diagrams for categories (see also Section 4.4.2), which are very simple. Indeed, each box can only have one input and one output, and they’re connected in a line:

On the other hand, we have seen that feasibility relations are the building blocks of co-design problems, and we know that co-design problems can be depicted with a much richer wiring diagram, for example:

This hints that the category Feas has more structure. We’ve seen wiring diagrams where boxes can have multiple inputs and outputs before, in Chapter 2; there they depicted morphisms in a monoidal preorder. On other hand the boxes in the wiring diagrams of Chapter 2 could not have distinct labels, like the boxes in a co-design problem: all boxes in a wiring diagram for monoidal preorders indicate the order ≤, while above we see boxes labelled by “Chassis”, “Motor”, and so on. Similarly, we know that Feas is a proper category, not just a preorder. To understand these diagrams then, we must introduce a new structure, called a monoidal category. A monoidal category is a categorified monoidal preorder.

Remark 4.33. While we have chosen to define Prof\(_{V}\) only for skeletal quantales in Theorem 4.23, it is not too hard to work with non-skeletal ones. There are two straight- forward ways to do this. First, we might let the morphisms of Prof\(_{V}\) be isomorphism classes of V-profunctors. This is analogous to the trick we will use when defining the category Cospan\(_{C}\) in Definition 6.45. Second, we might relax what we mean by category, only requiring composition to be unital and associative ‘up to isomorphism’. This is also a type of categorification, known as bicategory theory.

In the next section we’ll discuss categorification and introduce monoidal categories. First though, we finish this section by discussing why profunctors are called profunctors, and by formally introducing something called the collage of a profunctor.

Fun profunctor facts: companions, conjoints, collages

Companions and conjoints. Recall that a preorder is a Bool-category and a monotone map is a Bool-functor. We said above that a profunctor is a generalization of a functor; how so?

In fact, every V-functor gives rise to two V-profunctors, called the companion and the conjoint.

Definition: 4.34.

Let F : P → Q be a V-functor. The companion of F, denoted \(widehat{F}\) : P → Q and the conjoint of \(widehat{F}\), denoted \(\breve{F}\): Q P are defined to be the following V-profunctors:

\(\widehat{F}(p, q):=Q(F(p), q) \text { and } \breve{F}(q, p):=Q(q, F(p))\)

Let’s consider the Bool case again.

One can think of a monotone map F : P → Q as a bunch of arrows, one coming out of each vertex p \(\in\) P and landing at some vertex F(p) \(\in\) Q.

This looks like the pictures of bridges connecting cities, and if one regards the above picture in that light, they are seeing the companion \(\widehat{F}\). But now mentally reverse every dotted arrow, and the result would be bridges Q to P. This is a profunctor Q → P! We call it \(\breve{F}\).

Example 4.35.

For any preorder P, there is an identity functor id: P → P. Its companion and conjoint agree \(\widehat{id}\) = \(\breve{id}\): P → P. The resulting profunctor is in fact the unit profunctor, U\(_{P}\), as defined in Eq. (4.25).

Example 4.36.

Check that the companion \(\widehat{id}\) of id : P → P really has the unit profunctor formula given in Eq. (4.25). ♦

Example 4.37.

Consider the function +: \(\mathbb{R}\) × \(\mathbb{R}\) × \(\mathbb{R}\) → \(\mathbb{R}\), sending a triple (a, b, c) of real numbers to a + b + c \(\in\) \(\mathbb{R}\).

This function is monotonic, because if (a, b, c) ≤ (a′, b′, c′)—i.e. if a ≤ a and b ≤ b, and c ≤ c then obviously a + b + c ≤ a +b +c. Thus it has a companion and a conjoint.

Its companion \(\widehat{+}\) : (\(\mathbb{R}\) × \(\mathbb{R}\) × \(\mathbb{R}\)) → \(\mathbb{R}\) is the function that sends (a, b, c, d) to true if a + b + c ≤ d and to false otherwise.

Exercise 4.38.

Let +: \(\mathbb{R}\) × \(\mathbb{R}\) × \(\mathbb{R}\) → \(\mathbb{R}\) be as in Example 4.37. What is its conjoint \(\breve{+}\)? ♦

Remark 4.39 (V-Adjoints). Recall from Definition 1.95 the definition of Galois connec- tion between preorders P and Q. The definition of adjoint can be extended from the Bool-enriched setting (of preorders and monotone maps) to the V-enriched setting for arbitrary monoidal preorders V. In that case, the definition of a V-adjunction is a pair of V-functors F : P → Q and G : Q → P such that the following holds for all p \(\in\) P and q \(\in\) Q.

P(p, G(q)) \(\cong\) Q(F(p), q) (4.40)

Exercise 4.41.

Let V be a skeletal quantale, let P and Q be V-categories, and let F : P → Q and G : Q → P be V-functors.

1. Show that F and G are V-adjoints (as in Eq. (4.40)) if and only if the companion q of the former equals the conjoint of the latter: \(\widehat{F}\) = \(\breve{G}\).
2. Use this to prove that \(\widehat{id}\) = \(\breve{id}\), as was stated in Example 4.35. ♦

Collage of a profunctor. We have been drawing profunctors as bridges connect- ing cities. One may get an inkling that given a V-profunctor Φ: X → Y between V-categories X and Y, we have turned Φ into a some sort of new V-category that has X on the left and Y on the right. This works for any V and profunctor Φ, and is called the collage construction.

Definition: 4.42.

Let V be a quantale, let X and Y be V-categories, and let Φ : X → Y be a V-profunctor. The collage of Φ, denoted Col(Φ) is the V-category defined as follows:

(i) Ob(Col(Φ)) := Ob(X) ⊔ Ob(Y);
(ii) For any a, b \(\in\) Ob(Col(Φ)), define Col(Φ)(a, b) \(\in\) V to be

There are obvious functors \(i_{x}\) : X → Col(Φ) and \(i_{y}\) : Y → Col(Φ), sending each object and morphism to “itself,” called collage inclusions.

Some pictures will help clarify this.

Example 4.43.

Consider the following picture of a Cost-profunctor Φ: X → Y:

It corresponds to the following matrices

A generalized Hasse diagram of the collage can be obtained by simply taking the union of the Hasse diagrams for X and Y, and adding in the bridges as arrows. Given the above profunctor Φ, we draw the Hasse diagram for Col(Φ) below left, and the Cost-matrix representation of the resulting Cost-category on the right:

Exercise 4.44.

Draw a Hasse diagram for the collage of the profunctor shown here: