Theory and Applications of Categories, Vol. 21, No. 11, 2008, pp. 191–209.

ANALYTIC FUNCTORS AND WEAK PULLBACKS

For the sixtieth birthday of Walter Tholen

J. ADÁMEK AND J. VELEBIL

Abstract. For accessible set-valued functors it is well known that weak preservation of limits is equivalent to representability, and weak preservation of connected limits to familial representability. In contrast, preservation of weak wide pullbacks is equivalent to being a coproduct of quotients of hom-functors modulo groups of automorphisms. For finitary functors this was proved by André Joyal who called these functors analytic. We introduce a generalization of Joyal’s concept from endofunctors of Set to endofunctors of a symmetric monoidal category.

1. Introduction

From among accessible set-valued functors those preserving limits are known to be just the representable ones. And those preserving connected limits (or, equivalently, preserving wide pullbacks) were characterized by Aurelio Carboni and Peter Johnstone [CJ] as precisely the coproducts of representables; they call these functors familially representable. Moreover, Peter Freyd and André Scedrov proved in [FS], 1.829 that weak preservation of (connected) limits implies strong preservation of them. Surprisingly, many more accessible functors weakly preserve wide pullbacks; here the characterization is: all coproducts of symmetrized representables by which we mean the quotient of a hom-functor 𝒜 (A, −) modulo a group of automorphisms of A.

The latter is connected to the concept of analytic functor of André Joyal. In his categorical study of enumerative combinatorics, see [J_{1}] and [J_{2}], he introduced species of structures as functors from the category ℬ of natural numbers and permutations into Set. Example: the species p: ℬ [figure]Set of permutations assigning to n the set p(n) of all permutations on n and to every permutation σ: n [figure] n the action of σ on p(n). A set functor F is called analytic if it is the left Kan extension of a species f: ℬ [figure]Set. In other words, F is given on objects by the coend formula

F X = ∫ ^{n:ℬ} X^{n} × f(n).

The second author gratefully acknowledges the support of the grant No. 201/06/664 of the Grant Agency of the Czech Republic.

Received by the editors 2008-04-29 and, in revised form, 2008-11-25.

Published on 2008-11-29 in the Tholen Festschrift.

2000 Mathematics Subject Classification: 18A25, 18D10, 18B05.

Key words and phrases: analytic functor, weak limit, weak pullback.

\begin{matrix}c \\ ◯ \end{matrix} J. Adámek and J. Velebil, 2008. Permission to copy for private use granted.

Example: the species p of permutations yields the analytic functor P X = ∑_{n∈ℕ} X^{n}, the free-monoid functor. Joyal characterized analytic functors as precisely the finitary set functors weakly preserving wide pullbacks.

Another category in which Joyal studied analytic functors is the category Vec_{𝕂} of vector spaces over a given field. Here a species is a functor from ℬ to Vec_{𝕂}. The analytic functor F: Vec_{𝕂} [figure]Vec_{𝕂} corresponding to f is then given by the coend formula

F X = ∫ ^{n:ℬ} X^{⊗n} ⊗ f(n).

Example: the species of permutations yields the functor P X = ∑_{n∈ℕ} X^{⊗n}, the tensoralgebra functor. We can obviously play the same game in every symmetric monoidal category ℰ and define analytic endofunctors of ℰ as those obtained from a species via the above coend formula. Example: The analytic endofunctors of S-sorted sets are the S-tuples of analytic endofunctors of Set; they weakly preserve wide pullbacks but the converse does not hold.

Weak wide pullbacks appear in several applications of category theory, e.g. in coalgebra [G] and in stable domain theory [Ta]. However, the connection between them and analytic functors is, beyond the category of sets, quite loose: in many-sorted sets Example 4.4(iii) below demonstrates that a wide pullback preserving endofunctor need not be analytic, and in vector spaces Corollary 3.9 below implies that almost no analytic functor weakly preserves wide pullbacks.

Acknowledgement. We are grateful to the referee whose suggestions helped us improving the presentation of our paper.

Related Work

Ryu Hasegawa [H] presented an alternative proof of Joyal’s characterization of analytic endofunctors of Set. In the first section we provide a new proof which is simpler than both of the previously published ones. We also prove that countable wide pullbacks are sufficient.

Analytic functors of André Joyal have recently been generalized by Brian Day [D] who defined E-analytic functors for a kernel E(n, X); our definition is the special case of E(n, X) = X^{⊗n}. A different approach has been taken by Marcello Fiore et al, see [F] and [FGHW]: for a small category 𝒜 they form the groupoid ℬ𝒜 of all isomorphisms in the free completion of 𝒜 under finite coproducts. Then a functor F: [𝒜^{op}, Set] [figure] [𝒞^{op}, Set] is called analytic if it is the left Kan extension of a functor f: ℬ𝒜 [figure] [𝒞^{op}, Set] along canonical functor ℬ𝒜 [figure] [𝒜^{op}, Set]. In [F] these functors are, in case 𝒜 and 𝒞 are groupoids, characterized as precisely the finitary functors weakly preserving quasipullbacks. Finally, M. Abbot et al [AAGB] study quotient containers which generalize species of structures by considering groups of automorphisms on infinite sets. The corresponding generalization of analytic functor is called an extension of the quotient container. These are precisely the accessible set functors weakly preserving wide pullbacks as we prove in Section 3.

Weak preservation of various types of limits is also studied, for endofunctors of Set, in [AGT]. The characterization of weak preservation of wide pullbacks in Theorem 3.3 generalizes a result of that paper; the present proof is simpler.

2. Analytic Set Functors

