Theory and Applications of Categories, Vol. 11, No. 18, 2003, pp. 397–419.

SYMMETRIC MONOIDAL COMPLETIONS AND THE EXPONENTIAL PRINCIPLE AMONG LABELED COMBINATORIAL

STRUCTURES.

MATÍAS MENNI

ABSTRACT. We generalize Dress and Müller’s main result in [5]. We observe that their result can be seen as a characterization of free algebras for certain monad on the category of species. This perspective allows to formulate a general exponential principle in a symmetric monoidal category. We show that for any groupoid G, the category ˆ!G of presheaves on the symmetric monoidal completion !G of G satisfies the exponential principle. The main result in [5] reduces to the case G = 1. We discuss two notions of functor between categories satisfying the exponential principle and express some well known combinatorial identities as instances of the preservation properties of these functors. Finally, we give a characterization of G as a subcategory of ˆ!G.

1. Introduction

Let 𝔽 be the category of finite sets and functions and let 𝔹 be the subgroupoid of 𝔽 induced by bijections. The category of species is introduced in Section 1.2 of [10] as the category of functors from 𝔹 to 𝔽. To each species F there is an associated formal power series

F = |F 0| + |F 1|x + … + |F n|\frac{x^{n}}{n!} + … = ∑_{n≥0} F n\frac{x^{n}}{Aut(n)}

where Aut(n) is the cardinality of the set of endomorphisms on [1..n] and F n denotes the cardinality of F [1..n]. The assignment of series to species maps combinatorial constructions between species to operations between power series. For example, the category of species (denoted by Joy from now on) has a symmetric monoidal structure denoted by · which, at the level of power series, corresponds with the usual product of series. There is also a “derivative” functor ∂ : Joy → Joy and a (non-symmetric) monoidal structure that corresponds to composition. The theory obtained allows to calculate with combinatorial objects as though they were power series while keeping a clear intuition of what is the combinatorial meaning of the resulting identities in the calculation. In the notes to Chapter 5 of his book [23], Stanley refers to the theory of species as the “most sophisticated combinatorial theory of power series composition” and refers to the book [3] for further information. We assume from now on that the reader is familiar with [10]. Using the basic ideas behind the definition of species a number of variations have been proposed in order to deal with different problems in combinatorics. For example, linear species [10, 15, 3], partitionals [21], permutationals [2], colored species [18], Möbius species [19], tensorial species [11] and species on digraphs [20]. In all these variations, there is a groupoid G of “combinations of indeterminates” and a category E of “coefficients” so that the functor category E^{G} can be seen as a category of combinatorial interpretations of some kind of power series. Let us look at an example. Consider the groupoid 𝕊 whose objects are finite sets equipped with a permutation and whose maps are bijections between the underlying sets that preserve the permutation. Let x_{1}, x_{2}, … be a numerable set of formal variables. For any permutation σ of a set U we define pσ = x_{1}^{d_{1}}x_{2}^{d_{2}} ⋯ x_{n}^{d_{n}} where n is the cardinality of U and d_{i} is the number of cycles of length i in σ. We also say that σ is of class d = (d_{1}, d_{2}, …). For any functor F : 𝕊 → 𝔽 we can associate the power series

Funded by CONICET and MURST project MCTAAP2.

Received by the editors and, in revised form, 2003-09-26.

Transmitted by F. W. Lawvere. Published on 2003-11-24.

2000 Mathematics Subject Classification: 05A99, 18D10, 18D35.

Key words and phrases: symmetric monoidal categories, combinatorics.

\begin{matrix}c \\ ◯ \end{matrix} Matías Menni, 2003. Permission to copy for private use granted.

F (x_{1}, x_{2}, …) = ∑_{n≥0} ∑_{d⊢n} F d\frac{pd}{Aut(d)} = ∑_{n≥0} ∑_{d⊢n} F d\frac{x_{1}^{d_{1}}x_{2}^{d_{2}} …}{d_{1}!1^{d_{1}}d_{2}!2^{d_{2}} …}

where d = (d_{1}, d_{2}, …) is a sequence of non-negative integers, the notation d ⊢ n indicates that d_{1} + 2d_{2} + … = n and F d is the cardinality of the set given by F applied to a permutation σ of class d (it is clear that this is well defined). Functors F : 𝕊 → 𝔽 are called permutationals and they were introduced in [2].

In this paper we will work mainly with the categories, mentioning the associated power series mainly in the examples. But before we go into the results of the present paper, let us discuss Dress and Müller’s work [5]. For any species F seen as a functor F : 𝔹 → 𝔹 a DM-decomposition is a natural transformation t from the functor

\xymatrix{F × F : 𝔹 × 𝔹 \ar[r]^{F ×F} & 𝔹 × 𝔹 \ar[r]^{×} & 𝔹 \ar[r] & 𝔽}

to the functor

\xymatrix{F.+ : 𝔹 × 𝔹 \ar[r]^{+} & 𝔹 \ar[r]^{F} & 𝔹 \ar[r] & 𝔽}

such that for all finite sets U and V, t_{U,V} : F U × F V → F (U + V) is mono and such that

(D1) for each finite set U and two binary ordered partitions (U_{0}, U_{1}) and (V_{0}, V_{1}) of U it holds that

t(F U_{0} × F U_{1}) ∩ t(F V_{0} × F V_{1}) = t(t(F W_{00} × F W_{01}) × t(F W_{10} × F W_{11}))

where W_{ij} = U_{i} ∩ V_{j}.

Dress and Müller call a functor F : 𝔹 → 𝔹 weakly decomposable if it is not initial and has a DM-decomposition. For a DM-decomposition t on a functor F, Dress and Müller define a functor F_{t} whose value at 0 is empty and at non-empty U is given by the formula below

F_{t}U = F U\ ⋃_{I,J} t(F I × F J)

where the union is taken over the non-empty I, J’s such that I + J = U. We write F (x) for the formal power series associated to F. For a weakly decomposable functor F with DM-decomposition t define (F_{t}^{(0)})U = F U if U = ∅ and (F_{t}^{(0)})U = ∅ otherwise. Then define F_{t}^{(k+1)} by recursion:

F_{t}^{(k+1)}U = ⋃_{(U_{0},U_{1})∈Prt_{b}U} t(F_{t}U_{0} × F_{t}^{k}U_{1})

and define a functor F to be decomposable if it has a DM-decomposition that satisfies the following condition

(D2) For each finite set U the sets F_{t}^{(0)}, F_{t}^{(1)}, F_{t}^{(2)}, … are pairwise disjoint.

If we write [n] for {1, …, n} and F (x, y) for the formal power series below:

∑_{n,k≥0}(F_{t}^{(k)}[n])\frac{y^{k}x^{n}}{k!n!}

then we can state the main result (the exponential principle) in [5] as follows.

1.1. Theorem. (Dress-Müller) If F : 𝔹 → 𝔹 is a weakly decomposable functor with decomposition t then:

1. the equation F (x) = exp(F_{t}(x)) holds and

2. if t satisfies (D2) then F (x, y) = exp(yF_{t}(x)).

Dress and Müller apply their result to some enumeration problems arising in group theory and they show that their result implies that of Wilf (see [24], where more examples of enumeration problems solved by the exponential principle can be found). The purpose of the present paper is to generalize Theorem 1.1 to other variants of the theory of species. In order to do this we will first formulate an exponential principle in an arbitrary symmetric monoidal category and then prove that this principle holds in categories of presheaves over certain groupoids. The first item of Theorem 1.1 will be the instance of our result given by the terminal groupoid 1 while the second will follow from the case 1 + 1. We now define the general exponential principle and outline the contents of the paper.

Let (D, ·, I) be a symmetric monoidal category with tensor ·, unit I and natural isos r : F · I → F, l : I · F → F, a : (F · G) · H → F · (G · H) and c : F · G → G · F satisfying the usual coherence conditions [6]. We denote by CMon the category of commutative monoids in D. We say that an object F of D is simple if there exists a unique map I → F. We denote by SCMon the full subcategory of CMon given by those commutative monoids whose underlying object is simple (notice that the unit of a simple monoid is uniquely determined). We say that (D, ·, I) has algebraic families if the forgetful functor SCMon → D is monadic. In this case we will denote the relevant monad by (E, μ, η).

