Theory and Applications of Categories, Vol. 15, No. 2, 2005, pp. 40–65.

REFLECTIVE KLEISLI SUBCATEGORIES OF THE CATEGORY OF EILENBERG-MOORE ALGEBRAS FOR FACTORIZATION MONADS

MARCELO FIORE AND MATÍAS MENNI

Abstract. It is well known that for any monad, the associated Kleisli category is embedded in the category of Eilenberg-Moore algebras as the free ones. We discovered some interesting examples in which this embedding is reflective; that is, it has a left adjoint. To understand this phenomenon we introduce and study a class of monads arising from factorization systems, and thereby termed factorization monads. For them we show that under some simple conditions on the factorization system the free algebras are a full reflective subcategory of the algebras. We provide various examples of this situation of a combinatorial nature.

Contents

1 Motivation, overview, and examples 40

Motivating example 41 Overview 41 Examples 44 Organization of the paper 48

2 Characterization of free factorization-monad algebras 48

Generic elements 49 Free factorization-monad algebras 52

3 First main result 56

Minimal elements 56 The presheaf of chains 59

4 Second main result 61

1. Motivation, overview, and examples

We give an overview of our results discussing them in the context of the motivating example and some new ones.

Marcelo Fiore’s research was supported by an EPSRC Advanced Research Fellowship. Matías Menni is funded by Conicet and Lifia.

Received by the editors 2004-12=07 and, in revised form, 2005-03-02. Published on 2005-04-18 in the volume of articles from CT2004. 2000 Mathematics Subject Classification: 18A25, 18A40, 18C20, 05A10. Key words and phrases: factorization systems, monads, Kleisli categories, Schanuel topos, Joyal

species, combinatorial structures, power series.

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

Motivating example. Let B be the category of finite sets and bijections. One of the fundamental ideas of Joyal in [10, 11] is that Set^{B}, the category of species of structures, is a category of combinatorial power series in which the algebra of formal power series acquires structural combinatorial meaning leading to bijective proofs of combinatorial identities. For example, in this view, a covariant presheaf P on B can be seen as corresponding to the exponential power series ∑_{n∈ℕ} |P [n]| \frac{x^{n}}{n!} and the coproduct and tensor product of species respectively correspond to the addition and multiplication of power series. The impact of this theory and its extensions on combinatorics can be appreciated from the book [2].

A closely related category is the Schanuel topos Sch (see, e.g., [15, 9]). It has at least four well-known characterizations. It is: (1) the category of continuous actions for the topological group of bijections on ℕ, with the product topology inherited from ∏_{ℕ} ℕ;

(2) the classifying topos for the theory of an infinite decidable object; (3) the category of pullback-preserving covariant presheaves on the category of finite sets and injections I;

(4) the topos of sheaves for the atomic topology on I^{op}.

In [5, 18], we observed that the Schanuel topos can be further described as the Kleisli category associated to the monad on the topos Set^{B} of species induced by the inclusion B [figure] I. This is surprising, for Kleisli categories do not inherit, in general, much of the structure of their base categories. Moreover, this presentation provides a nice conceptual picture of the Schanuel topos as a category of combinatorial power series (see [5] and Example 1.14 below).

In investigating why this particular Kleisli category is a topos we noted that the associated sheaf functor Set^{I} [figure]Sch is a reflection for the embedding of the Kleisli category into the category of Eilenberg-Moore algebras. Following [5], we subsequently realized that its existence follows as an example of general abstract considerations in the context of an essentially small category (in this case I^{op}) equipped with a factorization system (in this case the all-iso factorization system) satisfying some simple conditions. This development is the subject of the paper.

Overview. Recall that every functor ϕ : C [figure] D induces the well-known adjoint situation ϕ_{!} ⊣ ϕ^{∗} : D̂ [figure] Ĉ. We will consider presheaf categories as categories of algebras in the light of the following observation.

1.1. Proposition. Let ϕ : C [figure] D be a functor between essentially small categories. The adjunction ϕ_{!} ⊣ ϕ^{∗} : D̂ [figure] Ĉ is monadic if and only if every object of D is a retract of one in the image of ϕ.

Proof. As D̂ has reflexive coequalizers and ϕ^{∗} preserves them, the adjunction is monadic if and only if ϕ^{∗} is conservative. In turn, this is equivalent to the condition stated, see [9, Example A4.2.7(b)].

This result will be applied to a functor induced by a factorization system [7], the definition of which we recall.

1.2. Definition. A factorization system on a category C is given by a pair (E, M) of classes of morphisms of C such that: (1) every isomorphism belongs both to E and M,

(2) both E and M are closed under composition, (3) every e in E is orthogonal to every m in M, and (4) every f in C can be factored as f = m e, with e in E and m in M.

Let (E, M) be a factorization system on C. In this context we will also write E and M for the subcategories of C respectively determined by the E-maps and M-maps. Further, we write I for their intersection; i.e., the groupoid underlying C. With this notation, the uniqueness of factorizations up to isomorphism can be expressed as an isomorphism as follows.

1.3. Lemma. The canonical family of maps

{ ∫^{I∈I} E(E, I) × M(I, M) [figure] C(E, M) }_{E∈E,M∈M}

induced by composition is a natural isomorphism.

1.4. Definition. We define the factorization monad associated to an (E, M) factorization system on an essentially small category C as the monad on M̂ induced by the adjunction ι_{!} ⊣ ι^{∗} : Ĉ [figure] M̂ where ι is the inclusion functor M [figure] C.

Note that, by Proposition 1.1, the category Alg_{M} of algebras for the factorization monad on M̂ is (equivalent to) the presheaf category Ĉ. We denote the Kleisli category for a factorization monad associated to (E, M) as Kl_{M}.

Factorization monads have a simple description. Indeed, the left adjoint ι_{!} : M̂ [figure] Ĉ, henceforth denoted ( )_{!}, is given by left Kan extending presheaves M^{op} [figure]Set along M^{op} [figure] C^{op}. It is however more revealing to calculate the following explicit description of it. For P a presheaf on M, we have the following bijective correspondence of sets

P_{!}X ≅ ∫^{M∈M} P M × C(X, M)
≅ ∫^{M∈M} P M × ( ∫^{I∈I} E(X, I) × M(I, M)) , by Lemma 1.3
≅ ∫^{I∈I} ( ∫^{M∈M} P M × M(I, M)) × E(X, I)
≅ ∫^{I∈I} P I × E(X, I)

which yields a natural isomorphism with respect to the action on { ∫^{I∈I} P I ×E(X, I) }_{X∈ C} given by

\xymatrix{C(Y, X) × ∫^{I∈I} P I × E(X, I) \ar[r] & ∫^{J∈I} P J × E(Y, J)}

( f , [I, p, ε] ) [figure] [J, p ·_{P} m, e]

where Y [figure: e] J [figure: m] I is an (E, M)-factorization of εf

Thus, it is justified to think of free factorization-monad algebras as combinatorial power series with basis given by the structure of the E-maps in C and with coefficients (which, by Corollary 2.14(2), are unique up to isomorphism) given by the restriction of presheaves on M to I. We found this intuition motivating and useful at work. In fact, the methods of Section 2 are generalized from [11].

A key observation is that in some cases Kl_{M} is equivalent to the subcategory of presheaves that preserve certain kind of limits. In this case, it happens that the embedding Kl_{M} [figure] Alg_{M} ≃ Ĉ is reflective. Most of our work is devoted to recognize these situations.

Let qEx(Ĉ) be the full subcategory of Ĉ determined by those presheaves that (are quasi E-exact in the sense that they) map pushouts along E-maps in C to quasi pullbacks in Set. We have the following factorizations (which are proved at the end of Section 2).

