The category P and species

The fundamental object of study of the theory of combinatorial species is the category P\bf P of finite sets and bijections, and its presheaf category [Pop,Set][{\bf P}^\text{op}, {\bf Set}]. (Note: since a groupoid is a self-dual category, there is not much difference between [Pop,Set][{\bf P}^\text{op}, {\bf Set}] and [P,Set][{\bf P}, {\bf Set}], but we will usually speak about the second category.)

The groupoid of natural numbers

Definition (The category P\bf P). The category P\bf P, also called the groupoid of natural numbers, has

  1. Objects the finite sets A,B,A,B,\dots;
  2. Hom sets hom(A,B)\hom(A,B) the set of bijective functions σ:AB\sigma : A \to B if card(A)=card(B)\text{card}(A) = \text{card}(B), and the empty set otherwise.

A skeleton of P\bf P consists of the category having objects the natural numbers [n]=1,,n[n]={1,\dots, n} (with the convention that [0][0] is empty), and hom-sets hom(n,n)\hom(n,n) the symmetric groups SnS_n for each n0n\ge 0.

Remark (On the structure of P\bf P). Every groupoid splits as a disjoint union of connected groupoids (each of which is equivalent to a group); the (skeleton of the) category P\bf P splits as a disjoint union of the symmetric groups SnS_n, with n0n\ge 0.

So the canonical decomposition of P\bf P is the equivalence of categories

Pn=0Sn. {\bf P} \cong \coprod_{n=0}^\infty S_n.

An immediate corollary of this decomposition is that a functor X:PSetX : {\bf P} \to {\bf Set} is uniquely determined by a “symmetric sequence”:

Corollary. A functor X:PSetX : {\bf P} \to {\bf Set} is completely determined by the following data:

  1. A sequence of sets (Xnn0)(X_n \mid n\ge 0);
  2. A sequence of functions (anX:Sn×XnXn)(a^X_n : S_n \times X_n \to X_n), each of which is a left action of SnS_n on the set XnX_n.

Proof. It is evident that the actions anXa^X_n are precisely the action on morphisms of a functor X:PSetX_\bullet : {\bf P} \to {\bf Set} (vice versa, every hom-set P(n,m){\bf P}(n,m) is empty for nmn\neq m, so the datum of the actions is enough to “glue” a functor XX).

Definition (Category of species). A functor X:PSetX_\bullet : {\bf P} \to {\bf Set} is called a combinatorial species. The category Spc\bf Spc of combinatorial species has objects the functors X:PSetX_\bullet : {\bf P} \to {\bf Set}, and morphisms the natural transformations α:XY\alpha : X_\bullet \Rightarrow Y_\bullet.

So, a combinatorial species is entirely described by a sequence of sets (Xnn0)(X_n\mid n\ge 0), each of which has an action of the symmetric group on nn letters.

Remark. (A critical remark on how to think about combinatorial species). Given the corollary above, it is not a mistake to interpret a combinatorial species as a “categorified formal power series”: the sequence of the XnX_n’s above is the sequence of coefficients of a formal power series a0+a1t+a2t2+a_0 + a_1t+a_2t^2+\dots. In slightly more formal terms, to the species XX_\bullet one can associate the “exponential” formal power series

gX(t)=n=0Xnn!tn g_X(t)= \sum_{n=0}^\infty \frac{|X_n|}{n!} t^n

(do not pay particular attention to the denominator term n!n!; it is there to simplify some expressions and blur the distinction between formal power series and analytic function to which it converges) where tt is a formal parameter and Xn|X_n| is the cardinality of XnX_n.

We will soon substantiate this idea showing that most of the operations that make sense for formal power series, such as addition, multiplication and an analogue of functional composition, also make sense for combinatorial species.

The reader shall however be warned that, while a quite intuitive invariant of the combinatorial species XX_\bullet, its generating series is also a quite coarse one. For example, the correspondence that sends XX_\bullet into gXg_X is not injective: there is plenty of species for which n.Xn=Yn\forall n.|X_n| = |Y_n| (and thus gX=gYg_X=g_Y) without them being isomorphic. (For example, the species SS of permutations and the species LL of linear orders: in that case, n.Sn=Ln=n!\forall n.|S_n| = |L_n| = n!, and gS=gL=n=0tn=11tg_S=g_L=\sum_{n=0}^\infty t^n = \frac1{1-t}.)