Let δ : (F_{0} · F_{1}) · (F_{2} · F_{3}) → (F_{0} · F_{2}) · (F_{1} · F_{3}) be some fixed composition of c’s and a’s that (naturally) swaps F_{1} and F_{2}.

1.2. Definition. A decomposition is a simple commutative monoid m : F · F → F such that the following diagram is a pullback.

\xymatrix{(F · F) · (F · F) \ar[d]_{m·m} \ar[r]^{(m·m).δ} & F · F \ar[d]^{m} \\ F · F \ar[r]_{m} & F}

Let Dec be the full subcategory of SCMon induced by decompositions.

1.3. Definition. A symmetric monoidal category (D, ·, I) is said to satisfy the exponential principle if it has algebraic families and the equivalence SCMon → Alg_{E} restricts to one Dec → Kl_{E}.

Let us introduce some examples. For any essentially small category C, its symmetric monoidal completion !C can be described as follows. The objects of !C are collections {g_{i}}_{i∈I} with I a finite set and g_{i} ∈ C. A morphism {g_{i}}_{i∈I} → {h_{j}}_{j∈J} is given by a bijection f : I → J together with maps α_{i} : g_{i} → h_{fi} in C. Its monoidal structure ⊔ is given by {g_{i}}_{i∈I} ⊔ {h_{j}}_{j∈J} = {t_{k}}_{k∈I+J} where k_{in_{0}i} = g_{i} and t_{in_{1}j} = h_{j}. The empty collection ∅ is the unit of this monoidal structure. (The obvious embedding C →!C induces, for every symmetric monoidal category D, an equivalence between the category of symmetric monoidal functors !C → D and the category of functors C → D.) Fix now an essentially small groupoid G. It is clear that !G is also a groupoid. Consider now the presheaf topos ˆ!G = Set^{(!G)^{op}}. The monoidal structure (!G, ⊔, ∅) induces, via Day’s construction [7], a symmetric monoidal (closed) structure on ˆ!G that we denote by (ˆ!G, ·, I). Intuitively, ˆ!G is a category of formal power series and the monoidal structure corresponds to the product of series.

1.4. Proposition. For any groupoid G, the symmetric monoidal category (ˆ!G, ·, I) satisfies the exponential principle. Moreover, the full subcategory of ˆ!G induced by the functors that take values in finite sets inherits the monoidal structure and the resulting symmetric monoidal category also satisfies the exponential principle.

In Section 2 we prove Proposition 1.4 and in Section 3 we show that many variations of the theory of species in the literature (e.g. [21, 2, 18, 20]) appear as instances of this proposition. In particular, below Example 3.2 we show that item 1 of Theorem 1.1 follows from the case G = 1. Below Example 3.5 we show that item 2 follows from the case G = 1 + 1. Also in Section 3 we show that for every symmetric monoidal category (D, ·, I) satisfying the exponential principle and every C in D, the slice D/(EC) also satisfies the exponential principle. This provides some insight into our main examples and also an abstract tool to start discussing morphisms between categories satisfying the exponential principle.

If we think of E as a “categorified” exponential function e^{( )} then we can think of monoidal categories with algebraic families as categorified exponential rings (see [17] for the achievements and prospects of exponential algebra). This perspective provides a reasonable notion of morphism between categories with algebraic families. For the sake of the following discussion fix symmetric monoidal categories (D, ·, I) and (D′, ·′, I′) and a symmetric strict (i.e. structure maps are isos) monoidal functor Θ : (D, ·, I) → (D′, ·′, I′) preserving simple objects. (From now on, every monoidal functor is symmetric and strict.) The functor Θ induces a functor SCMon(D) → SCMon(D′) that commutes with the “underlying object” functors. Assume from now on that D and D′ have algebraic families. So that there is a functor Θ_{0} : Alg_{E} → Alg_{E′} commuting with the forgetful functors of the monads E and E′. By results in [9], there is a natural transformation λ : E′Θ → ΘE.

1.5. Definition. We say that Θ : (D, ·, I) → (D′, ·′, I′) is an E-functor if the associated λ : E′Θ → ΘE is an iso.

If we let E_{0} : D → Alg_{E} be the free functor associated with E and E′_{0} that associated with E′ then (again by results in [9]) Θ as above is an E-functor if λ induces and iso Θ_{0}E_{0} ≅ E′_{0}Θ in Alg_{E}.

Every map f : C → ED induces, by post-composition with μ.(Ef), a functor D/(EC) to D/(ED). In Section 4 we show that the induced functor between slices is an E-functor and we present some examples of well-known combinatorial identities arising as applications of E-functors. This is very natural but it is useful to consider also a weaker notion.

1.6. Definition. We say that Θ is a weak E-functor if the functor Alg_{E} → Alg_{E′} induced by Θ maps free algebras to free algebras.

If the exponential principle holds in D and D′ then there is a simple sufficient condition to recognize weak E-functors.

1.7. Corollary. If (D, ·, I) and (D′, ·′, I′) satisfy the exponential principle and the functor Θ : D → D′ is monoidal and preserves simple objects and pullbacks then Θ is a weak E-functor.

Proof. The functor Θ preserves the pullback diagram defining decompositions.

Let D as above satisfy the exponential principle and let f : C → ED be a map. If D has pullbacks, the monoidal functor D/(EC) → D/(ED) induced by f has a right adjoint. It is well known (see [12]) that the right adjoint must be monoidal and it is easy to see that it preserves simple objects. Of course, it preserves pullbacks so it is a weak E-functor. We discuss these examples in more detail also in Section 4.

Finally, in Section 5, we give a purely categorical characterization of the image of the embedding y : G → ˆ!G. This will have no application in the present work but we believe it is relevant for further developments. Recall the notion of strength of a functor as reviewed, for example, in [8]. For any strong functor T with strength str_{l} : T F · G → T (F · G) let str_{r} : F · T G → T (F · G) be (T c).str_{l}.c.

1.8. Definition. Assume that D has finite coproducts. We say that a strong functor ∂ : D → D satisfies the Leibniz rule if [str_{l}, str_{r}] : (∂F · G) + (F · ∂G) → ∂(F · G) and the unique ! : 0 → ∂I are isomorphisms.

For example, the functor ∂ : Joy → Joy defined by (∂F)U = F (1 + U) has an evident strength that satisfies the Leibniz rule. Another example is given by the pointing operation ( )^{•} : Joy → Joy defined by F^{•}U = U × F U. The first example motivates the following. Let D be an object in D and assume that the functor D ·( ) has a right adjoint. Then the right adjoint has a canonical strength induced, essentially, by the counit of the adjunction.

1.9. Definition. Assume that D has finite colimits. An object x of D is called an infinitesimal if the functor x · ( ) has a right adjoint ∂_{x} that preserves finite colimits and satisfies Leibniz rule with respect to the canonical strength. We say that the infinitesimal x is amazing if ∂_{x} has a further right adjoint.

The characterization can then be stated as follows.

1.10. Proposition. For any groupoid G, the embedding G →!G → ˆ!G is equivalent to the full subcategory of ˆ!G induced by the infinitesimals in (ˆ!G, ·, I). Moreover, every infinitesimal in (ˆ!G, ·, I) is amazing.

If D satisfies the exponential principle and ∂ : D → D is a strong functor then we say that ∂ is E-strong if the map

\xymatrix{∂F · EF \ar[r]^{^{str^{l}}} & ∂(F · EF) \ar[r]^{∂(η·id)} & ∂(EF · EF) \ar[r] & ∂EF}

is an isomorphism. Again, lifting ideas from exponential algebra (see Definition 4 in [17]) we can define an infinitesimal x to be an E-infinitesimal if the associated strong functor ∂_{x} is E-strong. We will not use this idea but it seems relevant to mention that after the proof of Proposition 1.10 it will be clear that the infinitesimals in the statement are E-infinitesimals.

Other ways of generalizing the exponential formula are Stanley’s exponential structures [23] and Bender and Goldman’s prefabs [1]. See also [13, 25]. The precise connections between these and the approach of this paper will have to be treated elsewhere.

2. Proof of Proposition 1.4

