Theory and Applications of Categories, Vol. 23, No. 13, 2010, pp. 251–260.

WHAT ARE SIFTED COLIMITS?

J. ADÁMEK, J. ROSICKÝ, E. M. VITALE

Dedicated to Dominique Bourn on the occasion of his sixtieth birthday

Abstract. Sifted colimits, important for algebraic theories, are “almost” just the combination of filtered colimits and reflexive coequalizers. For example, given a finitely cocomplete category A, then a functor with domain A preserves sifted colimits iff it preserves filtered colimits and reflexive coequalizers. But for general categories A that statement is not true: we provide a counter-example.

Introduction

Sifted colimits play for the doctrine of finite products precisely the role which filtered colimits play for the doctrine of finite limits. Recall that a small category D which is filtered has the property that D-colimits commute with finite limits in Set. The converse is less well known (but trivial to prove using representable functors as diagrams): if Dcolimits commute with finite limits in Set, then D is filtered. Now sifted categories are defined as those small categories D such that D-colimits commute with finite products in Set. They were first studied (without any name) in the classical lecture notes of P. Gabriel and F. Ulmer [6] who proved that D is sifted iff the diagonal Δ: D → D × D is a final functor; this nicely corresponds to the fact that D is filtered iff the diagonals Δ: D → D^{J} are final for all finite graphs J. Sifted colimits are colimits whose schemes are sifted categories; they were studied (independently of [6]) by C. Lair [9] who called them “tamisante”, later P. T. Johnstone suggested the translation to “sifted”. Besides filtered colimits, prime examples of sifted colimits are reflexive coequalizers, that is, coequalizers of parallel pairs of epimorphisms with a joint splitting.

Sifted colimits are of major importance in general algebra. Recall that an algebraic theory (in the sense of F. W. Lawvere [10]) is a small category T with finite products and an algebra for T is a functor A : T → Set preserving finite products. The category Alg T of algebras is a full subcategory of the functor category Set^{T}. Now, let us denote by Sind A the free completion of a category A under sifted colimits (resembling the name Ind A for Grothendieck’s completion under filtered colimits, see [4]). Then for every algebraic theory T the category of algebras is just the above completion of T^{op}:

Financial support by the German Research Foundation (DFG) under the project “Coalgebraic Specifications”, by the Ministry of Education of the Czech Republic under the project MSM 0021622409, and by FNRS grant 1.5.276.09 are gratefully acknowledged.

Received by the editors 2009-06-22 and, in revised form, 2010-06-08.

Published on 2010-06-10 in the Bourn Festschrift.

2000 Mathematics Subject Classification: 18A30, 18A35.

Key words and phrases: sifted colimit, reflexive coequalizer, filtered colimit.

\begin{matrix}c \\ ◯ \end{matrix} J. Adámek, J. Rosický, E. M. Vitale, 2010. Permission to copy for private use granted.

Alg T = Sind T^{op}

see [2]. And algebraic functors, that is functors between algebraic categories induced by morphisms of algebraic theories, are precisely the functors preserving limits and sifted colimits, see [1].

The aim of our paper is to discuss the slogan

“filtered colimits = filtered colimits + reflexive coequalizers.”

This could mean the existence:

A category A has sifted colimits iff it has filtered colimits and reflexive coequalizers.

Or the preservation:

A functor F : A → B preserves sifted colimits iff it preserves filtered colimits and reflexive coequalizers.

Unfortunately, none of these two statements holds in general, as we demonstrate by counter-examples. However, both statements are true whenever A is finitely cocomplete. Whereas the first one is trivial, since filtered colimits imply cocompleteness, the latter one concerning preservation is not. Let us mention that this result, assuming A is cocomplete, was proved by A. Joyal (his proof even works for quasicategories, see [7]) and by S. Lack (see [8]). There proofs are different, and more elegant than our proof below, however, for our proof we only assume the existence of finite colimits. (Another proof assuming cocompleteness is presented in [3].)