2.1 Definition (A. Joyal). A functor F: Set [figure]Set is called analytic provided that it is the left Kan extension of a functor f from ℬ, the category of natural numbers and bijections, into Set. In other words, F is defined on objects X by the coend

F X = ∫ ^{n:ℬ} X^{n} × f(n).  (2.1)

2.2 Remark. For every natural number n the (symmetric) group of all permutations of n is denoted by 𝒮_{n}.

(i) Suppose that a species f is given on objects by

f(n) = V and f(k) = ∅ for all k ≠ n.

The coend formula then expresses F X as the joint coequalizer for all the automorphisms σ̄ = X^{σ} × f(σ^{−1}) of X^{n} × V for σ ∈ 𝒮_{n}. In other words

F X = X^{n} × V/∼  (2.2)

where ∼ is the equivalence relation consisting of all pairs

(x, i) ∼ (x·σ, f(σ^{−1})(i)) for all x ∈ X^{n}, i ∈ V, σ ∈ 𝒮_{n}.  (2.3)

(ii) Every species is an (objectwise) coproduct of species of the type (i) above. Since left Kan extension preserves coproducts, every analytic functor is a coproduct of functors given by (2.2).

2.3 Examples (see [J_{1}], [J_{2}]). (i) The representable functor (−)^{n} is, for every n ∈ ℕ, analytic. The corresponding species is given on objects by f(n) = 𝒮_{n} and f(k) = ∅ for k ≠ n; on morphisms put f(σ): τ [figure] σ·τ for σ, τ ∈ 𝒮_{n}.

(ii) The species of permutations

p(n) = 𝒮_{n} for all n ∈ ℕ

which is the coproduct of those in (i) yields the analytic functor

P X = ∑_{n∈ℕ}X^{n} = free monoid on X.

(iii) Let 𝒢 be a group of permutations, a subgroup of 𝒮_{n}. We denote by

F X = X^{n}/𝒢

the quotient functor of X^{n} modulo the following equivalence ∼_{𝒢}:

x ∼_{𝒢} y iff x = y·σ for some σ ∈ 𝒢.

These functors are called symmetrized representables. They are analytic: the corresponding species is the quotient of that in (i) given by

f(n) = 𝒮_{n}/∼_{𝒢} .

In fact, in the equivalence (2.3) all pairs (x, [id_{n}]) fulfil

(x, [id_{n}]) ∼ (y, [id_{n}]) iff x ∼_{𝒢} y,

and every pair (x, [σ]) is equivalent to (x·σ, [id_{n}]). Consequently, the equivalence relation (2.3) yields the quotient X^{n} × (𝒮_{n}/∼_{𝒢}) [figure] F X assigning to (x, [τ]) the value [x·τ].

(iv) The trivial species

e(n) = 1 for all n ∈ ℕ

yields the analytic functor

EX = finite multisets in X.

In fact, (2.2) implies that

EX = ∑_{n∈ℕ}X^{n}/𝒮_{n}

and this means that in an n-tuple in X^{n} the order of the coordinates does not matter, but the number of repetitions does.

(v) The species of trees assigns to every n the set t(n) of all (directed, rooted) trees on n = {0, 1, …, n − 1}. The corresponding analytic functor is

T X = isomorphism classes of trees labelled in X.

2.4 Remark. (i) As already observed by Věra Trnková [T], every set-valued functor F is a coproduct of functors preserving the terminal object: the coproduct is indexed by F 1 and for every i ∈ F 1 we consider the subfunctor F_{i} of F given on objects X by F_{i}X = (F t)^{−1}(i) for the unique morphism t: X [figure] 1. This fact immediately generalizes to functors F: 𝒜 [figure]Set for an arbitrary category 𝒜 having a terminal object.

(ii) We now characterize functors preserving weak pullbacks from among a special class of set functors; the same result was already published in [AT] but with a complicated proof.

2.5 Definition (see [AT]). A set functor F is called super-finitary if there exists a natural number n such that the elements of F n generate all of F. That is, for every set X we have

F X = ⋃_{f: n→X} F f[F n].  (2.4)

2.6 Theorem. For a super-finitary set functor the following conditions are equivalent:

(i) F weakly preserves pullbacks,

(ii) F is analytic,

and

(iii) F is a coproduct of symmetrized representables.

Proof. (i) ⇒ (iii) Due to 2.4(i) we can assume F 1 = 1. Then F weakly preserves finite products. Let us choose the least number n with (2.4). Then there exists x_{0} ∈ F n which is minimal, i.e. such that x_{0} does not lie in F_{i}[F k] for any proper subobject i: k [figure] n. It follows that

if x_{0} ∈ F f[F X] for some f: X [figure] n, then f is epic.  (2.5)

In particular, every element of

𝒢 = {σ: n [figure] n; F σ(x_{0}) = x_{0}}  (2.6)

is an epimorphism, thus an isomorphism. We obtain a subgroup 𝒢 ⊆ 𝒮_{n}, and we prove are going to that

F ≅ (−)^{n}/𝒢 .

In fact, the Yoneda transformation

(−)^{n}  [figure] F,  u [figure] F u(x_{0})

yields a natural isomorphism (−)^{n}/𝒢 ≅ F. This is clear provided that we prove that

(a) every element of F has the form F u(x_{0})

and

(b) given u, v ∈ X^{n} then F u(x_{0}) = F v(x_{0}) iff u ∼_{𝒢} v.

To prove (a) use (2.4): it is sufficient to prove that every element y ∈ F n has the form y = F u(x_{0}). Since F weakly preserves finite products, for x_{0}, y ∈ F n there exists z ∈ F (n × n) with