The fact that (ˆ!G, ·, I) has algebraic families is essentially an instance of a very general result involving categories of algebras for monads induced by (symmetric) operads in cocomplete symmetric monoidal closed categories (see e.g. [14]). We give an indication of this in the second paragraph. We are not aware of general results involving Kleisli categories for these monads so we give a concrete proof that the exponential principle holds. We do this with the help of explicit descriptions of the tensor · on ˆ!G and of the monad E. With these descriptions, readers not familiar with operads will be able to convince themselves that (ˆ!G, ·, I) has algebraic families. An extra advantage of the explicit presentation is that it will then be clear that the exponential principle holds also on the subcategory of ˆ!G induced by the functors valued in finite sets.

Let (E, ⊗, I) be a cocomplete symmetric monoidal closed category and let 𝔹 be the groupoid of finite sets and bijections. The category of functors E^{𝔹} can be equipped with a (non-symmetric) monoidal structure with tensor denoted by ∘ and unit J. A monoid for this tensor is called an operad and each operad induces a monad on E (see [14]). The (functor underlying the) monad M induced by the ‘trivial’ operad J ∘ J → J can be described by the coend

M(E ∈ E) = ∫ ^{n∈𝔹} E^{⊗n}

and the category of algebras for M is equivalent to the category CMon(E, ⊗, I) of commutative monoids in E. As (ˆ!G, ·, I) is cocomplete symmetric monoidal closed, the forgetful CMon(ˆ!G) → ˆ!G is monadic. The fact that SCMon(ˆ!G) → ˆ!G is monadic will follow easily once we have described the monads involved more explicitely.

2.1. Algebraic families. The monoidal structure (!G, ⊔, ∅) is lifted to (ˆ!G, ·, I) by defining

(F · G)U = ∫ ^{c,d∈!G}!G(U, c ⊔ d) × F c × Gd

and I =!G( , ∅). (See [7] for details.) It will be convenient to simplify this formula. Before we do that, notice that from the explicit description of the unit, it is easy to characterize the simple objects as those F ∈ ˆ!G such that F ∅ = 1.

2.2. Definition. Let U = {g_{i}}_{i∈I} be an object of !G. For n ≥ 0, an n-partition of U is a sequence (I_{1}, …, I_{n}) of subsets of I such that its components are pairwise disjoint and whose union equals I.

For n ≥ 0, each n-partition (I_{1}, …, I_{n}) determines an n-tuple of objects (U_{1}, …, U_{n}) where U_{k} = {g_{i}}_{i∈I_{k}}. We will generally confuse an n-partition with the induced sequence of objects. Only ∅ has a 0-partition. It is the empty sequence () and it determines the object ∅. Let us denote by Prt_{b}U the set of binary partitions of U.

2.3. Lemma. The map

∑_{(U_{1},U_{2})} F U_{1} × GU_{2} → (F · G)U

(where the sum ranges over Prt_{b}U) injecting the coproduct into the coend is actually an isomorphism.

Proof. This can be proved by the usual description of the coend (F · G)U as a colimit (see [16]) and using that !G is a groupoid.

2.4. Definition. Let U = {g_{i}}_{i∈I} be an object of !G. A partition π of U is just a partition of the set I in the usual sense, that is, a set of non-empty subsets of I that are pairwise disjoint and whose union is I.

The object ∅ has exactly one partition: the empty set. Each partition of U determines an obvious set of objects in !G. We may sometimes join and intersect such objects (using symbols ⊔ and ∩). The meaning of this is clear when we understand the operations as acting on subsets of the indexing set underlying U. If π is a partition of U then for each p in π we may denote the induced object of !G by U_{p}. Let Part U be the set of partitions of U. Define a functor E : ˆ!G → ˆ!G by the formula

(EF)U = ∑_{π} ∏_{p∈π} F U_{p}

where the sum ranges over Part U. Notice that (EF)∅ = 1. There is a natural transformation η : Id → E that for every F is defined as follows. When U is ∅, η is the unique F ∅ → 1. When U is not ∅, η : F U → (EF)U maps an element x of F U to the unique partition of U with one element together with x. There is also a transformation μ : EE → E whose explicit definition relies on the operation that takes a partition π of U together with a partition σ_{p} of p for each p in π and builds the evident, finer, partition of U given by the union of the σ_{p}’s. We leave the details for the reader.

2.5. Lemma. The category of algebras for (E, η, μ) is equivalent (over ˆ!G) to the category SCMon.

Proof. It is easy to give a concrete proof using the explicit description of the monoidal structure given in Lemma 2.3. Alternatively, readers familiar with operads can derive most of the proof by comparing E with M.

This finishes the sketch of the proof that (ˆ!G, ·, I) has algebraic families. Consider now the full subcategory of those functors that take values in finite sets. From the explicit description of the tensor · it is easy to see that the subcategory inherits the tensor. Moreover, from the explicit description of E it is clear that the sub-monoidal-category has algebraic families.

2.6. The exponential principle. In this section we show that the category of decompositions of (ˆ!G, ·, I) is equivalent (over ˆ!G) to the category of free algebras for E. For any algebra ζ : EF → F we define the subobject L(F, ζ) of F by (L(F, ζ))∅ = ∅ and

(L(F, ζ))U = {x ∈ F U | (∀z ∈ (EF)U)(ζz = x → z = ηx)} → F U

where U is not ∅. It is easy to see that L(F, ζ) is a an object of ˆ!G and that we have a monomorphism L(F, ζ) → F. We will denote this map by α_{ζ} or simply by α. Elements of L(F, ζ) are called connected. Let x in F U and let z ∈ (EF)U be such that ζz = x. Let z be given by a partition π of U together with a family {x_{p}}_{p∈π} with x_{p} ∈ F U_{p}. We say that z is a splitting of x if for every p ∈ π, x_{p} is connected. It is clear that every connected element has a unique splitting, namely, ηx. For the sake of the following statements let us call the unique element of F ∅ trivial and every other non-trivial.

2.7. Lemma. For every algebra ζ : EF → F, every non-trivial element has a splitting.

Proof. If U ∈!G is indexed by the singleton then the elements in F U are connected. Let U = {g_{i}}_{i∈I} and let x ∈ F U. If x is connected then it has a unique splitting, if not, there exists an element z in (EF)U, different from ηx, such that ζz = x. Let z be represented by a partition π of U together with a family {x_{p}}_{p∈π}. As π is a partition, each U_{p} ∈!G is indexed by a set of cardinality less than that of the set indexing U. We can then use induction to obtain a splitting of x_{p} for each p. Joining these splittings we obtain a splitting of x.

We can now characterize free algebras in terms of splittings.

2.8. Lemma. An algebra is free if and only if every non-trivial element has a unique splitting.

Proof. Let ζ : EF → F be an algebra. By Lemma 2.7, the maps

\xymatrix{(EL(F, ζ))U \ar[r]^{Eα} & (EF)U \ar[r]^{ζ} & F U}

are surjective. It is clear then that splittings are unique if and only if this map is an iso for each U. It is easy to show that this map is an algebra map from μ : EEL(F, ζ) → EL(F, ζ) to ζ. So, if splittings are unique then ζ is iso to a free algebra. On the other hand, it is easy to see that for any F and U ≠ ∅, α : (L(EF, μ))U → (EF)U is iso over (EF)U to η : F U → (EF)U. So μ.(Eα) = μ.(Eη) = id and hence splittings are unique in free algebras.

Finally we need to relate decompositions and free algebras.

2.9. Lemma. Let m : F · F → F be a simple monoid and let ζ : EF → F be the associated algebra. Then m is a decomposition if and only if ζ is free.