Let us also remark that there is another interpretation of the above slogan: the free completion of a category A under sifted colimits can be constructed as a free completion of Ind A under reflexive coequalizers. This is true if A has finite coproducts and false in general, see [2].

Acknowledgement We are grateful to the referee whose comments led us to an improved presentation of our result.

1. Existence of Sifted Colimits

As mentioned in the Introduction, a small category D is called sifted iff D-colimits commute in Set with finite products. That is, given a diagram

D × J → Set

where J is a finite discrete category, then the canonical morphism

colim_{D}(∏_{J} D(d, j) → ∏_{J}(colim_{D}D(d, j)

is an isomorphism.

Colimits of diagrams over sifted categories are called sifted colimits.

1.1. Remark.

(i) As proved by P. Gabriel and F. Ulmer [6], a small, nonempty category D is sifted if and only if the diagonal functor Δ: D → D × D is final. This means that for every pair of objects A, B of D the category (A, B) ↓ Δ of cospans on A, B is connected. That is:

(a) a cospan A → X ← B exists, and

(b) every pair of cospans on A, B is connected by a zig-zag of cospans.

This characterization was later re-discovered by C. Lair [9].

(ii) P. Gabriel and F. Ulmer [6] also proved that a small category D is sifted if and only if D is final in its free completion Fam D under finite coproducts. In fact, (a) and (b) above clearly imply the same property for finite families of objects too. This is precisely the finality of D → Fam D.

(iii) Every small category with finite coproducts is sifted. This immediately follows from (i).

1.2. Example. ([2]) Reflexive coequalizers are sifted colimits. That is, the category D given by the graph

\xymatrix{P \ar[r]^{a_{1}} \ar[r]_{a_{2}} & Q \ar[l]_{d}}

and the equations

a_{1} · d = id_{B} = a_{2} · d

is sifted. This follows from the characterization of sifted colimits mentioned in the Introduction. We present a full proof here because we are going to use it again below. Let us add that this fact was already realized by Y. Diers [5] but remained unnoticed. Another proof is given in [12], Lemma 1.2.3.

In fact, suppose that

\xymatrix{A \ar[r]_{a_{2}} \ar[r]^{a_{1}} & B \ar[r]^{c} & C & and & A′ \ar[r]_{a′_{2}} \ar[r]^{a′_{1}} & B′ \ar[r]^{c′} & C′}

are reflexive coequalizers in Set. We can assume, without loss of generality, that c is the canonical function of the quotient C = B/ ∼ modulo the equivalence relation described as follows: two elements x, y ∈ B are equivalent iff there exists a zig-zag

[figure: A:; z_{1}; a_{i_{1}}; a_{i_{2}}; z_{2}; a_{i_{3}}; a_{i_{4}}; ······; z_{k}; a_{i_{2k−1}}; a_{i_{2k}}; B:; x; ···; y]

where i_{1}, i_{2}, …, i_{2k} are 1 or 2. For reflexive pairs a_{1}, a_{2} these zig-zags can always be chosen to have the following form

[figure: A:; z_{1}; a_{1}; a_{2}; z_{2}; a_{2}; a_{1}; ······; z_{2k}; a_{2}; a_{1}; B:; x; ···; y]  (∗)

where for the elements z_{2i} of A we use a_{1}, a_{2} and for the elements z_{2i+1} we use a_{2}, a_{1}. In fact, let d: B → A be a joint splitting of a_{1}, a_{2}. Thus given a zig-zag, say,

\xymatrix{ & z \ar[dl]_{a_{2}} \ar[dr]^{a_{1}} \\ x &  & y}

we can modify it as follows: put z_{1} = d(x) and z_{2} = z to get

\xymatrix{ & z_{1} \ar[dl]_{a_{1}} \ar[dr]^{a_{2}} &  & z_{2} \ar[dl]_{a_{2}} \ar[dr]^{a_{1}} \\ x &  & x &  & y}

Moreover, the length 2k of the zig-zag (∗) can be prolonged to 2k + 2 or 2k + 4 etc. by using d. Analogously, we can assume C′ = B′/ ∼′ where ∼′ is the equivalence relation given by zig-zags of a′_{1} and a′_{2} of the above form (∗). Now we form the parallel pair

\xymatrix{A × A′ \ar[r]^{a_{1}×a′_{1}} \ar[r]_{a_{2}×a′_{2}} & B × B′}

and obtain its coequalizer by the zig-zag equivalence ≈ on B × B′. Given (x, x′) ≈ (y, y′) in B × B′, we obviously have zig-zags both for x ∼ y and for x′ ∼′ y′ (use projections of the given zig-zag). But also the other way round: whenever x ∼ y and x′ ∼′ y′, then we choose the two zig-zags so that they both have the above type (∗) and have the same lengths. They create an obvious zig-zag for (x, x′) ≈ (y, y′). From this it follows that the map

\xymatrix{A × A′ \ar[r]^{a_{1}×a′_{1}} \ar[r]_{a_{2}×a′_{2}} & B × B′ \ar[r]^{c×c′} & (B/ ∼) × (B′/ ∼′)}

is a coequalizer, as required.

1.3. Example. By merging two copies of reflexive pairs we also obtain a sifted category D: let D be given by the graph

\xymatrix{A \ar[r]^{a_{1}} \ar[r]_{a_{2}} & B \ar[l]_{d} \ar[r]^{d′} & A′ \ar[l]^{a′_{2}} \ar[l]_{a′_{1}}}

and the equations making both parallel pairs reflexive:

a_{i} · d = id_{B} = a′_{i} · d′ for i = 1, 2

The proof that D is sifted is completely analogous to the proof of Example 1.2: we verify that colimits over D in Set commute with finite products. Assume that the above graph depicts sets A, B and A′ and functions between them. Then a colimit can be described as the canonical function c: B → C = B/ ∼ where two elements x, y ∈ B are equivalent iff they are connected by a zig-zag formed by a_{1}, a_{2}, a′_{1} and a′_{2}. Since the two pairs are reflexive, the length of the zig-zag can be arbitrarily prolonged. And the type can be chosen to be

[figure: z_{1}; a_{1}; a_{2}; z_{2}; a_{2}; a_{1}; z_{3}; a′_{1}; a′_{2}; z_{4}; a′_{2}; a′_{1}; _{......}; z_{4k}; a′_{1}; x; y]

From that it is easy to derive that D is sifted.

1.4. Example. A category A which does not have sifted colimits although it has both filtered colimits and reflexive coequalizers: A is the free completion of D from 1.3 under filtered colimits and reflexive coequalizers. We claim that A is obtained from D by simply adding the coequalizer c of a_{1}, a_{2} and the coequalizer c′ of a′_{1}, a′_{2}. That is, we consider the graph

\xymatrix{A \ar[dr]^{a_{1}} \ar[dr]_{a_{2}} &  & A′ \ar[dl]^{a′_{2}} \ar[dl]_{a′_{1}} \\  & B \ar[ul]_{d} \ar[ur]^{d′} \ar[dl]_{c′} \ar[dr]^{c} \\ C′ &  & C}

and the equations

c · a_{1} = c · a_{2} c′ · a′_{1} = c′ · a′_{2}.

In fact, the category A is clearly finite. Therefore, its only filtered diagrams are its idempotents:

e_{i} = d · a_{i} and e′_{i} = d′ · a′_{i} (i = 1, 2) .

We claim that a_{1} is the colimit of e_{1}. In fact, a_{1} · e_{1} = a_{1}, and given a morphism f with

f · e_{1} = f ,

then we see that f · d · a_{1} = f, consequently, f factorizes through a_{1}. Since a_{1} is an epimorphism, this factorization is unique. Analogously for e_{2}, e′_{1} and e′_{2}. Thus, A has filtered colimits. And it has reflexive coequalizers because its only reflexive pairs of distinct morphisms are a_{1}, a_{2} whose coequalizer is c, and a′_{1}, a′_{2} whose coequalizer is c′. It is obvious that the (sifted) embedding D : D → A does not have a colimit.

2. Preservation of Sifted Colimits

2.1. Theorem. A functor F: A → B with A finitely cocomplete preserves sifted colimits iff it preserves filtered colimits and reflexive coequalizers.

Proof. Given a sifted diagram D: D → A with a colimit in A, we prove that F · D has colimit F (colim D) in D.

Recall from 1.1(ii) that D: D → FamD is final, thus, D has the same colimit as its extension \overline{D}: FamD → A preserving finite coproducts. Therefore, without loss of generality we can assume that D has finite coproducts and D preserves them (if not, substitute \overline{D} for D). Recall also the construction of finite colimits via finite coproducts and coequalizers from [11]: given a finite graph M and a functor F : M → A we form coproducts

∐_{i} F (i)

indexed by objects i of M and with injections.

α_{i} : F (i) → ∐_{i} F (i).

Analogously, we form coproducts

∐_{f:i→i′} F (i)

indexed by morphisms f of M and with injections

β_{f} : F (i) → ∐_{f:i→i′} F (i).

Consider morphisms

a, b : ∐_{f:i→i′} F (i) → ∐_{i} F (i)

such that a · β_{f} = α_{i} and b · β_{f} = α_{i′} · F f for each morphism f : i → i′ in M. If q : ∐_{i} F (i) → Q is the coequalizer of a and b, then Q = colim F with the colimit cocone q · α_{i}.

We now prove the theorem:

(1) For every finite reflexive subgraph M of D we form coproducts in D

i_{M} = ∐_{i} i j_{M} = ∐_{f:i→i′} i

and morphisms

a_{M}, b_{M} : j_{M} → i_{M}

analogous to those considered above. Since D preserves the two coproducts, we have a = Da_{M} and b = Db_{M} and the colimit Q_{M} of the domain restriction D/M of D on M is given by the coequalizer

\xymatrix{Dj_{M} \ar[r]^{Da_{M}} \ar[r]_{Db_{M}} & Di_{M} \ar[r]^{q_{M}} & Q_{M} = colim D/M}

Since the graph M is reflexive, a_{M}, b_{M} is a reflexive pair, thus, so is Da_{M}, Db_{M}. Let M be the directed family of all finite reflexive subgraphs of D.

(2) Let k_{i}: Di → K (i ∈ obj D) be a colimit of D, then we prove that (F k_{i}) is a colimit of F D. We express D as the directed union of all D/M for M ∈ M and for each M ∈ M we see that

k_{i_{M}} · Da_{M} = k_{j_{M}} = k_{i_{M}} · Db_{M}  (1)

from which we derive that k_{i_{M}} factors through the coequalizer

k_{i_{M}} = r_{M} · q_{M} for some r_{M}: Q_{M} → K .  (2)

Then K is the filtered colimit of all Q_{M} with the colimit cocone (r_{M})_{M∈M} (since every colimit is a filtered colimits of all finite subcolimits). We conclude that

(i) F K is a colimit of F Q_{M} with the cocone F r_{M} (M ∈ M),

and

(ii) for every M ∈ M the coequalizer of F Da_{M} and F Db_{M} is F q_{M}.

(3) Given a cocone

x_{i}: F D_{i} → X (i ∈ obj D)

of F D, we are to find a factorization through (F k_{i}). Analogously to (1) above we have, for every M ∈ M

x_{i_{M}} · F Da_{M} = x_{j_{M}} = x_{i_{M}} · F Db_{M}

thus, there exists a unique

y_{M}: F Q_{M} → C with x_{i_{M}} = y_{M} · F q_{M} .  (3)

These morphisms form a cocone of the filtered diagram of all F Q_{M}’s: in fact, the connecting morphisms

q_{M,M′}: Q_{M} → Q_{M′} (M, M′ ∈ M, M ⊆ M′)

are defined by the commutative squares

\xymatrix{Di_{M} \ar[r]^{Di_{MM′}} \ar[d]_{q_{M}} & Di_{M′} \ar[d]^{q_{M′}} \\ Q_{M} \ar[r]_{q_{M,M′}} & Q_{M′}}

where i_{MM′}: i_{M} → i_{M′} is the coproduct injection in D. The desired equality

y_{M} = y_{M′} · F q_{MM′}

easily follows since, by (ii), F q_{M} is an epimorphism:

\xymatrix{F Di_{M} \ar[rr]^{F Di_{MM′}} \ar[dr]_{x_{i_{M}}} \ar[dd]_{F q_{M}} &  & F Di_{M′} \ar[dd]^{F q_{M′}} \ar[dl]^{x_{i′_{M}}} \\  & · \\ F Q_{M} \ar[ur]_{y_{M}} \ar[rr]_{F q_{M,M′}} &  & F Q_{M′} \ar[ul]_{y_{M′}}}

Consequently, we obtain the unique

y: F K → X with y · F r_{M} = y_{M} .

This is the desired factorization: for every i ∈ I we have

y · F k_{i} = x_{i}.

In fact, consider the singleton subgraph M with one object i and its identity morphism. Obviously

i_{M} = i and q_{M} = id , thus, r_{M} = k_{i}

which yields by (3)

y_{M} · F k_{i} = y_{M} = y_{M} · F q_{M} = x_{i_{M}} = x_{i} .

The uniqueness is clear: since each F q_{M} is an epimorphism, from (2) we see that (F r_{M} · F q_{M}) is collectively epic, and then (1) implies that (F k_{i}) is collectively epic.

2.2. Example. A functor F which

(1) does not preserve sifted colimits

but

(2) preserves filtered colimits and reflexive coequalizers

can be constructed as follows.

By adding to the category A of 1.4 a terminal object T we obtain a category A′ in which the sifted diagram D: D → A has colimit

colim D = T .

Let B be the category obtained from A′ by adding a new terminal object S. The functor F: A′ → B with F (T) = S which is the identity map on objects and morphisms of A does not preserve sifted colimits because colim F · D = T but F (colim D) = S. It is easy to verify that F preserves filtered colimits and reflexive coequalizers.

WHAT ARE SIFTED COLIMITS?  259

References

[1] J. Adámek, F. W. Lawvere and J. Rosický, On the duality between varieties and algebraic theories, Alg. Univ. 49 (2003) 35–49.

[2] J. Adámek and J. Rosický, On sifted colimits and generalized varieties, Theory Appl. Categ. 8 (2000) 33–53.

[3] J. Adámek, J. Rosický and E. M. Vitale, Algebraic Theories: A Categorical Introduction to General Algebra, Cambridge Univ. Press 2010 (to appear).

[4] M. Artin, A. Grothendieck and J. L. Verdier, Théorie des topos at cohomologie étale des schémas, Springer LNM 269, Springer-Verlag 1972.

[5] Y. Diers, Type de densité d’un sous-catégorie pleine, Ann. Soc. Sc. Bruxelles 90 (1976) 25–47.

[6] P. Gabriel and F. Ulmer, Lokal Präsentierbare Kategorien, Springer LNM 221, Springer-Verlag 1971.

[7] A. Joyal, Notes on Logoi, preprint 2008.

[8] S. Lack and J. Rosický, Notions of Lawvere theory, Appl. Cat. Structures (to appear).

[9] C. Lair, Sur le genre d’esquissibilité des catégories modelables (accessibles) possédant les produit de deux, Diagrammes 35 (1996) 25–52.

[10] F. W. Lawvere, Functorial semantics of algebraic theories, Dissertation, Columbia University 1963.

[11] S. MacLane, Categories for the Working Mathematician, Springer-Verlag 1971.

[12] M. C. Pedicchio and F. Rovatti, Algebraic Categories, in: Categorical Foundations (edited by M. C. Pedicchio and W. Tholen), Cambridge Univ. Press 2004.

Institute of Theoretical Computer Science Technical University Braunschweig 38032 Braunschweig, Germany. Department of Mathematics and Statistics Masaryk University 611 37 Brno, Czech Republic. Institut de Recherche en Mathématique et Physique Université catholique de Louvain B 1348 Louvain-la-Neuve, Belgique

Email: j.adamek@tu-bs.de
      rosicky@math.muni.cz
      enrico.vitale@uclouvain.be

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

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

THEORY AND APPLICATIONS OF CATEGORIES (ISSN 1201-561X) will disseminate articles that significantly advance the study of categorical algebra or methods, or that make significant new contributions to mathematical science using categorical methods. The scope of the journal includes: all areas of pure category theory, including higher dimensional categories; applications of category theory to algebra, geometry and topology and other areas of mathematics; applications of category theory to computer science, physics and other mathematical sciences; contributions to scientific knowledge that make use of categorical methods. Articles appearing in the journal have been carefully and critically refereed under the responsibility of members of the Editorial Board. Only papers judged to be both significant and excellent are accepted for publication. Full text of the journal is freely available in .dvi, Postscript and PDF from the journal’s server at http://www.tac.mta.ca/tac/ and by ftp. It is archived electronically and in printed paper format.

Subscription information. Individual subscribers receive abstracts of articles by e-mail as they are published. To subscribe, send e-mail to tac@mta.ca including a full name and postal address. For institutional subscription, send enquiries to the Managing Editor, Robert Rosebrugh, rrosebrugh@mta.ca.

Information for authors. The typesetting language of the journal is TEX, and L^{A}TEX2e strongly encouraged. Articles should be submitted by e-mail directly to a Transmitting Editor. Please obtain detailed information on submission format and style files at http://www.tac.mta.ca/tac/.

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

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

Assistant TEX editor. Gavin Seal, Ecole Polytechnique Fédérale de Lausanne:

gavin seal@fastmail.fm

Transmitting editors.

Clemens Berger, Université de Nice-Sophia Antipolis, cberger@math.unice.fr Richard Blute, Université d’ Ottawa: rblute@uottawa.ca Lawrence Breen, Université de Paris 13: breen@math.univ-paris13.fr Ronald Brown, University of North Wales: ronnie.profbrown (at) btinternet.com Aurelio Carboni, Università dell Insubria: aurelio.carboni@uninsubria.it Valeria de Paiva, Cuill Inc.: valeria@cuill.com Ezra Getzler, Northwestern University: getzler(at)northwestern(dot)edu Martin Hyland, University of Cambridge: M.Hyland@dpmms.cam.ac.uk P. T. Johnstone, University of Cambridge: ptj@dpmms.cam.ac.uk Anders Kock, University of Aarhus: kock@imf.au.dk Stephen Lack, University of Western Sydney: s.lack@uws.edu.au F. William Lawvere, State University of New York at Buffalo: wlawvere@acsu.buffalo.edu Tom Leinster, University of Glasgow, T.Leinster@maths.gla.ac.uk Jean-Louis Loday, Université de Strasbourg: loday@math.u-strasbg.fr Ieke Moerdijk, University of Utrecht: moerdijk@math.uu.nl Susan Niefield, Union College: niefiels@union.edu Robert Paré, Dalhousie University: pare@mathstat.dal.ca Jiri Rosicky, Masaryk University: rosicky@math.muni.cz Brooke Shipley, University of Illinois at Chicago: bshipley@math.uic.edu James Stasheff, University of North Carolina: jds@math.unc.edu Ross Street, Macquarie University: street@math.mq.edu.au Walter Tholen, York University: tholen@mathstat.yorku.ca Myles Tierney, Rutgers University: tierney@math.rutgers.edu Robert F. C. Walters, University of Insubria: robert.walters@uninsubria.it R. J. Wood, Dalhousie University: rjwood@mathstat.dal.ca