1.5. Proposition. The Yoneda embedding C [figure] Ĉ factors through [figure: Kl; M; Ĉ] which in turn factors through qEx(Ĉ) [figure] Ĉ.

One of our main results will characterize when the embedding Kl_{M} [figure] qEx(Ĉ) is actually an equivalence relying on the following finiteness condition.

1.6. Definition. A category equipped with a factorization system (E, M) is said to be E-well-founded if in it every chain

X_{0} [figure: e_{0}] X_{1}  [figure] ⋯ [figure] X_{n} [figure: e_{n}] ⋯  (n ∈ ℕ)

of E-maps is eventually constant (in the sense that there is an n_{0} ∈ ℕ such that e_{n} is an iso for all n ≥ n_{0}).

We state our first main result (which is proved in Section 3).

1.7. Theorem. If C has pushouts along maps in E then C is E-well-founded if and only if every section is in M and the embedding Kl_{M} [figure] qEx(Ĉ) is an equivalence.

Let us see how this theorem allows us to obtain examples of Kleisli categories equivalent to full reflective subcategories of presheaf categories. Let Ex(Ĉ) be the full subcategory of Ĉ determined by those presheaves that (are E-exact in the sense that they) map pushouts along E-maps in C to pullbacks in Set, and let Pp(Ĉ) be the full subcategory of Ĉ of pullback-preserving presheaves. The following lemma states two conditions ensuring that qEx(Ĉ) is a category of functors that preserve some kind of limits.

1.8. Lemma. Every presheaf in qEx(Ĉ) maps epis in E to injections. It follows that qEx(Ĉ) = Ex(Ĉ) if every map in E is epi and that Ex(Ĉ) = Pp(Ĉ) if E is given by the epis and M by the isos.

Thus, known results about presheaves preserving certain kind of limits allow us to conclude the following.

1.9. Corollary.

1. If every map in E is epi, and C has pushouts along E-maps and it is E-well-founded, then the embedding Kl_{M} [figure] Ĉ of free factorization-monad algebras in algebras is reflective.

2. Further, if C has binary products and, for all X ∈ C, the endofunctor ×X on C preserves E-maps and pushouts along E-maps, then the reflective embedding [figure: Kl; M; Ĉ] is an exponential ideal and hence the reflection Ĉ [figure] Kl_{M} preserves finite products.

Proof. For the first part note that Theorem 1.7 and Lemma 1.8 imply that Kl_{M} is equivalent to Ex(Ĉ), which is a full reflective subcategory of Ĉ by results in [12]. The second part follows from results in [4, Subsection 11.2, § Orthogonality and cartesian closure].

Our second main result (which is proved in Section 4) replaces the well-founded hypothesis with a wide-completeness one.

1.10. Theorem. If every map in E is epi, and C has pushouts along E-maps and wide pushouts of E-maps, then the embedding Kl_{M} [figure] Ĉ of free factorization-monad algebras in algebras is reflective.

Proof. Corollary 2.17 and Proposition 4.3 imply that Kl_{M} is equivalent to the full subcategory of Ĉ of those presheaves that preserve pullbacks along E-maps and wide pullbacks of E-maps; this is reflective by results in [12].

Examples. Examples to which Theorem 1.10 applies follow.

1.11. Example. The all-iso factorization on a category of epis with wide pushouts. Like the opposite of the category of countable sets and injections, and posets with bounded sups.

Let us now consider examples to which Corollary 1.9(1) applies. First, there are posetal ones.

1.12. Example. Any co-well-founded poset with bounded binary sups with the all-iso factorization.

To ease the presentation of the rest of the examples we note the result below, which further exploits the coend description of factorization monads.

1.13. Lemma. We have that

P_{!}X ≅ ∐_{[I]≅ ∈ C_{/≅}} P I ⊗_{I} E^{op}(I, X)

where the sum ranges over the isomorphism classes of C and where ⊗_{I} is the tensor product of the obvious actions

P I × I(I, I) [figure] P I

and

I(I, I) × E^{op}(I, X) [figure] E^{op}(I, X)  (1)

over the automorphism group of I. Further, if the hom-actions (1) are free, then

P_{!}X ≅ ∐_{[I]≅ ∈ C_{/≅}} P I × E^{op}(I, X)_{/I(I,I)}  (2)

Note that if every map in E is epi then the hom-actions are free.

Let F be the category of finite sets and functions and I, S, and B the subcategories of F determined by injections, surjections, and bijections respectively.

1.14. Example. Consider I^{op} equipped with the all-iso factorization system. The hom-actions are free and I(I, X)_{/B(I,I)} can be described as the set Sub_{|I|}(X) of subsets of X of the same cardinality as I. Thus, the free algebras for the factorization monad are combinatorial power series I [figure] Set of the form

P_{!}X = ∐_{i∈ℕ} P [i] × Sub_{i}(X)

where P is a species B [figure]Set. These are the combinatorial presheaves of [5, Definition 1.1], and correspond to formal power series of the form

∑_{i∈ℕ} p_{i} \binom{x}{i}

which, as recently pointed out to us by Steve Schanuel, for p_{i} ∈ ℕ are Myhill’s combinatorial functions [20] (see also [3]).

In this case the factorization monad is given by ( )·exp where · denotes the multiplication (tensor product) of species and where exp is the exponential (terminal) species (see [2]). Further, Kl_{B} is equivalent to the Schanuel topos.

1.15. Example. Let Ford be the category of finite linear orders and strictly orderpreserving maps, and consider Ford^{op} with the all-iso factorization system. The automorphism groups Ford(I, I) are trivial and the homs Ford(I, X) are isomorphic to Sub_{|I|}(X). Thus, the free algebras for the factorization monad are combinatorial power series Ford [figure] Set of the form

P_{!}X = ∐_{i∈ℕ} P (i) × Sub_{i}(X)

where P is a linear species ℕ [figure] Set (see [10, Section 4]). They are similar to the ones in the previous example but with simpler coefficients.

The Kleisli category in this example is the topos of sheaves for the atomic topology on Ford^{op} studied by Johnstone in [8] which, as it is explained there, has many analogies with the Schanuel topos.

We now introduce an analog of the above two examples in the context of linear algebra.

1.16. Example. Let I_{q} be the category of finite dimensional vector spaces over a finite field 𝔽_{q} of order q and linear monomorphisms, and let B_{q} be its underlying groupoid. Consider I_{q}^{op} with the all-iso factorization. The hom-actions are free and I_{q}(I, X)_{/B_{q}(I,I)} can be described as the set Sub_{dim(I)}(X) of subspaces of X of the same dimension as I. Thus, the free algebras for the factorization monad are combinatorial power series I_{q} [figure] Set of the form

P_{!}X = ∐_{i∈ℕ} P (𝔽_{q}^{i}) × Sub_{i}(X)

where P : B_{q} [figure] Set. These correspond to formal q-power series of the form

∑_{i∈ℕ} p_{i} [ \begin{matrix}x \\ i \end{matrix} ]_{q}

where the q-binomial coefficient [ \begin{matrix}x \\ i \end{matrix} ]_{q} is given by

\frac{[x]_{q} [x − 1]_{q} … [x − i + 1]_{q}}{[i]_{q}!}

with [z]_{q} = \frac{q^{z}−1}{q−1} and [n]_{q}! = [n]_{q} [n − 1]_{q} … [1]_{q}.

We now provide two examples in which M is not a groupoid.

1.17. Example. Consider F^{op} equipped with the epi-mono factorization (I^{op}, S^{op}). The hom-actions are free and I(I, X)_{/B(I,I)} can be described as Sub_{|I|}(X). Thus, the free algebras for the factorization monad are combinatorial power series F [figure] Set of the form