Proof. First assume that m is a decomposition. In order to prove that ζ is free it is enough, by Lemma 2.8, to prove that splittings are unique. So let U = {g_{i}}_{i∈I} and x in F U be such that x has splittings given by a partition π and elements {x_{p}}_{p∈π} and by a partition σ and elements {y_{s}}_{s∈σ}. Let U_{k} in π and V_{l} in σ be such that U_{k} ∩ V_{l} is non empty. We are going to show that U_{k} = V_{l} and that x_{k} = y_{l} which implies that the splittings are the same. Let U′ be the complement of U_{k} in I. Similarly, let V′ be the complement of V_{l}. The splittings induce an x′ in F U′ and a y′ ∈ F V′ such that m(x′, x_{k}) = x = m(y′, y_{l}). The condition defining decompositions then says that there is a unique 4-partition (W_{0}, W_{1}, W_{2}, W_{3}) of U together with elements a ∈ F W_{0}, b ∈ F W_{1}, c ∈ F W_{2} and d ∈ F W_{3} such that m(a, b) = x′, m(a, c) = y′, m(c, d) = x_{k} and m(b, d) = y_{l}. It follows that W_{0} ⊔ W_{1} = U′, W_{2} ⊔ W_{3} = U_{k}, W_{0} ⊔ W_{2} = V′ and that W_{1} ⊔ W_{4} = V_{l}. In turn, this implies, that W_{0} = U′ ∩ V′, W_{1} = U′ ∩ V_{l}, W_{2} = U_{k} ∩ V′ and W_{3} = U_{k} ∩ V_{l}. As y_{l} is connected and U_{k} ∩ V_{l} is non-empty then it must be the case that U′ ∩ V_{l} is empty and hence that U_{k} = V_{l} and d = y_{l}. We then must have U_{k} ∩ V′ empty and x_{k} = d = y_{l}.

On the other hand, if every element x has a unique splitting it is not difficult to show that the axiom for decompositions (Definition 1.2) follows.

It follows that Dec is equivalent over ˆ!G to the Kleisli category of E. So the exponential principle holds. It is clear that the proof works for functors valued in finite sets so the proof of Proposition 1.4 is finished. The relation with Dress and Müller’s result will be discussed below Examples 3.2 and 3.5 below.

3. Some examples

The first example is a trivial case and the rest have been taken from the literature (in some cases, slightly modified to have sets as coefficients). The tensor · induced by Proposition 1.4 always corresponds, in each example, with the basic symmetric tensor that “explains” the combinatorics of the product of series modeled by the variant of species that motivates the example. This can be seen by checking the relevant reference and comparing with Lemma 2.3.

3.1. Example. (Trivial case with extensive coproducts.) Let C be an extensive category and consider the symmetric monoidal category (C, +, 0). In this case every object is simple and every monoid F + F → F is forced to be of the form [id, id] : F + F → F by the unit axioms. Also, every map is a map of monoids and hence the category of monoids is equivalent to C. So in this case the forgetful functor SCMon → C is an isomorphism and hence trivially monadic. In other words, (C, +, 0) has algebraic families trivially. On the other hand, few objects are decompositions. Indeed, no finite coproduct of connected objects is a decomposition. So if C has a connected object then (C, +, 0) does not satisfy the exponential principle.

3.2. Example. (Joyal [10].) Let 1 be the trivial groupoid with one object and one map. Then !1 = 𝔹 is equivalent to the groupoid of finite sets and bijections and (ˆ!1, ·, I) is the monoidal category of species.

This is, of course, the case where Proposition 1.4 reduces to the first item of Theorem 1.1. For a weakly decomposable F, Dress and Müller show (using that t has monic components) that F 0 = 1 and that a DM-decomposition t is commutative and associative. In order to relate DM-decompositions with decompositions as defined in this paper it seems more natural to start slightly differently. Consider natural transformations t : F × F → F.+ as above and notice that we can define a map m : F · F → F as follows. For each binary ordered partition (U_{0}, U_{1}) of U we have the map

\xymatrix{F U_{0} × F U_{1} \ar[r]^{t} & F (U_{0} + U_{1}) \ar[r]^{≅} & F U}

and by the universal property of coproducts we obtain a map m : F · F → F. If t is commutative and associative then m will be a commutative monoid. On the other hand, if we start with a commutative monoid m we can build a natural t as follows. For any pair U_{0}, U_{1} of finite sets consider the binary ordered partition (U_{0}, U_{1}) of the finite set U_{0} + U_{1}. If we define t at U_{0}, U_{1} as the composition below

\xymatrix{F U_{0} × F U_{1} \ar[r] & (F · F)(U_{0} + U_{1}) \ar[r]^{m} & F (U_{0} + U_{1})}

then it is easy to see that t is a commutative and associative natural transformation. Moreover, it is easy to see that this establishes a correspondence between commutative monoids and such natural transformations. Simple objects are exactly the objects such that F 0 = 1. Finally, it is easy to show that the commutative and associative natural transformations t satisfying (D1) on a simple object F are in correspondence with decompositions (in the sense of Definition 1.2) of F (the mono requirement of DMdecompositions is taken care of by the uniqueness of splittings stated in Lemma 2.8). In other words, DM-decompositions are exactly decompositions in the monoidal category (with tensor ·) of functors from 𝔹 to finite sets. The functor E corresponds, at the level of power series, to the function e^{( )} and this is why the first item of Theorem 1.1 is implied by the case G = 1 of Proposition 1.4. (The assignment of F_{t} to t ↦ F_{t} in [5] corresponds to what we have called L.)

3.3. Example. (Nava and Rota [21].) Consider the groupoid 𝕌 of non-empty finite sets and bijections. It is easy to show that its completion !𝕌 is equivalent to the groupoid ℙ whose objects are sets equipped with a partition and whose maps are bijections between the underlying sets that preserve components of the respective partitions. So that ( ˆ!𝕌, ·, I) is equivalent to the monoidal category of partitionals.

3.4. Example. (Joyal [10], Bergeron [2].) Let ℂ be the groupoid of cyclic permutations and isomorphisms of permutations. Then !ℂ is equivalent to the groupoid 𝕊 of finite sets equipped with a permutation and isomorphisms between them. So the monoidal category ( ˆ!ℂ, ·, I) is equivalent to that of permutationals. Compare with Section 3 in [10].

3.5. Example. (Joyal [10], Méndez and Nava [18].) Let I be a non-empty set and think of it as a set of colors. If we take I as a discrete groupoid then the groupoid !I is equivalent to the category 𝔹_{I} introduced in [18] whose objects are pairs (E, f) where E is a finite set and f is a function E → I (a coloration). Maps in 𝔹_{I} are bijections between the finite sets that preserve colorations. So (ˆ!I, ·, I) is equivalent to the category of I-colored species. See also Section 5 in [10].

Consider the special case when I is the set 1 + 1 with two elements and denote { \atop !(1 + 1)} by Joy_{2}. We think of F ∈ Joy_{2} as a formal power series

F (x, y) = … + F ([n], [m])\frac{x^{n}y^{m}}{n!m!} + …

in two variables x and y. For any G in Joy let G_{x} in Joy_{2} be defined by G_{x}(U, V) = GU if V = 0 and empty otherwise. So that G_{x} has the following representing series.

G_{x}(x, y) = G0 + (G1)x + … + (Gn)\frac{x^{n}}{n!} + …

Let Y be the object of Joy_{2} such that has value 0 at each (U, V) except for Y (0, 1) = 1. So that the representing series Y (x, y) is just y. For any species G the series

(G0)y + (G1)yx + (G2)\frac{yx^{2}}{2} + … + (Gn)\frac{yx^{n}}{n!} + …

represents Y · G_{x} since this functor is GU at stage (U, 1) and empty otherwise. We will explain item 2 of Theorem 1.1 as an application of the exponential principle in Joy_{2}. For any G in Joy such that G∅ = ∅ define ΘG in Joy_{2} as follows:

(ΘG)(U, V) = {{x_{p}}_{p∈π} ∈ (EG)U | |π| = |V |}

where | | denotes cardinality. Joining disjoint families induces a (simple) commutative monoid structure on ΘG and it is easy to show that it is a decomposition. To calculate the connected components notice that if {x_{p}}_{p∈π} in (ΘG)(U, V) is connected then V must be 1 and in this case π is the trivial partition with one element. Indeed, we obtain that L(ΘG) = Y · G_{x}, which is the combinatorial content of item 2 of Theorem 1.1. (The proof in [5] consists of a formal calculation using partial derivatives.) Notice that condition (D2) is not needed. Compare also with Example 39 in [10].

