Theory and Applications of Categories, Vol. 7, No. 8, 2000, pp. 171–205

M-COMPLETENESS IS SELDOM MONADIC OVER GRAPHS

J. Adámek and G.M. Kelly

Transmitted by Walter Tholen

Abstract. For a set M of graphs the category Cat_{M} of all M-complete categories and all strictly M-continuous functors is known to be monadic over Cat. The question of monadicity of Cat_{M} over the category of graphs is known to have an affirmative answer when M specifies either (i) all finite limits, or (ii) all finite products, or (iii) equalizers and terminal objects, or (iv) just terminal objects. We prove that, conversely, these four cases are (essentially) the only cases of monadicity of Cat_{M} over the category of graphs, provided that M is a set of finite graphs containing the empty graph.

1. Introduction

For more than twenty years several authors have studied properties of the category Cat_{M} of all M-complete categories and all strictly M-continuous functors. Here we might have taken M to be a set of categories, or more generally a set of weights in the context of weighted limits; but for the present paper we are concerned with the case where M is a set of graphs (in the usual modern sense of the word “graph” : namely a diagram in Set of the form s, t : E ⟶ V). Then an object of Cat_{M} is a small category C together with a choice of a limit-object and a limit-cone for each diagram D : M ⟶ C with M ∈ M (so that the same C with different limit-choices would be a different object of Cat_{M}), and a morphism in Cat_{M} is a functor preserving strictly the chosen M-limits; we may often use the alternative phrase “assigned M-limits”. In 1975, C. Lair [LR] observed that the evident forgetful functor from Cat_{M} to the category Cat of small categories is monadic; a recent proof of this can also be found in [KL]. A deeper question is the monadicity of the forgetful functor U_{M} : Cat_{M} ⟶ Gph where Gph is the category of (small) graphs and homomorphisms; when this is monadic, we often loosely say that “Cat_{M} is monadic over Gph”, it being understood that U_{M} is the functor in question. For example, C. Lair showed in [LR] that

(i) Cat is monadic over Gph (the case of empty M) and

The authors gratefully acknowledge the support of the Australian Research Council, which made possible a 1997 visit by the first author to Sydney. The first author gratefully acknowledges the support of the Czech Grant agency, Grant 201/99/0310

Received by the Editors 1999 July 8, and in revised form 2000 May 15.

Published on 2000 June 29.

2000 Mathematics Subject Classification: 18A35, 18A10, 18C15.

Key words and phrases: category, graph, limit, adjunction.

\begin{matrix}c \\ ◯ \end{matrix}J. Adámek and G.M. Kelly 2000. Permission to copy for private use granted.

(ii) Cat_{F P}, the category of all small categories with finite products, is also monadic

over Gph (the case where M consists of all finite discrete graphs). The categories Cat_{M} were later studied by A. Burroni in [BU] who proved, among other things, that the following categories are monadic over Gph:

(iii) Cat_{T}, the category of all small categories with a terminal object (the case where

M consists of the empty graph ∅ alone) and

(iv) Cat_{P B}, the category of all small categories with pullbacks (the case where M =

{Pb} and Pb is a single co-span). Burroni’s proofs consisted of giving operations whose arities were finite graphs, together with equations between derived operations, in such a way that the algebras for the theory so presented were the categories with chosen limits of the given kind; this provides a complete proof, since the algebras for such a theory are known to be those for a finitary monad — for a very general account of monads so presented on locally finitely presentable (perhaps enriched) categories, see [PW]. Accordingly, by putting together all the operations and all the equations in (iii) and (iv), we may conclude the monadicity over Gph of

(v) Cat_{P B+T}, the category of all small categories with pullbacks and a terminal

object (the case where M = {Pb, ∅}). Burroni interprets this last as the monadicity over Gph of

(vi) Cat_{LEX}, the category of all finitely-complete small categories (the case where

M consists of all finite graphs); but in fact this interpretation overlooks a delicate point that we shall discuss more fully below : namely, that the evident forgetful functor Cat_{LEX} ⟶ Cat_{P B+T} is not an equivalence, failing even to be fully faithful. In a subsequent paper [MS], J. MacDonald and A. Stone provide explicit operations and equations to establish the monadicity over Gph of (iii) once again, and also of

(vii) Cat_{EQ}, the category of all small categories with equalizers (the case where

M = {Eq} and Eq is a single parallel pair) and of (viii) Cat_{BP}, the category of all small categories with binary products (the case where

M = {Pr} and Pr is the two-vertex discrete graph). From (iii), (vii), and (viii) there follows at once the monadicity over Gph of such combinations as

(ix) Cat_{EQ+T}, the category of all small categories with equalizers and a terminal

object (the case where M = {Eq, ∅}, which we need to refer to below) and