F π_{1}(z) = x_{0} and F π_{2}(z) = y for the projections π_{1}, π_{2} : n × n [figure] n.

By (2.4) we have z_{0} ∈ F n with F f(z_{0}) = z. From

x_{0} = F π_{1}(z) = F (π_{1}·f)(z_{0})

we conclude that π_{1}·f: n [figure] n is epimorphism, see (2.5), thus, an isomorphism. Put

u = π_{2}·f·(π_{1}·f)^{−1},

then

y = F π_{2}(z) = F (π_{2}·f)(z_{0}) = F (π_{2}·f)·F (π_{1})^{−1}(x_{0}) = F u(x_{0})

as requested.

To prove (b), observe that u ∼_{𝒢} v implies u = v·σ with F σ(x_{0}) = x_{0}, thus, F u(x_{0}) = F v(x_{0}). Conversely, assuming F u(x_{0}) = F v(x_{0}), form a pullback

[figure: n; X; u; n; X; v; P; n; v̄; P; n; ū]

Since F weakly preserves it, there exists z ∈ F P with

F ū(z) = x_{0} = F v̄(z).

Express, using (a),

z = F f(x_{0}) for f: n [figure] P

then the morphisms ū·f, v̄·f: n [figure] n lie in 𝒢, and

u = u·(v̄·f)·(v̄·f)^{−1} = v·(ū·f)·(v̄·f)^{−1}

which yields the desired equation u = v.σ for

σ = (ū·f).(v̄·f)^{−1} ∈ 𝒢 .

(iii) ⇒ (ii) See Example 2.3(iii).

(ii) ⇒ (i) Let us verify that every functor F given by (2.2) weakly preserves pullbacks

[figure: A_{1}; B; a_{1}; A_{2}; B; a_{2}; P; A_{1}; p_{1}; P; A_{2}; p_{2}]

In fact, given elements [x_{k}, i_{k}] with F a_{1}([(x_{1}, i_{1})]) = F a_{2}([(x_{2}, i_{2})]), we have

(a_{1}·x_{1}, i_{1}) ∼ (a_{2}·x_{2}, i_{2}).

Thus there exists σ ∈ 𝒮_{n} with

a_{1}·x_{1}·σ = a_{2}·x_{2} and f(σ^{−1})(i_{1}) = i_{2}.

The first equality yields a unique b: n [figure] P with

x_{1}·σ = p_{1}·b and x_{2} = p_{2}·b.

Then the element [(b, i_{2})] is mapped by F p_{1} to [(x_{1}·σ, f(σ^{−1})(i_{1}))] = [(x_{1}, i_{1})] and by F p_{2} to [(x_{2}, i_{2})], as requested.

2.7 Corollary. For every finitary functor F: Set [figure] Set the following conditions are equivalent:

(i) F is analytic,

(ii) F is a coproduct of symmetrized representables,

(iii) F weakly preserves countable wide pullbacks,

(iv) F weakly preserves wide pullbacks.

Proof. In fact, it is sufficient to prove this for functors with F 1 = 1. The implication (ii) ⇒ (i) follows from 2.3(iii), and (iii) ⇒ (ii) follows from 2.6 because F is superfinitary. In fact, assuming the contrary, for every n ∈ ℕ we have x_{n} ∈ F X_{n} with x_{n} ∉ ⋃_{h∈X^{n}} F h[F n]. But F 1 = 1 implies that F weakly preserves countable products. Thus, there exists x ∈ ∏_{n∈ℕ} F X_{n} with F π_{n}(x) = x_{n} for all n ∈ ℕ. Since F is finitary, there exists a morphism g: k [figure] X and y ∈ F k with x = F g(y). Then x_{k} = F (π_{k}·g)(y), a contradiction.

Finally, (iv) ⇒ (iii) trivially and (i) ⇒ (iv) is proved as in 2.6.

2.8 Example. The finite-powerset functor 𝒫_{fin} preserves weak pullbacks. This demonstrates that in 2.7(iii) pullbacks are not sufficient.

2.9 Remark. (a) The equivalence of (i), (iii) and (iv) was proved by André Joyal [J_{2}], and a compact proof was later presented by Ryu Hasegawa [H].

(b) Condition (iii) trivially implies that F preserves limits of cofiltered diagrams (and the formulation of Joyal used that plus weak preservation of pullbacks). In fact, let

p_{t}: P [figure] X_{t} (t ∈ T)

be a cofiltered limit and assume, without loss of generality, that T has a terminal element t_{0}; thus we have connecting morphisms x_{t}: X_{t} [figure]X_{t_{0}} for t ∈ T. The limit cone is, obviously, a wide pullback of the cocone (x_{t})_{t∈T}, thus, F P is a wide pullback of (F x_{t})_{t∈T}.To prove that F p_{t} (t ∈ T) is a limit cone we only need to observe that it is collectively monic. Given elements x_{1} ≠ x_{2} in F P find a finite set m: M [figure] X with x_{1}, x_{2} ∈ F m[F M]. Since the limit is cofiltered, there exists t ∈ T such that p_{t}·m is monic, therefore F (p_{t}·m) is monic: recall that F preserves monomorphisms because it (weakly) preserves intersections. This implies F p_{t}(x_{1}) ≠ F p_{t}(x_{2}).

2.10 Corollary. A finitary set functor preserving countable limits is representable.

In fact, from 2.7 and F 1 = 1 we know that F is a symmetrized representable. Moreover, if F = (−)^{n}/𝒢 preserves equalizers, then 𝒢 is the trivial group: for every σ ∈ 𝒢 consider the equalizer e of σ and id_{n}, since F e is the equalizer of F σ and id_{F n} it is easy to derive σ = id_{n}.

