Species and analytic functors
This chapter embarks on a more category-theoretic study of species. Every species has a canonical decomposition as an infinite sum $f_0 + f_1 + f_2 + \dots$ and it gives rise to an endofunctor $\bar F $ of $\bf Set$ that admits a “Taylor expansion”. Such functors are called analytic, and they can be characterised intrinsically as the finitary endofunctors of $\bf Set$ satisfying a weak exactness property.
Analytic functors, wide pullbacks
Construction. Given a combinatorial species $f : {\bf P} \to \bf Set$, we can consider the left Kan extension
and for $X\in\bf Set$ the set $FX$ can be computed pointwise as the coend
Such a functor is called analytic, and we call similarly every functor that lies in the image of the functor $\text{Lan}_J$, where $J : {\bf P} \hookrightarrow {\bf Set}$ is the (nonfull) inclusion functor.
Definition (Analytic functor). An endofunctor $F$ of $\bf Set$ is called analytic if it lies in the essential image of $\text{Lan}_J$, or in other words, if it arises as the left Kan extension along $J : {\bf P} \hookrightarrow {\bf Set}$ of a combinatorial species $f : {\bf P} \to {\bf Set}$. Such a species will be called the generating species of $F$.
It is then evident that $\text{Lan}_J$ is the left adjoint in a pair
Since $J$ is not fully faithful, the category of combinatorial species cannot be seen as a full subcategory of endofunctors of $\bf Set$ subject to some additional property prescribed by the coreflection $J^*$.
Its essential image is thus a little bit more difficult to characterise than in the case of $[{\bf Fin}, {\bf Set}]$ examined in lecture 1.
With a little bit more effort, we can however characterise such an essential image as the subcategory of those $F : {\bf Set} \to {\bf Set}$ such that
- $F$ is finitary;
- $F$ weakly preserves wide pullbacks.
The second condition deserves a bite more explanation.
Definition. An endofunctor $F : {\bf Set} \to {\bf Set}$ is said to weakly preserve pullbacks if for every pullback square
the canonical map $F(A\times_C B) \to FA \times_{FC} FB$ is surjective.
Definition. Let $E$ be a set and $\cal C$ a category; a ($E$-ary) wide pullback with sink $X \in \cal C$ is the limit of a diagram $E \to {\cal C}/X$ where $E$ is regarded as a discrete category and ${\cal C}/X$ is the slice of $\cal C$ over $X$.
In simple terms, a wide pullback is a pullback having possibly more than two arrows pointing to the same object.
In more obscure terms, let $E$ be a set, and let $E^\rhd$ be the category where a distinguished new object $\infty$ has been forcefully rendered a terminal object; a $E$-ary wide pullback in $\cal C$ is a limit of a diagram $E^\rhd \to \cal C$.
The characterisation of analytic functors in terms of weak preservation of wide pullbacks was first shown by Joyal in his “Foncteurs analytiques”.
The proof will occupy the entire lecture, and it comes from a more modern presentation of this idea in Adamek-Velebil that is purely elementary, in the sense that it relies on elementary category theory and is pretty straightforward.
Canonical decomposition and examples
Since $\text{Lan}_J$ is a left adjoint, it is evident that $\text{Lan}_J(f \sqcup g) \cong \text{Lan}_J f \sqcup \text{Lan}_J g$, so that the class of analytic functors is close under finite (and in fact, arbitrarily large) coproducts. More importantly, the analytic functor associated to $f\sqcup g$ is just the coproduct of the analytic functors $F=\text{Lan}_Jf$ and $G=\text{Lan}_Jg$.
Thus, to completely understand analytic functors, it is enough to understand the $\sqcup$-indecomposable objects of $\bf Spc$. Such indecomposable objects can be characterised.
Proposition (Canonical decomposition of a species). Every combinatorial species $f : {\bf P} \to {\bf Set}$ splits into a countable sequence of $\sqcup$-indecomposable objects, unique up to reordering: the canonical decomposition of $f$.
Proof. The category ${\bf P}$ splits as a coproduct of groups, namely ${\bf P} = \coprod_{n\ge 1} S_n$, so that a functor $f : {\bf P} \to {\bf Set}$ is in fact determined by a countable family of (left) $S_n$-sets $f_n : S_n \times X_n \to X_n$ under the isomorphism
keeping in mind that the category $[S_n, {\bf Set}]$ is just the category of sets equipped with a left $S_n$-action. Thus, the action of $f$ on objects and morphisms is determined as the sum $f_1 + f_2 + f_3 + \dots$
Corollary. Since the decomposition of a species $f$ as a sum $f_1 + f_2 + f_3 + \dots$ is uniquely determined, the following concepts are well defined:
- the odd part $f_o$ of a species $f : {\bf P} \to {\bf Set}$ consisting of the sum $\sum_{k\ge 0} f_{2k+1}=f_1+f_3+\dots$;
- the even part $f_o$ of a species $f : {\bf P} \to {\bf Set}$ consisting of the sum $\sum_{k\ge 1} f_{2k}=f_2+f_4+\dots$.
The following splitting formula for the cycle index series of the even and odd part of a species $f$ holds true:
Example. Let $f : {\bf P} \to {\bf Set}$ be the sym-representable species sending $[n]\mapsto S_n/H$; the associated analytic functor sends a set $X$ to the set $X^n/H$, where the tuples of elements of $X$ are identified iff they differ by a permutation in $H$.
The functor $X\mapsto X^n/H$ is called sym-representable analytic.
As an important corollary of the previous example and of the canonical decomposition, we obtain that every analytic functor splits into a disjoint union of sym-representables as follows: Let $F$ be analytic; then the equivalence relation in the coend $(\star)$ acts separately on each summand, and yields the decomposition of $FX$ as a coproduct $FX = \coprod_{n\ge 1} \frac{f(n)\times X^n}{\sim}$, where $\sim$ is the equivalence relation consisting of all pairs $(e;\vec x) \sim (f(\sigma).e; \vec x \cdot \sigma)$.
Writing the above coproduct as a sum and interpreting the quotient as a “fraction by $n!$”, we get that every analytic functor admits a Taylor series expansion
Example (The AF of the species of singletons). Recall that the species $U$ of singletons is defined as the species centered in $1$, with value a one-element set. So, the colimit that computes $\text{Lan}_J U$ reduces to be the identity functor ${\bf Set} \to {\bf Set}$.
Example (The AF of a representable species). The species concentrated in $n\ge 1$ over the set $S_n$ gives rise to the functor $X\mapsto {\bf Set}(Jn, X)=X^n$ raising $X$ to the $n$th power.
Example (The AF of the species of sets). The species of sets $E$ gives rise to the analytic functor sending a set $X$ to the set of finite multisets on $X$, i.e. finite $\mathbb N$-linear combinations of elements of $X$ like $3x+y+z$ or $x+2y+11w+t$…
From the colimit formula for $\text{Lan}_JE$ we derive that $\tilde E$ sends $X$ to $\sum_n X^n/S_n$ (quotient sets), and this means that in an $n$-tuple of elements of $X$, the order of the coordinates does not matter, but the number of repetitions does.
Example (The AF of the species of permutations). The species of permutations gives rise to the analytic functor sending $X$ to $\sum_n X^n$. This functor builds the free monoid (if the sum starts from 0) or the free semigroup (if the sum starts from 1) on the set $X$.
Example (The AF of the species of oriented cycles).
Example (The AF of the species of subsets).
We now embark on the proof of the characterisation theorem for analytic functors. We provide an elementary proof in two parts.
Definition. An endofunctor of $\bf Set$ is called superfinitary if there exists a finite set $[n] = \{1,dots,n\}$ with the property that for each $X \in \bf Set$, the set $FX$ is the union of the images of $Fh$’s, with $h : [n] \to X$. In simple words, $F$ is superfinitary if, there exists an $n\ge 0$ such that for every set $X$, $FX$ is generated by the set $X^n$. Note that in this definition, $n$ is the same for all $X$’s.
Observe that if $F$ is superfinitary,
- we can choose a minimal $n$ with the property that $X^n$ generates $FX$; say this minimal $n$ is called $n_0$. Then,
- there exists $x_0 \in Fn_0$ which is minimal, i.e. such that $x_0$ does not lie in the image of any $F(f : [k] \hookrightarrow [n])$ for $[k]$ a proper subobject of $[n]$ (this would violate minimality).
Lemma. Every endofunctor $F$ of $\bf Set$ is the coproduct (in the category $[{\bf Set}, {\bf Set}]$) of functors $F_i$ that preserve the terminal object.
Proof. The coproduct will be indexed by the set $F1$; given $x\in F1$, define the functor $F_x : {\bf Set} \to {\bf Set}$ sending $A$ to the fiber of $Ft_A$ over $x$, if $t_A : A \to 1$ is the terminal map. On morphisms, a map $A\to B$ defines a function $(Ft_A)^\leftarrow(x) \to (Ft_B)^\leftarrow(x)$. Clearly, this is a functor, and each $F_x$ sends $1$ to $F(\text{id}_1)(x)=\{x\}$, so it preserves the terminal object.
It is equally clear that $F$ results as the coproduct $\sum_{x\in F1} F_x$, because each $FA$ is isomorphic to the sum $\sum_{x\in F1} (Ft_A)^\leftarrow x$ (we are secretly using the equivalence of categories ${\bf Set}/F1 \cong {\bf Set}^{F1}$).
This apparently simple lemma has powerful consequences: when we want to prove a statement for a certain class ${\cal A}$ of endofunctors of $\bf Set$, and $\cal A$ is stable under coproducts, we can assume that an endofunctor in $\cal A$ preserves the terminal object.
A particular case of such an $\cal A$ is the class of analytic functors.
Theorem (Characterisation of analytic functors, I). For a superfinitary functor $F : {\bf Set} \to {\bf Set}$ the following conditions are equivalent:
- $F$ weakly preserves pullbacks;
- $F$ is analytic;
- $F$ splits as a coproduct of sym-representables.
When this is proved, the assumption of superfinitariness (is that even a name…?) can be removed obtaining Joyal’s characterisation of $\cal A$.
Theorem (Characterisation of analytic functors, II). For a finitary functor $F : {\bf Set} \to {\bf Set}$ the following conditions are equivalent:
- $F$ is analytic;
- $F$ is a coproduct of symmetrised representables;
- $F$ weakly preserves countable wide pullbacks;
- $F$ weakly preserves wide pullbacks (of all cardinality).
Proof of the first theorem
Let’s prove that $(1 \Rightarrow 3)$. First of all, we can assume that $F1\cong 1$. Note that as a consequence $F$ weakly preserve products, because it weakly preserves the pullback
This means that provided we choose a minimal $n_0, x_0$ as in the previous remark, every $f : X \to [n]$ such that $x_0$ lies in the image of $Ff$ must be an epimorphism.
In particular, all elements in the set
are epimorphisms, and since $[n]$ is finite, they must be bijection as well. This determines a subgroup $H_F \le S_n$.
We shall show that there exists an isomorphism of functors $\tilde{\xi}_{x_0} : {\bf P}(n,-)/H_F \cong F$, where ${\xi}_{x_0}$ is the unique natural transformation corresponding to $x_0$ via Yoneda.
First of all, $\xi_{x_0}$ descends to the quotient “exactly”, in the sense that $\xi_{x_0}u=\xi_{x_0}v$ if and only if $u,v$ lie in the same $H_F$-orbit (if: obvious; only if: the pullback of $u$ against $v$ must be weakly preserved by $F$), and thus defines an injective function $\tilde{\xi}_{x_0} : {\bf P}(n,-)/H_F \hookrightarrow F$; using that $F$ weakly preserves pullbacks, we can show that $\tilde{\xi}_{x_0}$ is also surjective: given $y\in Fn$, there exist $f : n\times n \to n$ and $z\in Fn$ such that $F\pi_1 z=x_0$ and $F\pi_2 z = y$. But then $\pi_1f\in \text{Fix}(F|x_0)$, so it is invertible. Then, $\xi_{x_0}u=y$ if we fix $u=\pi_2 f (\pi_1 f)^{-1}$.
The implication that $(3 \Rightarrow 2)$ is evident from the fact that each sym-representable is analytic, and $\cal A$ is closed under coproducts.
Finally, let’s prove that $(2 \Rightarrow 1)$.
Remark. The proof of the second theorem, which was the one initially proved by Joyal, follows from a similar argument; in particular, the implication $3\Rightarrow 2$ follows from the fact that each $F$ that weakly preserves countable wide pullbacks is superfinitary (prove this by contradiction as an exercise). All other implications are trivial or follow clearly from what we already know.