P_{!}X = ∐_{i∈ℕ} P [i] × Sub_{i}(X)

where P : S [figure] Set. These are similar to those of Example 1.14 but with more sophisticated coefficients.

1.18. Example. Consider the category F equipped with the surjection-injection factorization. The hom-actions are free and S(X, I)_{/B(I,I)} can be described as the set Part_{|I|}(X) of partitions of X of the same cardinality as I. Thus, the free algebras for the factorization monad are combinatorial power series F^{op} [figure] Set of the form

P_{!}X = ∐_{i∈ℕ} P [i] × Part_{i}(X)

where P : I^{op} [figure] Set. These are analogous to the Stirling power series of Paré [22], and correspond to formal power series of the form

∑_{i∈ℕ} p_{i} S(x, i)

where S denotes the Stirling numbers of the second kind. Since by results in [22], pushouts of surjections in F are absolute, it follows that a presheaf in F̂ is a free factorization-monad algebra if and only if it maps pushouts of surjections along injections to pullbacks.

In the above two examples Corollary 1.9(2) applies. Thus the reflective embeddings [figure: Kl; S^{op}; F̂^{op}] and Kl_{I} [figure] F̂ are exponential ideals. Further, the latter is a subtopos; unlike the former. The topos-theoretic aspects of the present work, however, will be the subject of a companion paper.

Readers interested in further examples from combinatorics may wish to look in [21, 1, 17, 16], where variations on the theory of species suitable for modeling other types of power series are developed. (See also [19, 6].)

For applications in combinatorics it is useful that the above combinatorial presheaves have enough structure to interpret the common operations in algebras of formal power series. Our results allow us to derive totality, a very strong form of completeness and cocompleteness (see, e.g., [23]).

1.19. Corollary. If every map in E is epi, C has pushouts along E-maps, and either C is E-well-founded or C has wide pushouts of E-maps, the Kleisli category for the induced factorization monad is total (in the sense of Street and Walters [24]).

Proof. Because either by Corollary 1.9(1) or by Theorem 1.10, we have that Kl_{M} is equivalent to a full reflective subcategory of Ĉ (see, e.g., [13, Theorem 6.1]).

It follows from this result that limit and colimit operations on diagrams of free algebras (combinatorial power series) in Kl_{M} induce operations on diagrams of presheaves (of coefficients) on M. Indeed, for every D : Δ [figure] M̂ we have

lim D_{!} ≅ (\overline{D})_{!} and colim D_{!} ≅ (\underline{D})_{!}

for essentially unique presheaves (of coefficients) \overline{D} and \underline{D} on M. For instance, as ( )_{!} is a left adjoint, we have as a general rule that the coefficients of the coproduct of combinatorial presheaves are the coproduct of the coefficients:

P_{!} + Q_{!} ≅ (P + Q)_{!}

The situation with limits and coequalisers is more interesting. For example, in the context of Joyal species and the Schanuel topos (Example 1.14) we have that

1 ≅ I_{!}

where I is the representable species B(∅, ), and that

P_{!} × Q_{!} ≅ (P ∗ Q)_{!}

where, for species P and Q, the species P ∗ Q is given by

(P ∗ Q)(U) = ∐_{U_{1}∪U_{2}=U} P (U_{1}) × Q(U_{2})

with action

(U_{1}, U_{2}, p, q) ·_{P ∗Q} σ = ( σ(U_{1}) , σ(U_{2}) , p ·_{P} (σ_{↾U_{1}}) , q ·_{Q} (σ_{↾U_{2}}) )

for all σ : U [figure: ≅] V in B. The above yield a monoidal structure on species; which, as far as we know, is new.

In all the above examples Corollary 1.19 is applicable. On the other hand, the following natural factorization system is neither well-founded, nor it admits wide pushouts.

1.20. Example. Consider F^{op} equipped with the all-iso factorization. In this case, free algebras are combinatorial functors F [figure] Set of the form

P_{!}X = ∐_{i∈ℕ} P [i] ⊗_{𝔖_{i}} X^{i}

for P a species B [figure] Set. These are equivalent to Joyal’s analytic functors [11], and for free symmetric group actions

P [i] × 𝔖_{i} [figure] P [i]

amount to combinatorial power series of the form

P_{!}X = ∐_{i∈ℕ} P [i]_{/𝔖_{i}} × X^{i}

corresponding to formal exponential power series

∑_{i∈ℕ} p_{i} \frac{x^{i}}{i!}

Joyal [11] shows that analytic functors can be characterized by both left and rightexactness conditions. We wonder whether our results can be extended to include this example.

Organization of the paper. In Section 2 we provide a characterization of Kleisli categories for factorization monads and prove Proposition 1.5. In Section 3 we prove the equivalence described in Theorem 1.7. In Section 4 we prove Theorem 1.10.

2. Characterization of free factorization-monad algebras

We give an intrinsic characterization of free factorization-monad algebras, which is both convenient and interesting in its own right. We discuss the statement of the result now and leave the details of the proof to the rest of the section.

2.1. Definition. The category of elements ∫ F of a presheaf F on the essentially small category C has objects given by pairs (X, x) with X in C and x ∈ F X, and morphisms f : (X, x) [figure] (Y, y) given by maps f : X [figure] Y in C such that x = (F f)y. For convenience we will write (F f)y as y ·_{F} f, or simply as y · f.

Let C be an essentially small category with an (E, M) factorization system.

2.2. Definition. For a presheaf F on C, we say that (X, x) is E-generic if for every e : (Z, z) [figure] (Y, y) in ∫ F with e in E and f : (Z, z) [figure] (X, x) in ∫ F there exists g : (Y, y) [figure] (X, x) in ∫ F such that the diagram

\xymatrix{(Z, z) \ar[dr]_{f} \ar[rr]^{e∈E} &  & (Y, y) \ar@{-->}[dl]^{g}_{∃} \\  & (X, x)}

commutes.

This is a natural generalization of Joyal’s definition in [11, Appendice].

2.3. Definition. For a presheaf F on C we say that (X, x) in ∫ F is engendered (resp. E-engendered) by (Y, y) in ∫ F if there exists a map (X, x) [figure](Y, y) in ∫ F (that is in E).

If x is engendered by y via the map f, then x is E-engendered by y · m via the map e where (e, m) is an (E, M)-factorization of f. Further, if y is E-generic then also y · m is E-generic (see Lemma 2.5), and so an element is engendered by an E-generic element if and only if it is E-engendered by an E-generic element in an essentially unique way (see Corollary 2.6).

2.4. Definition. A presheaf is said to be E-generically engendered if every element in it is engendered by an E-generic element.

For example, the E-generic elements of representable presheaves are the M-maps and the representable presheaves are E-generically engendered. These two facts are essentially the first part of Proposition 1.5. Details are given at the end of this section (see Proposition 2.18) after we establish the following characterization of the Kleisli category: a presheaf is free as an algebra for the factorization monad if and only if it is E-generically engendered (see Corollary 2.17).

Generic elements. We provide various basic properties of generic elements and then study the restriction of presheaves to presheaves of generic elements.

2.5. Lemma. Let F be a presheaf on the essentially small category C and let

f : (X, x) [figure] (Y, y)

in ∫ F.

1. For f in E the following hold.

(a) If (X, x) is E-generic then f is a split mono.

(b) If (X, x) and (Y, y) are E-generic then f is an iso.

2. If (Y, y) is E-generic then (X, x) is E-generic iff f ∈ M.

Proof. (1) If (X, x) is E-generic then

\xymatrix{(X, x) \ar[rr]^{f∈E} \ar[dr]_{id} &  & (Y, y) \ar@{-->}[dl]_{∃}^{r} \\  & (X, x)}