3. Weak Wide Pullbacks

3.1 Assumption. Throughout this section 𝒜 denotes a locally λ-presentable category. Recall that this means that (i) 𝒜 is complete and (ii) (for some infinite cardinal λ) it has a set 𝒜_{λ} of objects that are λ-presentable (that is, the hom-functors preserve λ-filtered colimits) and whose closure under λ-filtered colimits is all of 𝒜. In fact, we could require less: all we need is that 𝒜 be cowellpowered, λ-accessible (that is, have λ-filtered colimits and satisfy (ii) above), have weak pullbacks an initial object, and (epi, strong mono) factorizations. All this holds in locally λ-presentable categories, see [AR].

Recall that a functor is called λ-accessible if it preserves λ-filtered colimits.

3.2 Definition. By a symmetrized representable functor is meant a quotient of a hom-functor 𝒜 (A, −) modulo a group 𝒢 of automorphisms of A; notation:

𝒜 (A, −)/𝒢 : 𝒜 [figure]Set .

Explicitly, to an object X this functor assigns the set

𝒜 (A, X)/∼_{𝒢}

where for f, f′: A [figure] X we put

f ∼_{𝒢} f′  iff  f = f′·σ for some σ ∈ 𝒢.

3.3 Theorem. An accessible functor F: 𝒜 [figure]Set weakly preserves wide pullbacks iff it is a coproduct of symmetrized representables.

Remark. More detailed, for a λ-accessible functor F: 𝒜 [figure]Set we prove equivalence of the following conditions:

(i) F weakly preserves wide pullbacks

and

(ii) F is a coproduct of functors 𝒜 (A, −)/𝒢 where A is λ-accessible.

Proof. (ii) ⇒ (i) is trivial and analogous to 2.6, let us prove (i) ⇒ (ii). Due to 2.4(i) we can assume that F 1 = 1, thus, F weakly preserves products. Let λ be a cardinal such that 𝒜 is a locally λ-presentable category and F is λ-accessible. Then all elements

x ∈ F A (A λ-presentable)

generate F in the sense that every element y ∈ F Y has, for some such x ∈ F A, the form y = F f(x) where f: A [figure] Y is a morphism. Since F weakly preserves products, there is a single element x_{0} ∈ F A generating F, and since F (weakly) preserves intersections we can assume that x_{0} lies in no image of F m where m: M [figure] A is a proper subobject. It follows that x_{0} is minimal, that is, (2.5) holds. (In fact given x_{0} ∈ F f[F X], factorize f = m·e where e is epic and m is strongly monic, then x_{0} lies in the image of F m which implies that m is an isomorphism, thus, f is an epimorphism.) This element x_{0} yields a surjective Yoneda transformation 𝒜 (A, −) [figure] F. Since F is λ-accessible, it is easy to see that the minimality implies that A is λ-presentable. We prove

F ≅ 𝒜 (A, −)/𝒢

for the group 𝒢 of all automorphisms σ: A [figure] A with F σ(x_{0}) = x_{0}. The proof is completely analogous to that in 2.6: (a) is clear. In (b) we need to verify that the morphism

e = ū·f: A_{1} [figure] A_{1}

is an isomorphism (by symmetry, so is v̄·g). From the minimality of x_{0} we know that e is an epimorphism, since F e(x_{0}) = x_{0}. We will now construct a chain

C: Ord^{op} [figure] 𝒜

with connecting morphisms C_{ij}: C(i) [figure] C(j) for i ≥ j such that

C(i) = A and C_{i+1,i} = e for all i ∈ Ord.

Since 𝒜 is cowellpowered, the object A has less than α quotients for some cardinal α, therefore the quotients

C_{α,i}: A [figure] A (i < α)

are not pairwise distinct. Consequently, there exists i < α such that C_{α,i+1} and C_{α,i} represent the same quotient, and then from C_{i+1,i} = e it follows that e is an isomorphism.

The chain C is defined by transfinite induction in such a way that for all i ≥ j we have that x_{0} is a fixed point of F C_{i,j}. Put C(0) = A. Given C(i) put C(i + 1) = A and let C_{i+1,j} = C_{i,j}·e for all j ≤ i. If i is a limit ordinal, form a limit l_{j}: L [figure] A (j < i) of the i-chain already defined. This is a wide pullback of all C_{j,0} with j < i, and since F weakly preserves this wide pullback, we know from F C_{j,0}(x_{0}) = x_{0} that there exists b ∈ F L with F l_{j}(b) = x_{0} for all j < i. There exists f: A [figure] L with b = F f(x_{0}). Put

C_{i,j} = l_{j}·f for all j < i

then x_{0} is a fixed point of C_{i,j} as requested.

3.4 Corollary. Let 𝒜 and ℬ be locally presentable categories. An accessible functor F: 𝒜 [figure] ℬ weakly preserves wide pullbacks iff every functor ℬ(B, F −) for B ∈ obj ℬ is a coproduct of symmetrized representables.

In fact, the functors ℬ(B, −) are accessible and collectively create wide weak pullbacks.

3.5 Example. An accessible functor F: Set^{I} [figure]Set^{I} weakly preserves wide pullbacks iff it is an I-tuple of coproducts symmetrized representables.

3.6 Remark. (i) Mark Weber introduced in [W] the concept of generic factorizations for a given functor. From his results it easily follows that only functors weakly preserving wide pullbacks can admit generic factorizations. Our Corollary 3.4 shows the converse implication for accessible functors between locally presentable categories.

