4.5: Profunctors form a Compact Closed Category

In this section we will define compact closed categories and show that Feas, and more generally V-profunctors, form such a thing. Compact-closed categories are monoidal categories whose wiring diagrams allow feedback. The wiring diagrams look like this:

It’s been a while since we thought about co-design, but these were the kinds of wiring diagrams we drew, e.g. connecting the chassis, the motor, and the battery in Eq. (4.1). Compact closed categories are symmetric monoidal categories, with a bit more struc- ture that allow us to formally interpret the sorts of feedback that occur in co-design problems. This same structure shows up in many other fields, including quantum mechanics and dynamical systems.

In Eq. (2.13) and Section 2.2.3 we discussed various flavors of wiring diagrams, including those with icons for splitting and terminating wires. For compact-closed categories, our additional icons allow us to bend outputs into inputs, and vice versa. To keep track of this, however, we draw arrows on our wire, which can either point forwards or backwards. For example, we can draw this

We then add icons—called a cap and a cup—allowing any wire to reverse direction from forwards to backwards and from backwards to forwards.

Thus we can draw the following (4.57)

and its meaning is equivalent to that of Eq. (4.56).
We will begin by giving the axioms for a compact closed category. Then we will look again at feasibility relations in co-design—and more generally at enriched profunctors—and show that they indeed form a compact closed category.

Compact closed categories

As we said, compact closed categories are symmetric monoidal categories (see Defini- tion 4.45) with extra structure.

Definition: 4.58.

Let (C, I, ⊗) be a symmetric monoidal category, and c \(\in\) Ob(C) an object. A dual for c consists of three constituents

(i) an object c∗ \(\in\) Ob(C), called the dual of c,

(ii) a morphism η\(_{c}\) :I → c∗ ⊗ c, called the unit for c,

(iii) a morphism ε\(_{c}\) : c ⊗ c∗ → I, called the counit for c

These are required to satisfy two equations for every c \(\in\) Ob(C), which we draw as commutative diagrams:

These equations are sometimes called the snake equations.
If for every object c \(\in\) Ob(C) there exists a dual c∗ for c, then we say that (C, I, ⊗) is compact closed.

In a compact closed category, each wire is equipped with a direction. For any object c, a forward-pointing wire labeled c is considered equivalent to a backward-pointing

write labeled c*, i.e. \(\stackrel{c}{\rightarrow} \text { is the same as } \stackrel{c^{*}}{\leftarrow} \text { . }\) The cup and cap discussed above are in fact the unit and counit morphisms; they are drawn as follows.

In wiring diagrams, the snake equations (4.59) are then drawn as follows:

Note that the pictures in Eq. (4.57) correspond to ε\(_{sound}\) and η\(_{sound∗}\).

Recall the notion of monoidal closed preorder; a monoidal category can also be monoidal closed. This means that for every pair of objects c, d \(\in\) Ob(C) there is an object c -o d and an isomorphism C(b ⊗ c, d) \(\cong\) C(b, c -o d), natural in b. While we will not provide a full proof here, compact closed categories are so-named because they are a special type of monoidal closed category.

Proposition 4.60.

If C is a compact closed category, then

1. C is monoidal closed; and for any object c \(\in\) Ob(C),

2. if c∗ and c′ are both duals to c then there is an isomorphism c\(^{∗}\) \(\cong\) c′; and

3. there is an isomorphism between c and its double-dual, c \(\cong\)c\(^{∗∗}\).

To prove 1., the key idea is that for any c and d, the object c -o d is given by c∗ ⊗ d, and the natural isomorphism C(b ⊗ c, d) \(\cong\) C(b, c -o d) is given by precomposing with id\(_{b}\) ⊗η\(_{c}\).

Before returning to co-design, we give another example of a compact closed category, called Corel, which we’ll see again in the chapters to come.

Example 4.61.

Recall, from Definition 1.18, that an equivalence relation on a set A is a reflexive, symmetric, and transitive binary relation on A. Given two finite sets, A and B, a corelation A → B is an equivalence relation on A ⊔ B.

So, for example, here is a corelation from a set A having five elements to a set B having six elements; two elements are equivalent if they are encircled by the same dashed line.

There exists a category, denoted Corel, where the objects are finite sets, and where a morphism from A → B is a corelation A → B. The composition rule is simpler to look at than to write down formally.\(^{2}\) If in addition to the corelation α : A → B above we have another corelation β : B → C

Then the composite β ◦ α of our two corelations is given by

That is, two elements are equivalent in the composite corelation if we may travel from one to the other staying within equivalence classes of either α or β.

