Preliminaries; finite sets, convolution
The category $\bf Fin$ has objects the finite sets and morphisms all functions; a skeleton of $\bf Fin$ is the category whose objects are sets $[n]={1,\dots,n}$ for $n\ge 0$ (with the convention that $[0]=\varnothing$), and morphisms are functions $f : [n] \to [m]$.
The universal property of $\bf Fin$ and $[{\bf Fin},{\bf Set}]$
Theorem. The category $\bf Fin$ is the free finite coproduct completion of the singleton $\bullet$.
Proof. It is enough to show that a functor $\bf Fin \to \mathcal{C}$ that preserves coproducts is uniquely determined by the image of $[1]$, i.e. by $F[1]=X$; this is obvious, because
(if $ \_ \otimes \_ $ denotes the tensor of $X\in\mathcal{C}$ with the set $[n]$). $\blacksquare$
As an immediate corollary, the opposite category ${\bf Fin}^\text{op}$ is the free finite product completion of the singleton $\bullet$.
Theorem. There is an equivalence of categories between
- The category of all functors ${\bf Fin} \to {\bf Set}$, and natural transformations;
- The category of finitary endofunctors of $\bf Set$, i.e. those $T : {\bf Set} \to {\bf Set}$ that preserve filtered colimits.
Proof. Let’s first build an adjunction between the two categories; the “tautological” inclusion functor $J : {\bf Fin} \to {\bf Set}$ induces an adjunction
where $J^*$ is the “precomposition with $J$” functor and $\text{Lan}_J$ its left adjoint. Such a left adjoint is fully faithful because $J$ is fully faithful, and this last condition entails that in the diagram
The 2-cell $\eta : F \Rightarrow (\text{Lan}_J F)\circ J $ is invertible; $\eta$ is precisely the unit of the adjunction $\text{Lan}_J \dashv J^*$, and this, in turn, entails that the left adjoint in the adjunction is fully faithful.
It only remains to characterise the essential image of $\text{Lan}_J$ as the full subcategory of finitary functors on $\bf Set$. Once again, a general theorem comes to the rescue: the objects we are interested in are just the ones at whose components the counit of the adjunction $\text{Lan}_J \dashv J^*$ is an isomorphism; unwinding this condition, we get to prove that the following conditions are equivalent:
- $T : {\bf Set} \to {\bf Set}$ is finitary;
- The counit $\epsilon_T : \text{Lan}_J(TJ) \Rightarrow T$ is a natural isomorphism.
The equivalence is easily seen: assume $T$ is finitary, and unwind the counit using the universal property; given $A\in \bf Set$, the left Kan extension of $TJ$ along $J$, computed in $A$, is just the weighted colimit of $TJ$ with weight $P={\bf Set}(J-, A)$, and this is, in turn, the colimit of $TJ$ over the (opposite of the) category of elements of $P$, i.e the colimit of the composition $T \circ \Sigma^\text{op}$, where the category of elements and the canonical projection $\Sigma$ appear in the upper left corner in the pullback
This category is filtered, so in the end $\lambda A.\text{Lan}_J(TJ)A\cong \lambda A.T((\text{Lan}_J J)A)\cong \lambda A.TA$, naturally in $A$ (because $\text{Lan}_JJ$ is isomorphic to the identity functor). $\blacksquare$
Remark. From a higher perspective, this is a consequence of a more general theorem (but this explanation is imprecise); given a suitable class of “shapes”, i.e. a subcategory $\mathcal{D} \subseteq {\bf Cat}$, there is an equivalence of categories between
- The category of all functors $F_\mathcal{D}(\bullet) \to {\bf Set}$, and natural transformations;
- The category of endofunctors of $\bf Set$ that commute with $\mathcal{D}$-filtered colimits,
where $F_\mathcal{D}(\bullet)$ is the free completion of the point under $\mathcal{D}$-shaped limits.
Fact. Given an equivalence of categories $F :{\cal V} \leftrightarrows {\cal W} : G$, where $\cal V$ is (symmetric) monoidal, there is an essentially unique way to give $\cal W$ a monoidal structure, so that $F,G$ become strong monoidal functors.
Sketch of proof. Let’s say $(\otimes, I)$ is a monoidal structure on $\cal V$. Define a tensor product on $\cal W$ using $F,G$: $(X,Y)\mapsto X\odot Y= F(GX \otimes GY)$. Define a monoidal unit $K:= GI$. Straightforward from here. $\blacksquare$
Corollary. Under the same notation as above, there is an equivalence of categories
induced by $(F,G)$ between internal monoids in $(\cal V, \otimes, I)$ and internal monoids in $(\cal W, \odot, K)$.
Remark. The category of all endofunctors of $\bf Set$ is strict monoidal, with respect to composition of functors. The category $[{\bf Set}, {\bf Set}]_\omega$ of finitary endofunctors inherits a strict monoidal structure from $[{\bf Set}, {\bf Set}]$, because the composition of finitary functors is again finitary.
As a consequence, the category $[{\bf Fin}, {\bf Set}]$ inherits a (non strict) monoidal structure, called the substitution product: the substitution of a pair of functors $M,N : {\bf Fin}\to{\bf Set}$ is the functor
Exercise. Unwind the definition of $\text{Lan}_J M \circ N$ finding an explicit formula for $M\triangleleft N$. (We will come back to this.)
An additional introductory remark introduces the universal property of the presheaf category.
Theorem. Let $\cal C$ be a small category; the category $[{\cal C}^\text{op}, {\bf Set}]$ is the free small cocomplete category generated by $\cal C$.
Proof. This means that there is an isomorphism of categories between
- The category of functors ${\cal C} \to {\cal D}$, when $\cal D$ is small-cocomplete;
- The category of cocontinuous functors $[{\cal C}^\text{op}, {\bf Set}] \to \cal D$.
The equivalence is induced by the functor “precomposition with the Yoneda embedding” ${\cal C} \to [{\cal C}^\text{op}, {\bf Set}]$, that defines a correspondence
The last introductory remark is about the so-called convolution product of functors. Given a monoidal category $({\cal A}, \otimes, I)$ we can endow the presheaf category $[{\cal A}^\text{op}, {\bf Set}]$ with a monoidal structure such that the Yoneda embedding $\text{よ} : {\cal A} \to [{\cal A}^\text{op}, {\bf Set}]$ is a strong monoidal functor (in fact, the operation built in this way is universal with respect to this property).
Let $F,G : {\cal A}^\text{op} \to {\bf Set}$ be functors; define their Day convolution as the functor $F * G : {\cal A}^\text{op} \to {\bf Set}$ obtained as left Kan extension of $F\times G$ along $\otimes$, i.e. as the curved arrow in the following diagram
More explicitly, $F * G$ acts on objects as the integral
and on morphism (natural transformations of presheaves) by the evident functoriality of this construction.
(Exercise: Prove that if $\cal A$ is a cartesian category (i.e., $\otimes = \times$) then $F * G \cong F\times G$; prove that the monoidal unit of $*$ is the representable presheaf $\text{よ}(I)$ on the monoidal unit of $({\cal A}, \otimes)$.)
Refer to [???,???] for more information.
Reading list
…