and hence f is a split mono and r a split epi. Moreover, r is in E because both f and r f = id are. Further, if (Y, y) is E-generic we have that

\xymatrix{(Y, y) \ar[rr]^{r∈E} \ar[dr]_{id} &  & (X, x) \ar@{-->}[dl]^{∃} \\  & (Y, y)}

from which it follows that r, and hence f, is an iso.

(2[figure]) Let e : (A, a) [figure] (B, b) in ∫ F with e in E and (A, a) [figure] (X, x) in ∫ F. As (Y, y) is E-generic we have a diagram as on the left below

\xymatrix{(A, a) \ar[r]^{e∈E} \ar[d] & (B, b) \ar@{-->}[d]^{g}_{∃} & A \ar[r]^{e} \ar[d] & B \ar@{-->}[dl]^{h}_{∃!} \ar[d]^{g} \\ (X, x) \ar[r]_{f} & (Y, y) & X \ar[r]_{f} & Y}

and since f is in M there exists a unique h : B [figure] Y such that the diagram on the right above commutes. But since x · h = y · f · h = y · g = b we have h : (B, b) [figure](X, x) in ∫ F, making (X, x) E-generic.

(2 [figure] ) Let

\xymatrix{X \ar[rr]^{f} \ar[dr]_{e∈E} &  & Y \\  & Z \ar@{-->}[ur]_{m∈M}}

be an (E, M)-factorization. Since (Y, y) is E-generic and m ∈ M it follows from (2[figure]) that (Z, y · m) is E-generic. Further, since both (X, x) and (Z, y · m) are E-generic and e : (Y, y) [figure] (Z, x · m) in ∫ F with e ∈ E it follows from (1b) that e is an iso. Hence, we have f in M.

2.6. Corollary. For (X, x) [figure: e] (Y, y) [figure: e′] (X′, x′) in ∫ F with both e and e′ in E, if (X, x) and (X, x′) are E-generic then they are isomorphic.

Proof. Since (X, x) is E-generic and e′ is in E, e factors through e′; say as e = f e′. In addition, as e′ and f e′ = e are both in E then so is f. Finally, since moreover (X, x) and (X′, x′) are E-generic, by Lemma 2.5 (1b), we have that f is in fact an iso.

Since E-generic elements are closed under the action of maps in M (see Lemma 2.5(2)), the following definition is natural.

2.7. Definition. For a presheaf F on C, the presheaf F^{∘} on M is given by setting

F^{∘}X = { x ∈ F X | x is E-generic } (X in M)

with action as for F.

We now identify a subcategory of Ĉ on which the operation ( )^{∘} on presheaves can be extended to a functor.

2.8. Definition. A natural transformation φ : F [figure] G : C^{op} [figure] Set is quasi E-cartesian if for every map e : X [figure] Y in E, the naturality square

\xymatrix{F Y \ar[r]^{φ_{Y}} \ar[d]_{F e} & GY \ar[d]^{Ge} \\ F X \ar[r]_{φ_{X}} & GX}

is a quasi pullback.

The interest in quasi E-cartesian natural transformations at this stage is the following remark.

2.9. Lemma. Quasi E-cartesian natural transformations in Ĉ preserve E-generic elements.

Proof. Let φ : F [figure]G be a quasi E-cartesian natural transformation, and assume that (X, x) ∈ ∫ F is E-generic. To prove that (X, φx) in ∫ G is E-generic consider e : (Z, z′) [figure] (Y, y′) in ∫ G with e in E and f : (Z, z′) [figure] (X, φx) in ∫ G. As φ is quasi E-cartesian, there exists y ∈ F Y such that y · e = x · f and φy = y′. Hence we have the following situation

\xymatrix{(Z, y · e) \ar[rr]^{e∈E} \ar[dr]_{f} &  & (Y, y) \ar@{-->}[dl]_{∃}^{g} \\  & (X, x)}

in ∫ F. We further have g : (Y, y′) [figure] (X, φx) in ∫ G, showing that φx is E-generic.

By Lemma 2.9, we thus obtain a functor ( )^{∘} : Ĉ_{↾ qEc} [figure]M̂ (see Definition 2.7), where Ĉ_{↾ qEc} denotes the subcategory of Ĉ consisting of the quasi E-cartesian natural transformations.

Free factorization-monad algebras. We have seen that factorization monads have a simple description using coends. Below we will use the following explicit description of the free functor. For C an essentially small category with an (E, M) factorization system, the left adjoint ( )_{!} : M̂ [figure] Ĉ induced by the inclusion functor M [figure] C is given (for P in M̂ and C in C) by the quotient

\xymatrix{∐_{X,Y ∈C} P X × M(Y, X) × C(C, Y) \ar[r]^{λ} \ar[r]_{ρ} & ∐_{Z∈C} P Z × C(C, Z) \ar@{->>}[r] & P_{!}C}

where λ(x, m, f) = (x ·_{P} m, f) and ρ(x, m, f) = (x, m f). The equivalence class of the pair (x, f) is denoted x ⊗f. Naturally, for h : D [figure] C in C we have that (x ⊗f)·_{P_{!}} h = x ⊗(f h).

2.10. Definition. For P a presheaf on M, f : C [figure] X and g : C [figure] Y in C, x ∈ P X, and y ∈ P Y we define (x, f) ∼ (y, g) if there exists a map m : Y [figure]X in M such that x · m = y and f = m g.

2.11. Lemma.

1. For f in C and m in M, we have that x ⊗(m f) = (x · m) ⊗f.

2. Let e_{0} : E [figure] X_{0} and e_{1} : E [figure] X_{1} be in E. Then (x_{0}, e_{0}) ∼ (x_{1}, e_{1}) if and only if there exists an iso i : X_{1} [figure] X_{0} such that x_{0} · i = x_{1} and e_{0} = i e_{1}.

3. Every element of P_{!} is of the form x ⊗e with e in E, and we have that the relation ∼ restricted to pairs (x, e) with e in E is an equivalence relation.

Proof. (1) Trivial. (2) The relationship (x_{0}, e_{0}) ∼ (x_{1}, e_{1}) holds if and only if there exists a map m : X_{1} [figure] X_{0} in M such that x_{0} · m = x_{1} and m e_{1} = e_{0}; or equivalently, since m is then necessarily both in M and E, that there exists an iso i : X_{1} [figure] X_{0} such that x_{0} · i = x_{1} and e_{0} = i e_{1}. (3) Follows from the other two.

In particular, if m_{0} e_{0} and m_{1} e_{1} are (E, M) factorizations of f_{0} and f_{1} respectively, then x_{0} ⊗f_{0} = x_{1} ⊗f_{1} if and only if there exists an iso i such that x_{0} · m_{0} · i = x_{1} · m_{1} and e_{0} = i e_{1}.

We characterize generic elements of free factorization-monad algebras.

2.12. Lemma. Let P be a presheaf on M and let f : Z [figure] X in C.

1. The element (X, x ⊗id) in ∫ P_{!} is E-generic.

2. The element (Z, x ⊗f) in ∫ P_{!} is E-generic iff f is in M.

Proof. (1) Let h : (Z, x ⊗f) [figure] (Y, y ⊗g) in ∫ P_{!} with h in E. Thus, for (e, m) an (E, M) factorization of f, we have that (x · m) ⊗e = y ⊗(g h). By Lemma 2.11(1) we can assume that g is in E and, from Lemma 2.11(2), we can conclude that there exists an iso i such that x · m · i = y and e = i g h. It follows that

\xymatrix{(Z, x ⊗f) \ar[dr]_{f} \ar[rr]^{h∈E} &  & (Y, y ⊗g) \ar@{-->}[dl]^{m i g} \\  & (X, x ⊗id)}