(ii) The definition of analytic functor in 2.1 has an obvious infinitary variant: given a cardinal λ let ℬ_{λ} be the category of all cardinals smaller than λ and all isomorphisms. We can investigate all set functors that are left Kan extensions of functors from ℬ_{λ} to Set. Each of them is clearly λ-accessible, i.e., preserves λ-filtered colimits. Theorem 3.3 gives a full characterization of these functors: they are the λ-accessible functors weakly preserving wide pullbacks. Or, equivalently, coproducts of symmetrized representables Set(A, −)/𝒢 with card A < λ.

(iii) More generally, if 𝒜 is a locally λ-presentable category then the following conditions are equivalent for accessible functors F: 𝒜 [figure]Set:

(a) F weakly preserves wide pullbacks

and

(b) F is the left Kan extension of a functor from the category of λ-presentable objects and isomorphisms into Set.

3.7 Remark. André Joyal considered in [J_{1}] also analytic endofunctors of the category

Vec_{𝕂}

of vector spaces over a given field. Here we prove that, in contrast to Set, almost none of them weakly preserves wide pullbacks:

3.8 Proposition. Let 𝒜 be a complete abelian category. An endofunctor F weakly preserves wide pullbacks iff it has the form F (−) = F_{0}(−) + B where F_{0} preserves limits.

Proof. The condition is clearly sufficient. To prove that it is necessary, consider an endofunctor F preserving weak wide pullbacks and with F 0 = 0. Then F preserves limits. In fact, F preserves weak products and intersections. We will prove that F preserves every product π_{i}: X [figure] X_{i} (i ∈ I) strongly, that is, (F π_{i}) is collectively monic. In fact, F preserves kernels because a kernel m of a morphism f is characterized by the weak pullback

[figure: m; 0; f]

which F preserves. Since (π_{i}) is collectively monic, we have ⋂_{i∈I} ker π_{i} = 0, therefore, ⋂_{i∈I} ker F π_{i} = F (⋂_{i∈I} ker π_{i}) = 0, thus, F preserves products. Consequently, it preserves limits.

To conclude the proof, let F 0 be arbitrary, put

B = F 0.

The zero morphisms e_{X}: X [figure] 0 define short exact sequences

F_{0}X [figure: m_{X}] F X [figure: F e_{X}] B

and since F e_{X} is a split epimorphism, we conclude

F X = F_{0}X + B.

Thus m: F_{0} [figure] F is a subfunctor such that F_{0} weakly preserve wide pullbacks. In fact, this follows from F having this property and F (−) = F_{0}(−) × B: given a wide pullback p_{i}: P [figure] A_{i} of a_{i}: A_{i} [figure] A (i ∈ I) and given elements x_{i} ∈ F_{0}A_{i} with F_{0}a_{i}(x_{i}) = x for all i ∈ I, then for (x_{i}, 0) ∈ F A_{i} we have F a_{i}(x_{i}, 0) = (x, 0). Consequently, there exists (y, b) ∈ F P = F_{0}P × B with F_{0}a_{i}(y) = x_{i} for all i ∈ I. Since F_{0}0 = 0, we conclude from the above that F_{0} preserves limits.

3.9 Corollary. The only endofunctors of Vec_{𝕂} weakly preserving wide pullbacks are the coproducts

Vec_{𝕂}(A, −) + B

of enriched representables and constant functors.

In fact, a limit preserving endofunctor F_{0} has a left adjoint G (use Special Adjoint Functor Theorem). For A = GK we have G ≅ A ⊗ − (since G preserves copowers of K), thus, F_{0} ≅ Vec_{𝕂}(A, −).

4. Generalized Analytic Functors

Throughout this section (ℰ , ⊗, I) denotes a symmetric monoidal category with colimits. We assume that ⊗ commutes with coproducts.

The symmetry isomorphisms s_{X,Y} : X ⊗ Y [figure] Y ⊗ X allow us to define, for every permutation σ in 𝒮_{n}, the corresponding automorphism X^{⊗σ} of X^{⊗n} = X ⊗ (X ⊗ ⋯ ⊗ X)) …). For example, if σ just swaps i and i + 1 then X^{⊗σ} = X^{⊗(i−1)} ⊗s_{X,X} ⊗X^{⊗(n−i−1)}. This extends to all permutations by the rule

X^{⊗ id} = id_{X^{⊗n}} and X^{⊗σ·τ} = X^{⊗τ}·X^{⊗σ}

since every permutation is a composite of transpositions i [figure] i + 1.

In fact, we obtain a functor

K: ℬ^{op} × ℰ [figure] ℰ

given on objects by

(n, X) [figure] X^{⊗n}

and on morphisms by

(σ, f) [figure] X^{⊗n} [figure: X^{⊗σ}] X^{⊗n} [figure: f^{⊗n}] Y^{⊗n}.

The following definition is an obvious extension of the cases ℰ = Set and ℰ = Vec_{𝕂} considered by André Joyal in [J_{2}]:

4.1 Definition. By a ℰ -species is meant a functor

f: ℬ [figure] ℰ .

The corresponding analytic functor F: ℰ [figure] ℰ is the functor defined by the ordinary coend

F X = ∫ ^{n:ℬ} X^{⊗n} ⊗ f(n).  (4.1)

4.2 Remark. The coend formula (4.1) indeed defines a functor F: ℰ [figure] ℰ since K(n, X) = X^{⊗n} is functorial in X. Thus, for h: X [figure] Y, F h: F X [figure] F Y is defined by

F h = ∫ ^{n:ℬ} h^{⊗n} ⊗ f(n).