Remark. (A remark on the generality of this definition). Originally, Joyal defined a “finitary species” (espèce finitaire) as an endofunctor of P\bf P; the red book also concentrates on species having finite values. These two definitions are equivalent, because a functor PFin{\bf P} \to {\bf Fin} factors along the inclusion PFin{\bf P} \hookrightarrow {\bf Fin}; but the category of all Set\bf Set-valued functors PSet{\bf P} \to {\bf Set} has way nicer categorical properties.

The category P\bf P and Spc\bf Spc have two important universal properties:

Theorem. The category P\bf P is the free symmetric monoidal category on a singleton.

Proof. Proving this claim amounts to show that given a symmetric monoidal category A\cal A there is an equivalence of categories between

  1. the category A\cal A, and
  2. The category of strong monoidal functors F:PAF : {\bf P} \to {\cal A}.

In simple terms, a strong monoidal functor FF as above is determined by its value on the point. This is evident in light of the definition of the “sum and shuffle” monoidal product: the generic object of P\bf P is [n]=[1][1][n] = [1] \oplus \dots \oplus [1], so that a strong monoidal functor FF must send [n][n] to F[1]nF[1]^{\otimes n}.

Similarly, with the additional request of cocompleteness, one proves the following.

Theorem. The category Spc\bf Spc is the free cocomplete symmetric monoidal category on a singleton.

A few examples of species

Example (The species of singletons). The species UU of singletons (UU stands for “un seul élément”, a single element in French) sends a finite set AA into a one-point set {\bullet} if AA is itself a one-point set, and in the empty set otherwise. The action of the symmetric group on each U[n]U[n] is the only possible one.

Example (The species of subsets). The species of subsets sends a finite set [n][n] into the set [n]\wp[n] of all possible subsets of [n][n]; so, [n]\wp[n] has exactly 2n2^n elements, and the action of the symmetric group is defined as post-composition, identifying [n]\wp[n] with the set Set(n,2){\bf Set}(n,2); in simple words, σSn\sigma \in S_n acts on [n]\wp[n] sending the set n1,,nk{n_1,\dots, n_k} to the set σn1,,σnk{\sigma n_1,\dots, \sigma n_k}.

Example (The terminal species). The species EE of sets (EE stands for “ensemble”, set in French) is the terminal object of the category Spc\bf Spc; it is the constant functor on the singleton {\bullet}. The species EE has two important sub-species that we will meet again later: the species EeE_e of even sets, and the species EoE_o of odd sets. Note that thinking of a species FF as a rule assigning to a finite set “the set of all structures of type FF on [n][n]”, the terminal species can be thought as the species of sets: for each finite set [n][n], E[n]E[n] is the set of all possible set structures on [n][n]: there is just one such structure.

Example (The species of permutations). The species SS of permutations sends each finite set [n][n] into the (carrier of the) symmetric group on nn letters, SnS_n. The symmetric group acts on itself by left translation: if τSn\tau \in S_n, σ:SnSn\sigma : S_n \to S_n is the map sending τστ\tau\mapsto \sigma\tau.

Example (The species of linear orders). The species LL of linear orders sends each finite set [n][n] to the set of all possible linear orderings of [n][n]; the set L[n]L[n] has exactly n!n! elements, because each linear ordering x1<<xn{x_1 <\dots < x_n} of an nn-element set can be thought as induced under transport of structure by the ordering 1<2<<n{1 < 2 < \dots < n} on [n][n].

Example (The species of oriented cycles). The species C\cal C of oriented cycles sends a finite set [n][n] in the set of possible inequivalent ways to sit nn people at a round table, or more formally, in the set of cylic orderings of x1,,xn{x_1,\dots,x_n}, where the ordering x1,,xnx_1,\dots,x_n is indistinguishable from x2,x3,xn,x1x_2,x_3\dots,x_n, x_1, from x3,x4,xn,x1,x2x_3, x_4\dots,x_n, x_1, x_2, and frome very other cyclic permutation of its members. It can be shown by induction (or using simple arguments from group actions and orbits) that C[n]=(n1)!|{\cal C}[n]| = (n-1)!.

One can also cook up more abstract examples of combinatorial species:

Example (The species centered in nNn\in\mathbb N). Let n1n\ge 1 be a natural number. The species cn:PSetc_n : {\bf P} \to {\bf Set}, “concentrated” or “centered” in nn is defined as the functor sending [n]P[n] \in \bf P to a singleton set \bullet, and every other set to the empty set. Clearly, c1=Uc_1 = U above, and cnc_n can legitimately be called the species of nn-element sets. More generally we can talk about the species cnEc_n^E, concentrated in nn, and such that cnE([n])=Ec_n^E([n]) = E, and empty otherwise.

