Example of two dinatural transformations between finite categories that do not compose

Question

It is often stated that dinatural transformations do not compose. It is clear from their definition that there is no reason to expect them to compose. However, I have found it surprisingly difficult to find explicit counterexamples in the literature. Two counterexamples are given on page 41 of Bainbridge, Freyd, Scedrov, and Scott's Functorial polymorphism. However, they are non-concrete, and therefore not particularly satisfying.

What is an example of two finite categories $\mathbb C$ and $\mathbb D$, three functors $F, G, H : \mathbb C^{\text{op}} \times \mathbb C \to \mathbb D$, and two dinatural transformations $\alpha : F \Rightarrow G$ and $\beta : G \Rightarrow H$ for which $\alpha$ is not composable with $\beta$?

Answer 1

I found a very explicit counterexample by running some numbers in Rust:

• Take $\mathbb C := (0 \rightarrow 1)$ the walking arrow, so that $\mathbb C^{\textsf{op}} \times \mathbb C$ becomes a commutative square of arrows $A\,;B = C\,;D$ (we take $A,B$ to always be on the upper-half of the hexagon and $C,D$ to be on the bottom-half).
• Take $\mathbb D := \{\{0,1\}\}$ the subcategory of $\textsf{Set}$ consisting of just the set $\{0,1\}$.

Then consider the following situation, where $\textsf K_0 : \{0,1\} \rightarrow \{0,1\}$ indicates the constant map in $0$:

• Take $F = G : \mathbb C^{\textsf{op}} \times \mathbb C \rightarrow \mathbb D$ doing the only possible thing on objects and mapping $A,B,C,D \mapsto \textsf K_0$. Functoriality is satisfied since $\textsf{K}_0\,;\textsf{K}_0 = \textsf{K}_0\,;\textsf{K}_0$.
• Take $H : \mathbb C^{\textsf{op}} \times \mathbb C \rightarrow \mathbb D$ maps $A,B,C \mapsto \textsf K_0$ and $D \mapsto\textsf{id}$. Functoriality is satisfied since $\textsf{K}_0\,;\textsf{K}_0 = \textsf{K}_0\,;\textsf{id}$.

Consider the following hexagons, where $\alpha_{i\in\{0,1\}} = \textsf{swap}$ and $\beta_{i\in\{0,1\}} := \textsf{id}$:

Clearly the hexagons commute since the $\textsf K_0$s collapse everything together; but now the top side of the outer hexagon is $\textsf K_0$, and the bottom side is $\textsf K_1$.

Here is the Rust code I used to generate this counterexample!

---

Inspired by @varkor's comment, here is an even simpler example where the codomain is the 2-element monoid $\mathbb D := \{\textsf{id}, \color{red}{a}\}$ such that $\color{red}{a} \,; \color{red}{a} = \color{red}{a}$.

Consider the following situation, where black morphisms indicate the identity $\textsf{id}$ and red morphisms indicate the element/morphism $\color{red}{a}$:

Functoriality holds since each square is either trivial or has at least one red morphism on both the top and bottom sides.

The hexagon on the left commutes since it only has identities, and the hexagon on the right commutes since each side has at least one red morphism.

However, the outer hexagon does not commute since the top side is the identity $\textsf{id}$ but the bottom side is $\color{red}{a}$.

(More formally, the functors are defined as follows,

• $F : \mathbb{C}^{\textsf{op}} \times \mathbb{C} \rightarrow \mathbb{D}$ sends $A,B,C,D\mapsto \textsf{id}$,
• $G : \mathbb{C}^{\textsf{op}} \times \mathbb{C} \rightarrow \mathbb{D}$ sends $A,C\mapsto \color{red}{a}$ and $B,D\mapsto \textsf{id}$,
• $H : \mathbb{C}^{\textsf{op}} \times \mathbb{C} \rightarrow \mathbb{D}$ sends $A,D\mapsto \color{red}{a}$ and $B,C\mapsto \textsf{id}$,

and the dinatural families $\alpha,\beta$ are given by $\alpha_{i} = \beta_{i} = \textsf{id}$.)

Answer 2

If $\mathbb C=(0<1)$ is the walking arrow, then the question of composability reduces to the question of whether, given that the two small hexagons below commute, the outer hexagon commutes:

It’s straightforward enough to arrange that $G$ makes it easy for $\alpha,\beta$ to be dinatural while $F$ and $H$ are more resistant for $\alpha \beta$ to be so. In particular, let's let $G(1,0)$ be initial in $\mathbb D$ and $G(0,1)$ be terminal so that $\alpha$ and $\beta$ will be dinatural no matter what other choices we make. Let $x$ be some object of $\mathbb D$ admitting a nontrivial endomorphism $\varphi$ and let $F,H,$ and the diagonal of $G$ be constant at $x.$ Then the outer hexagon is commutative if and only if $\alpha_0\beta_0=\alpha_1\beta_1,$ which we can prevent by picking exactly one of those four morphisms to be $\varphi.$

So for a completely specific example, we see it would work to take $\mathbb D$ a category freely generated by objects $0,1,2$ subject to the conditions that $0$ is initial, $1$ is terminal, and $\mathbb D(2,2)$ is, say, $\mathbb Z/2\mathbb Z.$ I think there are only eight morphisms here, and it seems like it would be hard to go much smaller (though the other answer currently visible does a bit better.)