3.6. Example. (Mendez [20].) Let I be a set (this time, thought of as a set of vertices) and consider the set J = I × I as a discrete groupoid. The groupoid !J can be thought of as the groupoid of directed graphs with nodes in I and labeled edges. The monoidal category (ˆ!I, ·, I) of species on digraphs was introduced loc. cit. using the machinery of colored species (Example 3.5). Mendez also considers the case where K is the set of unordered pairs of elements of I so that !K is the groupoid of undirected graphs with nodes in I.

3.7. Example. Also in the context of colored species Mendez and Nava introduce a colored generalization of Bergeron’s permutationals (Example 3.4). For a fixed set I, let ℂ_{I} be the groupoid whose objects are cyclic permutations (U, σ) together with a constant function U → I. The monoidal category of I-permutationals described in Section 3.2 of [18] is equivalent to ( ˆ!ℂ_{I}, ·, I).

3.8. Example. (Leroux and Viennot [15].) Let 𝕃 be the groupoid of finite sets equipped with a linear order and monotone bijections between them. Consider the functor category 𝕃̂ and define the monoidal structure · as below

(F · G)(U, ≤) = ∑ F (U_{0}, ≤_{0}) × G(U_{1}, ≤_{1})

where the sum ranges over the binary partitions (U_{0}, U_{1}) of U and ≤_{0} and ≤_{1} are the total orders induced by ≤ on the components of the partition. The unit I is as in the case of ordinary species. A functor valued on finite sets is called an 𝕃-species by Leroux and Viennot who use this category to develop a combinatorial theory of differential equations. It is clear that the groupoid 𝕃 is not a symmetric monoidal completion so we can not apply Proposition 1.4. But using similar ideas one can show that (𝕃̂, ·, I) satisfies the exponential principle. It is interesting to note that Joyal describes in Section 4 of [10] a different monoidal structure on the category 𝕃̂.

In a sense, Proposition 1.4 can be seen as abstracting from the case of Joy by generalizing the nature of the indeterminates in the associated power series. Other general results can probably be obtained by generalizing the nature of coefficients. In our cases these are sets (cardinalities) or finite sets (natural numbers). But consider for example the tensorial species introduced in [11] where coefficients are vector spaces or the Möbius species introduced in [19] where coefficients are families of certain posets.

For many variants of the theory of species there is a monoidal structure ∘ that corresponds, at the level of formal power series, to composition. For species, colored-species and linear species (in the sense of [15]), E = 1 ∘ ( ). (See Remark 1.2 in [18] for the case of colored species.) But this is not the case for permutationals and partitionals. Also, in [10] there is a different monoidal structure ∘ among linear species, which corresponds also to composition among certain type of power series, but which does not satisfy E = 1 ∘ ( ).

3.9. Slices. It is well known that every commutative monoid X in a monoidal category (D, ·, I) induces a symmetric monoidal structure (D/X, ·, I) on the slice D/X and that the forgetful D/X → D is monoidal. Moreover, the category CMon(D/X) is equivalent, over CMon(D), to CMon(D)/X. If X is simple then the functor D/X → D creates simple objects and so, the equivalence CMon(D/X) → CMon(D)/X restricts to an equivalence SCMon(D/X) → SCMon(D)/X. Analogously, for any monad (M, η, μ) on D and algebra ζ : MX → X there is a monad M/ζ on D/X such that the category of algebras Alg(M/ζ) is equivalent, over Alg(M), to Alg(M)/ζ. (The monad M/ζ assigns ζ.(Mt) to each object t : A → X in D/X.) Moreover, if ζ is a free algebra μ : MMA → MA then the Kleisli category Kl(M/μ) is equivalent over Alg(M) to Kl(M)/μ. Using these well known facts it is easy to prove the following.

3.10. Lemma. Let (D, ·, I) be a symmetric monoidal category with algebraic families. For any simple commutative monoid m : X · X → X, the monoidal category D/m has algebraic families. Moreover, if D satisfies the exponential principle and m is a decomposition then D/m also satisfies the exponential principle.

Proof. Let ζ be the E-algebra related with m via the equivalence SCMon ≅ Alg_{E}. Then SCMon(D/m) ≅ SCMon(D)/m ≅ Alg_{E}/ζ ≅ Alg_{E/ζ}. Now, concerning decompositions, the functor D/X → D creates pullbacks (and recall that it is monoidal) so if m is a decomposition then a commutative monoid in D/X is a decomposition if and only if its image in D is a decomposition. So, if m is the decomposition corresponding to the free algebra μ : EEA → EA, we can calculate Dec(D/m) ≅ Dec(D)/m ≅ Kl_{E}/μ ≅ Kl_{E/μ}. In other words, D/(EA) satisfies the exponential principle.

When D is a category of the form ˆ!G, it is possible to give a more explicit description of D/(EA). Let us start with an arbitrary groupoid H, and R in Ĥ. Define an R-structure to be an element of RU for some U in H (see [10] 1.1). Let u : V → U be a map in H and let r ∈ RU, if r′ = (Ru)r then we say that u is a morphism from r′ to r. We denote by el(R) the category (obviously a groupoid) of R-structures and morphisms between them. There is forgetful functor el(R) → H and every map R → R′ in Ĥ induces a functor el(R) → el(R′) that commutes with the forgetful functors. Proposition 2 in [10] also lifts to show that the slice category Ĥ/R is equivalent to { \atop el(R)}.

3.11. Lemma. For any C in ˆ!G, el(EC) ≅!el(C).

Proof. An object of el(EC) is given by an object {g_{i}}_{i∈I} in !G, a partition π of I and for every p ∈ π an element x_{p} ∈ Cp. The collection {x_{p}}_{p∈π} is an object in !el(C). It is not difficult to show that the induced functor el(EC) →!el(C) is an equivalence.

The equivalence el(EC) →!el(C) induces an equivalence { \atop el(EC)} → { \atop !el(C)} and so, an equivalence ˆ!G/(EC) → { \atop !el(C)}. It is not difficult to show that it is a monoidal equivalence. We now look at some examples, slightly abusing notation in order to make clear the connection with the examples in Section 2.

3.12. Example. Let 𝕌 in Joy be the subspecies of 1 obtained by requiring that 𝕌∅ = ∅. The species E𝕌 is the species ℙ of partitions and the monoidal category Joy/ℙ is equivalent to that of partitionals (Example 3.3).

3.13. Example. Let ℂ in Joy be the species of cyclic permutations. Then Eℂ is the species 𝕊 of permutations and Joy/𝕊 is equivalent to the category of permutationals (Example 3.4).

3.14. Example. For a fixed set I, let ε_{I} be the species such that ε_{I}∅ = ∅, ε_{I}1 = I and for every other finite set U, ε_{I}U = ∅. It is clear that Joy/(Eε_{I}) is the monoidal category of I-colored species (Example 3.5). The categories of (di)graphical species (Example 3.6) are particular cases of this construction.

3.15. Example. Again for a fixed set I, let ℂ_{I}U be the set of pairs (σ, f) such that σ is a cyclic permutation on U and f : U → I is a constant function. The monoidal category Joy/(Eℂ_{I}) is that of I-permutationals (see Example 3.7).

3.16. Example. Let 𝕃 be the species of total orders. Concatenation induces a (noncommutative) monoid m : 𝕃 · 𝕃 → 𝕃. The slice category Joy/𝕃 is the category described in Example 3.8. On the other hand, the monoidal structure described in that example is not the one induced by m.

Before we go on to discuss E-functors let us mention that the terminal object in our main examples is in the image of E. We will use this in the next section.

3.17. Lemma. Let G be an essentially small groupoid. Let ε be the object in ˆ!G such that εU = 1 if U is in G and it is empty otherwise. Then Eε = 1 in ˆ!G.

Proof. Easy.

4. Basic results on E-functors

Let (D, ·, I) satisfy the exponential principle and let C be an object of D. We saw in Lemma 3.10 that the category D/(EC) equipped with the monoidal structure induced by the decomposition μ_{C} satisfies the exponential principle. Any map f : C → ED induces a functor D_{f} : D/(EC) → D/(ED) that assigns to t : X → EC, the composition μ.(Ef).t : X → ED.

4.1. Proposition. Let (D, ·, I) be symmetric monoidal and satisfy the exponential principle. Then, for any map f : C → ED, the functor D_{f} : D/(EC) → D/(ED) is an E-functor.

Proof. This is a simple calculation using the definitions of E/μ and D_{f}.