Example (The representable species as a particular case). Each representable functor [n]:PSet\text{よ}[n] : {\bf P} \to \bf Set is a combinatorial species acting as follows: [n][k]:=P(n,k)\text{よ}[n][k] := {\bf P}(n,k) is empty if nkn\ne k, so the species is centered in nn, and [n][n]=Sn\text{よ}[n][n] = S_n is the (underlying set of the) symmetric group on nn elements. The action on morphisms is the same as in the species of permutations, and in fact the species of permutation arises as the infinite sum

S=[1]+[2]+[3]+ S = \text{よ}[1] + \text{よ}[2] + \text{よ}[3] + \dots

Example (The sym-representable species nSn/Hnn\mapsto S_n/H_n). Generalising from the preceding example we can fix n1n\ge 1 and a subgroup HSnH \le S_n; we can restrict the left regular representation of SnS_n on iteslf to HH. This defines a species fHf_H sending [n][n] to the space of orbits of HSnH \curvearrowright S_n and every other [k][n][k]\neq [n] to the emptyset.

These species will be the building blocks for our next lecture on analytic functors: we will show that every species can be thought of a categorification of the coefficients of a formal power series, because it defines a functor

F~:SetSet:Xn1f(n)×Xnn! \tilde F : {\bf Set} \to {\bf Set} : X\mapsto \sum_{n\ge 1} \frac{f(n) \times X^n}{n!}

where the quotient by n!n! ihas to be interpreted as the quotient of the numerator by an action of the symmetric group.

Contact of order nn between species

As it is well-known, in the ring of formal power series KtK\llbracket t\rrbracket (KK any commutative unital ring), one can define a binary relation n\sim_n of contact of order n between elements f,gf,g: two series have contact of order nn if they are congruent modulo tnt^n (more formally: fngf\mathrel{\sim_n}g if the difference fgf-g is in the kernel of the canonical map KtK[t]/(tn)K\llbracket t\rrbracket \to K[t]/(t^n) from the inverse limit).

Definition. For every n0n\ge 0, we denote ιn:PnP\iota_n : {\bf P}_{\le n} \hookrightarrow {\bf P} the inclusion of the full subcategory of P\bf P on the objects [0],[1],,[n]{[0],[1],\dots, [n]}.

Precomposition with ιn\iota_n determines a truncation functor

ιn:=τn:Spc=[P,Set][Pn,Set] \iota^*_n := \tau_n : {\bf Spc} = [{\bf P}, {\bf Set}]\to [{\bf P}_{\le n}, {\bf Set}]

and left and right Kan extensions along ιn\iota_n put τn\tau_n in the middle of a triple of adjoint functors

lnτnrn l_n \dashv \tau_n \dashv r_n

Formally, lnl_n (resp., rnr_n) is the left (resp., right) Kan extension of a functor H[Pn,Set]H \in [{\bf P}_{\le n}, {\bf Set}] along the functor ιn\iota_{\le n}; as an exercise, prove that these functors can be described explicitly as

lnF:m{Fmmnm>nrnF:m{Fmmnm>n l_nF : m \mapsto \begin{cases} Fm & m \le n \\ \varnothing & m > n \end{cases} \qquad \qquad r_nF : m \mapsto \begin{cases} Fm & m \le n \\ * & m > n \end{cases}

We will say that a species FF has a contact of order nn with a species GG if τnF=τnG\tau_n F = \tau_n G. We denote this relation as FnGF \mathrel{\sim_n} G.

It is clear that when FF has contact of order nn with GG, their associated series stand in the same relation.

Definition. A sequence of species is an ordered family of species (F0,F1,)(F_0,F_1,\dots). The sequence (F0,F1,)(F_0,F_1,\dots) is said to converge to the species FF_\infty if the following “Cauchy” condition is satisfied:

for every N0N\ge 0 there exists an index nˉ\bar n such that for every nnˉn\ge \bar n, FnNFF_n \mathrel{\sim_N} F_\infty.

In simple terms, (F0,F1,)(F_0,F_1,\dots) converges to FF_\infty if for every N0N\ge 0, all but a finite number of terms of the sequence have contact of order NN with FF_\infty. If this is the case, we write FnnFF_n \overset{n\to\infty}\rightharpoondown F_\infty.

Exercise. Is there a way to interpret this notion as a categorical construction? If FnnFF_n \overset{n\to\infty}\rightharpoondown F_\infty, does FF_\infty have a universal property?

Reading list