4.3 Remarks. (i) The (objectwise) coproduct ∑_{i∈I} f_{i} of ℰ -species yields a coproduct of the corresponding analytic functors. This follows from ⊗ commuting with coproducts.

(ii) Suppose f is a species such that for some n ∈ ℬ we have

f(n) = V and f(k) = 0 for all n ≠ k

(where 0 is the initial object). Then F X is defined by the joint coequalizer

[figure: X^{⊗n} ⊗ V; F X; k; X^{⊗n} ⊗ V; σ̄; (σ ∈ 𝒮_{n})]  (4.2)

of the morphisms

σ̄ = X^{⊗σ} ⊗ f(σ^{−1}): X^{⊗n} ⊗ V [figure] X^{⊗n} ⊗ V.  (4.3)

This follows from the usual formula for coends together with the obvious “shortening” of zig-zags

[figure: X^{⊗n} ⊗ V; X^{⊗n} ⊗ V; X^{⊗σ}⊗f(σ^{−1}); X^{⊗n} ⊗ V; X^{⊗n} ⊗ V; id ⊗f(σ); X^{⊗n} ⊗ V; X^{⊗n} ⊗ V; X^{⊗σ}⊗id]

(iii) Every species is a coproduct of species of type (ii) above. Thus, every analytic functor is a coproduct of functors given on objects X by the coequalizer (4.2).

4.4 Example. (i) For every n ∈ ℕ the n-th tensor power functor

F X = X^{⊗n}

is analytic. Its species is defined by

f(n) = 𝒮_{n} • I and f(k) = 0 for k ≠ n

on objects and by f(σ)·i_{τ} = i_{σ·τ} on morphisms σ ∈ 𝒮_{n}, where i_{τ}: I [figure] 𝒮_{n} • I are the injections. In fact, the coequalizer (4.2) is easily seen to be the morphism k: 𝒮_{n} • X^{⊗n} [figure] X^{⊗} defined by k·i_{τ} = X^{⊗τ} for all τ ∈ 𝒮_{n}.

(ii) The functor

F X = ∑_{n∈ℕ}X^{⊗n}

is analytic. This is, in case ℰ = Set, the free-monoid functor and in case ℰ = Vec_{𝕂} (with the tensor product) the functor of tensor algebra on X.

(iii) The analytic endofunctors of the category

𝒜 = Set^{S}

of S-sorted sets are precisely the functors

F (X_{s})_{s∈S} = (F_{s}X_{s})_{s∈S}

given by an S-tuple of analytic functors F_{s}: Set [figure]Set. This follows easily from the fact that a species f: ℬ [figure]Set^{S} is just an S-tuple of species in the sense of Section 2.

Every analytic functor is finitary and weakly preserves wide pullbacks—but not conversely. For example the functor F: Set × Set [figure]Set × Set defined by

F (X, Y) = (X × Y, 1)

preserves limits but is not analytic.

(iv) Let ℰ be a symmetric monoidal closed category. The endomorphism operad of an object Z, see [MSS], is the analytic functor whose species is

f(n) = [Z^{⊗n}, Z] for all n ∈ ℬ.

(v) For every group 𝒢 ⊆ 𝒮_{n} we define the functor

F X = X^{⊗n}/𝒢

called symmetrized tensor power on objects by the joint coequalizer of all X^{⊗σ}, σ ∈ 𝒢:

[figure: X^{⊗n}; X^{⊗n}/𝒢; X^{⊗n}; X^{⊗σ}; (σ ∈ 𝒢)]

This functor is analytic as proved below.

Consequently, coproducts of symmetrized tensor powers are analytic. For example in Vec_{𝕂} the functor of symmetric algebra on X

F X = ∑_{n∈ℕ}X^{⊗n}/𝒮_{n}

is analytic.

4.5 Remark. (1) The reason why we do not work with ℰ -functors is that important examples of analytic functors are not ℰ -functors. For ℰ = Vec_{𝕂} this means linearity on hom-sets, and it is easy to see that neither the tensor-algebra functor nor the symmetricalgebra functor are linear on hom-sets.

(2) In case of Set the elegant definition of analytic functors was: they are the Kan extensions of species. This, however, does not work in general. For Vec_{𝕂} the Kan extension would be given by ∫^{n:ℬ} X^{n} × f(n).

4.6 Observation. Every species in Set, f: ℬ [figure]Set yields a ℰ -species

f_{ℰ} : ℬ [figure] ℰ

by putting

f_{ℰ} (n) = f(n) • I

and analogously on morphisms. For the corresponding analytic functor F: Set [figure]Set we denote by F_{ℰ} : ℰ [figure] ℰ the analytic endofunctor of ℰ.

In the following examples we consider the monoidal category Vec_{𝕂} of vector spaces on a field 𝕂.

(i) The free monoid functor P, see 2.3(ii), yields the above tensor algebra functor

P_{Vec_{𝕂}}X = ∑_{n∈ℕ}X^{⊗n}.

(ii) The finite multiset functor E of 2.3(iv) yields

E_{Vec_{𝕂}}X = ∑ X^{⊗n}/𝒮_{n} (symmetric algebra on X).

(iii) The tree species, 2.3(v), yields the functor

T_{Vec_{𝕂}}X = free pre-Lie algebra on X,

see [BL]. Also the free Lie algebras define an analytic functor, see [J_{2}].

4.7 Proposition. The analytic functors F_{ℰ} obtained from analytic set functors F are precisely the coproducts of symmetrized tensor powers.

Proof. (1) Consider the species f defining the analytic set functor F X = X^{n}/𝒢 in 2.3(iii). The corresponding analytic endofunctor F_{ℰ} of ℰ is given by the coequalizer (4.2):