(x) Cat_{BP +EQ+T} (the case where M = {Pr, Eq, ∅}; once again, overlooking the delicate point above, MacDonald and Stone interpret (x) as the monadicity over Gph of Cat_{LEX}.

The methods used by the authors above, and others who investigated the categories Cat_{M} (see for example [CL], [DK]), were quite disparate. The second author and I.J. Le Creurer proved in [KL] a single result which subsumes all of the valid results above : recall that a graph without cycles is called acyclic and observe that, except in (vi), all the graphs used above (Pb, Eq, ∅, Pr and other discrete graphs) are acyclic.

1.1 Theorem. ([KL]) For every class M of finite acyclic graphs, the functor U_{M} : Cat_{M} ⟶ Gph is monadic.

The paper [KL] also contains the first published case which fails to be monadic: categories having limits of endomorphisms. More precisely, let Le be the one-vertex graph {s : e ⟶ e}; then the forgetful functor U_{{Le}} : Cat_{{Le}} ⟶ Gph (from the category of all small categories with limits of endomorphisms) is not monadic.

Note that Theorem 1.1 does not imply the monadicity over Gph of Cat_{LEX}, since not all finite graphs are acyclic. In view of the gaps in the earlier arguments, it is not clear that any valid proof of the monadicity over Gph of Cat_{LEX} has yet been given.

The present paper has two goals. First, we analyze and resolve such difficulties as the failure of Cat_{LEX} ⟶ Cat_{P B+T} to be an equivalence, proving Theorem 1.4 below, which among other things fills the gaps in the earlier arguments regarding Cat_{LEX} and restores their validity — although its real use is much wider, and we need it to state our main result. However we do this analysis in an Appendix, since it necessarily involves the more general concept of weighted limit, and is as easily carried out for enriched categories as for ordinary ones. The second and more central goal is the rather surprising result that all the monadic cases of U_{M} are among those listed above – provided that M is required to contain the empty graph, so that terminal objects are among the M-limits. (If we don’t insist on a terminal object, we get rather odd examples, such as categories with ternary products and such other limits as are consequences of these, namely the products A_{1} × A_{2} ⋯ × A_{n} with n odd; the reader will easily construct even wilder examples.) Both in order to formulate and prove Theorem 1.4, and to state our central result with precision, we need to introduce the following concept (called “closure” in the Albert-Kelly paper [AK], where it was considered in much greater generality):

1.2 Definition. The saturation of a class M of finite graphs is the class \overline{M} of all those finite graphs A such that every category with M-limits has A-limits. We call M saturated when M = \overline{M}; and we call the classes M and N equivalent, writing M ∼ N, when they have the same saturation.

Remark. It is proved in [AK] that every functor between M-complete categories that preserves M-limits (in the usual, non-strict, sense) also preserves \overline{M}-limits. We recall in Theorem 3.1 below the explicit condition for A to lie in \overline{M}. Note that the concept of saturation is context-sensitive : here we are speaking about classes of finite graphs, but there are analogous concepts for classes of finite categories, of arbitrary small categories, or of the weights involved in weighted limits.

There is of course an evident “forgetful” functor U_{\overline{M},M} : Cat\overline{M} ⟶ Cat_{M}, which is over Cat in the sense that it commutes with the forgetful functors Cat_{M} ⟶ Cat and Cat\overline{M} ⟶ Cat; but except when M = \overline{M} it fails to be an equivalence or indeed to be fully faithful. The reason is like that for the failure of Cat_{LEX} ⟶ Cat_{P B+T} to be fully faithful : there is no reason why a functor strictly preserving the chosen pullbacks and the chosen terminal object should strictly preserve the other chosen finite limits, such as (say) a ternary product – for these other choices may be quite arbitrary. The following simple example illustrates the point starkly:

1.3 Example. Certainly M ∼ N if M is empty and N consists of the single graph having one object and no arrows. Here Cat_{M} = Cat; while an object of Cat_{N} is a category A along with an isomorphism α_{A} : L(A) ⟶ A in A for each object A ∈ A, and a morphism in Cat_{N} is to preserve these isomorphisms strictly. So the forgetful Cat_{N} ⟶ Cat_{M} is not fully faithful.

In Example 1.3, however, there is a “natural” functor Cat_{M} ⟶ Cat_{N} over Cat, given by choosing all the α_{A} to be identity maps. In the Appendix we prove that this is no coincidence : whenever M ⊂ N ⊂ \overline{M} there is a functor Γ : Cat_{M} ⟶ Cat_{N} over Cat with U_{N ,M}Γ = 1. Based on this result (which we actually formulate at the level natural to it, of general weighted limits for enriched categories), together with Lemma 2.2 below, we are able in the Appendix to prove:

1.4 Theorem. If M and N are equivalent classes of finite graphs and Cat_{M} is monadic over Gph, so is Cat_{N}.

We can now formulate precisely our central result:

1.5 Main Theorem. For a set M of finite graphs containing the empty graph, U_{M} : Cat_{M} ⟶ Gph is monadic if and only if M ∼ N where N is one of the sets {∅}, {Eq, ∅}, {Pr, ∅}, {Pb, ∅}; which correspond (for suitable choices of the set M equivalent to N) to Cat_{T} , Cat_{EQ+T} , Cat_{F P}, and Cat_{LEX}, respectively.

Our first result needed for the proof of Theorem 1.5 concerns equalizers : we prove in Theorem 2.5 that, for any set M of finite graphs such that M-completeness implies the existence of equalizers (that is to say, such that Eq ∈ \overline{M}), the category Cat_{M} is monadic over Gph. This result can also be derived from Proposition 47 of [CL]. However that proposition is stated without proof (and the preceding Proposition 46, which essentially states the monadicity of Cat_{{Eq}} over Gph, has a proof completely different from ours below); accordingly we elect to present a full proof in Section 2, and in fact one which extends easily to cover an important class of weighted limits – see Remark 2.7. Of course Theorem 2.5 provides yet another proof of the monadicity over Gph of Cat_{LEX}.

Section 3 presents a number of rather technical results on the saturation \overline{M} of M. Using those results we are able, in Section 4, actually to characterize those sets M of finite graphs with ∅ ∈ M for which Cat_{M} is monadic over Gph; and then, based on that characterization, we present a proof of Theorem 1.5. Finally, Section 5 comprises the Appendix mentioned above.

1.6 Notational Remarks. Throughout the paper we denote by M^{∗} the free category on a graph M : the objects of M^{∗} are the nodes (or vertices, or objects) of M, and the hom-set M^{∗}(a, b) is the set of all paths

a = p_{0} ⟶^{α_{1}} p_{1} ⟶^{α_{2}} p_{2} ⋯ ⟶^{α_{n}} p_{n} = b

in M, including when a = b the empty path, giving the identity morphism; here, of course, the α_{i} are elements of what are variously called the edges, or arrows, or morphisms, of M. We often write a ∈ M, rather than a ∈ ob M, to mean that a is an object of M; similarly we often use A ∈ C to mean that A is an object of the category C.

Note: When dealing with the following common graphs, we may sometimes loosely confuse M with M^{∗} — as when we write [Eq, Set] for the more correct [Eq^{∗}, Set], to denote the functor-category.

Eq, the equalizer domain  e_{1}  [figure: s; t] e_{2}

Pb, the pullback domain [figure: e_{1}; s; e_{3}; t; e_{2}]

Pr, the binary-product domain  e_{1}  e_{2}
Le, the limit-of-endomorphism domain  e  \overline{s} e

∅, the empty domain.

We moreover use henceforth this (e_{i}, s, t) notation for the graphs above, without further explanation.

1.7 Foundational remarks. We need to be precise about matters of size. We suppose chosen once for all an inaccessible cardinal ∞, whereupon a set is said to be small when its cardinal is less than ∞; we write Set for the category of small sets. A category A is small when its set of arrows is small, and is locally small when each hom-set A(A, B) is small; we write Cat for the category (or the 2-category, in some contexts) of small categories, and CAT for the category (or 2-category) of locally-small categories. In order that CAT be an honest category, we must also put some restriction on the size of ob A for a locally-small A — by supposing that ob A has cardinal less than or equal to some inaccessible cardinal ∞′ ⩾ ∞, which is usually taken to be ∞ itself. (When, however, we speak of locally-finite categories, which is the case ∞ = ω, it is usual to take ∞′ to be a larger inaccessible.)

2. Equalizers Imply Monadicity

2.1 We start with a general necessary and sufficient condition for the monadicity over Gph of Cat_{M} (where M is a set of graphs). The forgetful functor U_{M} : Cat_{M} ⟶ Gph under study is the composite of the forgetful functor E_{M} : Cat_{M} ⟶ Cat and the evident forgetful functor V : Cat ⟶ Gph. (We use the usual convention of ignoring V notationally : a category is denoted by the same letter as the underlying graph, and similarly for functors.) Since both E_{M} and V are monadic functors (see [LR]), the functor U_{M} = V · E_{M} is always a right adjoint. We conclude from Beck’s Theorem, in the form given by Mac Lane as Theorem 1 on page 147 of [ML], that U_{M} is monadic if and only if creates coequalizers of U_{M}-split pairs.

Let us therefore consider a pair of morphisms P_{1}, P_{2} : K ⟶ L in Cat_{M} and a split coequalizer

[figure: U_{M}(K); U_{M}(P_{1}), U_{M}(P_{2}); \underline{J}; U_{M}(L); Q; \underline{I}; C]

in Gph; that is to say :

Q · U_{M}(P_{1}) = Q · U_{M}(P_{2}) ; Q · I = id ; U_{M}(P_{1}) · J = id ; U_{M}(P_{2}) · J = I · Q .

Since V is a monadic functor, there is a unique category-structure on the graph C for which Q is the underlying homomorphism of a functor (called Q); and moreover

[figure: K; P_{1}; P_{2}; L; Q; C]

is a coequalizer in Cat. So U_{M} creates the U_{M}-split coequalizer above if and only if (i) there is a unique way of so assigning a limit to each diagram D : M ⟶ C with M ∈ M that the functor Q : L ⟶ C strictly preserves M-limits, and (ii) Q is then the coequalizer of P_{1} and P_{2} not only in Cat but also in Cat_{M}. When this is so, each D : M ⟶ C must have as its assigned limit the cone (Qα_{d} : QL ⟶ QIDd = Dd)_{d∈M}, where (α_{d} : L ⟶ IDM) is the assigned limit-cone for the diagram ID : M ⟶ L; in these circumstances, let us write lim D = Q lim ID, it being understood that such equations assert the equality not only of the objects but of the cones as well. Until further notice, lim denotes the assigned limit.

2.2 Lemma. For any class M of graphs, U_{M} : Cat_{M} ⟶ Gph is monadic if and only if, given morphisms P_{1}, P_{2} : K ⟶ L in Cat_{M} whose coequalizer

[figure: K; P_{1}; P_{2}; L; Q; C]

in Cat has a splitting in Gph, given by homomorphisms I : C ⟶ L and J : L ⟶ K with

QI = id , P_{1}J = id , and P_{2}J = IQ ,

then C has and Q preserves M-limits (in the usual sense, that Q takes any M-limit-cone in L to a limit-cone in C). In fact, it suffices that Q preserve, in this usual sense, the limit of ID : M ⟶ L for each diagram D : M ⟶ C with M ∈ M.

Proof. The “only if” part is clear from the above, and we turn to “if”. If Q is to preserve M-limits strictly, we are forced to assign as the limit of D : M ⟶ C the cone (Qα_{d}), where (α_{d} : L ⟶ IDd) is lim ID; and we can do this when (Qα_{d}) is a limit-cone. So now lim D = Q lim ID. We must verify next that Q strictly preserves the assigned M-limits. In fact, for E : M ⟶ L with M ∈ M we have

Q lim E = Q lim P_{1}JE since P_{1}J = 1

= QP_{1} lim JE since P_{1} preserves M-limits strictly = QP_{2} lim JE since QP_{2} = QP_{1} = Q lim P_{2}JE since P_{2} preserves M-limits strictly = Q lim IQE since IQ = P_{2}J = lim QE by our choice of M-limits in C .

Finally we must verify that the coequalizer Q of P_{1} and P_{2} in Cat is also their coequalizer in Cat_{M}. This will follow if a functor R : C ⟶ D, where D ∈ Cat_{M}, preserves Mlimits strictly whenever RQ does so; and this is so because

R lim D = RQ lim ID = lim RQID = lim RD.

2.3 Remark. In the following proof we work with finite diagrams D : M ⟶ X in categories X having equalizers. Let us call a collection of morphisms (α_{d} : A ⟶ Dd) for d ∈ M (with no side conditions) a pre-cone over D, writing it as α : A ⟶ D. There is a universal map e_{α} : E_{α} ⟶ A having the property that α·e_{α} is a cone over D (where α · e_{α} is the collection of all α_{d}e_{α} for d ∈ M). In fact, e_{α} is a joint equalizer of the pairs Dm · α_{d}, α_{d′} : A ⟶ Dd′ for all morphisms m : d ⟶ d′ of M. We call e_{α} a conifier of the pre-cone α. Of course, α is a cone precisely when e_{α} is an isomorphism. Moreover functors preserving equalizers preserve (in the obvious non-strict sense) conifiers of finite diagrams.

2.4 Notation. Recall that Eq denotes the graph consisting of a parallel pair of morphisms between two objects; see 1.6.

2.5 Theorem. Let M be a set of finite graphs whose saturation \overline{M} contains Eq. Then Cat_{M} is monadic over Gph.

Proof. We are going to verify the condition of Lemma 2.2, that Q preserves the limit of ID for each D : M ⟶ C with M ∈ M; we retain the notation of that lemma. The proof consists of the five parts (a) - (e) below. First, a property of Q used in the proof will be established. Recall that, since Eq ∈ \overline{M}, the categories K and L have equalizers, and the functors P_{1} and P_{2} preserve equalizers. We say that a parallel pair p′, p′′ : A ⟶ B in L is Q-equalized if and only if Qp′ = Qp′′; then

(a) Q maps the equalizer of each Q-equalized pair p′, p′′ to an isomorphism in C. Proof. Let e : E ⟶ JA be an equalizer of Jp′, Jp′′ in K. Then since P_{1} preserves equalizers and P_{1}J = id, we see that P_{1}e is an equalizer of p′, p′′ in L. It is sufficient to show that QP_{1}e is an isomorphism in C. Since P_{2} preserves equalizers and P_{2}J = IQ, we see that P_{2}e is an equalizer of IQp′, IQp′′. But by assumption, the last two morphisms are equal, so that P_{2}e is an isomorphism in L. It follows that QP_{2}e = QP_{1}e is an isomorphism in C.

(b) Given a finite collection of parallel pairs in L with a common domain, each of

which is Q-equalized, then Q maps their joint equalizer to an isomorphism in C. Proof. This is an easy induction based on (a) : suppose p′_{i}, p′′_{i} : A ⟶ B_{i} are Qequalized pairs (i = 1_{,} ⋯, n) and let e be a joint equalizer of these n pairs. If n = 1, then Qe is an isomorphism by (a). For n > 1 let \overline{e} be a joint equalizer of the pairs p′_{i}, p′′_{i}, for i = 1, ⋯, n − 1; then Q\overline{e} is an isomorphism by the induction hypothesis. Let e be an equalizer of p′_{n}\overline{e}, p′′_{n}\overline{e}; since this last pair is Q-equalized, Qe is an isomorphism by (a). And \overline{e}e is clearly a joint equalizer of the given pairs.

(c) Q(lim ID) is a weak limit of D. Proof. Let us denote the cone lim ID by α : A ⟶ ID. Then, since α is a cone over ID (and Q is a functor), we see that Qα is a cone over QID = D. Now let β : B ⟶ D be a cone over D. Then Iβ is a pre-cone over ID, and we form as in 2.3 a conifier e_{Iβ} : E_{Iβ} ⟶ IB of Iβ. Then e_{Iβ} is a joint equalizer of Q-equalized pairs : indeed, for each pair IDm · Iβ_{d}, Iβ_{d′}, where m : d ⟶ d′ is a morphism of M, we have, since QI = id, the equality

Q(IDm · Iβ_{d}) = Dm · β_{d} = β_{d′} = Q(Iβ_{d′}) .

By (b), we conclude that

Qe_{Iβ} is an isomorphism .

Next, since Iβ · e_{Iβ} is a cone over ID, it factorizes uniquely through the limit-cone α = lim ID; that is, there is a unique morphism f_{β} such that the diagram

E_{Iβ}

[figure: e_{Iβ}; f_{β}]

(3)  IB  A

[figure: Iβ; α]

ID

commutes. Consequently, QIβ · Qe_{Iβ} = Qα · Qf_{β}, and since β = QIβ, while Qe_{Iβ} is invertible, this yields the desired factorization of β through the cone Qα; in fact we have a canonical factorization

β = Qα · (Qf_{β} · [Qe_{Iβ}]^{−1}) .

(d) When we take for β above the cone Qα itself, the corresponding f_{Qα} in (3) has Qf_{Qα} invertible.

Proof. Let α′ : A′ ⟶ JID be the chosen limit-cone of JID in K. Let us form a conifier e_{Jα} of Jα in K; then we have a unique morphism g such that the following square

E_{Jα}

[figure: e_{Jα}; g]

(4)  JA  A′

[figure: Jα; α′]

JID

commutes in K. Consider the image of this square under P_{1} and P_{2}. Since both are morphisms of Cat_{M} (that is, strictly M-continuous), we have P_{i}α′ = α for i = 1, 2. Moreover both preserve equalizers, and thus preserve conifiers. For P_{1} this means that P_{1}e_{Jα} is a conifier of P_{1}Jα = α; and since α is a cone, P_{1}e_{Jα} is an isomorphism. The square above is mapped by P_{1} to the following square:

P_{1}E_{Jα}

[figure: P_{1}e_{Jα}; P_{1}g]

A  A

[figure: α; α]

ID

Since α is a limit cone, P_{1}g = P_{1}e_{Jα}; so that P_{1}g too is an isomorphism. Next, P_{2} maps (4) to

P_{2}E_{Jα}

[figure: P_{2}e_{Jα}; P_{2}g]

IQA  A

[figure: IQα; α]

ID

Since P_{2}e_{Jα} is, like e_{IQα}, a conifier of IQα, there is an isomorphism u : E_{IQα} ⟶ P_{2}E_{Jα} with e_{IQα} = (P_{2}e_{Jα})·u. Now we conclude that f_{Qα} = (P_{2}g)·u because α is a limit-cone with (see (3)) α · f_{Qα} = IQα · e_{IQα} = IQα · (P_{2}e_{Jα}) · u = α · (P_{2}g) · u. Applying Q, we see that Qf_{Qα} = QP_{2}g · Qu; and since QP_{2}g = QP_{1}g is an isomorphism and Qu is an isomorphism, this proves (d). To complete the proof of the theorem, it remains only to prove :

(e) Qα is a jointly monomorphic cone. Proof. Let u_{1}, u_{2} : B ⟶ QA be morphisms with Qα · u_{1} = Qα · u_{2}; we show that u_{1} = u_{2}. Let R be the family of parallel pairs in L, with the domain IB, consisting of the following pairs:

(α) all the pairs

[figure: IB; Iu_{1}; Iu_{2}; IQA; IQα_{d}; IDd]
where d ∈ M;

(β) all the pairs

[figure: IB; Iu_{t}; IQA; IQα_{d′}; IDd′]

[figure: IQα_{d}; IDm]

IDd

where m : d ⟶ d′ is a morphism in M and t = 1, 2. Observe that all these pairs are Q-equalized : for (α) we have

Q(IQα_{d} · Iu_{1}) = Qα_{d} · u_{1} = Qα_{d} · u_{2} = Q(IQα_{d} · Iu_{2}) ,

and for (β) this follows from the fact that Qα like α is a cone, whence

Q(IDm · IQα_{d}) = Dm · Qα_{d} = Qα_{d′} = Q(IQα_{d′}) .

By (b) above, if h : H ⟶ IB is the joint equalizer of all the pairs in R, then

(5)  Qh is an isomorphism in C .

It is clear, from the pairs (β) of R, that IQα · Iu_{t} · h is a cone over ID (for t = 1, 2); and the universal property of the conifier e_{IQα} implies that there exists a unique morphism v_{t} : H ⟶ E_{IQα} with

(6)  Iu_{t} · h = e_{IQα} · v_{t} for t = 1, 2 .

Thus, we get a diagram as follows:

H

[figure: h; v_{1}; v_{2}]

IB  E_{IQα}

[figure: Iu_{1}; Iu_{2}; e_{IQα}; f_{Qα}]

IQA  A

[figure: IQα; α]

ID

Because the pairs (α) lie in R, it follows from the commutativity above that

α · (f_{Qα} · v_{1}) = α · (f_{Qα} · v_{2}) .

Now α = lim ID is a jointly monomorphic cone, so that

f_{Qα} · v_{1} = f_{Qα} · v_{2} .

Next (d) gives

Qv_{1} = Qv_{2} ,

whence (6) yields Q(Iu_{1} · h) = Q(Iu_{2} · h); that is,

u_{1} · Qh = u_{2} · Qh ;

which, together with (5), gives u_{1} = u_{2}, as desired

2.6 Remark. On the one hand, the theorem above implies Proposition 47 of [CL]; on the other, we could of course have greatly simplified the proof of our theorem by an appeal to the result of [CL]. We gave in the Introduction our reason for providing an independent complete proof.

2.7 Remark. In Section 5 below we recall the notion of the limit {ϕ, T } of T : K ⟶ C weighted by ϕ : K ⟶ Set, where K is a small category and ϕ, T are functors. This has the special case where K is the free category M^{∗} on a graph M, so that to give ϕ and T is just to give graph-homomorphisms θ : M ⟶ Set and D : M ⟶ C; then we may as well write {θ, D} in place of {ϕ, T } for the limit. Of course the classical limit, lim D, is obtained by taking for θ the homomorphism constant at the set 1. It is easy to see that the proof of Theorem 2.5 extends, with only minor changes, to the case where the set M of finite categories is replaced by a set of “finite weights” θ : M ⟶ Set with graphs as domains, such a weight being called finite when M is a finite graph and θd is a finite set for each d ∈ M. For example, when M is the graph b ⟵ a ⟶ c and θa = ∅ (the empty set) while θb = θc = 1 (the singleton), a category C admits (M, θ)-limits precisely when it has binary products B × C, not for all pairs B, C, but for such pairs as belong to some diagram of the form B ⟵ A ⟶ C; this is quite an important kind of completeness. As for the changes needed in the proof, the cone β : B ⟶ D is now replaced by a natural transformation β : θ ⟶ C(B, D−), and here e_{Iβ} : E_{Iβ} ⟶ IB, for instance, is replaced by the joint equalizer of the finite set of pairs

IDm · Iβ_{d}(x), I(Dm · β_{d}(x)) : IB ⟶ IDd′ ,

where m : d ⟶ d′ is an edge in M and x ∈ θd; and similarly for the other steps in the proof.

3. Some properties of the saturation

The saturation \overline{M} has been fully characterized in [AK] as follows (see the Appendix for the more general case of weighted limits) : given a small graph A we denote by Y : A^{∗} ⟶ [A^{∗}, Set]^{op} the usual Yoneda embedding sending a to A^{∗}(a, −). Let M(A) denote the closure of the set of all these representables A^{∗}(a, −) under M-limits in [A^{∗}, Set]^{op}. That is, M(A) is the smallest full replete subcategory of [A^{∗}, Set]^{op} which contains Y (A^{∗}) and is closed in [A^{∗}, Set]^{op} under the formation of M-limits for all M ∈ M.

3.1 Theorem. [AK]. A graph A belongs to the saturation of a class M of graphs if and only if the functor Δ1 : A^{∗} ⟶ Set (the functor constant at 1 ∈ Set) lies in M(A).

3.2 Remark. In order to avoid variance confusion, we work with the dual description : A ∈ \overline{M} if and only if Δ1 lies in the closure M(A) of the representables A^{∗}(a, −) under M^{op}-colimits in [A^{∗}, Set], where M^{op} = {M^{op}|M ∈ M}. We will thus be concerned with diagrams D : D ⟶ [A^{∗}, Set] having Δ1 ≅ colimit D, or equivalently, diagrams such that, for each object a ∈ A, if D(a) denotes D evaluated at a — that is, the composite of D with the functor eval_{a} : [A^{∗}, Set] ⟶ Set — then 1 ≅ colim D(a) in Set for all a ∈ A.

3.3 Definition. A graph is said to be poor if it has no pair of objects a, b such that

(i) there exists a pair of disjoint paths from a to b (that is, two paths with no

common arrow); and

(ii) there exists no path from b to a.

3.4 Proposition. For every non-poor graph A the saturation of {A, ∅} contains Eq.

Proof. By Theorem 3.1 we are to prove that Δ1 : Eq ⟶ Set lies in the closure of Y (Eq^{op}) under A^{op}-colimits and the initial object Δ∅ (the constant functor with value the empty set ∅) in [Eq, Set]. To this end, we shall find a diagram D : A^{op} ⟶ [Eq, Set] which maps A^{op} into the full subcategory {Y e_{1}, Y e_{2}, Δ∅} of [Eq, Set], and satisfies Δ1 ≅ colim D. Recall from 1.6 that Eq has edges s, t : e_{1} ⟶ e_{2}.

Since A is not poor, it has objects a and b satisfying (i) and (ii) in Definition 3.3. Denote by A_{1} the full subgraph of A determined by all objects x with the hom-set A^{∗}(x, a) non-empty and by A_{2} the full subgraph of A determined by all objects x ∉ A_{1} with A^{∗}(x, b) non-empty. We define D on objects x of A^{op} by

Dx = \{ \begin{matrix}Y e_{1} & if x ∈ A_{1}, \\ Y e_{2} & if x ∈ A_{2}, \\ Δ∅ & otherwise. \end{matrix}

To define D on morphisms, let the disjoint paths of Definition 3.3 be

a = p_{0} ⟶^{α_{0}} p_{1} ⟶^{α_{1}} ⋯ ⟶^{α_{n}} p_{n} = b

and

a = q_{0} ⟶^{β_{0}} q_{1} ⟶^{β_{1}} ⋯ →^{β_{m}} q_{m} = b .

Since A^{∗}(b, a) = ∅, there exists i^{∗} ∈ {1, ⋯, n} with

p_{i^{∗}−1} ∈ A_{1} and p_{i^{∗}} ∈ A_{2}

as well as j^{∗} ∈ {1, ⋯, m} with

q_{j^{∗}−1} ∈ A_{1} and q_{j^{∗}} ∈ A_{2} .

We define Dh : Dy ⟶ Dx for a morphism h : x ⟶ y of A as follows. First, Dh = 1 whenever Dx = Dy; next, the case of y ∉ A_{1} ∪A_{2} is clear (since Dy is the initial object), and so is the case x = y (for then Dh = id). The only remaining case has x ∈ A_{1} and y ∈ A_{2}. We have just two morphisms from Dy = Y e_{2} to Dx = Y e_{1}, namely Y s and Y t. For h : x ⟶ y with x ∈ A_{1} and y ∈ A_{2}, we set

Dh = Y s if h ≠ α_{i}∗ , and Dα_{i}∗ = Y t .

We claim that Δ1 ≅ colim D in [Eq, Set]; that is, the diagrams D(e_{1}) and D(e_{2}) : A^{op} ⟶ Set (see 3.2) have each a singleton colimit.

(i) D(e_{1}) has the value {id} on objects of A_{1} and ∅ elsewhere. Since A_{1} is a connected graph, we conclude that 1 ≅ colim D(e_{1}).

(ii) D(e_{2}) has the value {s, t} on objects of A_{1}, the value {id} on objects of A_{2}, and the value ∅ elsewhere. Observe that A_{1} and A_{2} are connected graphs, and that D(e_{2}) maps each arrow of A_{1} to the identity map of {s, t}. Moreover, since Dα_{i}∗ = Y t and Dβ_{j∗} = Y s, the diagram D(e_{2}) has D(e_{2})α_{i}∗ mapping id to t and D(e_{2})β_{j∗} mapping id to s; from which we immediately conclude that colim D(e_{2}) is a singleton set : in fact, all the elements of type id are identified in the colimit (since A_{2} is connected), as are all the elements of type s (since A_{1} is connected), and all the elements of type t (for the same reason); while the final remark shows that id and t and s are also identified.

3.5 Definition. A graph A is said to be rooted if each component of A^{∗} has a weaklyinitial object. Note that the empty graph ∅, having no components, is rooted.

3.6 Proposition. For every finite non-rooted graph A, the saturation of {A, ∅} contains all finite graphs.

Proof. It is clearly sufficient to prove that the saturation of {A, ∅} contains Pb. That is, that Δ1 : Pb ⟶ Set lies in the closure under A^{op}-colimits of Y (Pb^{op}) and the initial object Δ∅ in [Pb, Set]. Recall from 1.6 that Pb has edges s : e_{1} ⟶ e_{3} and t : e_{2} ⟶ e_{3}. We shall find a diagram D : A^{op} ⟶ [Pb, Set] mapping A^{op} into the full subcategory {Y e_{1}, Y e_{2}, Y e_{3}, Δ∅} of [Pb, Set] and satisfying Δ1 ≅ colim D. The diagram D is specified on objects by defining full subgraphs A_{1}, A_{2}, A_{3} of A and putting

Dx = \{ \begin{matrix}Y e_{i} & if x ∈ A_{i} for some i = 1, 2, 3, \\ Δ∅ & otherwise . \end{matrix}

To define A_{1}, A_{2}, A_{3}, choose a component of A^{∗} without any weakly initial object, and denote by Ã the preordered reflection of that component. Then Ã is a finite, connected, preordered set with no least element. Consequently, Ã has two minimal elements that are incomparable. Choose a, b ∈ Ã as two incomparable minimal elements with a shortest zig-zag from a to b; such a zig-zag exists since Ã is connected. It is obvious that this zig-zag has the form

a ⩽ c and c ⩾ b for some c ∈ Ã .

Thus in A^{∗} we have paths

a = p_{0} ⟶^{α_{1}} p_{1} ⟶^{α_{2}} ⋯ ⟶^{α_{n}} p_{n} = c

and

b = q_{0} ⟶^{β_{1}} q_{1} ⟶^{β_{2}} ⋯ ⟶^{β_{m}} q_{m} = c .

We now take the A_{i} to be the following full subgraphs of A:

A_{1} = {x ∈ A | A^{∗}(x, a) ≠ ∅} ,
A_{2} = {x ∈ A | A^{∗}(x, b) ≠ ∅} ,

and

A_{3} = {x ∈ A − (A_{1} ∪ A_{2}) | A^{∗}(x, c) ≠ ∅} .

Since a and b are minimal and incomparable, A_{1} and A_{2} are disjoint, and moreover A^{∗}(c, a) = ∅ = A^{∗}(c, b); thus there exist i^{∗} ∈ {1, ⋯, n} with

p_{i^{∗}−1} ∈ A_{1} and p_{i^{∗}} ∈ A_{3}

and j^{∗} ∈ {1, ⋯, m} with

q_{j^{∗}−1} ∈ A_{2} and q_{j^{∗}} ∈ A_{3} .

Define Dh : Dy ⟶ Dx for a morphism h : x ⟶ y of A as follows. The only cases to be considered are x ∈ A_{1} ∪ A_{2} and y ∈ A_{3} (since the Y p_{i}, for i ≠ 1, 2, 3, have only trivial endomorphisms id, and Δ∅ is the initial object, while A^{∗}(x, y) = ∅ if x ∈ A_{3} and y ∈ A_{1} ∪ A_{2}). We put, as we must,

Dh = Y s if x ∈ A_{1}, y ∈ A_{3}

and

Dh = Y t if x ∈ A_{2}, y ∈ A_{3} .

We claim that 1 ≅ colim D(e_{i}) in Set for i = 1, 2, 3.

(i) 1 ≅ colim D(e_{1}). In fact, D(e_{1}) takes the value {id} for objects of A_{i} and ∅ elsewhere, and A_{1} is a connected graph.

(ii) 1 ≅ colim D(e_{2}) — this is analogous to (i).

(iii) 1 ≅ colim D(e_{3}). In fact, D(e_{3}) takes the values {s}, {t}, {id} for objects of A_{1}, A_{2} and A_{3} respectively, and ∅ elsewhere. Each of the graphs A_{1}, A_{2}, A_{3} is connected, and D(e_{2})α_{i}^{∗} takes {id} to {s} while D(e_{3})β_{j}^{∗} takes {id} to {t}. It follows that 1 ≅ colim D(e_{3}) in Set.

3.7 Definition. A graph A is said to be smooth if every cycle C in A contains every arrow whose codomain lies on C. That is, if C is

a = p_{0} ⟶^{α_{1}} p_{1} ⟶^{α_{2}} ⋯ ⟶^{α_{n}} p_{n} = a ,

then the only arrow with codomain a in A is α_{n}.

3.8 Proposition. For every non-smooth graph A the saturation of {A, Pr, ∅} contains all finite graphs.

Proof. Since A is not smooth it has a cycle

a = p_{0} ⟶^{α_{1}} p_{1} ⟶^{α_{2}} ⋯ ⟶^{α_{n}} p_{n} = a

and a morphism β : b ⟶ a with β ≠ α_{n}. Case I. Suppose A^{∗}(a, b) = ∅.

We shall prove that Eq lies in the closure of {A, Pr, ∅}; this obviously implies that all finite graphs lie in that closure. We are going to find a diagram D : A^{op} ⟶ [Eq, Set] whose values lie in the full subcategory {Y e_{1}, Y e_{2} + Y e_{2}, Δ∅} of [Eq, Set], and for which Δ1 ≅ colim D in [Eq, Set]. This proves that Δ1 lies in the closure of Y (Eq) under finite coproducts and A^{op}-colimits, whereupon we apply Theorem 3.1.

Denote by A_{1} the full subgraph of A determined by all objects x with A^{∗}(x, b) ≠ ∅ and A_{2} the full subgraph of A determined by all objects x ∉ A_{1} with A^{∗}(x, a) ≠ ∅. The definition of D on objects x of A^{op} is:

Dx = \{ \begin{matrix}Y e_{1} & if x ∈ A_{1} , \\ Y e_{2} + Y e_{2} & if x ∈ A_{2} , \\ Δ ∅ & otherwise. \end{matrix}

Denote by r : Y e_{2} + Y e_{2} ⟶ Y e_{1} the morphism with components Y s and Y t, and by q : Y e_{2} + Y e_{2} ⟶ Y e_{2} + Y e_{2} the canonical isomorphism (interchanging the two copies of Y e_{2}). We define Dh : Dy ⟶ Dx for a morphism h : x ⟶ y of A as follows:

(a) if x ∈ A_{1} and y ∈ A_{2}, then Dh = r ;

(b) if x, y ∈ A_{2}, then Dh = 1 if h ≠ α_{1} and Dα_{1} = q.

In the remaining cases (x, y ∈ A_{1} or y ∉ A_{1} ∪ A_{2}), the value of Dh is clear. We claim that Δ1 ≅ colim D in [Eq, Set]:

(i) D(e_{1}) has the value {id} on objects of A_{1} and ∅ elsewhere. Since A_{1} is a connected graph, it follows that 1 ≅ colim D(e_{1}) in Set.

(ii) D(e_{2}) has the value {s, t} on objects of A_{1}, the value {id} + {id} on objects of A_{2}, and the value ∅ elsewhere. Denote, for simplicity, the two copies of id in {id} and {id} by id^{1} and id^{2}. Observe that A_{1} is connected and D(e_{2}) maps arrows of A_{1} to the identity map. Therefore, all the elements of the form s are identified in colim D(e_{2}), as are all those of the form t. Further, the graph A_{2} is connected, and remains connected when α_{1} is deleted from the arrows of A_{2}; since D maps all arrows of A_{2} except α_{1} to the identity map, we see that all elements of the form id^{1} are identified in colim D(e_{2}), as are all those of the form id^{2}. Finally, from Dα_{1} = q and Dβ = r we see that (De_{2})α_{1} sends id^{1} to id^{2} and id^{2} to id^{1}, while (De_{2})β sends id^{1} to s and id^{2} to t. Consequently, 1 ≅ colim D(e_{2}). Case II. Suppose A^{∗}(a, b) ≠ 0.

Here, again, we show that Eq lies in the closure of {A, Pr, ∅} by presenting a diagram D : A^{op} ⟶ [Eq, Set] whose values lie now in the full subcategory {Y e_{1} + Y e_{2}, Δ∅} and which is such that Δ1 ≅ colim D.

Let A_{0} be the full subgraph of A determined by all objects x with A^{∗}(x, a) ≠ ∅. We define D on objects x of A^{op} by Dx = Y e_{1} + Y e_{2} if x ∈ A_{0}, Dx = Δ∅ otherwise. Denote by \overline{Y s}, \overline{Y t} : Y e_{1} + Y e_{2} ⟶ Y e_{1} + Y e_{2} the morphisms whose first components are equal to the first injection of Y e_{1} + Y e_{2} and whose second components are Y s or Y t respectively, composed with this first injection. We define Dh : Dy ⟶ Dx for a morphism h : x ⟶ y of A as follows: the only case to consider is x, y ∈ A_{0}, and then Dh = id if h is neither β nor α_{n}, while Dβ = \overline{Y t} and Dα_{n} = \overline{Y s}. We shall show that Δ1 ≅ colim D.

(i) D(e_{1}) has the value {id} on objects of A_{0} and ∅ elsewhere. Since A_{0} is connected, we conclude that 1 ≅ colim D(e_{1}).

(ii) D(e_{2}) has the value {s, t, id} on objects of A_{0} and ∅ elsewhere. First observe that A_{0} is a connected graph and remains connected even if α_{n} and β are removed from the arrows of A_{0}. (In fact, we have a path from a to b. Take the shortest path possible; then certainly α_{n} is not among the arrows of that path. Thus after removing α_{n} we still have a path from a to b, which allows us to remove β without disconnecting the graph). All arrows in A_{0} except α_{n} and β are mapped by D(e_{2}) to the identity mapping; thus all elements of the same type (s, t or id) are identified in colim D(e_{2}). Since D(e_{2}) maps α_{n} and β respectively to the mappings f and g, where f(id) = f(s) = s and f(t) = t, while g(id) = g(t) = t and g(s) = s, we conclude that 1 ≅ colim D(e_{2}).

3.9 Proposition. For every graph A with a cycle the saturation of {A, ∅} contains Le.

Proof. Recall from 1.6 that Le has a single edge e : s ⟶ s. We shall find a diagram D : A^{op} ⟶ [Le, Set], mapping A^{op} into the full subcategory {Y e, Δ∅} of [Le, Set], for which Δ1 ≅ colim D.

Let α : a ⟶ b be an arrow lying on a cycle of A. Denote by A_{0} the full subgraph of A determined by all objects x with A^{∗}(x, a) ≠ ∅. Observe that A_{0} remains a connected graph after the arrow α has been deleted from it. Define D on objects x by Dx = Y e for x ∈ A_{0}, Dx = Δ∅ otherwise. For morphisms h : x ⟶ y of A with x, y ∈ A_{0} put Dh = id if h ≠ α and Dα = Y s. Then Δ1 ≅ colim D.

In fact, after evaluating at e we get the diagram D(e) in Set whose value is the set {s^{n}}_{n∈ω} on objects of A_{0} and is the set ∅ elsewhere. Since each arrow in the connected graph obtained by deleting α from A_{0} is mapped by D(e) to an identity map, and since D(e)α is the mapping s^{n} ⟼ s^{n+1} for n ∈ ω, it is clear that 1 ≅ colim D(e) in Set.

3.10 Proposition. The saturation of {Eq} contains all finite, connected, rooted graphs; that is, it contains every finite graph A for which A^{∗} has a weakly-initial object.

Proof. Let r be a weakly-initial object in A^{∗}. Thus for every object x we can choose a morphism ϕ_{x} : r ⟶ x in A^{∗}; in particular we choose ϕ_{r} = id.

It is sufficient to prove that Δ1 : A^{∗} ⟶ Set lies in the closure of Y (A^{op}) under coequalizers in [A^{∗}, Set]. To do this, consider for each arrow ψ : x ⟶ y in A the pair ϕ_{y}, ψϕ_{x} : r ⟶ y in A^{∗} and its image under Yoneda, namely Y (ϕ_{y}), Y (ψϕ_{x}) : Y y ⟶ Y r; and write t : Y r ⟶ T for the joint coequalizer in [A^{∗}, Set] of these latter pairs. Since A is finite, T certainly lies in the closure of Y (A^{op}) under coequalizers; and we shall now show that T ≅ Δ1. This is equivalent to saying that, for each object a of A, the joint coequalizer T z of the pairs

A^{∗}(y, z) [figure: – · ϕ_{y}; – · (ψϕ_{x})] A^{∗}(r, z)  for all ψ: x ⟶ y in A

is a singleton set. In fact, T z is isomorphic to A^{∗}(r, z)/ ∼, where ∼ is the smallest equivalence relation such that

αϕ_{y} ∼ αψϕ_{x} for all ψ : x ⟶ y in A and all α : y ⟶ z in A^{∗} .

By the transitivity of ∼ we conclude that the property above holds, in fact, for all ψ : x ⟶ y in A^{∗}. In particular, if we set y = z, α = id, and x = r we thus obtain

ϕ_{z} ∼ ψ for all ψ : r ⟶ z in A^{∗} .

This means that ∼ has precisely one equivalence class, which concludes the proof.

3.11. We next want to prove that the saturation of {Le} contains all connected, rooted, poor, smooth graphs. We first establish a result about the nature of such graphs. Recall that a non-identity path in a graph is said to be simple when its nodes are pairwise distinct; and similarly for a simple cycle.

Proposition. Let A be a connected, rooted, poor, smooth graph. Then if A is acyclic, the category A^{∗} has an initial object r, so that for each x ∈ A there is in A^{∗} a unique morphism γ_{x} : r ⟶ x. When A is not acyclic, we can find a simple cycle β : r ⟶ r in A^{∗} and associate to each object x of A a morphism γ_{x} : r ⟶ x in A^{∗}, which is the identity id_{r} if x = r and a simple path otherwise, such that every morphism r ⟶ x in A^{∗} has the form γ_{x}β^{i} for a unique natural number i ⩾ 0.

Proof. (1) A^{∗} has a weakly-initial object r because A is rooted and connected. We shall prove that every cycle C of A contains r.

In fact, choose a node x ∈ C. If x ≠ r, there exists a non-identity path γ : r ⟶ x. The last arrow of γ lies on the cycle C, since A is smooth and the codomain of that arrow lies on C. Analogously, the last-but-one arrow of r lies on the cycle C, and so on. Thus C contains the whole path γ; in particular, it contains r.

(2) If A is acyclic, put β = id_{r}; otherwise, let β : r ⟶ r be a cycle of the smallest possible length. Then β is a simple cycle, and we shall prove that A has no cycles other than the β^{i}, for i = 1, 2, 3, · · · .

In fact, let γ : r ⟶ r be an arbitrary cycle of A. Arguing as in (1), we see that each arrow of γ lies on the cycle β; and conversely, each arrow of β lies on γ. Consequently, since β is simple, we conclude that γ = β^{i} for some i ⩾ 1. Therefore A^{∗}(r, r) = {β^{i}| i = 0, 1, 2, ⋯ }.

(3) For every object x ≠ r choose a path γ_{x} : r ⟶ x of the smallest length; this is clearly simple. We shall prove that every path δ : r ⟶ x has the form δ = γ_{x}β^{i} for some i ⩾ 0; in particular, if δ is simple, it follows that δ = γ_{x}.

The statement is true if x lies on the cycle β. In fact, here γ_{x} is the section of the cycle β from r to x (because, arguing as above, γ_{x} lies on the cycle β and γ_{x} is simple). That is, we have β = β′γ_{x} for some β′ : x ⟶ r in A^{∗}. Now the composite β′δ : r ⟶ r has the form β^{i}, by (2) above, and i > 0 since x ≠ r; therefore

β′δ = ββ^{i−1} = β′γ_{x}β^{i−1} ,

giving δ = γ_{x}β^{i−1}.

Let us prove that statement for x lying outside of the cycle β. If the paths γ_{x} and δ do not share the last arrow, put δ′ = δ; if they do, denote by δ′′ the maximum section at the end of the path δ which is shared with γ_{x}. That is, we have a decomposition δ = δ′′δ′, with δ′ : r ⟶ y and δ′′ : y ⟶ x, such that the last arrow of δ′ does not lie on the path γ_{x}, and we have γ_{x} = δ′′γ′_{x} with γ′_{x} : r ⟶ y. We shall prove that y lies on the cycle β. This will conclude the proof : from the last paragraph we then know (since γ′_{x} is simple) that γ′_{x} = γ_{y} and δ′ = γ_{y}β^{i} for some i, so that δ = δ′′δ′ = δ′′γ_{y}β^{i} = δ′′γ′_{x}β^{i} = γ_{x}β^{i}.

To prove that y lies on the cycle β, denote by z the last node of the path γ′_{x} which lies on the path δ. Then the sections of the paths γ′_{x} and δ from z to y are disjoint.

Since A is poor, we conclude that a path exists from y to z. Composing that path with the section of γ′_{x} from z to y, we obtain a cycle containing y. But by (2) the only cycles of A are the β^{i}; and so y lies on the cycle β.

3.12 Corollary. The saturation of {Le} contains all connected, rooted, poor, smooth graphs.

Proof. Let A be such a graph as in Lemma 3.11. We shall prove that the closure of Y (A^{op}) under colimits of endomorphisms in [A^{∗}, Set] contains Δ1 : A^{∗} ⟶ Set; in other words that A ∈ \overline{\{Le\}}. If A^{∗} has an initial object r, then the diagram D : Le ⟶ [A^{∗}, Set] with De = Y r and Ds = id satisfies Δ1 ≅ colim D ; in fact, for every object x of A, D(x) has a single element. If A^{∗} does not have an initial object, define D : Le ⟶ [A^{∗}, Set] by De = Y r and Ds = Y β. Then Δ1 ≅ colim D. In fact, for every object x the diagram D(x) is the endomorphism of the set A^{∗}(r, x) = {γ_{x}β^{i}| i = 0, 1, 2, ⋯ } defined by composition with β; that is, γ_{x}β^{i} ⟼ γ_{x}β^{i+1}. So all the γ_{x}β^{i} get identified, and colim D(x) ≅ 1.

Corollary 3.12 has the following simple generalization:

3.13 Corollary. The saturation of {Le, Pr} contains all non-empty rooted smooth poor graphs.

Proof. Let the connected components of the rooted simple poor graph A be A_{1}, ⋯, A_{n}, so that the graph A is the coproduct A_{1} +⋯+A_{n}, and the category A^{∗} is the coproduct A_{1}^{∗} + ⋯ + A_{n}^{∗}. Each A_{j} is a connected rooted smooth poor graph, and has the structure described in 3.11, with a corresponding β_{j} : r_{j} ⟶ r_{j} which is either the identity or a simple cycle. We define a diagram D_{j} : Le ⟶ [A^{∗}, Set] by taking for D_{j}e the

representable Y r_{j} and for D_{j}s the endomorphism β_{j}. Then D = ∑_{j=1}^{n} D_{j} : Le ⟶

[A^{∗}, Set] is a coproduct of representables, and colim D ≅ Δ1; for colim D(x) = ∑ colim D_{j}(x), and, as in the proof of 3.12, colim D_{j}(x) is a singleton for x ∈ A_{j} and empty for x ∉ A_{j}. So the result follows from 3.1.

3.14 Proposition. The saturation of {Pr} consists of these non-empty finite graphs A for which each component of A^{∗} has an initial object; so by 3.11 it contains all nonempty finite, acyclic, rooted poor graphs.

Proof. By 3.1, A lies in the saturation of {Pr} if and only if Δ1 ∈ [A^{∗}, Set] lies in the closure under binary coproducts of the representables A^{∗}(a, −); that is, if and only if we have a_{1}, ⋯ a_{n} in A with n > 0 such that the coproduct A^{∗}(a_{1}, b) + ⋯ A^{∗}(a_{n}, b) is a singleton for each b ∈ A. This, however, is just to say that each a_{i} is initial in its component of A^{∗}.

3.15 Proposition. The saturation of the empty class of graphs consists of those nonempty finite graphs A for which A^{∗} has an initial object; so by 3.11 it includes all connected finite acyclic rooted poor graphs.

Proof. By 3.1, A lies in the saturation of the empty class of graphs if and only if Δ1 ∈ [A^{∗}, Set] is representable — that is, isomorphic to A^{∗}(a, −) for some a ∈ A. But this is to say that each A^{∗}(a, b) is a singleton, or that a is initial in A^{∗}.

3.16 Proposition. If the graph A has at least two components A_{1} and A_{2}, Pr lies in the saturation of {A, ∅}.

Proof. A is a coproduct A_{1} + A_{2} + B; define D : A ⟶ [Pr^{∗}, Set] to have the constant values Y e_{1} on A_{1}, Y e_{2} on A_{2}, and Δ∅ on B; then colim D ≅ Δ1.

3.17 Proposition. The saturation of {Eq, ∅} consists of the empty graph and all graphs A for which A^{∗} has a weakly-initial object.

Proof. By Proposition 3.10, A lies in the saturation of {Eq}, and hence of {Eq, ∅}, if A^{∗} has a weakly-initial object. For the converse, suppose that A is a non-empty graph in the saturation of {Eq, ∅}. Since Pr does not lie in the saturation of {Eq, ∅}, it does not lie in the saturation of {A, ∅}; accordingly A is connected by 3.16 and rooted by 3.6.

4. A characterization of the monadicity of Cat_{M}

4.1 Theorem. Let M be a set of finite graphs containing the empty graph ∅. Then Cat_{M} is monadic over Gph if and only if the set M

(i) contains a non-rooted graph, or (ii) contains a non-poor graph, or (iii) contains both a non-smooth graph and a non-empty disconnected one, or (iv) consists of acyclic graphs.

Remark. As mentioned in the Introduction, Case (iv) has been proved, in a completely different way, in [KL] (where the result is more general since the requirement ∅ ∈ M has not been made). We use, throughout the proof, Theorem 1.4, asserting that the monadicity over Gph of Cat_{M} depends only on \overline{M}; recall that it is to be proved in the Appendix below.

Proof of sufficiency.

Cases (i) and (ii) are sufficient for monadicity by 2.5 because \overline{M} contains Eq; see 3.6 and 3.4, respectively.

In Case (iii), \overline{M} contains Pr by 3.16 and thus it contains all finite graphs by 3.8; once again, 2.5 gives the monadicity.

In Case (iv) we may assume by (i) and (ii) that all the non-empty graphs M of M, besides being acyclic and therefore smooth, are poor and rooted. So by 3.11 each component of each M^{∗} has an initial object. Thus, if all the non-empty graphs M of M are connected, we have M ∼ {∅} by 3.15. If M contains a disconnected graph, then M ∼ {Pr, ∅} by 3.14. And of course each of Cat_{{∅}} and Cat_{{Pr,∅}} is monadic over Gph, as observed in the Introduction.

Proof of necessity.

Supposing each of (i) - (iv) to be false, we are to prove that Cat_{M} is not monadic over Gph. Thus we are supposing that M contains a graph with a cycle, so that Le ∈ \overline{M} by 3.9; that all the non-empty graphs of M are poor and rooted; and that either all of them are smooth or all of them are connected. In these circumstances we shall construct

(1) an object L of Cat_{M}, the chosen limit-cone of D : M ⟶ L with M ∈ M being

written as α_{D} : lim D ⟶ D, with components α_{D,x} : lim D ⟶ Dx, and

(2) a congruence ∼ on (the morphisms of) L, giving the quotient category C = L/ ∼,

with the canonical quotient functor Q : L ⟶ C, having the properties

(3) whenever D, E : M ⟶ L with M ∈ M have QD = QE : M ⟶ C, then we also have lim D = lim E and Qα_{D} = Qα_{E} (or equivalently α_{D} ∼ α_{E});

(4) for each D : M ⟶ L with M ∈ M, the cone Qα_{D} : Q lim D ⟶ QD is jointly

monomorphic; that is, f ∼ g whenever f, g : A ⟶ lim D in L have α_{D}f ∼ α_{D}g; and

(5) C fails to have limits of endomorphisms. Once this is done, we deduce the non-monadicity of U_{M} : Cat_{M} ⟶ Gph from Lemma 2.2 as follows.

We write P_{1}, P_{2} : K ⟶ L for the kernel-pair in Cat of Q : L ⟶ C. We can regard K as the subcategory of L × L whose objects are those of the form (A, A) and whose morphisms (A, A) ⟶ (B, B) are those (f, g) : (A, A) ⟶ (B, B) in L×L having f ∼ g; then P_{1}, P_{2} are the restrictions to K of the projections from L × L to L. (Of course we could identify the object (A, A) of K with the object A of L, and for that matter with the object QA of C, treating each of P_{1}, P_{2}, Q as being the identity on objects; but it may be clearer to keep the three different names for the objects (A, A), A, and QA.) Clearly Q : L ⟶ C is the coequalizer in Cat of P_{1}, P_{2} : K ⟶ L. Moreover this coequalizer admits a splitting in Gph : we get a graph-morphism I : C ⟶ L with QI = 1 by setting IQA = A on objects and by choosing for each arrow QA ⟶ QB in C some representative A ⟶ B in L. Then QIQ = Q = Q1; and since P_{1}, P_{2} : K ⟶ L is also the kernel-pair of Q in Gph, there is a graph-morphism J : L ⟶ K with P_{1}J = 1 and P_{2}J = IQ. Next, L × L has the pointwise structure of an object of Cat_{M}, the chosen limit of (D, E) : M ⟶ L × L being (α_{D}, α_{E}) : (lim D, lim E) ⟶ (D, E). We claim that the subcategory K of L × L is closed under these limits, so that K too becomes an object of Cat_{M}, with P_{1}, P_{2} : K ⟶ L morphisms of Cat_{M}. For let QD = QE. First, (3) gives lim D = lim E and α_{D} ∼ α_{E}, so that the object (lim D, lim E) = (lim D, lim D) lies in K and the morphisms constituting the cone (α_{D}, α_{E}) lie in K. Next, given any cone (β, γ) : (B, B) ⟶ (D, E) in K, we have β = α_{D}b and γ = α_{E}c for unique morphisms b : B ⟶ lim D and c : B ⟶ lim E = lim D in L, so that (β, γ) = (α_{D}, α_{E})(b, c) for a unique (b, c) : (B, B) ⟶ (lim D, lim D) in L × L. Finally, (b, c) lies in fact in K; for we have β ∼ γ and so α_{D}b ∼ α_{E}c ∼ α_{D}c, whence b ∼ c by (4). So P_{2}, P_{2} : K ⟶ L do indeed lie in Cat_{M}; and now, if U_{M} were monadic, C would admit M-limits by Lemma 2.2, and hence limits of endomorphisms since Le ∈ \overline{M}; but this is false by (5).

Suppose, then, than ∅ ∈ M, that Le ∈ M, and that the graphs in M−{∅} are either

(A) poor, rooted, and connected

or

(B) poor, rooted, and smooth.

We treat these two cases in order.

Analysis of Case A

In order to construct our category L, we begin with the graph having three objects a, b, c and three arrows p : a ⟶ b, i : c ⟶ b, and r : b ⟶ b; and we form the category generated by this, subject to the single relation ri = i. Then we obtain our category L from this category by freely adding to it a terminal object 1 and an initial object 0. The congruence ∼ on L is that generated by the single relation rp ∼ p. The quotient category C = L/ ∼ certainly satisfies (5) above : for in C the endomorphism r : b ⟶ b admits (besides the cone 0 ⟶ b) the two cones p : a ⟶ b and i : c ⟶ b, neither of which is a limit-cone. It remains to examine the M-limits in L for M ∈ M, and to make choices of them satisfying (3) and (4).

In the terminal-object case M = ∅, (3) is trivially satisfied, and so is (4). Turning to non-empty M, write j for a weekly-initial object in the rooted and connected M. For a diagram D : M ⟶ L, we shall examine the cones over D, and the limit-cones among them, according to the various values of the object Dj of L.

When Dj is 0, c, or 1, there is clearly a unique cone over D with vertex Dj, and this is a limit-cone, which of course we choose as lim D; clearly (3) and (4) are then satisfied.

When Dj = b, write M_{b} for the full sub-graph of M given by the objects x having Dx = b. It may be the case that D has the property

(∗)Df = Dg for each parallel pair f, g : x ⟶ y in M_{b}^{∗}.

When this is the case, we get a cone α_{D} : b ⟶ D by setting α_{D,x} = Df_{x} for any choice of path f_{x} : j ⟶ x in M^{∗}; this cone has α_{D,j} = id_{b} and is clearly a limit-cone, and we choose it. Of course we have (3) and (4), since Q is an isomorphism when restricted to the full subcategory determined by 0, c, b, and 1. When (∗) is not the case, D admits no cone of vertex b; the only cones are the unique one of vertex 0 and the unique one of vertex c; the latter is a limit-cone, and we choose it. Once again, for the same reason, we have (3) and (4).

The final case is that where Dj = a. Write M_{a} for the full subgraph of M given by the objects x with Dx = a, and M_{b} for that given by the objects x with Dx = b. Once again, if (∗) is not satisfied, there is no cone over D of vertex b; the only cone over D is that of vertex 0, which is a limit-cone and which we choose. This time (3) and (4) are trivially satisfied; note that E satisfies (∗) when D does so, if QE = QD. So we may as well suppose that (∗) is satisfied. We claim that, in these circumstances, we have Df = Dg for each pair f, g : j ⟶ x in M^{∗}. Once we prove this we shall be done : we get a cone α_{D} : a ⟶ D by setting α_{D,x} = Df_{x} for any choice of a path f_{x} : j ⟶ x in M^{∗}; this cone has α_{D,j} = id_{a} and is clearly a limit-cone, and we choose it. Now (3) is satisfied; for if QE = QD, then E too has Ej = a and satisfies (∗), so certainly as objects we have lim E = lim D = a, while Qα_{E,x} = QEf_{x} = QDf_{x} = α_{D,x}. And (4) is satisfied because Qα_{D,j} = Q(id_{a}) = id_{Qa}.

It remains to show that Df = Dg for any f, g : j ⟶ x in M^{∗}. Let f be the path β_{n}β_{n−1} ⋯ β_{1} where the β_{i} : z_{i−1} ⟶ z_{i} are edges of M, with z_{0} = j and z_{n} = x; and similarly let g be the path γ_{m}γ_{m−1} ⋯ γ_{1} where γ_{i} : w_{i−1} ⟶ w_{i}, with w_{0} = j and w_{m} = x. If x ∈ M_{a} there is nothing to prove, since Df = Dg = 1; so suppose that x ∉ M_{a}. Let i′ be the greatest i for which (a) z_{i} ∈ M_{a} and (b) z_{i} is one of the w_{j}. Moreover let j′ be the greatest j for which w_{j} = z_{i′}; and write s for the common value w_{j′} = z_{i′}. We may call s the last common node of f and g that lies in M_{a}. Next, let i′′ be the first i > i′ for which z_{i} is one of the w_{j}; and let j′′ be the least j for which w_{j} = z_{i′′}. We may call the common value t = z_{i′′} = w_{j′′} the first common node of f and g after s. Now we can write f : j ⟶ x as the composite of f_{1} : j ⟶ s, f_{2} : s ⟶ t, and f_{3} : t ⟶ x, where f_{1} is the part of the path up to z_{i′}, while f_{2} is the part from z_{i′} to z_{i′′}, and f_{3} is the rest; and similarly g : z ⟶ x is the composite of g_{1} : j ⟶ s, g_{2} : s ⟶ t, and g_{3} : t ⟶ x. Now of course Df_{1} = Dg_{1} = id_{a}; while Df_{3} = Dg_{3} by (∗) if t ∈ M_{b}, and trivially if Dt = 1. It remains to examine f_{2}, g_{2} : s ⟶ t. Since Ds = a and Dt is b or 1, there is no morphism Dt ⟶ Ds, and hence no path t ⟶ s in M^{∗}. Since M is poor, it follows from Definition 3.3 that f_{2} and g_{2} share a common arrow. Since t is the first common node of f and g after s, it must be the case that i′′ = i′ + 1 and j′′ = j′ + 1, so that f_{2} = β_{i′′} and g_{2} = γ_{j′′}, and that in fact β_{i′′} = γ_{j′′}; which is to say that f_{2} = g_{2}, giving Df_{2} = Dg_{2}, and finally Df = Dg as required — completing the proof of necessity in Case A.

Analysis of Case B.

We may as well suppose that some graph in M is disconnected, since otherwise we are in Case A. So \overline{M}, besides containing ∅ and containing Le by hypothesis, contains Pr by (3.16). On the other hand, M lies in the saturation of {Le, Pr, ∅} by 3.13. Accordingly it suffices by Theorem 4.1 to prove the non-monadicity of U_{M} where M = {Le, Pr, ∅} : which we do by constructing as above an L in Cat_{M} and a congruence ∼ on L satisfying (3), (4), and (5).

We begin with the graph having two objects a, b and two arrows p : a ⟶ b and r : b ⟶ b; and we write L_{0} for the free category on this. Then we write L_{1} for the free completion of L_{0} under finite products, which we may describe as follows. An object (I, x) of L_{1} is a finite set I, which we can see as a discrete category, together with a functor x : I ⟶ L_{0}; and a morphism (f, ϕ) : (I, x) ⟶ (J, y) in L_{0} is a functor f : J ⟶ I together with a natural transformation ϕ : xf ⟶ y. The composite of (f, ϕ) : (I, x) ⟶ (J, y) and (g, ψ) : (J, y) ⟶ (K, z) is (fg, θ) where θ : xfg ⟶ z is the composite of ϕg : xfg ⟶ yg and ψ : yg ⟶ z; and the identity of (I, x) is (1_{I}, id). In elementary terms, x is a finite family x : I ⟶ {a, b} with components x_{i}, and ϕ has components ϕ_{j} : x_{fj} ⟶ y_{j} which are morphisms in L_{0}. In these terms, the components of θ in the composite (fg, θ) above are given by θ_{k} = ψ_{k}ϕ_{gk}. When x : I ⟶ {a, b} is constant at b, we may call (I, x) the power b^{I} of b, and similarly for a^{I}; while the unique (I, x) with I = ∅ is the terminal object 1 of L_{1}. (To ensure smallness of L_{1}, we should restrict our class of finite sets I — for instance, to subsets of the natural numbers.)

Our next task is to examine endomorphisms in L_{1}, and cones over these, including limit-cones when such exist. So we now consider an endomorphism (e, ϕ) : (I, x) ⟶ (I, x) in L_{1}, where e : I ⟶ I and ϕ_{i} : x_{ei} ⟶ x_{i}. Let us write g : I ⟶ K for the colimit in Set of the endomorphism e; here K is the quotient of I by the equivalence relation generated by identifying ei with i, and g is the canonical surjection whose fibres are the orbits of e in I, which we identify with the elements k of K, so that gi denotes the orbit of i. Write R for {i ∈ I| e^{n}i = i for some n > 0}; for each orbit k we may call k ∩ R its core, which has the cyclic form i, ei, ⋯, e^{n−1}i, e^{n}i = i for some i ∈ k, and has the property that, for every j ∈ k, e^{m}j lies in the core of k for some m ⩾ 0. Since there is no morphism b ⟶ a in L_{0}, the existence of ϕ_{i} : x_{ei} ⟶ x_{1} implies that x_{ei} = a if x_{i} = a, or equally that x_{i} = b if x_{ei} = b. It follows that the elements {i, ei, ⋯, e^{n}i = i} of the core of an orbit k are either all equal to a or all equal to b.

Consider now the possibility of a cone (r, ρ) : (J, z) ⟶ (I, x) in L_{1} over the endomorphism (e, ϕ) : (I, x) ⟶ (I, x); that is, a function r : I ⟶ J with re = r along with morphisms ρ_{i} : z_{ri} ⟶ x_{i} for which ρ_{i} = ϕ_{i}ρ_{ei}. Iterating this last equation gives ρ_{i} = ϕ_{i}ρ_{ei} = ϕ_{i}ϕ_{ei}ρ_{e^{2}i} and so on, or more generally

(6)  ρ_{i} = ϕ_{i}ϕ_{ei}ϕ_{e^{2}i} ⋯ ϕ_{(e^{n−1}i)}ρ_{e^{n}i}

for n ⩾ 0. Suppose now that i ∈ R, so that i is in the core of its orbit gi, and chose n so that e^{n}i = i; now (6) becomes

(7)  ρ_{i} = ϕ_{i}ϕ_{ei} ⋯ ϕ_{(e^{n−1}i)}ρ_{i} .

We have seen above that either each e^{r}i here is a, or else each is b; in the first case each ϕ_{e^{r}i} here is id_{a}, while in the second case it is a power of r. In the latter case, since the category L_{0} is free on the original graph, it follows from (7) that each ϕ_{e^{r}i}, including ϕ_{i} itself, must be the identity id_{b}. In other words, there can be no cone over the endomorphism (e, ϕ) : (I, x) ⟶ (I, x) unless

(8)  ϕ_{i} is an identity for each i ∈ R .

When (8) is satisfied, consider what it is to give a cone (r, ρ) over (e, ϕ) with vertex (J, z). To give r : I ⟶ J with re = r is of course just to give some s : K ⟶ J, whereupon r = sg. Then it remains to give the morphisms ρ_{i} : z_{ri} = z_{sgi} ⟶ x_{i} satisfying ρ_{i} = ϕ_{i}ρ_{ei}. By (6), the value of ρ_{i} is forced once we choose the value of ρ_{e^{n}i} for some n with e^{n}i in the core of the weight gi. Indeed, it suffices to choose morphisms ρ_{i} : z_{sgi} ⟶ x_{i} for i ∈ R, satisfying ρ_{i} = ϕ_{i}ρ_{ei} (which by (8) reduces for i ∈ R to ρ_{i} = ρ_{ei}) and then to define ρ_{i} for a general i by (6); for now ρ_{i} is, by (8), well-defined by (6), independently our choice of an n with e^{n}i ∈ R, and the ρ_{i} so defined clearly satisfy ρ_{i} = ϕ_{i}ρ_{ei}. Thus, if we write y_{k} for the common value of the x_{i} with i in the core of the orbit k, choosing such a cone comes down to choosing for each k ∈ K a morphism σ_{k} : z_{sk} ⟶ y_{k}, and defining ρ_{i} for i in the core of k by setting ρ_{i} = σ_{gi}.

In fact we find such a cone with vertex (K, y) on taking s to be 1_{K} and taking σ_{k} : z_{sk} ⟶ y_{k} to be the identity of y_{k}; call this cone (g, ψ) : (K, y) ⟶ (I, x), noting that ψ_{i} : y_{gi} ⟶ x_{i} is the identity for i ∈ R. Now the description above of the general cone (r, ρ) when (8) is satisfied shows that (g, ψ) is then the limit-cone; for the general cone (r, ρ) factorizes uniquely through (g, ψ) as (r, ρ) = (g, ψ)(s, σ), where σ : zs ⟶ y has the components σ_{k} : z_{sk} ⟶ y_{k} above. This completes our analysis of endomorphisms in L_{1} and of the cones over them.

We now complete our description of the category L. First we add to L_{1} a new object c, along with new morphisms given by the identity of c and, in addition, one new morphism j_{I} : c ⟶ b^{I} for each power b^{I} of b; the definition of composition in the resulting category L_{2} is forced, and c is an initial object in the full subcategory of L_{2} determined by c and the powers b^{I}. Finally we form L by freely adding an initial object 0 to L_{2}.

To define the congruence ∼ on L, we first consider the congruence ≡ on L_{0} generated by the single relation rp ≡ p; then ∼ is the congruence on L generated by setting (f, ϕ) ∼ (f, ψ) : (I, x) ⟶ (I, y) for morphisms of L_{1} satisfying ϕ_{i} ≡ ψ_{i} : x_{fi} ⟶ y_{i} for each i ∈ I. If C is the quotient category L/ ∼, we note that (I, x) is the product of the x_{i} not only in L_{1} but also in L and moreover in C.

Certainly C satisfies (5) above : in fact the endomorphism r : b ⟶ b of C admits no limit in C. For it admits the cones p : a ⟶ b and j_{1} : c ⟶ b, and any cone through which each of these factorizes must be of the form h : b^{I} ⟶ b for some power b^{I} of b; but such an h, being a projection b^{I} ⟶ b composed with some r^{n} : b ⟶ b, is not a cone over r. So it remains only to examine the M-limits in L where M ∈ {Le, Pr, ∅}, and to make choices of them satisfying (3) and (4) above.

In the terminal-object case M = ∅, we choose the limit 1 given by (I, x) with I = ∅, whereupon (3) and (4) are trivially satisfied. Next is the case M = Pr of binary products; here (3) is automatically satisfied since Pr is a discrete graph. For objects (I, x) and (J, y) of L_{1}, the product (I + J, (x, y)) in L_{1} is, as we said, also a product in L, and we choose it; moreover (4) is satisfied because this is also a product in C. Finally a product of c with a power b^{I} is given by c, as is a product of c with itself; and any other product is given by 0 — moreover (4) is trivially satisfied when we make these choices.

It remains to consider the limit in L of an endomorphism. If we are speaking of an endomorphism of c or of 0, the limit is trivially c or 0 respectively, and (3) and (4) are trivially satisfied. If we are speaking of an endomorphism (e, ϕ) : (I, x) ⟶ (I, x) in L_{1}, and if (8) is not satisfied, the limit is c if (I, x) is a power of b, and is 0 otherwise; moreover (3) and (4) are trivially satisfied once we observe that, if (e′, ϕ′) : (I, x) ⟶ (I, x) is another endomorphism with (e′, ϕ′) ∼ (e, ϕ), and if (e, ϕ) satisfies (8), so does (e′, ϕ′); for then e′ = e and ϕ′_{i} ≡ ϕ_{i} : x_{ei} ⟶ x_{i} for each i ∈ I.

So there remains only the case where (e, ϕ) : (I, x) ⟶ (I, x) satisfies (8); here the (g, ψ) : (K, y) ⟶ (I, x) above is a limit of (e, ϕ) not only in L_{1}, but also in L; and we choose it.

To verify that the limit (g, ψ) satisfies (4), suppose that (s, σ), (s′, σ′) : (J, z) ⟶ (K, y) have (sg, ψ·σg) ∼ (s′g, ψ·σ′g). Then sg = s′g, giving s′ = s, and ψ_{i}·σ_{gi} ≡ ψ_{i}·σ′_{gi} for each i ∈ I. Since ψ_{i} is an identity when i lies in the core of the orbit k = gi, this gives σ_{k} ≡ σ′_{k}, and hence (s, σ) ∼ (s′, σ′), as desired.

Finally we must show that (3) is satisfied in this case. Suppose then that the endomorphisms (e, ϕ), (e′, ϕ′) : (I, x) ⟶ (I, x) have (e′, ϕ′) ∼ (e, ϕ), or equivalently e′ = e and ϕ′_{i} ≡ ϕ_{i} : x_{ei} ⟶ x_{i} for each i ∈ I; as we saw above, (e′, ϕ′) satisfies (8) when (e, ϕ) does so, which is the case under consideration. Because e′ = e, the limits of (e, ϕ) and of (e′, ϕ′) coincide as objects, each being (K, y) as before; and the limit-cones (y, ψ) and (y′, ψ′) have y′ = y. We have seen however that ψ_{i} : y_{gi} ⟶ x_{i} has the form

ψ_{i} = ϕ_{i}ϕ_{ei} ⋯ ϕ_{e^{n−1}i}ψ_{e^{n}i} ,

where ψ_{e^{n}i} is an identity when n is such that e^{n}i lies in the core of the orbit gi; and now from ψ_{i} = ϕ_{i}ϕ_{ei} ⋯ ϕ_{e^{n−1}i} and ψ′_{i} = ϕ′_{i}ϕ′_{ei} ⋯ ϕ′_{e^{n−1}i}, along with ϕ_{j} ≡ ϕ′_{j} for each j, we get ψ′_{i} ≡ ψ_{i}, giving (y, ψ′) ∼ (y, ψ), as desired. This completes the proof of necessity in Case B, and hence completes the proof of Theorem 4.1.

4.2 Proof of Theorem 1.5

It remains to show that, if a set M of finite graphs containing ∅ satisfies the conditions of Theorem 4.1, we have M ∼ N where N is one of the sets {∅}, {Eq, ∅}, {Pr, ∅}, and {Pb, ∅}. We look in order at (i) - (iv) of Theorem 4.1. Case (i): M contains a non-empty, non-rooted graph. Here \overline{M} contains all finite graphs by 3.6, so that M ∼ {Pb, ∅}.

For the remaining cases we may suppose that each non-empty graph in M is rooted. Case (ii)a: M contains a non-poor graph with at least two components. Here \overline{M} contains Eq by 3.4 and contains Pr by 3.16, so that again M ∼ {Pb, ∅}. Case (ii)b: M contains a non-poor graph, and each non-empty graph in M is connected. Then Eq ∈ \overline{M} by 3.4, and M is contained in the saturation of \{Eq, ∅\} by (3.17) : for each non-empty graph in M, being rooted and connected, has a weaklyinitial object. Thus M ∼ {Eq, ∅}. Case (iii): M contains a non-smooth graph and one with at least two components. Then \overline{M} contains Pr by 3.16, whence it contains all finite graphs by 3.8. So again M ∼ {Pb, ∅}. Case (iv): Here the graphs in M are acyclic, and hence smooth, and we may suppose them rooted and poor. Then, as we already saw in the proof of sufficiency for Theorem 4.1, we have M ∼ {∅} by 3.15 if all the non-empty graphs in M are connected, and M ∼ {Pr, ∅} otherwise.

5. Appendix on Saturation

5.1 Even when M is only a class of graphs, the Albert-Kelly criterion for a graph A to lie in the saturation \overline{M}, given in Theorem 3.1 above, refers to M(A), which is a set of presheaves in [A^{∗}, Set]. Accordingly it is much more natural to discuss saturation and its properties, as was done in [AK], at the level of weighted limits, since weights are nothing but presheaves. Moreover, by the nature of the theory, it is less complicated if we work with categories admitting certain weighted colimits, rather than certain weighted limits; we observed this already in Remark 3.2. Once we are at this level, it is just as easy to deal with enriched categories as with ordinary ones. Because some readers may be less familiar with enriched categories, we shall in fact write our discussion for ordinary ones — noting, however, that the results remain true for enriched ones, with exactly the same proofs.

Recall now (for instance from [KE], wherein weighted colimits were called indexed colimits) that a weight is a functor ϕ : K^{op} ⟶ Set with K a small category. A functor T : K ⟶ A, where A is locally small, is said to admit a ϕ-weighted colimit, or just a ϕcolimit, if the functor A ⟶ Set sending A to [K^{op}, Set](ϕ, A(T −, A)) is representable; that is, if there is an object ϕ ∗ T in A and an isomorphism

π : A(ϕ ∗ T, A) ≅ [K^{op}, Set](ϕ, A(T −, A))

natural in A ∈ A. Then we say that (ϕ ∗ T, π) is a choice of ϕ-colimit for T. If another such choice is given by

π′ : A(ϕ ∗′ T, A) ≅ [K^{op}, Set](ϕ, A(T −, A)) ,

then there is a unique isomorphism λ : ϕ ∗ T ⟶ ϕ ∗′ T for which π′ = π · A(λ, A). Of course we often speak loosely of ϕ ∗ T, which is determined to within a unique isomorphism, as the ϕ-colimit of T; but, even in such phrases, ϕ∗T is really a shorthand for the pair (ϕ∗T, π). When ϕ is Δ1 : K^{op} ⟶ Set, the functor constant at the singleton set 1, we note that [K^{op}, Set](Δ1, A(T −, A)) is in effect the set of inductive cones over T with vertex A, so that Δ1 ∗ T is the classical colimit, colim T, of T. This in turn has the special case where K is the free category M^{∗} on a graph M, so that T : M^{∗} ⟶ A corresponds to a graph-morphism P : M ⟶ A; here it is common to write colim P for colim T. Of course ϕ-weighted limits in A are just ϕ-weighted colimits in A^{op} : more precisely, if ϕ : K^{op} ⟶ Set is a weight as above, and T : K^{op} ⟶ A is a functor, giving rise to the dual functor T^{op} : K ⟶ A^{op}, the ϕ-weighted colimit ϕ ∗ T^{op} is also called the ϕ-weighted limit {ϕ, T } of T : K^{op} ⟶ A; in particular, {Δ1, T } is the classical lim T.

If G : A ⟶ B is a functor for which both ϕ ∗ T and ϕ ∗ GT exist, we can form the composite

\xymatrix{A(ϕ ∗ T, A) \ar[r]^{π} & [K^{op}, Set](ϕ, A(T −, A)) \ar[d]^{[K^{op},Set](ϕ,G_{T −,A})} \\ B(ϕ ∗ GT, GA) & [K^{op}, Set](ϕ, B(GT −, GA)) \ar[l]^{π^{−1}} & ;}

and by the Yoneda lemma, this composite has the form

\xymatrix{A(ϕ ∗ T, A) \ar[r]_{G_{ϕ∗T,A}} & B(G(ϕ ∗ T), GA) \ar[r]_{B(τ,GA)} & B(ϕ ∗ GT, GA)}

for a unique

τ : ϕ ∗ GT ⟶ G(ϕ ∗ T)

which we call the canonical comparison map. We say that G preserves the colimit ϕ ∗ T when τ is invertible, and that G strictly preserves the colimit ϕ∗T when τ is an identity. 5.2 A category A is said to admit Φ-colimits, or to be Φ-cocomplete, where Φ is a class of weights, if it admits the colimit ϕ ∗ T for each pair (ϕ, T) where ϕ : K^{op} ⟶ Set is a weight in Φ and T : K ⟶ A is a functor with domain K. We write Φ-COCOM for the 2-category of Φ-cocomplete locally-small categories, functors preserving Φ-colimits (such functors are also said to be Φ-cocontinuous), and all natural transformations between these. There is an evident forgetful 2-functor W_{Φ} : Φ-COCOM ⟶ CAT.

There is also a 2-category Φ-COLIM, an object of which is a category A in Φ-COCOM together with, for each pair (ϕ : K^{op} ⟶ Set, T : K ⟶ A) having ϕ ∈ Φ, a choice (ϕ ∗ T, π) of a ϕ-colimit of T; more briefly, we call such an object a category A with chosen Φ-colimits. A morphism in Φ-COLIM is a functor which strictly preserves the chosen Φ-colimits; and a 2-cell is again an arbitrary natural transformation. So the forgetful 2-functor J_{Φ} : Φ-COLIM ⟶ Φ-COCOM, which is surjective on objects, is not fully faithful. Let us write U_{Φ} : Φ-COLIM ⟶ CAT for the composite to W_{Φ}J_{Φ}.

When we want to restrict to small Φ-cocomplete categories, or to small categories with chosen Φ-colimits, we replace the notation

\xymatrix{Φ-COLIM \ar[r]_{J_{Φ}} & Φ-COCOM \ar[r]_{W_{Φ}} & CAT}

along with the composite U_{Φ} = W_{Φ}J_{Φ}, by

\xymatrix{Φ-Colim \ar[r]_{j_{Φ}} & Φ-Cocom \ar[r]_{w_{Φ}} & Cat}

along with the composite u_{Φ} = w_{Φ}j_{Φ}.

When M is a class of finite graphs, and Φ consists of the weights Δ1 : M^{∗} ⟶ Set (that is, ((M^{∗})^{op})^{op} ⟶ Set) for all M ∈ M, Φ-Colim is the 2-category of small categories A with chosen colimits (in the classical sense) of each diagram D : M^{op} ⟶ A with M ∈ M. When we consider this only as a category, by ignoring the 2-cells, it is isomorphic to the category Cat_{M} of the Introduction, by the isomorphism ( )^{op} sending A to A^{op}. Then the forgetful functor U_{M} : Cat_{M} ⟶ Cat of the Introduction is the composite

\xymatrix{Cat_{M} \ar[r]^{≅}_{( )^{op}} & Φ-Colim \ar[r]_{u_{Φ}} & Cat \ar[r]^{≅}_{( )^{op}} & Cat \ar[r]_{V} & Gph.}

For classes Φ ⊂ Ψ of weights we have evident forgetful 2-functors U_{Ψ,Φ} : Ψ-COLIM ⟶ Φ-COLIM and W_{Ψ,Φ} : Ψ-COCOM ⟶ Φ-COCOM, connected by the equality J_{Φ}U_{Ψ,Φ} = W_{Ψ,Φ}J_{Ψ}, and further satisfying W_{Φ}W_{Ψ,Φ} = W_{Ψ} and U_{Φ}U_{Ψ,Φ} = U_{Ψ}; recall from the Introduction that we express these last two equations by saying that W_{Ψ,Φ} and U_{Ψ,Φ} are 2-functors over Cat.

It may be the case that W_{Ψ,Φ} is an equality of 2-categories : that is, every Φcocomplete category is Ψ-cocomplete and every Φ-cocontinuous functor between Φcocomplete categories is Ψ-cocontinuous. For a given Φ there is clearly a greatest Ψ with this property, namely the class \overline{Φ} consisting of those weights ψ : K^{op} ⟶ Set such that every Φ-cocomplete category is ψ-cocomplete and every Φ-cocontinuous functor between such categories is ψ-cocontinuous. (The second clause here, about cocontinuity, is known to be a consequence of the first one, about cocompleteness, when ψ is of the form Δ1 : L^{op} ⟶ Set, so that ψ-colimits are classical K-colimits; but not for a general ψ — see [AK] and [PR].) We call \overline{Φ} the saturation of Φ, and call the class Φ saturated when \overline{Φ} = Φ. (Note that, since limits in A are colimits in A^{op}, it also follows from ψ ∈ \overline{Φ} that Φ-complete categories are ψ-complete, and so on.) The saturation of Φ was determined by Albert and Kelly [AK], as follows.

For any locally-small category K we have the fully-faithful Yoneda embedding Y : K ⟶ [K^{op}, Set] sending the object K of K to K(−, K). The functor-category [K^{op}, Set] admits, like Set, all small colimits and thus all weighted ones; write Φ(K) for the closure of the representables in [K^{op}, Set] under Φ-colimits — that is, the intersection of those replete full subcategories of [K^{op}, Set] which contain the representables K(−, K) and admit Φ-colimits. It is well known that Φ(K) is again locally small, and is a “free” Φ-cocomplete category on K, in the sense that composition with the embedding Z : K ⟶ Φ(K) induces an equivalence of categories Φ-COCOM (Φ(K), A) ≃ CAT (K, A); but this property of Φ(K) does not explicitly concern us here. The following formulation of the Albert-Kelly result needs only the definition of Φ(K) for a small K :

5.3 Theorem. [AK] Given a class Φ of weights, the weight ψ : K^{op} ⟶ Set lies in the saturation \overline{Φ} of Φ if and only if the object ψ of [K^{op}, Set] lies in the closure Φ(K) of the representables under Φ-colimits.

5.4. We can build up Φ(K) from K by transfinite induction. We describe inductively full replete subcategories K_{α} of [K^{op}, Set], where α is an ordinal ⩽ ∞. First, K_{0} consists of all the isomorphs of the representables K(−, K); that is, it consists of what, in a wider sense, are called the “representables”. Next, K_{α+1} consists of K_{α} together with all those objects of [K^{op}, Set] which appear as colimits ϕ ∗ S where ϕ : L^{op} ⟶ Set is a weight in Φ and S : L ⟶ [K^{op}, Set] is a functor taking its values in K_{α}. (In this context we are not speaking of chosen colimits : an object ψ of [K^{op}, Set] is in K_{α+1} if, for some ϕ and some S as above, there is a natural (in θ) isomorphism [K^{op}, Set](ψ, θ) ≅ [L^{op}, Set](ϕ, [K^{op}, Set](S−, θ)), expressing ψ as a value of ϕ ∗ S.) Finally, for a limitordinal α, we set K_{α} = ⋃_{β<α} K_{β}. Clearly each K_{α} is contained in Φ(K); and in fact

K_{∞} = Φ(K), since K_{∞} is closed in [K^{op}, Set] under Φ-colimits. For if ϕ : L^{op} ⟶ Set lies in Φ and S : L ⟶ [K^{op}, Set] takes its values in K_{∞}, the smallness of L ensures that S in fact takes its values in K_{α} for some small α, so that ϕ∗S lies K_{α+1}, and hence in K_{∞}.

A similar argument shows that, when Φ is a small class of weights, Φ(K) is equal to K_{α} for some small α; whence Φ(K) is (equivalent to) a small category. When each Φ(K) is small (to within equivalence) we say that Φ is locally small; this may well be the case when Φ is not small. Indeed, since Φ and \overline{Φ} have the same saturation, it follows from Theorem 5.3 that \overline{Φ}(K) = Φ(K) for each K; and even when Φ is small, \overline{Φ} is not — since it certainly contains all the representables L(−, L) for every small category L.

Of course there are also relative notions of saturation : it may be that we are interested purely in weights belonging to some class Θ, and then, by the saturation of a subclass Φ of Θ, we should mean \overline{Φ} ∩ Θ. For instance, Θ might be the class of all weights of the form Δ1 : L^{op} ⟶ Set, corresponding to the classical (or “conical”) colimits. Or again, Θ might be the class of weights of the form Δ1 : M^{∗} ⟶ Set, where M^{∗} is the free category on a graph M; or perhaps just a finite graph M. It is this last that corresponds to the notion of saturation in the body of this paper, given in Definition 1.2; a class M of finite graphs corresponds to the class Φ of weights of the form Δ1 : M^{∗} ⟶ Set with M ∈ M, and then the \overline{M} of Definition 1.2 corresponds to the class \overline{Φ} ∩ Θ, when Θ has the last sense above. Here, of course, \overline{M} is indeed small, since Θ is small.

We now prove the result that will ultimately give us Theorem 1.4. Although the forgetful 2-functor W_{\overline{Φ},Φ} : \overline{Φ}-COCOM ⟶ Φ-COCOM is an equality of 2-categories, the forgetful 2-functor U_{\overline{Φ},Φ} : \overline{Φ}-COLIM ⟶ Φ-COLIM is not even an equivalence at the level of the underlying categories : indeed it fails to be fully faithful for the same reason that Cat_{LEX} ⟶ Cat_{P B+T} failed to be so in the Introduction, namely that a functor preserving the chosen Φ-colimits has no reason to preserve the chosen ψ-colimits for ψ ∈ \overline{Φ} − Φ. However we can prove the following, a special case of which we foreshadowed in the Introduction.

5.5 Theorem. For any class Φ of weights, there is a 2-functor Γ : Φ-COLIM ⟶ \overline{Φ}- COLIM over CAT for which U_{\overline{Φ},Φ}Γ is the identity of Φ-COLIM.

Proof. To give a 2-functor Γ : Φ-COLIM ⟶ \overline{Φ}-COLIM over CAT is just to assign a choice of \overline{Φ}-colimits to every (locally small) category with chosen Φ-colimits, in such a way that each functor strongly preserving the original Φ-colimits also strongly preserves the newly-chosen \overline{Φ}-colimits. We shall shortly construct such a Γ, but without making any attempt to meet the further requirement that U_{\overline{Φ},Φ}Γ = 1, which asks the new \overline{Φ}- colimit ψ ∗ T to be the old Φ-colimit ψ ∗ T (with its representing isomorphism) when ψ ∈ Φ; for such an attempt would complicate our induction below. Once we have such a Γ, we can modify it trivially to meet the requirement that U_{\overline{Φ},Φ}Γ = 1 : for ψ ∈ Φ, we just throw away the new \overline{Φ}-colimit ψ ∗ T, and replace it by the original Φ-colimit.

Suppose, then, that A is a category with chosen Φ-colimits, and that K is a small category. We shall now assign to A inductively all those \overline{Φ}-colimits ψ ∗ T for which T : K ⟶ A is a functor with domain K and ψ : K^{op} ⟶ Set is an element of \overline{Φ} with domain K^{op}, each with its representing isomorphism π : A(ψ ∗ T, A) ≅ [K^{op}, Set](ψ, A(T −, A)); and we shall check at each stage that ψ ∗ T is strictly preserved by all those functors G : A ⟶ B that strictly preserve the chosen Φ-colimits.

The ψ in \overline{Φ} with domain K^{op} are the objects of Φ(K), which as in Section 5.4 is ⋃_{α<∞} K_{α}. For each ψ in K_{0} we choose a pair (K, ρ) where K ∈ K and ρ : K(−, K) ≅ ψ is an isomorphism in [K^{op}, Set]. We have the composite natural (in A) isomorphism

\xymatrix{[K^{op}, Set](ψ, A(T −, A)) \ar[r]_{[K^{op},Set](ρ,1)} & [K^{op}, Set](K(−, K), A(T −, A)) \ar[d]^{κ} \\  & A(T K, A)}

wherein π is the Yoneda isomorphism. Accordingly we may assign as the colimit ψ∗T the object T K of A, with the inverse of the composite isomorphism above as the representing isomorphism π for ψ ∗T. It is immediate that any functor G : A ⟶ B strictly preserves this colimit ψ ∗ T.

We now suppose inductively that the colimits ψ ∗ T, along with this representing isomorphisms π, have been chosen for all ψ ∈ K_{α}, and are strictly preserved by such functors as strictly preserve the (original) chosen Φ-colimits; and we now consider a weight ψ : K^{op} ⟶ Set lying in K_{α+1} but not in K_{α}. For each such ψ we choose a triple (ϕ, S, λ) where ϕ : L^{op} ⟶ Set is a weight in Φ, while S : L ⟶ [K^{op}, Set] is a functor taking its values in K_{α}, and λ is a natural ( in θ) isomorphism [K^{op}, Set](ψ, θ) ≅ [L^{op}, Set](ϕ, [K^{op}, Set](S−, θ)) expressing ψ as a value of the colimit ϕ ∗ S. By the inductive hypothesis we have for each L in L the Φ-colimit SL ∗ T, with its representing isomorphism which we re-name

μ_{L} : A(SL ∗ T, A) ≅ [K^{op}, Set](SL, A(T −, A)) .

Again, we have the original Φ-colimit ϕ∗(S?∗T), where we are now using ? to denote a variable object of L, and – to denote one of K; along with its representing isomorphism

ν : A(ϕ ∗ (S? ∗ T), A) ≅ [L^{op}, Set](ϕ, A(S? ∗ T, A)) .

Putting θ = A(A, T −) in the isomorphism λ, we have the composite isomorphism

\xymatrix{[K^{op}, Set](ψ, A(T −, A)) \ar[r]^{λ} & [L^{op}, Set](ϕ?, [K^{op}, Set]((S−)?, A(T −, A)) \ar[d]^{[L^{op},Set](ϕ?,μ^{−1})} \\ A(ϕ ∗ (S? ∗ T), A) & [L^{op}, Set](ϕ?, A(S? ∗ T, A)). \ar[l]^{ν^{−1}}}

Accordingly we may assign as the colimit ψ ∗ T the object ϕ ∗ (S? ∗ T) of A, with the inverse of the composite isomorphism above as its representing isomorphism π. Moreover G : A ⟶ B strictly preserves this colimit if it strictly preserves Φ-colimits; for in the relevant diagram from Section 5.1, the λ-part commutes by the naturality of λ in θ, the μ-part commutes by the inductive hypothesis, and the ν-part commutes because G strictly preserves Φ-colimits. The truth of the theorem now follows by induction.

5.6 Corollary. Whenever Ψ is a class of weights with Φ ⊂ Ψ ⊂ \overline{Φ}, there is a 2functor Γ′ : Φ-COLIM ⟶ Ψ-COLIM over CAT for which U_{Ψ,Φ}Γ′ is the identity of Φ-COLIM.

Proof. With Γ : Φ-COLIM ⟶ \overline{Φ}-COLIM as in Theorem 5.5, we have only to set Γ′ = U_{\overline{Φ},Ψ}Γ.

Restricting to small categories and to classical colimits — or rather limits — of diagrams with finite graphs as domains, and now writing Γ rather than Γ′ in Corollary 5.6, we get what we need for Theorem 1.4:

5.7 Corollary. Given classes M and N of finite graphs with M ⊂ N ⊂ \overline{M}, write (as in the Introduction) U_{N ,M} : Cat_{N} ⟶ Cat_{M} for the forgetful functor. Then there is a functor Γ : Cat_{M} ⟶ Cat_{N} over Cat having U_{N ,M}Γ = 1.

5.8 The proof of Theorem 1.4 We use Corollary 5.7 and Lemma 2.2. It suffices to treat the case where M ⊂ N ⊂ \overline{M}, as in the corollary above. Suppose first that Cat_{M} is monadic over Gph, and consider as in Lemma 2.2 a coequalizer

\xymatrix{K \ar[r]^{P_{1}} \ar[r]_{P_{2}} & L \ar[r]_{Q} & C}

in Cat which is split in Gph, the functors P_{1} and P_{2} being morphisms in Cat_{N}. Then they are a fortiori morphisms in Cat_{M}; and since this is monadic over Gph it follows that C has and Q preserves M-limits. Because N ⊂ \overline{M} it is also the case that C has and Q preserves N -limits; so that Cat_{N} is monadic over Gph by Lemma 2.2.

Now suppose that Cat_{N} is monadic over Gph, and consider again a coequalizer as above in Cat which is split in Gph, but now with P_{1}, P_{2} : K ⟶ L being morphisms in Cat_{M}. Then ΓP_{1}, ΓP_{2} : ΓK ⟶ ΓL (with the Γ of 5.7) are morphisms in Cat_{N}, which as functors are just P_{1}, P_{2} : K ⟶ L, since U_{N ,M}Γ = 1. By the monadicity over Gph of Cat_{N}, it follows that C has and Q preserves N -limits; so certainly C has and Q preserves M-limits, so that Cat_{M} is monadic over Gph by Lemma 2.2.

5.9 Remark. We have not used above that part of Theorem 5.5 and Corollary 5.6 stating that Γ and Γ′ are not merely functors but in fact 2-functors over CAT. However this extra piece of knowledge has important consequences. Kelly and Lack show in the article [LK] that Φ-Colim is 2-monadic over Cat, and that Φ-COLIM is 2-monadic over CAT, even for large classes Φ and even for enriched categories (with CAT replaced by V-CAT). If T is the 2-monad on CAT for Φ-COLIM, and \overline{T} that for \overline{Φ}-COLIM, there is a canonical morphism ρ : \overline{T} ⟶ T of 2-monads corresponding to the forgetful U_{\overline{Φ},Φ}. Now Theorem 5.5 gives the existence of a morphism σ : T ⟶ \overline{T} of 2-monads with σρ = 1; whereupon ρσ ≅ 1 follows from the equality \overline{Φ}-COCOM = Φ-COCOM. Thus the 2-monads T and \overline{T} are exhibited as equivalent, although not isomorphic; see Section 4 of [LK] for the details.

References

[AHS] J. Adámek, H. Herrlich and G. E. Strecker, Abstract and Concrete Categories, Wiley Publ., New York 1990

[AK] M.H. Albert and G.M. Kelly, The closure of a class of colimits, J. Pure Appl. Algebra 51 (1988), 1-17.

[BU] A. Burroni, Algèbres graphiques, Cahiers de Topologie et Géom. Différentielle 22 (1981), 249-265.

[CL] F. Coppey and C. Lair, Algébricité, monadicité, esquissabilité, et non-algébricité, Diagrammes 25, Paris 1991.

[DK] E.J. Dubuc and G.M. Kelly, A presentation of topoi as algebraic relative to categories or graphs, J. Algebra 81 (1983), 420-433.

[KE] G.M. Kelly, Basic Concepts of Enriched Category Theory, London Math. Soc. Lecture Notes Series 64, Cambridge Univ. Press, 1982.

[LK] G.M. Kelly and Stephen Lack, On the monadicity of categories with chosen colimits, Theory and Applications of Categories 7 (2000), 148-170.

[KL] G.M. Kelly and I. Le Creurer, On the monadicity over graphs of categories with limits, Cahiers de Topologie et Geóm. Diff. Catégoriques 38 (1997), 179-191.

[PR] G.M. Kelly and R. Paré, A note on the Albert-Kelly paper “The closure of a class of colimits”, J. Pure Appl. Algebra 51 (1988), 19-25.

[PW] G.M. Kelly and A.J. Power, Adjunctions whose counits are coequalizers and presentations of finitary enriched monads, J. Pure Appl. Algebra 89 (1993), 163-179.

[LR] C. Lair, Esquissabilité des structures algébriques, Thèse de Doctorat es Sciences, Amiens, 1977.

[ML] S. Mac Lane, Categories for the Working Mathematician, Springer-Verlag, New York-Heidelberg-Berlin 1971.

[MS] J. MacDonald and A. Stone, Topoi over graphs, Cahiers de Topologie et Géom. Diff. Catégoriques 25 (1984), 54-62.

Technical University of Braunschweig Postfach 3329, 38023 Braunschweig GERMANY

School of Mathematics and Statistics FO7 University of Sydney N.S.W. 2006 AUSTRALIA

E-mail: adamek@iti.cs.tu-bs.de and maxk@maths.usyd.edu.au

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/7/n8/n8.{dvi,ps}.

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

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

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

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

rrosebrugh@mta.ca.

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

Editorial board.

John Baez, University of California, Riverside: baez@math.ucr.edu Michael Barr, McGill University: barr@barrs.org Lawrence Breen, Université 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: carboni@fis.unico.it 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 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 Andrew Pitts, University of Cambridge: Andrew.Pitts@cl.cam.ac.uk Robert Rosebrugh, Mount Allison University: rrosebrugh@mta.ca Jiri Rosicky, Masaryk University: rosicky@math.muni.cz James Stasheff, University of North Carolina: jds@math.unc.edu Ross Street, Macquarie University: street@math.mq.edu.au Walter Tholen, York University: tholen@mathstat.yorku.ca Myles Tierney, Rutgers University: tierney@math.rutgers.edu Robert F. C. Walters, University of Insubria: walters@fis.unico.it R. J. Wood, Dalhousie University: rjwood@mathstat.dal.ca