The category Corel may be equipped with the symmetric monoidal structure (Ø, ⊔). This monoidal category is compact closed, with every finite set its own dual. Indeed, note that for any finite set A there is an equivalence relation on A ⊔ A := {(a, 1), (a, 2) | a \(\in\) A} where each part simply consists of the two elements (a, 1) and (a,2) for each a \(\in\) A. The unit on a finite set A is the corelation η\(_{A}\):Ø → A ⊔ A specified by this equivalence relation; similarly the counit on A is the corelation ε\(_{A}\) : A ⊔ A → Ø specifed by this same equivalence relation.

Exercise 4.62.

Consider the set \(\underline{3}\) = {1, 2, 3}.

1. Draw a picture of the unit corelation Ø → 3 ⊔ 3.

2. Draw a picture of the counit corelation 3 ⊔ 3 → Ø.

3. Check that the snake equations (4.59) hold. (Since every object is its own dual, you only need to check one of them.) ♦

Feas as a compact closed category

We close the chapter by returning to co-design and showing that Feas has a compact closed structure. This is what allows us to draw the kinds of wiring diagrams we saw in Eqs. (4.1), (4.55), and (4.56): it is what puts actual mathematics behind these pictures.

Instead of just detailing this compact closed structure for Feas = Prof\(_{Bool}\), it’s no extra work to prove that for any skeletal (unital, commutative) quantale (V, I, ⊗) the profunctor category Prof\(_{V}\) of Theorem 4.23 is compact closed, so we’ll discuss this general fact.

Theorem 4.63.

Let V be a skeletal quantale. The category Prof\(_{V}\) can be given the structure of a compact closed category, with monoidal product given by the product of V-categories.

Indeed, all we need to do is construct the monoidal structure and duals for objects. Let’s sketch how this goes.

Monoidal products in Prof\(_{V}\) are just product categories. In terms of wiring diagrams, the monoidal structure looks like stacking wires or boxes on top of one another, with no new interaction.

We take our monoidal product on ProfV to be that given by the product of V-categories; the definition was given in Definition 2.74, and we worked out several examples there. To recall, the formula for the hom-sets in X × Y is given by

\((x \times y)\left((x, y),\left(x^{\prime}, y^{\prime}\right)\right):=X\left(x, x^{\prime}\right) \otimes y\left(y, y^{\prime}\right)\)

But monoidal products need to be given on morphisms also, and the morphisms in Prof\(_{V}\) are V-profunctors. So given V-profunctors Φ: X1 → X2 and Ψ: Y1 → Y2, one defines a V-profunctor (Φ × Ψ): X1 × Y1 → X2 × Y2 by

\((\Phi \times \Psi)\left(\left(x_{1}, y_{1}\right),\left(x_{2}, y_{2}\right)\right):=\Phi\left(x_{1}, x_{2}\right) \otimes \Psi\left(y_{1}, y_{2}\right)\).

Exercise 4.64.

Interpret the monoidal products in Prof\(_{Bool}\) in terms of feasibility. That is, preorders represent resources ordered by availability (x ≤ x′ means that x is available given x′) and a profunctor is a feasibility relation. Explain why X × Y makes sense as the monoidal product of resource preorders X and Y and why Φ × Ψ makes sense as the monoidal product of feasibility relations Φ and Ψ. ♦

The monoidal unit in Prof\(_{V}\) is 1. To define a monoidal structure on Prof\(_{V}\), we need not only a monoidal product—as defined above—but also a monoidal unit. Recall the V-category 1; it has one object, say 1, and (1, 1) = I is the monoidal unit of V. We take1 to be the monoidal unit of Prof\(_{V}\).

Exercise 4.65.

In order for 1 to be a monoidal unit, there are supposed to be isomor- phisms X × 1 → X and 1 × X → X in Prof\(_{V}\), for any V-category X. What are they? ♦

Duals in Prof\(_{V}\) are just opposite categories. In order to regard Prof\(_{V}\) as a compact closed category (Definition 4.58), it remains to specify duals and the corresponding cup and cap.

Duals are easy: for every V-category X, its dual is its opposite category X\(^{op}\) (see Exercise 2.73). The unit and counit then look like identities. To elaborate, the unit is a V-profunctor \(_{ηX}\) → 1 X\(^{op}\) × X. By definition, this is a V-functor

\(\eta_{x}: \mathbf{1} \times x^{\mathrm{op}} \times x \rightarrow v\);

we define it by \(_{ηX}\)(1, x, x′) := X(x, x′). Similarly, the counit is the profunctor ε\(_{X}\) : (X × X\(^{op}\)) → 1, defined by ε\(_{X}\)(x, x′, 1) := X(x, x′).

Exercise 4.66.

Check these proposed units and counits do indeed obey the snake equations Eq. (4.59). ♦