When the monoidal category D is of the form (ˆ!G, ·, I) for some groupoid G, it is possible to give a more explicit description of the functor D_{f} along the equivalences ˆ!G/(EC) → { \atop !el(C)} and ˆ!G/(ED) → { \atop !el(D)}. Indeed, the map f : C → ED induces a functor !el(f) :!el(C) →!el(ED) ≅!!el(D). The universal property of ! applied to the identity functor !el(D) →!el(D) provides a functor !!el(D) →!el(D) which can be post-composed with !el(f) to obtain a functor f :!el(C) →!el(D). We then have f_{!} : { \atop !el(C)} → { \atop !el(D)} defined by (f_{!}H)A = ∑ HU for A in !el(D) and the sum ranging over the U’s such that fU = A. We now describe how some functors that have appeared in [10, 2, 20] arise as in Proposition 4.1.

4.2. Example. The functor ( )_{x} : Joy → Joy_{2} used below Example 3.5 is an E-functor because it is induced by the map η.in_{0} : ε → E(ε + ε).

4.3. Example. There is a unique map ι : ε → ℂ in Joy. Intuitively, it distinguishes the unique cycle on a one-element set. The map η.ι : ε → Eℂ = 𝕊 induces an E-functor 𝔎 : Joy → Joy/(Eℂ). At the level of elements the map η.ι : ε → Eℂ induces the functor 𝔹 → 𝕊 from the groupoid of finite sets to that of permutations that assigns to U the permutation (U, id). So that, for each species F, the functor 𝔎 : Joy → 𝕊̂ is defined by (𝔎F)(U, σ) = F U if σ = id and (𝔎F)(U, σ) = ∅ otherwise.

4.4. Example. Consider now the map ℂ → 1 = Eε in Joy which collapses cycles. This map induces an E-functor 𝔘 : Joy/(Eℂ) → Joy. At the level of elements the map ℂ → 1 induces the functor 𝕊 → 𝔹 which assigns to each permutation (U, σ) its underlying set. So that 𝔘 : 𝕊̂ → Joy is explicitely defined by

(𝔘T)A = ∑_{σ∈𝕊A}T σ

and it is explained in [2] that when one thinks of T as being the combinatorial interpretation of a power-series t(x_{1}, x_{2}, x_{3}, …) on an infinite set of variables x_{1}, x_{2}, … as in the introduction then 𝔘 corresponds to the assignment t ↦ t(x, x^{2}, x^{3}, …).

4.5. Example. Recall the species 𝕌 of non-empty sets and consider the map ℂ → 𝕌 that forgets cycles. At the level of elements the induced map Eℂ → E𝕌 corresponds to the functor 𝕊 → ℙ that assigns to each permutation (U, σ) the partition that σ induces on U. In [2], Bergeron proposes to compare the categories of permutationals and of partitionals via the resulting functor 𝔖 : 𝕊̂ → ℙ̂ whose explicit definition is, for each permutational T and each partition π of a finite set U, (𝔖T)π = ∑ T σ where the sum is taken over all the permutations σ whose induced partition is π.

In Section 6 of [10], Joyal introduces the espèces pondérées and uses them to give combinatorial interpretations of four well known formulas. We now show that Examples 36 and 38 in [10] can be seen as the application of an E-functor to a terminal object. For any C in Joy, Lemma 3.17 implies that the terminal object in Joy/(EC) is such that 1 = Eε for some ε. So for any ϕ : C → ED in Joy, the induced E-functor ϕ : Joy/(EC) → Joy/(ED) satisfies ϕ1 = ϕEε = Eϕε.

4.6. Example. (Example 36 in [10].) Let x_{1}, x_{2}, … be a denumerable set of formal variables. For any permutation σ on a finite set U we define pσ = x_{1}^{d_{1}}x_{2}^{d_{2}} ⋯ x_{n}^{d_{n}} where n is the cardinality of U and d_{i} is the number of σ-cycles of length i. The cycle indicator polynomial associated with U is the formal expression

Z_{n} = \frac{1}{n!} ∑_{σ∈𝕊U} pσ

where n is the cardinality of U and 𝕊U denotes the set of permutations on the set U. Consider the terminal object 1 in the category of permutationals. We can assume that 1(U, σ) is the singleton set with pσ as its unique element and apply the E-functor 𝔘 : 𝕊̂ → Joy (Example 4.4) so that (𝔘1)U = ∑_{σ∈𝕊U} pσ and

(𝔘ε)U = ∑_{σ∈𝕊U} εσ = ∑_{σ∈ℂU} εσ = (n − 1)!x_{n}

where n is the cardinality of U. Switching to formal power series we obtain the identity

∑_{n≥0} Z_{n}x^{n} = 𝔘1 = E𝔘ε = E (∑_{n≥0} x_{n} \frac{x^{n}}{n} )

and the reader should also compare with Proposition 7.3 in [4].

We can modify Examples 4.4 and 4.6 to apply to partitionals.

4.7. Example. (Example 38 in [10]) Let x_{1}, x_{2}, … a set of formal variables. For any partition π of a set U we define pπ = x_{1}^{d_{1}}x_{2}^{d_{2}} ⋯ x_{n}^{d_{n}} where n is the cardinality of U and d_{i} is the number of π-classes of cardinality i. The exponential polynomial associated with U is the formal sum

Y_{n} = ∑_{π∈Part U} pπ.

Consider the terminal object 1 in the category of partitionals. The map 𝕌 → 1 = Eε corresponds, at the level of elements, to the forgetful functor from ℙ → 𝔹 and it induces an E-functor ϕ : ℙ̂ → Joy such that for each partitional F and finite set U, (ϕF)U = ∑ F π where the sum is taken over the partitions of U. As before, we can assume that the terminal object is defined by 1(U, π) = {pπ} so that (ϕ1)U = Y_{n} where n is the cardinality of U and (ϕε)U = x_{n}. Switching to formal power series we obtain the identity

∑_{n≥0} Y_{n} \frac{x^{n}}{n!} = ϕ1 = Eϕε = E (∑_{n≥0} x_{n} \frac{x^{n}}{n!} ) .

4.8. Example. Fix a set I thought of as a set of nodes and let J be I × I and let K be the set of unordered pairs of elements of I. There is an obvious epi d : J → K. It induces an E-functor from digraphical to graphical species (recall Examples 3.6 and 3.14) with a right adjoint which we know, by Corollary 1.7, that it is a weak E-functor. Compare with Proposition 6.2 in [20]. We discuss more examples of weak E-functors below.

4.9. Weak E-functors. Recall from the discussion below Corollary 1.7 that the right adjoints D/(ED) → D/(EC) induced by the maps C → ED in D are weak E-functors (Definition 1.6). As in the case of the left adjoints (see below Proposition 4.1) when D is of the form ˆ!G the right adjoints have a more explicit description. If the map C → ED induces a functor K :!el(C) →!el(D) then the right adjoint K^{∗} : { \atop !el(D)} → { \atop !el(C)} is defined simply as K^{∗}F = F K, that is, pre-composition with K. For example, the right adjoint R : Joy_{2} → Joy to the functor ( )_{x} : Joy → Joy_{2} of Example 4.2 is defined by (RF)U = F (U, ∅). It should be noticed that R is an E-functor.

The right adjoint to the functor 𝔎 : Joy → 𝕊̂ in Example 4.3 is the (weak E-functor) 𝔗 : 𝕊̂ → Joy explicitely defined in [2] by (𝔗T)A = T (A, id). Bergeron explains that when one thinks of T as being the combinatorial interpretation of a power-series t(x_{1}, x_{2}, x_{3}, …) then 𝔗 corresponds to the assignment t ↦ t(x, 0, 0, …). As in the previous case, this functor is not just a weak E-functor but also an E-functor.

Consider now the right adjoint induced by the map ℂ → 1 = Eε of Example 4.4. This is the weak E-functor R : Joy → 𝕊̂ defined by (RF)(U, σ) = F U. In this case, R is not an E-functor (it is easy to see this by applying E(RF) and R(EF) to a non-trivial cycle).

