Yoneda Lemma in promise CSP

As I am working on write-ups on our recent work on the complexity of CSPs [¹, ²], it become more and more obvious that the categorical language might be useful in formulating our results and providing formal proofs thereof. This is why me and Tomáš Jakl started working on categorical understanding of the theory of promise CSPs—this will take us a while as we are slowly learning that everything has been proved in 70’s. Nevertheless, this endeavour lead me to an interesting observation: The following statement about polymorphism minions of minions is the Yoneda Lemma!

lemma (Yoneda Lemma)

Let $M$ be a minion, and $P$ be the minion of projections, then $\operatorname{pol}(P, M)$ is isomorphic to $M$.

I have been aware of this observation, and the fact that it can be easily proven using the Yoneda Lemma, for a while. But up until now, I thought it is simply a consequence of the lemma—nevertheless, it is a formulation of the lemma in a different language which is almost as powerful as the original statement. (One obvious weakness is that it only talks about the category of finite sets.)

Though I am not completely sure who the target audience for this post is, let me try to explain some of the definitions that you need to know in order to understand the statement, and translate it to the more traditional categorical language. For simplicity, we define a minion as below, though the usual definition is slightly more general.

definition (minion)

An (abstract locally finite) minion is an endofunctor $M$ of the category of finite sets such that $M(X) = \emptyset$ if and only if $X = \emptyset$.

Why do we care about minions? They naturally arise in the study of gadget reductions between promise CSPs. Each promise CSP is defined by a template which is a pair of relational structures $A, B$ such that $A$ maps homomorphically to $B$. Polymorphisms of such a template contain enough information to determine the complexity of the corresponding promise CSP up to log-space reductions.

definition (polymorphism minion)

A polymorphism from a structure $A$ to another structure $B$ is a homomorphism $f\colon A^X \to B$ where $X$ is a finite set called arity of $f$. The symbol $A^X$ denotes the $X$-fold power of $A$.

The mapping $M$ that maps $X$ to the set $\operatorname{pol}^{(X)}(A, B)$ of all $X$-ary polymorphisms naturally forms a minion: Given $\pi\colon X \to Y$, we define its image under the polymorphism minion to be the mapping \[ \pi^M \colon \operatorname{pol}^{(X)}(A, B) \to \operatorname{pol}^{(Y)}(A, B) \] by mapping $f$ to the function $f^\pi \colon a \mapsto a \circ \pi$. We denote this minion by $\operatorname{pol}(A, B)$.

It can be proved that one promise CSP reduces to another via a gadget reduction (which is a certain log-space reduction) if and only if there is a natural transformation from the polymorphism minion of the second template to the polymorphism minion of the first one. If you are interested in details, we wrote enough in [³].

Naturally, the definition of the polymorphism minion extends from the category of (finite) structures to any category with finite products. Since the category of minions themselves has finite products, this raises a natural question: ‘What about polymorphisms of minions?’ The products in the category of endofunctors of finite sets can be described in a few ways. One of them is to define $M^X$ as the functor $\operatorname{hom}(X, M({-}))$. Hence a minion polymorphism of arity $X$ from a minion $M$ to a minion $N$ is a natural transformation from $\operatorname{hom}(X, M({-}))$ to $N$.

This leads us one step closer to the Yoneda Lemma. The final missing definition is that of the minion $P$, which is called the minion of projections. Often, it is defined as the polymorphism minion of 1-in-3SAT, i.e., as a certain minion consisting of Boolean functions. Here, it is easier to define it as the identity functor on finite sets, i.e., by $P(X) = X$.

Finally, we approach the Yoneda Lemma which, as I have formulated above, claims that for each minion $M$, $\operatorname{pol}(P, M)$ and $M$ are naturally equivalent. Unfolding the definitions, this claims the following bijection: \[ \operatorname{Nat}(\operatorname{hom}(X, {-}), M) \simeq M(X) \] and moreover that this bijection is natural in $X$. This looks way more like the standard categorical statement of the Yoneda Lemma. Though, if you are knowledgeable in category theory, you might complain that the Yoneda Lemma also claims that this isomorphisms is also natural in $M$. Let me just add it to my original statement.

lemma (Yoneda Lemma, properly)

For each minion $M$, there is a natural equivalence \[ \upsilon_M \colon \operatorname{pol}(P, M) \to M. \] Moreover for each minion homomorphism $\chi\colon M \to N$, we have that $\chi \circ \upsilon_M = \upsilon_N \circ \chi^*$ where $\chi^*\colon \operatorname{pol}(P, M) \to \operatorname{pol}(P, N)$ is the minion homomorphism defined as $\chi^*(\xi) = \chi \circ \xi$.