commutes in ∫ P_{!}.

(2) We have f : (Z, x ⊗f) [figure] (X, x ⊗id) in ∫ P_{!} and as, by (1), x ⊗id is E-generic then, by Lemma 2.5 (2), x ⊗f is E-generic iff f ∈ M.

We further study how natural transformations act on generic elements.

2.13. Proposition. For P a presheaf on M and G a presheaf on C, if the natural transformation φ : P_{!} [figure] G in Ĉ preserves E-generic elements then it is quasi E-cartesian.

Proof. For e : X [figure] Y in E, consider the naturality square

\xymatrix{P_{!}Y \ar[r]^{φ_{Y}} \ar[d]_{P_{!}e} & GY \ar[d]^{Ge} \\ P_{!}X \ar[r]_{φ_{X}} & GX}

and let z ⊗f ∈ P_{!}X (with z ∈ P Z and f : X [figure] Z) and y ∈ GY be such that φ(z ⊗f) = y · e. By Lemma 2.12(1) and hypothesis, φ(z ⊗id) is E-generic and we have the following situation

\xymatrix{(X, φ(z ⊗f)) \ar[rr]^{e∈E} \ar[dr]_{f} &  & (Y, y) \ar@{-->}[dl]^{∃g} \\  & (Z, φ(z ⊗id))}

in ∫ G. The element z ⊗g ∈ P_{!}Y has the property that (z ⊗g) · e = z ⊗f and that φ(z ⊗g) = φ(z ⊗id) · g = y. Thus φ is quasi E-cartesian.

2.14. Corollary.

1. For every natural transformation ρ : P [figure]Q in M̂, the natural transformation ρ_{!} : P_{!} [figure] Q_{!} in Ĉ is quasi E-cartesian.

2. For P and Q in M̂, P_{!} ≅ Q_{!} in Ĉ iff P ≅ Q in M̂.

Thus, the free-algebra functor ( )_{!} : M̂ [figure]Ĉ is conservative and factors through the inclusion functor Ĉ_{↾ qEc} [figure] Ĉ.

2.15. Proposition. The functor ( )_{!} : M̂ [figure]Ĉ_{↾ qEc} is an embedding and has ( )^{∘} : Ĉ_{↾ qEc} [figure] M̂ as right adjoint.

Proof. For a presheaf P on M and X in C we have a function η_{P X} : P X [figure] (P_{!})^{∘}X mapping x to x ⊗id which, since (x · m) ⊗id = x ⊗m for m in M, yields a natural transformation η_{P} : P [figure] (P_{!})^{∘} in M̂, that is also natural in P by construction. Further, since by Lemma 2.12 every element of (P_{!})^{∘} is of the form x ⊗id, by Lemma 2.11(2), η_{P} is clearly an iso.

On the other hand, for F in Ĉ_{↾ qEc} and X in C, by Lemma 2.11, the assignment

(x ⊗f) ∈ (F^{∘})_{!}X [figure] x · f ∈ F X

yields a function ε_{F X} : (F^{∘})_{!}X [figure] F X, which, by Lemmas 2.5(2) and 2.12(2), and Proposition 2.13. gives a quasi E-cartesian natural transformation ε_{F} : (F^{∘})_{!} [figure] F, that is natural in F by construction.

Finally we show that η and ε satisfy the triangle identities. Indeed, for a presheaf P on M we have

ε_{P_{!}}(η_{!}(x ⊗f)) = ε_{P_{!}}((ηx) ⊗f) = (x ⊗id) · f = x ⊗f

for all x ⊗f in P_{!}; whilst, for a presheaf F on Ĉ_{↾ qEc}, we have

ε^{∘}(η_{F^{∘}}(x)) = ε^{∘}(x ⊗id) = x · id = x

for all x in F^{∘}.

Note that Lemma 2.12(1) implies that free algebras are E-generically engendered. Thus, the embedding Kl_{M} [figure] Ĉ factors through the embedding Eng(Ĉ) [figure]Ĉ, where Eng(Ĉ) denotes the full subcategory of Ĉ determined by the E-generically engendered presheaves, and the embedding ( )_{!} : M̂ [figure]Ĉ_{↾ qEc} factors through the embedding Eng(Ĉ)_{↾ qEc} [figure] Ĉ_{↾ qEc}, where Eng(Ĉ)_{↾ qEc} denotes the intersection of Eng(Ĉ) and Ĉ_{↾ qEc}.

2.16. Proposition. The adjunction M̂ [figure: ⊤] Ĉ_{↾ qEc} cuts down to an equivalence M̂ ≃ Eng(Ĉ)_{↾ qEc}.

Proof. For F ∈ Eng(Ĉ)_{↾ qEc} and X ∈ C, by Corollary 2.6 and Lemma 2.5, the assignment

x ∈ F X [figure] (x′ ⊗e) ∈ (F^{∘})_{!}X

where e : (X, x) [figure](X′, x′) in ∫ F with e in E and (X′, x′) E-generic, yields a function which is an inverse for the counit of the adjunction (see Proposition 2.15).

2.17. Corollary. The embedding Kl_{M} [figure] Eng(Ĉ) is an equivalence.

Proof. As the functor

( )_{!} : M̂ [figure] Eng(Ĉ)_{↾ qEc}

is an equivalence and the functor Eng(Ĉ)_{↾ qEc} [figure] Eng(Ĉ) is bijective on objects, the embedding Kl_{M} [figure] Eng(Ĉ) is essentially surjective; so it is an equivalence.

Summarizing, we have the following situation.