The functor Fix : Joy → 𝕊̂ defined by (FixF)(U, σ) = {x ∈ F U | (F σ)x = x} is discussed from slightly different perspectives in [10] and [2]. The functor Fix is monoidal and preserves coproducts (see Proposition 3 in [2]) but it does not preserve epis (for example, it does not preserve the unique epi from the species 𝕃 of totally ordered sets to the terminal species 1). So it does not have a right adjoint and hence it is not induced by a map ε → Eℂ in Joy. But it is easy to prove that Fix preserves pullbacks so it is a weak E-functor by Corollary 1.7. That is, for any N in Joy, Fix(EN) is a free E-algebra in the category 𝕊̂ of permutationals. Indeed, there is an interesting way of expressing Fix(EN) as an exponential (see Section 3 in [10]). A crown of N-structures for some species N is an element of {x_{p}}_{p∈π} of (EN)U (for some finite set U and partition π of U) together with an automorphism σ (given by an iso σ : U → U) whose action permutes the x_{p}’s in a cycle. We denote the set of N-crowns with underlying iso σ by (CrN)σ. Because (Fix(EN))(U, σ) is the set of elements of (EN)U that are fixed by σ it is easy to see that the connected elements of the free simple monoid Fix(EN) are the crowns of N-structures. In other words, Fix(EN) = E(CrN). It is then clear that Fix is not an E-functor. Is Fix the right adjoint induced by a map ℂ → 1 in Joy? The answer is again no. For suppose it is, then there exists a functor Γ : 𝕊 → 𝔹 such that (FixF)(U, σ) = F (Γ(U, σ)). Consider now the species 𝕃 of total orders. For every non trivial cycle σ, (Fix𝕃)σ = ∅. On the other hand for every set U, 𝕃U is not empty. So no such Γ exists.

The reader is invited to check if the weak E-functors that are right adjoints to the E-functors described in Examples 4.5 and 4.8 are also E-functors.

Finally, it is well known that every functor K : C → C′ between small categories induces a right adjoint K_{∗} : Ĉ → Ĉ′ to K^{∗}. Using the same argument that we used for the case of the functors K :!el(C) →!el(D) one shows that K_{∗} is a weak E-functor. I have not found any use of these functors in the literature on species, though.

5. Infinitesimals

It is easy to see that the monoidal structure (D, +, 0) given by coproducts does not have infinitesimals. The same happens with products. In order to characterize the infinitesimals in the monoidal structures of the form (ˆ!G, ·, I) it is useful to have the following simple result.

5.1. Lemma. In any extensive symmetric monoidal category (D, ·, I) the following hold:

1. if I is connected then so is every object D such that D · ( ) has a right adjoint that preserves finite coproducts

2. if I is projective then so is every object D such that D · ( ) has a right adjoint that preserves regular epis

3. if I is infinitesimal then I is initial.

Proof. For the first item let ∂ denote the right adjoint to D · ( ) and assume that I is connected and that ∂ preserves coproducts. We first show that D is not initial. For assume that it is, then there exists a map D → 0 and by transposition a map I → ∂0 ≅ 0 which is absurd. It is also easy to show that C(D, ) preserves finite coproducts and so D is connected. The case of projectivity is also easy. For the last item let ∂ be the right adjoint to I · ( ). Then the identity I → I induces a map I → ∂I≅ 0 and as 0 is strict (the underlying category is extensive), I is initial.

We can now characterize infinitesimals in our main examples of monoidal categories.

Proof of Proposition 1.10. First we show that every object C in G induces an amazing infinitesimal in ˆ!G. Let x denote the induced object in ˆ!G and let ∂ be the right adjoint to x · ( ). Using that Yoneda preserves the tensor it is easy to show that for any F in ˆ!G and U in !G, (∂F)U = F (C ⊔ U). The strength str_{l} : ∂F · G → ∂(F · G) is given as follows. An element of ∂F · G at stage U is given by a binary partition (U_{0}, U_{1}) of U together with an element x ∈ F (C ⊔ U_{0}) and an element y ∈ GU_{1}. The strength then assigns to this information the pair (C ⊔ U_{0}, U_{1}) (seen as a partition of C ⊔ U) together with x and y. To construct an inverse to the map (∂F · G) + (F · ∂G) → ∂(F · G) we must start with a binary partition (V_{0}, V_{1}) of C ⊔ U and a pair (x, y) in F V_{0} × GV_{1}. As C is in G, it must be the case that C is in V_{0} or C is in V_{1}. In the first case, it must be the case that V_{0} = C ⊔ W with W ⊔ V_{1} = U. So we have a binary partition (W, V_{1}) of U and a pair (x, y) in F (C ⊔ W) × GV_{1} which altogether give an element of ∂F · G. Similarly in the case when C is in V_{1}. So we obtain a map ∂(F · G) → ∂F · G + F · ∂G. It is easy to see that it is the inverse of the map in the opposite direction given by the strengths. It is also clear that the map 0 → ∂I is an iso so the Leibniz rule holds. To prove that x is an infinitesimal we need to show that ∂ preserves finite colimits. For this it is enough to show that it is a left adjoint (making x amazing). But given the explicit description of ∂ it is easy to show that its right adjoint ♢ is given by the following formula

(♢F)U = ∏_{V} F V

where V ranges over the objects of !G obtained from U = {C_{i}}_{i∈I} by removing some C_{k} such that C_{k} ≅ C.

Now assume that x is an infinitesimal. As I is representable we have that it is connected and projective. It follows by Lemma 5.1 that so is x and then, as ˆ!G is a presheaf topos, we have that x is an object D from !G. So we need to show that D is actually in G. Assume that D is ∅. Then I = y∅ = yD = x is infinitesimal and by Lemma 5.1, I is initial. Absurd, so D is not ∅. Now assume that there is an iso D → D_{0} ⊔ D_{1} in !G and let y_{0} and y_{1} be the representables induced by D_{0} and D_{1}. Via Yoneda we obtain a map x → y_{0} · y_{1} in ˆ!G and by transposition we get a map I → ∂(y_{0} · y_{1}). Using the Leibniz rule and without loss of generality we can assume that we obtain a map I → ∂y_{0} · y_{1}. So that there is an element in (∂y_{0} · y_{1})∅. But this can only happen if D_{0} is iso to D and D_{1} is iso to ∅ in !G. So D is indeed an object of G.

In the context of categories of combinatorial structures, the only explicit appearance, I am aware of, of a right adjoint to a derivative functor is in [22] where the (essentially unique) amazing infinitesimal in the topos Joy is considered in detail. Some properties discussed loc. cit. can be lifted to infinitesimals in the monoidal categories discussed in Proposition 1.10 above.

Finally, let us consider the example of an object D which fails to be an infinitesimal but for the preservation of epis. Consider the topos of “irreflexive” graphs. This is the topos of presheaves on the category with two objects E and N and two non-trivial maps s, t : N → E. So an object F of this topos is a graph with set of nodes F N and set of directed edges F E. The source and target of an edge e ∈ F E given by s ▪ e and t ▪ e respectively. Define the tensor · as follows.

(F · G)N = F N × GN (F · G)E = (F E × GN) + (F N × GE)

The source of an edge (e, n) in (F E×GN) is given by (s▪e, n) and its target by (t▪e, n). The unit is the graph I with one node and no edges. It is easy to show that this is a symmetric monoidal structure on the topos of graphs. This monoidal structure is obviously different from that of products or coproducts. Consider for example the graph F given by a discrete set of points (no edges) and think of it as a line. Then picture the graph G induced by a cyclic permutation on a finite set as a circle. It is fair to think of F · G as a “tube” while F × G and F + G give completely different things. Let us look for infinitesimals. Since I is representable by N and the underlying category is a presheaf topos, Lemma 5.1 implies that any infinitesimal must be representable. Indeed, item 3 of Lemma 5.1 leaves only one option: the object representable by E. This is the graph (also denoted by E) with two nodes and one edge joining them. It is not difficult to show that E · ( ) has a right adjoint ð. The graph ðG has the edges of G as nodes and an edge between two such nodes is a pair of edges in G forming a square in the obvious way. It is easy to see that ð satisfies Leibniz rule. It also preserves coproducts but it does not preserve epis as it can be seen by applying ð to the epi that quotients the graph with two nodes each with a loop by the equivalence relation that relates the two nodes but not the loops.