[figure: (𝒮_{n}/∼_{𝒢}) • X^{⊗n}; F_{ℰ} X; c; (𝒮_{n}/∼_{𝒢}) • X^{⊗n}; σ̄]

We will verify that F_{ℰ} is the symmetrized power X^{⊗n}/𝒢. For every [τ] ∈ 𝒮_{n}/∼_{𝒢} let i_{[τ]} be the coproduct injection of (𝒮_{n}/∼_{𝒢}) • X^{⊗n}, then σ̄ is defined by

σ̄·i_{[τ]} = i_{[σ^{−1}·τ]}·X^{⊗σ}.

The property c·σ̄ = c thus yields

c·i_{[τ]} = c·i_{[σ^{−1}·τ]}·X^{⊗σ}

for all σ, τ ∈ 𝒮_{n}. By putting σ = τ we get

c·i_{[σ]} = c·i_{[id]}·X^{⊗σ}.

For all σ ∈ 𝒢 we thus see that, since [σ] = [id], the morphism c_{0} = c·i_{[id]} : X^{⊗n} [figure] F_{ℰ} X coequalizes X^{⊗σ}, σ ∈ 𝒢. To prove that c_{0} is the joint coequalizer (and therefore F_{ℰ} X = X^{⊗n}/𝒢), let f: X^{⊗n} [figure] Y also coequalize X^{⊗σ}, σ ∈ 𝒢. Define g: (𝒮_{n}/∼_{𝒢}) • X^{⊗n} [figure] Y by

g·i_{[τ]} = f·X^{⊗τ}.

Then for all σ ∈ 𝒮_{n} we have

g·σ̄·i_{[τ]} = g·i_{[σ^{−1}·τ]}·X^{⊗σ}
= f·X^{⊗σ^{−1}·τ}·X^{⊗σ}
= f·X^{⊗τ}
= g·i_{[τ]}.

Thus g coequalizes all σ̄, σ ∈ 𝒮_{n}, and then it uniquely factorizes through c. Consequently, f = g·i_{[id]} uniquely factorizes through c_{0} = c·i_{[id]}.

(2) Every analytic functor F: Set [figure]Set yields as F_{ℰ} a coproduct of symmetrized tensor powers. This follows from (1) and 2.7: F is a coproduct of symmetrized representables and the corresponding species is a coproduct of the species in (1).

(3) Every coproduct of symmetrized tensor powers is of the form F_{ℰ} for the corresponding coproduct F of symmetrized representables—again, this follows from (1).

4.8 Example. There are important examples of analytic functors on Vec_{𝕂} that are not obtained from set functors:

(i) The functor

F X = X ⊗ X/(x ⊗ x = 0)

of the tensor square modulo the subspaces spanned by all the vectors x ⊗ x. This is given by the species

f(2) = 𝕂 × 𝕂 and f(k) = 0 for k ≠ 2

which assigns to the transposition σ: 2 [figure] 2 the linear map

f(σ): (u_{0}, u_{1}) [figure] (u_{0}, −u_{1}).

In fact, the coequalizer (4.2) yields the equivalence ∼ on X ⊗ X ⊗ (𝕂 ⊗ 𝕂) given by

x ⊗ y ⊗ (u_{0}, u_{1}) ∼ y ⊗ x ⊗ (u_{0}, −u_{1}) = −y ⊗ x ⊗ (u_{0}, u_{1})

and the representatives of the form x ⊗ y ⊗ (0, 1) present the quotient space as precisely F X above.

(ii) For every n ∈ ℕ let A_{n} be the subspace of the tensor power X^{⊗n} spanned by all vectors x_{1} ⊗ ⋯ ⊗ x_{n} with x_{i} = x_{j} for some i ≠ j. Then the functor

F X = ∑_{n∈ℕ}X^{⊗n}/A_{n} (external algebra of X)

is analytic. The corresponding species is defined on objects by

f(n) = 𝕂^{n}

and on morphisms so that it assigns to the transposition σ_{i}: 0 [figure] i (for i = 1, …, n − 1) the linear map

(u_{0}, u_{1}, …, u_{n−1}) [figure] (u_{0}, u_{1}, …, u_{i−1}, −u_{i}, u_{i+1}, …, u_{n−1}).

4.9 Corollary. Analytic endofunctors of presheaf categories ℰ = [𝒞^{op}, Set] are precisely the finitary endofunctors weakly preserving wide pullbacks.

We also know that these are precisely the functors F: ℰ [figure]ℰ that are objectwise coproducts of symmetrized representables, that is, for each C ∈ 𝒞 the composite ev_{C}·F: [𝒞^{op}, Set] [figure]Set has the form

ev_{C}·F = ∑_{i∈I} ℰ (A_{i}, −)/𝒢_{i} with A_{i} finitely presentable.

See Corollary 3.4.

4.10 Example. Analytic endofunctors of Gra are precisely those carried by the analytic endofunctor of Set × Set, see 4.4(iv).

5. Conclusions and Open Problems

André Joyal [J_{2}] introduced analytic endofunctors of Set and characterized them as precisely the finitary endofunctors weakly preserving wide pullbacks. We have presented a short proof of that result. Ryu Hasegawa observed in [H] that the category of species, [ℬ, Set], is equivalent to the category of analytic functors and weakly cartesian transformations (that is, those for which all naturality squares are weak pullbacks).

