The category P and species
The fundamental object of study of the theory of combinatorial species is the category of finite sets and bijections, and its presheaf category . (Note: since a groupoid is a self-dual category, there is not much difference between and , but we will usually speak about the second category.)
The groupoid of natural numbers
Definition (The category ). The category , also called the groupoid of natural numbers, has
- Objects the finite sets ;
- Hom sets the set of bijective functions if , and the empty set otherwise.
A skeleton of consists of the category having objects the natural numbers (with the convention that is empty), and hom-sets the symmetric groups for each .
Remark (On the structure of ). Every groupoid splits as a disjoint union of connected groupoids (each of which is equivalent to a group); the (skeleton of the) category splits as a disjoint union of the symmetric groups , with .
So the canonical decomposition of is the equivalence of categories
An immediate corollary of this decomposition is that a functor is uniquely determined by a “symmetric sequence”:
Corollary. A functor is completely determined by the following data:
- A sequence of sets ;
- A sequence of functions , each of which is a left action of on the set .
Proof. It is evident that the actions are precisely the action on morphisms of a functor (vice versa, every hom-set is empty for , so the datum of the actions is enough to “glue” a functor ).
Definition (Category of species). A functor is called a combinatorial species. The category of combinatorial species has objects the functors , and morphisms the natural transformations .
So, a combinatorial species is entirely described by a sequence of sets , each of which has an action of the symmetric group on 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 ’s above is the sequence of coefficients of a formal power series . In slightly more formal terms, to the species one can associate the “exponential” formal power series
(do not pay particular attention to the denominator term ; it is there to simplify some expressions and blur the distinction between formal power series and analytic function to which it converges) where is a formal parameter and is the cardinality of .
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 , its generating series is also a quite coarse one. For example, the correspondence that sends into is not injective: there is plenty of species for which (and thus ) without them being isomorphic. (For example, the species of permutations and the species of linear orders: in that case, , and .)
Remark. (A remark on the generality of this definition). Originally, Joyal defined a “finitary species” (espèce finitaire) as an endofunctor of ; the red book also concentrates on species having finite values. These two definitions are equivalent, because a functor factors along the inclusion ; but the category of all -valued functors has way nicer categorical properties.
The category and have two important universal properties:
Theorem. The category is the free symmetric monoidal category on a singleton.
Proof. Proving this claim amounts to show that given a symmetric monoidal category there is an equivalence of categories between
- the category , and
- The category of strong monoidal functors .
In simple terms, a strong monoidal functor 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 is , so that a strong monoidal functor must send to .
Similarly, with the additional request of cocompleteness, one proves the following.
Theorem. The category is the free cocomplete symmetric monoidal category on a singleton.
A few examples of species
Example (The species of singletons). The species of singletons ( stands for “un seul élément”, a single element in French) sends a finite set into a one-point set if is itself a one-point set, and in the empty set otherwise. The action of the symmetric group on each is the only possible one.
Example (The species of subsets). The species of subsets sends a finite set into the set of all possible subsets of ; so, has exactly elements, and the action of the symmetric group is defined as post-composition, identifying with the set ; in simple words, acts on sending the set to the set .
Example (The terminal species). The species of sets ( stands for “ensemble”, set in French) is the terminal object of the category ; it is the constant functor on the singleton . The species has two important sub-species that we will meet again later: the species of even sets, and the species of odd sets. Note that thinking of a species as a rule assigning to a finite set “the set of all structures of type on ”, the terminal species can be thought as the species of sets: for each finite set , is the set of all possible set structures on : there is just one such structure.
Example (The species of permutations). The species of permutations sends each finite set into the (carrier of the) symmetric group on letters, . The symmetric group acts on itself by left translation: if , is the map sending .
Example (The species of linear orders). The species of linear orders sends each finite set to the set of all possible linear orderings of ; the set has exactly elements, because each linear ordering of an -element set can be thought as induced under transport of structure by the ordering on .
Example (The species of oriented cycles). The species of oriented cycles sends a finite set in the set of possible inequivalent ways to sit people at a round table, or more formally, in the set of cylic orderings of , where the ordering is indistinguishable from , from , 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 .
One can also cook up more abstract examples of combinatorial species:
Example (The species centered in ). Let be a natural number. The species , “concentrated” or “centered” in is defined as the functor sending to a singleton set , and every other set to the empty set. Clearly, above, and can legitimately be called the species of -element sets. More generally we can talk about the species , concentrated in , and such that , and empty otherwise.
Example (The representable species as a particular case). Each representable functor is a combinatorial species acting as follows: is empty if , so the species is centered in , and is the (underlying set of the) symmetric group on 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
Example (The sym-representable species ). Generalising from the preceding example we can fix and a subgroup ; we can restrict the left regular representation of on iteslf to . This defines a species sending to the space of orbits of and every other 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
where the quotient by ihas to be interpreted as the quotient of the numerator by an action of the symmetric group.
Contact of order between species
As it is well-known, in the ring of formal power series ( any commutative unital ring), one can define a binary relation of contact of order n between elements : two series have contact of order if they are congruent modulo (more formally: if the difference is in the kernel of the canonical map from the inverse limit).
Definition. For every , we denote the inclusion of the full subcategory of on the objects .
Precomposition with determines a truncation functor
and left and right Kan extensions along put in the middle of a triple of adjoint functors
Formally, (resp., ) is the left (resp., right) Kan extension of a functor along the functor ; as an exercise, prove that these functors can be described explicitly as
We will say that a species has a contact of order with a species if . We denote this relation as .
It is clear that when has contact of order with , their associated series stand in the same relation.
Definition. A sequence of species is an ordered family of species . The sequence is said to converge to the species if the following “Cauchy” condition is satisfied:
for every there exists an index such that for every , .
In simple terms, converges to if for every , all but a finite number of terms of the sequence have contact of order with . If this is the case, we write .
Exercise. Is there a way to interpret this notion as a categorical construction? If , does have a universal property?
Reading list
…