\xymatrix{M̂ \ar@{^{(}->}[d]_{_{( )_{!}}}|{≃} \ar[r] & Kl_{M} \ar@{^{(}->}[d]|{≃} \\ _{Eng(Ĉ)_{↾ qEc}} \ar@{^{(}->}[d] \ar[r] & Eng(Ĉ) \ar@{^{(}->}[d] \\ Ĉ_{↾ qEc} \ar[r] & Ĉ}

With the characterization of free factorization-monad algebras in terms of generic elements we can now prove the first part of Proposition 1.5; that is, that the Yoneda embedding factors through [figure: Kl; M; Ĉ].

2.18. Proposition. A map with codomain C in C is E-generic for the presheaf on C represented by C if and only if it is in M. Moreover, representable presheaves on C are E-generically engendered.

Proof. From the definition of E-generic element one deduces that a map is E-generic if and only if it is weakly orthogonal to every map in E. Thus, M-maps are E-generic. Further, since every map in C is engendered by its M factor (via its E factor), representable presheaves are E-generically engendered and, by Corollary 2.5(1b), E-generic elements are in M.

Finally, we prove the second part of Proposition 1.5; that is, that the embedding [figure: Kl; M; Ĉ] factors through qEx(Ĉ) [figure] Ĉ.

2.19. Lemma. Every E-generically engendered presheaf on C maps pushouts along E-maps in C to quasi pullbacks in Set.

Proof. Let F be an E-generically engendered presheaf and let the square below be a pushout in C

\xymatrix{Z \ar[d]_{f} \ar[r]^{e∈E} & Y \ar[d]^{p} \\ X \ar[r]_{q} & U}  (3)

with e, and hence also q, in E. Moreover, let x ∈ F X and y ∈ F Y be such that x · f = y · e. As F is E-generically engendered there exists a map e′ : (X, x) [figure] (X′, x′) in ∫ F with e′ in E and (X′, x′) E-generic. Hence, we have the following situation

\xymatrix{(Z, z) \ar[d]_{f} \ar[r]^{e∈E} & (Y, y) \ar@{-->}[d]^{g}_{∃} \\ (X, x) \ar[r]_{e′} & (X′, x′)}

and the pushout property of (3) gives a map h : U [figure] X′ such that e′ = h q and g = h p. Finally, since for u = x′ · h ∈ F U we have that u · q = x and u · p = y, we are done.

3. First main result

Minimal elements. We have described generators of free algebras for factorization monads via the notion of generic element. In the situations we are interested in the generators have an alternative description which is important to study.

Let C be an essentially small category with an (E, M) factorization system.

3.1. Definition. For a presheaf F on C, we say that (X, x) in ∫ F is E-minimal if the following equivalent conditions hold.

1. Every (X, x) [figure] (Y, y) in ∫ F which is in E is an iso.

2. Every (X, x) [figure] (Y, y) in ∫ F is in M.

We characterize minimal elements of free factorization-monad algebras. To do this, it is convenient to prove the following result.

3.2. Lemma. For a presheaf P on M and x ∈ P X (X in C), the element (X, x ⊗id) in ∫ P_{!} is E-minimal iff every section X [figure] Y is in M.

Proof. ( [figure] ) Because for every section s : X [figure] Y in E with retraction r : Y [figure] X in C we have that s : (X, x ⊗id) [figure] (Y, x ⊗r) in ∫ P_{!}.

([figure]) Because every s : (X, x ⊗id_{X}) [figure] (Y, y ⊗g) in ∫ P_{!} is a section and so, by hypothesis, is in M.

We can now give a characterization of minimal elements in free factorization-monad algebras.

3.3. Corollary. Let P be a presheaf on M, x ∈ P X (X in C) and f : Z [figure] X in C. The element (Z, x ⊗f) in ∫ P_{!} is E-minimal iff f is in M and every section Z [figure] Y is in M.

Proof. As usual we have f : (Z, x ⊗f) [figure] (X, x ⊗id) in ∫ P_{!} so, if (Z, x ⊗f) is E-minimal, f is in M. As (x · f) ⊗id_{Z} = x ⊗f, by Lemma 3.2, every section with domain Z is in M. Conversely, if every section with domain Z is in M then, again by Lemma 3.2, x ⊗f = (x · f) ⊗id_{Z} is E-minimal for any f ∈ M.

3.4. Corollary. In free factorization-monad algebras, E-minimal implies E-generic.

Proof. Compare the characterizations in Corollary 3.3 and Lemma 2.12.

In general the converse does not hold but using Corollary 3.3 it is easy to characterize the situation when E-minimal and E-generic elements coincide.

3.5. Definition. A presheaf on C is unbiased if its E-minimal and E-generic elements coincide.

3.6. Corollary. The following are equivalent.

1. Every section is in M.

2. For every presheaf on C, E-generic elements are E-minimal.

3. Free factorization-monad algebras are unbiased.

Proof. To prove that (1) implies (2) use Lemma 2.5. Corollary 3.4 shows that (2) implies (3). To prove that (3) implies (1), consider the presheaf 1_{!} which is unbiased by hypothesis. For X in C, the element (X, ∗ ⊗id) is E-generic by Lemma 2.12(1). It is then E-minimal and so every section with domain X is in M by Lemma 3.2.

3.7. Definition. A presheaf is said to be E-minimally E-engendered if every element in it is E-engendered by an E-minimal element.

3.8. Lemma. Let P be a presheaf on C such that its E-minimal elements are E-generic. If P is E-minimally E-engendered then it is unbiased.

Proof. We need to show E-generic implies E-minimal in P. So let (X, x) be E-generic. By hypothesis, there exists a map e : X [figure] Y in E and an E-minimal element (Y, y) such that e : (X, x) [figure] (Y, y). But (Y, y) is E-generic by hypothesis so Lemma 2.5 implies that e is an iso and so, (X, x) is E-minimal.

Now E-well-foundedness (Definition 1.6) enters the picture.

3.9. Lemma. Every presheaf on an E-well-founded C is E-minimally E-engendered.

Proof. Let F be a presheaf on C, and let (X, x) in ∫ F. If (X, x) is not E-minimal then there exists a map e : (X, x) [figure] (X′, x′) in ∫ F with e in E not an iso. If (X′, x′) is E-minimal then the result is proved. If not, repeat the process. The E-well-foundedness assumption on C ensures that we reach an E-minimal element in a finite number of steps. As E-maps are closed under composition, the result follows.

We are ready to prove the implication stated in Theorem 1.7 with E-well-foundedness as hypothesis.

3.10. Corollary. If C is E-well-founded then every section is in M.

Proof. By Corollary 3.6 it is enough to prove that free factorization-monad algebras are unbiased. By Corollary 3.4 E-minimal implies E-generic in free factorization-monad algebras. As C is E-well-founded, Lemma 3.9 implies that free factorization-monad algebras are E-minimally E-engendered and so, by Lemma 3.8, we obtain that E-generic and E-minimal elements coincide.

It remains to show that the embedding Kl_{M} [figure] qEx(Ĉ) is an equivalence.

3.11. Lemma. If C has pushouts along E-maps then, for presheaves in qEx(Ĉ), E-minimal elements are E-generic.

Proof. Assume that C has pushouts along E-maps and let F be a presheaf on C mapping these pushouts to quasi pullbacks. For an E-minimal element (X, x) in ∫ F, to prove that it is E-generic, let e : (Z, z) [figure] (Y, y) in ∫ F with e in E and f : (Z, z) [figure] (X, x) in ∫ F.

Take the pushout of e along f in C as below

\xymatrix{Z \ar[d]_{f} \ar[r]^{e∈E} & Y \ar[d]^{p} \\ X \ar[r]_{q} & U}

where q necessarily belongs to E. As F maps this pushout to a quasi pullback, there is an element u ∈ F U such that the diagram

\xymatrix{(Z, z) \ar[r]^{e} \ar[d]_{f} & (Y, y) \ar[d]^{p} \\ (X, x) \ar[r]_{q} & (U, u)}

commutes in ∫ F. Since (X, x) is E-minimal and q is in E, we have that q is an iso and hence that (X, x) has the property of being E-generic.

Together with Corollary 3.10 the following result establishes one half of the equivalence in Theorem 1.7.

3.12. Corollary. If C has pushouts along E-maps and it is E-well-founded then the vertical functors in the diagram below are equivalences.

\xymatrix{M̂ \ar[d]_{_{( )_{!}}} \ar[r] & Kl_{M} \ar@{^{(}->}[d] \\ _{qEx(Ĉ)_{↾ qEc}} \ar[r] & qEx(Ĉ)}

Proof. By Lemma 3.9 every presheaf in qEx(Ĉ) is E-minimally E-engendered. From Lemma 3.11 we have that every such presheaf is E-generically engendered, and hence, by Lemma 2.19, that Eng(Ĉ) = qEx(C). Finally, Proposition 2.16 and Corollary 2.17 establish the result.

The presheaf of chains. For (E, M) a factorization system on an essentially small category C, we prove the remaining part of Theorem 1.7; namely, that if every section is in M and the embedding Kl_{M} [figure] qEx(Ĉ) is an equivalence then C is E-well-founded. The idea of the proof is to construct a particular presheaf R that maps pushouts to quasi pullbacks and such that R being E-generically engendered, together with the assumption that split monos are in M, implies that C is E-well-founded. The rest of the section builds such an R and proves the relevant properties.

A chain in C is a functor from the linear order ω = (0 ≤ 1 ≤ ⋯ ≤ n ≤ ⋯) (n ∈ ℕ) to C. Note that a category is defined to be E-well-founded if every chain consisting of maps in E is eventually a sequence of isos.

For any chain α we let α_{↓0} = id_{α0} and α_{↓(j+1)} = α(j ≤ j + 1) α_{↓j} : α0 [figure]α(j + 1) for all j ∈ ℕ. We also define α_{↑j} (j ∈ ℕ) to be the chain such that for every m, n ∈ ℕ, α_{↑j}(m ≤ n) = α(j + m ≤ j + n).

We now define an equivalence relation ∼ on the sets of chains with the same initial domain. For such chains α and β, i.e. such that α0 = β0, we let α ∼ β if and only if there exists j, k ∈ ℕ such that α_{↓j} = β_{↓k} and α_{↑j} = β_{↑k}.

3.13. Lemma. The relation ∼ is an equivalence relation.

Proof. The relation is clearly reflexive and symmetric. For transitivity assume that α ∼ β is witnessed by j, k ∈ ℕ such α_{↓j} = β_{↓k}, α_{↑j} = β_{↑k} and that β ∼ γ is witnessed by l, m in ℕ such that β_{↓l} = γ_{↓m} and β_{↑l} = γ_{↑m}. Then, the relationship α ∼ γ is witnessed by j + l, m + k ∈ ℕ.

For a chain α and a map f : X [figure]α0, we let α · f be the chain determined by the identities (α · f)(0 ≤ 1) = f and (α · f)(n + 1 ≤ n + 2) = α(n ≤ n + 1) for all n ∈ ℕ.

3.14. Lemma. The following hold for any chains α and β with α0 = β0.

1. For any f : X [figure] α0, α ∼ β implies α · f ∼ β · f.

2. α ∼ α · id_{α0}

3. For any g : Y [figure] X and f : X [figure] α0, α · (f g) ∼ (α · f) · g.

For X ∈ C, we let RX be the quotient of the set of chains with domain X by the equivalence relation ∼; that is,

RX = { α : ω [figure] C | α0 = X }_{/∼}

and denote the equivalence class of a chain α as [α]. By Lemma 3.14, for every map f : X [figure] Y in C, the assignment

\xymatrix{[α] \ar@{|->}[r] & [α · f] & (α0 = Y)}

yields a function Rf : RY [figure] RX that makes R into a presheaf on C.

3.15. Lemma. The presheaf R maps pushouts to quasi pullbacks.

Proof. For a pushout square as on the left below

\xymatrix{Q \ar[d]_{q} \ar[r]^{r} & Z \ar[d]^{g} & RP \ar[d]_{Rf} \ar[r]^{Rg} & RZ \ar[d]^{Rr} \\ Y \ar[r]_{f} & P & RY \ar[r]_{Rq} & RQ}

we need to prove that the square on the right is a quasi-pullback. So let [α] ∈ RY and [β] ∈ RZ be such that [α] · q = [β] · r. There exist j, k ∈ ℕ such that (α · q)_{↓j} = (β · r)_{↓k} and (α · q)_{↑j} = (β · r)_{↑k}. It follows that there exist j, k ∈ ℕ such that α_{↓j} · q = β_{↓k} · r and α_{↑j} = β_{↑k}. Then the pushout property implies that there exists a map t such that t f = α_{↓j} and t g = β_{↓k}. Now consider Γ · t ∈ RP for Γ = [α_{↑j}] = [β_{↑k}]. We have that (Γ · t) · f = [α_{↑j}] · α_{↓j} = [α] and, similarly, that (Γ · t) · g = [β]. So R maps the above pushout to a quasi-pullback. That is, R is in qEx(Ĉ). Notice that if the embedding Kl_{M} [figure] qEx(Ĉ) is an equivalence then, by Corollary 2.17, R is E-generically engendered. The rest of the section shows that under the further assumption that split monos are in M we obtain that C is E-well-founded.

3.16. Lemma. Let (Y, [β]) in ∫ R be E-generic and for every k ∈ ℕ let (e_{k}, m_{k}) be the (E, M)-factorization of β_{↓k}. Then e_{k} is split mono for every k. In particular, if split monos are in M then β_{↓k} is in M for every k. If, moreover, every map in β is in E then every map in β is an iso.

Proof. It is clear that, for any k, [β] = [β_{↑k}] · (β_{↓k}) = ([β_{↑k}] · m_{k}) · e_{k} so, as [β] is E-generic, e_{k} is a split mono by Lemma 2.5. If split monos are in M then e_{k} is an iso and so β_{↓k} is in M. Finally, assume that every map in β is in E and proceed by induction. We have that β(0 ≤ 1) is both in E and M so it is an iso. Now consider β(n + 1 ≤ n + 2). By the first part of the lemma we have that β_{↓(n+2)} = (β(n + 1 ≤ n + 2)) β_{↓(n+1)} is in M. As by inductive hypothesis β_{↓(n+1)} is an iso, it follows that β(n + 1 ≤ n + 2) is in M and hence an iso.

Now we know what is needed about the generic elements of R.

3.17. Lemma. If sections are in M and R is E-generically engendered then C is E-well-founded.

Proof. Let α be a chain such that every map in it is in E. By hypothesis there exists a map e : α0 [figure] Y in E and an E-generic [β] ∈ RY such that [β] · e = [α]. Thus, there exist j, k ∈ ℕ such that α_{↓j} = (β · e)_{↓k} and α_{↑j} = (β · e)_{↑k}. It follows that there exist j, k ∈ ℕ such that α_{↓j} = β_{↓k} · e and α_{↑j} = β_{↑k}. As both α_{↓j} and e are in E, so is β_{↓k}. But β_{↓k} is in M by Lemma 3.16 so it is an iso. We then have that [β_{↑k}] is E-generic. But as α_{↑j} = β_{↑k}, every map in β_{↑k} is in E so Lemma 3.16 implies that every map in β_{↑k} is an iso. That is, α is eventually a sequence of isos.

Theorem 1.7 is proved.

4. Second main result

This section establishes Theorem 1.10.

Let C be an essentially small category with an (E, M) factorization system.

4.1. Proposition. Every E-generically engendered presheaf maps wide pushouts of E-maps in C to quasi wide pullbacks in Set.

Proof. Consider the wide span { e_{i} : Z [figure]X_{i} in E }_{i∈I} and, for F an E-generically engendered presheaf, let z ∈ F Z and x_{i} ∈ F X_{i} (i ∈ I) be such that z = x_{i} · e_{i} (i ∈ I).

For each i ∈ I, let q_{i} : (X_{i}, x_{i}) [figure] (Y_{i}, y_{i}) in ∫ F with q_{i} in E and (Y_{i}, y_{i}) E-generic. By Corollary 2.6, we have the following situation

\xymatrix{ & (X_{i}, x_{i}) \ar[r]^{q_{i}} & (Y_{i}, y_{i}) \ar[dd]|{≅} \\ (Z, z) \ar@{-->}[ur]^{e_{i}} \ar@{-->}[dr]_{e_{j}} \\  & (X_{j}, x_{j}) \ar[r]_{q_{j}} & (Y_{j}, y_{j})}

for every i, j ∈ I. It follows that there exists { q′_{i} : (X_{i}, x_{i}) [figure] (Y, y) }_{i∈I} in ∫ F with q′_{i} in E and (Y, y) E-generic such that the diagram in ∫ F

\xymatrix{ & (X_{i}, x_{i}) \ar@{-->}[dr]^{q′_{i}} \\ (Z, z) \ar@{-->}[ur]^{e_{i}} \ar@{-->}[dr]_{e_{j}} &  & (Y, y) \\  & (X_{j}, x_{j}) \ar@{-->}[ur]_{q′_{j}}}

commutes for all i, j ∈ I. By the wide pushout property, there exists a unique u : X [figure] Y in C such that q′_{i} = u f_{i} for all i ∈ I, where { f_{i} : X_{i} [figure] X } is the wide pushout of { e_{i} : Z [figure] X_{i} in E }_{i∈I}. Hence, y · u ∈ F X is such that y · u · f_{i} = x_{i} for all i ∈ I.

4.2. Proposition. Assume that every map in E is epi. For a presheaf F on C and an element (Z, z) in ∫ F, if the wide span

{ e_{i} : Z [figure] X_{i} in E | e_{i} : (Z, z) [figure] (X_{i}, x_{i}) in ∫ F }_{i∈I}

has a wide pushout in C and F maps it to a quasi wide pullback in Set then (Z, z) is E-minimally E-engendered.

Proof. Let

[figure: Z; ···; e_{i}; e_{j}; ···; ···; X_{i}; ···; f_{i}; ···; X_{j}; f_{j}; ···; X]

be a wide pushout, and let x ∈ F X be such that x · f_{i} = x_{i} for all i ∈ I.

For i ∈ I, let (q_{i}, p_{i}) be an (E, M) factorization of f_{i}. Since, for all i, j ∈ I, we have the following situation

[figure: Z; e_{i}; e_{j}; X_{i}; q_{i}; f_{i}; X_{j}; q_{j}; f_{j}; Y_{i}; p_{i}; ≅; Y_{j}; p_{j}; X]

there exist q′_{i} ∈ E (i ∈ I) and p ∈ M such that the diagram

[figure: Z; e_{i}; e_{j}; X_{i}; q′_{i}; f_{i}; X_{j}; q′_{j}; f_{j}; Y; p; X]

commutes for all i, j ∈ I. Note that we have q′_{i} : (X_{i}, x_{i}) [figure] (Y, x · p) in ∫ F for all i ∈ I.

By the wide pushout property, we have that there exists a unique u : X [figure]Y such that q′_{i} = u f_{i} (i ∈ I), and also that p u = id.

Further, since q = q′_{i} e_{i} : Z [figure]Y (i ∈ I) is a map (Z, z) [figure](Y, x · p) in ∫ F which is in E, the definition of the collection { e_{i} }_{i∈I} implies that there exists k ∈ I such that e_{k} = q. In particular, e_{k} = q′_{k} e_{k} and, as e_{k} is epi, we have that q′_{k} = id and hence that f_{k} = p q′_{k} = p. Thus, u p = u f_{k} = q′_{k} = id, and so p is an iso and f_{i} = p q′_{i} is in E for all i ∈ I. It follows that (Z, z) is E-engendered by (X, x) via the map f_{i} e_{i} : Z [figure] X (i ∈ I).

Finally, we show that (X, x) is E-minimal. To this end, let e : (X, x) [figure](X′, x′) in ∫ F be in E. Since e p q : (Z, z) [figure](X′, x′) in ∫ F is in E, there exists ℓ ∈ I such that e_{ℓ} = e p q. Thus,

f_{ℓ} e p q = f_{ℓ} e_{ℓ} = p q′_{ℓ} e_{ℓ} = p q

and, as p q in E is epi, we have f_{ℓ} e = id, making e in E a split mono and hence an iso.

4.3. Proposition. If every map in E is epi, and C has pushouts along E-maps and wide pushouts of E-maps, then for a presheaf F on C the following statements are equivalent.

1. F maps pushouts along E-maps to (quasi) pullbacks and wide pushouts of E-maps to (quasi) wide pullbacks.

2. F maps pushouts along E-maps to (quasi) pullbacks and is E-minimally E-engendered.

3. F is E-generically engendered.

Proof. (1) [figure](2) By Proposition 4.2. (2) [figure](3) By Lemma 3.11. (3) [figure](1) By Lemma 2.19 and Proposition 4.1. Notice also that (3) [figure] (2) by Lemma 2.19 and Corollary 3.6.

Theorem 1.10 now appears as a corollary of Corollary 2.17 and Proposition 4.3.

Acknowledgments. We thank Ross Street for his proficient handling of the paper and the anonymous referee for pointing out that not only completeness and cocompleteness but further totality (Corollary 1.19) followed from our results.

References

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

[2] F. Bergeron, G. Labelle, and P. Leroux. Combinatorial species and tree-like structures, volume 67 of Encyclopedia of Mathematics and its Applications. Cambridge University Press, 1998.

[3] J. C. E. Dekker. Myhill’s theory of combinatorial functions. Modern Logic, 1(1):3–21, 1990.

[4] M. Fiore. Enrichment and representation theorems for categories of domains and continuous functions. Manuscript available electronically, 1996.

[5] M. Fiore. Notes on combinatorial functors. Draft available electronically, January 2001.

[6] M. Fiore. Mathematical models of computational and combinatorial structures. Invited address for Foundations of Software Science and Computation Structures (FOSSACS 2005), volume 3441 of Lecture Notes in Computer Science, pages 25–46. Springer-Verlag, 2005.

[7] P. J. Freyd and G. M. Kelly. Categories of continuous functors I. Journal of Pure and Applied Algebra, 2:169–191, 1972. (Erratum in Journal of Pure and Applied Algebra, 4:121, 1974.)

[8] P. T. Johnstone. A topos-theorist looks at dilators. Journal of Pure and Applied Algebra, 58(3):235–249, 1989.

[9] P. T. Johnstone. Sketches of an elephant: A topos theory compendium, volumes 43-44 of Oxford Logic Guides. Oxford University Press, 2002.

[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.

[12] G. M. Kelly. Basic Concepts of Enriched Category Theory. Number 64 in LMS Lecture Notes. Cambridge University Press, 1982.

[13] G. M. Kelly. A survey of totality for enriched and ordinary categories. Cahiers de Top. et Géom. Diff. Catégoriques, 27:109–132, 1986.

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

[15] S. Mac Lane and I. Moerdijk. Sheaves in Geometry and Logic: A First Introduction to Topos Theory. Universitext. Springer-Verlag, 1992.

[16] M. Méndez. Species on digraphs. Advances in Mathematics, 123(2):243–275, 1996.

[17] M. Méndez and O. Nava. Colored species, c-monoids and plethysm, I. Journal of Combinatorial Theory (Series A), 64:102–129, 1993.

[18] M. Menni. About � -quantifiers. Applied Categorical Structures, 11(5):421–445, 2003.

[19] M. Menni. Symmetric monoidal completions and the exponential principle among labeled combinatorial structures. Theory and Applications of Categories, 11:397–419, 2003.

[20] J. Myhill. Recursive equivalence types and combinatorial functions. Bull. Amer. Math. Soc., 64:373–376, 1958.

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

[22] R. Paré. Contravariant functors on finite sets and Stirling numbers. Theory and Applications of Categories, 6(5):65–76, 1999.

[23] R. Street. The family approach to total cocompleteness and toposes. Transactions of the American Mathematical Society, 284(1):355–369.

[24] R. Street and R. Walters. Yoneda structures on 2-categories. Journal of Algebra, 50:350–379, 1978.

University of Cambridge, Computer Laboratory 15 JJ Thomson Avenue, Cambridge CB3 0FD, UK

Lifia, Facultad de Informática 50 y 115 s/n,1900 - La Plata, Argentina

Email: Marcelo.Fiore@cl.cam.ac.uk
      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/15/2/15-02.{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.

Information for authors. The typesetting language of the journal is TEX, and L^{A}TEX2e 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.

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

TEXnical editor. Michael Barr, McGill University: mbarr@barrs.org

Transmitting editors.

Richard Blute, Université d’ Ottawa: rblute@mathstat.uottawa.ca Lawrence Breen, Université de Paris 13: breen@math.univ-paris13.fr Ronald Brown, University of North Wales: 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, Xerox Palo Alto Research Center: paiva@parc.xerox.com

Ezra Getzler, Northwestern University: getzler(at)math(dot)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 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@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