In the present paper we study analytic endofunctors in a symmetric monoidal category ℰ. This is a special case of the concept introduced recently by Brian Day [D] who studies Fourier transforms depending on a choice of a kernel; we concentrated on the kernel X^{⊗n}. The case of ℰ = Vec_{𝕂}, the monoidal category of vector spaces, has also been studied by Joyal [J_{2}] who presented a number of examples of important analytic functors; none of them weakly preserves wide pullbacks, as we proved in Proposition 3.8. An open problem is a characterization of the morphisms between analytic functors (corresponding to the transformations between species). An abstract condition has been formulated in [D], however, in the important case of vector spaces a more concrete characterization is desirable.

We also study weak preservation of wide pullbacks by functors F: 𝒜 [figure]Set. In case 𝒜 is locally presentable and F is accessible, we have proved that precisely the coproducts of symmetrized representables weakly preserve wide pullbacks. In contrast, weak preservation of connected limits is equivalent to familial representability: see [CJ] and [FS].

Here accessibility cannot be omitted: the power-set functor weakly preserves wide pullbacks but it is not accessible. A characterization of general set functors preserving weak wide pullbacks is an open problem.

References

[AAGB] M. Abbot, T. Altenkirch, N. Ghani and C. Mc Bride, Constructing polymorphic programs with quotient types, Proceedings MCP 2004.

[AGT] J. Adámek, P. Gumm and V. Trnková, Presentation of set functors: a coalgebraic perspective, to appear in J. Logic Comput.

[AR] J. Adámek and J. Rosický, Locally presentable and accessible categories, Cambridge University Press 1994.

[AT] J. Adámek and V. Trnková, Automata and Algebras in Categories, Kluwer Academic Publ., Boston, 1990.

[BL] N. Bergeron and M. Livernet, A combinatorial basis for the free Lie algebra of the labelled rooted trees, arXiv: math/0707.4466v1 [math. RA], 30Jul 2007.

[CJ] A. Carboni and P. Johnstone, Connected limits, familial representability and Artin gluing, Mathemat. Struct. Comput. Sci. 5 (1995), 441–459.

[D] B. J. Day, Monoidal functor categories and graphic Fourier transforms, arXiv: math/0612496v1 [math. QA], 18Dec 2006.

[F] M. Fiore, Exact characterization of generalized analytic functors, a preprint.

[FGHW] M. Fiore, N. Gambino, M. Hyland and G. Winskel, The cartesian closed category of generalized species of structures, London Math. Soc. 2007, 1–18.

[FS] P. Freyd and A. Scedrov, Categories, Allegories, North-Holland 1990.

[G] P. Gumm, Elements of the general theory of coalgebras, LUTACS 1999 Lecture Notes, Rand Africaans University, Johannesburg.

[H] R. Hasegawa, Two applications of analytic functors, Theoret. Comput. Sci. 272 (2002), 113–175.

[J_{1}] A. Joyal, Une théorie combinatoire des séries formelles, Advances in Math. 42 (1981), 1–82.

[J_{2}] A. Joyal, Foncteurs analytiques et espèces de structures, Lecture Notes Math. 1234, Springer 1986, 126–159.

[MSS] M. Markl, S. Shnider and J. Stasheff, Operads in Algebra, Topology and Physics, Math. Surveys and Monographs, Vol. 96, American Math. Society, 2002.

[Ta] P. Taylor, An algebraic approach to stable domains, J. Pure Appl. Algebra 64 (1990), 171–203.

[T] V. Trnková, Some properties of set functors, Comment. Math. Univ. Carolinæ 10 (1969), 323–352.

[W] M. Weber, Generic morphisms, parametric representations and weakly cartesian monads, Theory Appl. Categ. 13:14(2004), 191–234.

Jiří Adámek University of Technology of Braunschweig Germany

Jiří Velebil Technical University in Prague Czech Republic

Email: Adamek@iti.cs-tu.bs.de
      Velebil@math.feld.cvut.cz

This article may be accessed at http://www.tac.mta.ca/tac/ or by anonymous ftp at

ftp://ftp.tac.mta.ca/pub/tac/html/volumes/21/11/21-11.{dvi,ps,pdf}

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. Full text of the journal is freely available in .dvi, Postscript and PDF from the journal’s server at http://www.tac.mta.ca/tac/ and by ftp. It is archived electronically and in printed paper format.

Subscription information. Individual subscribers receive abstracts of articles by e-mail as they are published. 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}TEX2e strongly encouraged. Articles should be submitted by e-mail directly to a Transmitting Editor. Please obtain detailed information on submission format and style files at http://www.tac.mta.ca/tac/.

Managing editor. Robert Rosebrugh, Mount Allison University: rrosebrugh@mta.ca

TEXnical editor. Michael Barr, McGill University: barr@math.mcgill.ca

Assistant TEX editor. Gavin Seal, McGill University: gavin seal@fastmail.fm

Transmitting editors.

Richard Blute, Université d’ Ottawa: rblute@uottawa.ca Lawrence Breen, Université de Paris 13: breen@math.univ-paris13.fr Ronald Brown, University of North Wales: ronnie.profbrown (at) btinternet.com Aurelio Carboni, Università dell Insubria: aurelio.carboni@uninsubria.it Valeria de Paiva, Cuill Inc.: valeria@cuill.com Ezra Getzler, Northwestern University: getzler(at)northwestern(dot)edu Martin Hyland, University of Cambridge: M.Hyland@dpmms.cam.ac.uk P. T. Johnstone, University of Cambridge: ptj@dpmms.cam.ac.uk 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@acsu.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 Jiri Rosicky, Masaryk University: rosicky@math.muni.cz Brooke Shipley, University of Illinois at Chicago: bshipley@math.uic.edu 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