Acknowledgments

I would like to thank Pino Rosolini for his hospitality at DISI (Universitá di Genova, Italia) where much of this work was done. I would also like to thank Marcelo Fiore and Angus Macintyre for a number of helpful discussions. The XY-pic diagrams package was used.

References

[1] E. Bender and J. Goldman. Enumerative uses of generating functions. Indiana university mathematics journal, 20:753–764, 1971.

[2] F. Bergeron. Une combinatoire du pléthysme. Journal of combinatorial theory (Series A), 46:291–305, 1987.

[3] F. Bergeron, G. Labelle, and P. Leroux. Combinatorial species and tree-like structures, volume 67. Cambridge University Press, 1998.

[4] Flavio Bonetti, Gian-Carlo Rota, Domenico Senato, and Antonietta M. Venezia. On the foundation of combinatorial theory. X. A categorical setting for symmetric functions. Stud. Appl. Math., 86(1):1–29, 1992.

[5] A. Dress and T. Müller. Decomposable functors and the exponential principle. Advances in mathematics, 129:188–221, 1997.

[6] S. Eilenberg and G. M. Kelly. Closed categories. In Proceedings of the Conference on Categorical Algebra, La Jolla 1965, pages 421–562. Springer, 1966.

[7] G. B. Im and G. M. Kelly. A universal property of the convolution monoidal structure. Journal of pure and applied algebra, 43:75–88, 1986.

[8] P. Johnstone. Cartesian monads on toposes. Journal of pure and applied algebra, 116:199–220, 1997.

[9] P. T. Johnstone. Adjoint lifting theorems for categories of algebras. Bulletin of the London Mathematical Society, 7:294–297, 1975.

[10] A. Joyal. Une theorie combinatoire des séries formelles. Advances in mathematics, 42:1–82, 1981.

[11] A. Joyal. Foncteurs analytiques et especès de structures. In G. Labelle and P. Leroux, editors, Combinatoire énumérative, volume 1234 of Lecture notes in mathematics, pages 126–159. Springer-Verlag, 1986. Proceedings, Montréal, Quebec 1985.

[12] G. M. Kelly. Doctrinal adjunction. In Category Seminar (Proc. Sem., Sydney, 1972/1973), pages 257–280. Lecture Notes in Math., Vol. 420. Springer, Berlin, 1974.

[13] Gilbert Labelle and Pierre Leroux. An extension of the exponential formula in enumerative combinatorics. Electron. J. Combin., 3(2):Research Paper 12, approx. 14 pp. (electronic), 1996. The Foata Festschrift.

[14] Stephen Lack. On the monadicity of finitary monads. J. Pure Appl. Algebra, 140(1):65–73, 1999.

[15] P. Leroux and G. X. Viennot. Combinatorial resolution of systems of differential equations, I. Ordinary differential equations. In G. Labelle and P. Leroux, editors, Combinatoire énumérative, volume 1234 of Lecture notes in mathematics, pages 210– 245. Springer-Verlag, 1986. Proceedings, Montréal, Quebec 1985.

[16] S. Mac Lane. Categories for the Working Mathematician. Graduate Texts in Mathematics. Springer Verlag, 1971.

[17] Angus J. Macintyre. Exponential algebra. In Logic and algebra (Pontignano, 1994), volume 180 of Lecture Notes in Pure and Appl. Math., pages 191–210. Dekker, New York, 1996.

[18] M. Méndez and O. Nava. Colored species, c-monoids and plethysm, I. Journal of combinatorial theory, Series A, 64:102–129, 1993.

[19] M. Méndez and J. Yang. Möbius species. Advances in mathematics, 85:83–128, 1991.

[20] Miguel A. Méndez. Species on digraphs. Adv. Math., 123(2):243–275, 1996.

[21] O. Nava and G-C. Rota. Plethysm, categories and combinatorics. Advances in mathematics, 58:61–88, 1985.

[22] D. S. Rajan. The adjoints to the derivative functor on species. Journal of combinatorial theory (Series A), 62:93–106, 1993.

[23] R. P. Stanley. Enumerative combinatorics 2, volume 62 of Cambridge studies in advanced mathematics. Cambridge University Press, 1999.

[24] Herbert S. Wilf. Generatingfunctionology. Academic Press Inc., Boston, MA, second edition, 1994.

[25] Tomoyuki Yoshida. Categorical aspects of generating functions. I. Exponential formulas and Krull-Schmidt categories. J. Algebra, 240(1):40–82, 2001.

Lifia, Facultad de Informática, Universidad Nacional de La Plata, 50 y 115 1er Piso, (1900) La Plata, Argentina

Email: matias@sol.info.unlp.edu.ar

This article may be accessed via WWW at http://www.tac.mta.ca/tac/ or by anony-

mous ftp at ftp://ftp.tac.mta.ca/pub/tac/html/volumes/11/18/11-18.{dvi,ps}

THEORY AND APPLICATIONS OF CATEGORIES (ISSN 1201-561X) will disseminate articles that significantly advance the study of categorical algebra or methods, or that make significant new contributions to mathematical science using categorical methods. The scope of the journal includes: all areas of pure category theory, including higher dimensional categories; applications of category theory to algebra, geometry and topology and other areas of mathematics; applications of category theory to computer science, physics and other mathematical sciences; contributions to scientific knowledge that make use of categorical methods.

Articles appearing in the journal have been carefully and critically refereed under the responsibility of members of the Editorial Board. Only papers judged to be both significant and excellent are accepted for publication.

The method of distribution of the journal is via the Internet tools WWW/ftp. The journal is archived electronically and in printed paper format.

Subscription information. Individual subscribers receive (by e-mail) abstracts of articles as they are published. Full text of published articles is available in .dvi, Postscript and PDF. Details will be e-mailed to new subscribers. To subscribe, send e-mail to tac@mta.ca including a full name and postal address. For institutional subscription, send enquiries to the Managing Editor, Robert Rosebrugh,

rrosebrugh@mta.ca.

Information for authors. The typesetting language of the journal is TEX, and L^{A}TEX is the preferred flavour. TEX source of articles for publication should be submitted by e-mail directly to an appropriate Editor. They are listed below. Please obtain detailed information on submission format and style files from the journal’s WWW server at http://www.tac.mta.ca/tac/. You may also write to tac@mta.ca to receive details by e-mail.

Editorial board.

John Baez, University of California, Riverside: baez@math.ucr.edu Michael Barr, McGill University: barr@barrs.org, Associate Managing Editor Lawrence Breen, Université Paris 13: breen@math.univ-paris13.fr Ronald Brown, University of Wales Bangor: r.brown@bangor.ac.uk Jean-Luc Brylinski, Pennsylvania State University: jlb@math.psu.edu Aurelio Carboni, Università dell Insubria: aurelio.carboni@uninsubria.it Valeria de Paiva, Palo Alto Research Center: paiva@parc.xerox.com Martin Hyland, University of Cambridge: M.Hyland@dpmms.cam.ac.uk P. T. Johnstone, University of Cambridge: ptj@dpmms.cam.ac.uk G. Max Kelly, University of Sydney: maxk@maths.usyd.edu.au Anders Kock, University of Aarhus: kock@imf.au.dk Stephen Lack, University of Western Sydney: s.lack@uws.edu.au F. William Lawvere, State University of New York at Buffalo: wlawvere@buffalo.edu Jean-Louis Loday, Université de Strasbourg: loday@math.u-strasbg.fr Ieke Moerdijk, University of Utrecht: moerdijk@math.uu.nl Susan Niefield, Union College: niefiels@union.edu Robert Paré, Dalhousie University: pare@mathstat.dal.ca Robert Rosebrugh, Mount Allison University: rrosebrugh@mta.ca, Managing Editor Jiri Rosicky, Masaryk University: rosicky@math.muni.cz James Stasheff, University of North Carolina: jds@math.unc.edu Ross Street, Macquarie University: street@math.mq.edu.au Walter Tholen, York University: tholen@mathstat.yorku.ca Myles Tierney, Rutgers University: tierney@math.rutgers.edu Robert F. C. Walters, University of Insubria: robert.walters@uninsubria.it R. J. Wood, Dalhousie University: rjwood@mathstat.dal.ca