Theory and Applications of Categories, Vol. 6, No. 6, pp. 77–82.

COMPARING COEQUALIZER AND EXACT COMPLETIONS

Dedicated to Joachim Lambek on the occasion of his 75th birthday.

M. C. PEDICCHIO AND J. ROSICKÝ

ABSTRACT. We characterize when the coequalizer and the exact completion of a category 𝒞 with finite sums and weak finite limits coincide.

Introduction

Our aim is to compare two well known completions: the coequalizer completion 𝒞_{coeq} of a small category 𝒞 with finite sums (see [P]) and the exact completion of a small category 𝒞 with weak finite limits (see [CV]). For a category 𝒞 with finite sums and weak finite limits, 𝒞_{ex} is always a full subcategory of 𝒞_{coeq}. We characterize when the two completions are equivalent - it turns out that this corresponds to a finiteness condition expressed in terms of reflexive and symmetric graphs in 𝒞.

1. Two completions

For a small category 𝒞 with finite sums, the coequalizer completion of 𝒞 is a category 𝒞_{coeq} with finite colimits together with a finite sums preserving functor G𝒞 : 𝒞 → 𝒞_{coeq} such that, for any finite sums preserving functor F : 𝒞 → 𝒳 into a finitely cocomplete category, there is a unique finite colimits preserving functor \overline{F} : 𝒞_{coeq} → 𝒳 with \overline{F} · G𝒞 = F. This construction has been described by Pitts (cf. [BC]).

For a small category 𝒞 with weak limits, the exact completion E𝒞 : 𝒞 → 𝒞_{ex} can be characterized by a universal property as well (see [CV]). In a special case when 𝒞 has finite limits, E𝒞 is a finite limits preserving functor into an exact category 𝒞_{ex} such that, for any finite limits preserving functor F : 𝒞 → 𝒳 into an exact category, there is a unique functor F′ : 𝒞_{ex} → 𝒳 which preserves finite limits and regular epimorphisms such that F′ · E𝒞 = F. Following [HT], 𝒞_{ex} can be described as a full subcategory of Set^{𝒞 ^{op}} and E𝒞 as the codomain restriction of the Yoneda embedding Y : 𝒞 → Set^{𝒞 ^{op}}. To explain it, we recall that a functor H : 𝒞 ^{op} → Set is weakly representable if it admits a regular epimorphism γ : Y C → H from a representable functor. Then 𝒞_{ex} consists of those weakly representable functors H admitting γ : Y C → H whose kernel pair

Second author partially supported by the Grant Agency of the Czech Republic under the grant No.

201/99/0310 and by the Italian CNR.

Received by the editors 1999 January 12 and, in revised form, 1999 August 27.

Published on 1999 November 30.

1991 Mathematics Subject Classification: 18A99.

Key words and phrases: exact completion, coequalizer completion, variety.

\begin{matrix}c \\ ◯ \end{matrix} M. C. Pedicchio and J. Rosický 1999. Permission to copy for private use granted.

\xymatrix{K \ar[r]^{α} \ar[r]_{β} & Y C \ar[r]^{γ} & H}  (1)

has K weakly representable.

We will start by showing that 𝒞_{coeq} can be presented as a full subcategory of Set^{𝒞 ^{op}} too, with G𝒞 being the codomain restriction of Y. The full subcategory of Set^{𝒞 ^{op}} consisting of all finite products preserving functors will be denoted by F P (𝒞 ^{op}). It is well known that F P (𝒞 ^{op}) is a variety (see [AR] 3.17).

1.1. Lemma. Let 𝒞 be a category with finite sums. Then 𝒞_{coeq} is equivalent to the full subcategory of F P (𝒞 ^{op}) consisting of finitely presentable objects in F P (𝒞 ^{op}).

Proof. By the universal property of 𝒞_{coeq}, we get

F P (𝒞 ^{op}) ≈ Lex((𝒞_{coeq})^{op})

where, on the right, there is the full subcategory of Set^{(𝒞_{coeq})^{op}} consisting of all finite limits preserving functors. The result thus follows from [AR] 1.46.

1.2. Proposition. Let 𝒞 be a category with finite sums and weak finite limits. Then 𝒞_{ex} is equivalent to a full subcategory of 𝒞_{coeq}.

Proof. Let H ∈ 𝒞_{ex} and consider the corresponding diagram (1). There is a regular epimorphism δ : Y D → K (because K is weakly representable) and we obtain a coequalizer

\xymatrix{Y D \ar[r]^{\overline{α}} \ar[r]_{\overline{β}} & Y C \ar[r]^{γ} & H}  (2)

where \overline{α} = αδ and \overline{β} = βδ. Since Y D is a regular projective in Set^{𝒞 ^{op}}, the graph (\overline{α}, \overline{β}) is reflexive (it means the existence of φ : Y C → Y D with \overline{α}φ = \overline{β}φ = id_{Y (C)}). Following [PW], (2) is a coequalizer in F P (𝒞 ^{op}). Therefore, H is finitely presentable in F P (𝒞 ^{op}) (cf. [AR] 1.3). Hence, using Lemma 1.1, H belongs to 𝒞_{coeq}.

When 𝒞 has finite sums, objects of 𝒞 are precisely finitely generated free algebras in the variety F P (𝒞 ^{op}). The condition of having weak finite limits too, is a very restrictive one. We give another formulation of it.

1.3. Proposition. Let 𝒞 have finite sums. Then 𝒞 has weak finite limits iff finite limits of objects of 𝒞 in F P (𝒞 ^{op}) are finitely generated.

Proof. Let D : 𝒟 → 𝒞 be a finite diagram and (δ_{d} : A → Y D_{d})_{d∈𝒟} its limit in F P (𝒞 ^{op}).

Assume that A is finitely generated. Then there is a regular epimorphism π : Y C → A where C ∈ 𝒞. Consider a cone (f_{d} : X → D_{d})_{d∈𝒟} in 𝒞. There is a unique φ : Y X → A with δ_{d}φ = Y f_{d} for all d ∈ 𝒟 . Since π is a regular epimorphism (and Y X regular projective) φ factorizes through π and therefore (δ_{d}π : Y C → Y D_{d})_{d∈𝒟} is a weak limit of Y D in Y (𝒞). Hence D has a weak limit in 𝒞.

Conversely, assume that D has a weak limit (γ_{d} : C → D_{d})_{d∈𝒟} in 𝒞. There is a unique π : Y C → A with δ_{d}π = Y γ_{d} for all d ∈ 𝒟 . Consider φ : Y X → A, X ∈ 𝒞. There exists φ : X → C such that Y (γ_{d}ψ) = δ_{d}φ for all d ∈ 𝒟 . Hence φ = πψ, which implies that π is a regular epimorphism (because Y X, X ∈ 𝒞 are finitely generated free algebras in the variety F P (𝒞 ^{op})). Hence A is finitely generated.

2. When do they coincide?

2.1. Construction. Let 𝒞 be a category with weak finite limits. Let r_{0}, r_{1} : C_{1} → C_{0} be a reflexive and symmetric graph in 𝒞. It means that there are morphisms d : C_{0} → C_{1} and s : C_{1} → C_{1} with r_{0}d = r_{1}d = id_{C_{0}} and r_{1}s = r_{0}, r_{0}s = r_{1}. We form a weak pullback

\xymatrix{ & C_{2} \ar[dl]_{_{\overline{r}_{0}}} \ar[dr]^{_{\overline{r}_{1}}} \\ C_{1} \ar[dr]_{r_{1}} &  & C_{1} \ar[dl]_{r_{0}} \\  & C_{0}}  (3)

By taking r_{i}^{2} = r_{i}r̄_{i}, i = 0, 1, we get the graph

\xymatrix{C_{2} \ar[r]^{r_{0}^{2}} \ar[r]_{r_{1}^{2}} & C_{1}}

This graph is reflexive: d^{2} : C_{0} → C_{2} is given by r̄_{0}d^{2} = r̄_{1}d^{2} = d. It is also symmetric: s^{2} : C_{2} → C_{2} is given by r̄_{0}s^{2} = sr̄_{1} and r̄_{1}s^{2} = sr̄_{0}. By iterating this procedure, we get reflexive and symmetric graphs

\xymatrix{C_{n} \ar[r]^{r_{0}^{n}} \ar[r]_{r_{1}^{n}} & C_{1}}

for n = 1, 2, . . ..

2.2. Definition. Let 𝒞 have weak finite limits. We say that a reflexive and symmetric graph r_{0}, r_{1} : C_{1} → C_{0} has a bounded transitive hull if there is n ∈ ℕ such that, for any m > n, there exists f_{m} : C_{m} → C_{n} with r_{0}^{n}f_{m} = r_{0}^{m} and r_{1}^{n}f_{m} = r_{1}^{m}.

It is easy to check that the definition does not depend on the choice of weak finite limits. Evidently, if 𝒞 has finite limits, Definition 2.2 means that the pseudoequivalence generated by the graph r_{0}, r_{1} : C_{1} → C_{0} is equal to r_{0}^{n}, r_{1}^{n} : C_{n} → C_{0}.

2.3. Theorem. Let 𝒞 have finite sums and weak finite limits. Then 𝒞_{ex} is equivalent to 𝒞_{coeq} iff any reflexive and symmetric graph in 𝒞 has a bounded transitive hull.

Proof. I. Let r_{0}, r_{1} : C_{1} → C_{0} be a reflexive and symmetric graph in 𝒞. Consider the coequalizer

\xymatrix{Y C_{1} \ar[r]^{Y r_{0}} \ar[r]_{Y r_{1}} & Y C_{0} \ar[r]^{γ} & H}

in Set^{𝒞 ^{op}}. Put H_{1} = Y C_{1}, H_{0} = Y C_{0} and γ_{i} = Y r_{i} for i = 0, 1. Let γ_{0}^{n}, γ_{1}^{n} : H_{n} → H_{0} be iterations of the graph (γ_{0}, γ_{1}) constructed as before, by using pullbacks in Set^{𝒞 ^{op}}. There are morphisms ξ_{n} : Y C_{n} → H_{n} such that ξ_{1} = id_{H_{0}} and γ̄_{i}^{n}ξ_{n+1} = ξ_{n}Y (r̄_{i}^{n}) for i = 1, 2 and n = 0, 1, …:

\xymatrix{ &  & Y C_{n+1} \ar[dll]_{Y r̄_{0}^{n}} \ar[d]^{ξ_{n+1}} \ar[drr]^{Y r̄_{1}^{n}} \\ Y C_{n} \ar[dr]_{ξ_{n}} &  & H_{n+1} \ar[dl]_{γ̄_{0}^{n}} \ar[dr]^{γ̄_{1}^{n}} &  & Y C_{n} \ar[dl]^{ξ_{n}} \\  & H_{n} \ar[dr]_{γ_{1}^{n}} &  & H_{n} \ar[dl]^{γ_{0}^{n}} \\  &  & H_{0}}

By induction, we will prove that ξ_{n} are regular epimorphisms in Set^{𝒞 ^{op}}. Assume that ξ_{n} is a regular epimorphism and consider the pullback

\xymatrix{ & G \ar[dl]_{ρ_{0}} \ar[dr]^{ρ_{1}} \\ Y C_{n} \ar[dr]_{γ_{1}^{n}ξ_{n}} &  & Y C_{n} \ar[dl]^{γ_{0}^{n}ξ_{n}} \\  & H_{0}}

in Set^{𝒞 ^{op}}. There are morphisms φ : Y C_{n+1} → G and ψ : G → H_{n+1} such that ψφ = ξ_{n+1}, ϱ_{i}φ = Y r̄_{i}^{n} and γ̄_{i}^{n}ψ = ξ_{n}ϱ_{i} for i = 0, 1. Since ξ_{n} is a regular epimorphism in Set^{𝒞 ^{op}}, ψ is a regular epimorphism in Set^{𝒞 ^{op}}. Furthermore, it follows from the proof of Proposition 1.3 that φ is a regular epimorphism in Set^{𝒞 ^{op}} too. Hence ξ_{n+1} is a regular epimorphism in Set^{𝒞 ^{op}}.

Let I be the relation in Set^{𝒞 ^{op}} determined by the graph (γ_{0}, γ_{1}). It means that I is given by the regular epi-monopair factorization

\xymatrix{H_{1} \ar[rr]^{γ_{0}} \ar[rr]_{γ_{1}} \ar[dr]_{ι} &  & H_{0} \\  & I \ar[ur]^{ι_{0}} \ar[ur]_{ι_{1}}}

in Set^{𝒞 ^{op}}. Let ι_{0}^{n}, ι_{1}^{n} : I^{n} → H_{0} be the composition of n copies of I. Then I^{n} is the relation generated by the graph γ_{0}^{n}, γ_{1}^{n} : H_{n} → H_{0}. Since ξ_{n} : Y C_{n} → H_{n} is a regular epimorphism, I^{n} is also the relation generated by the graph Y r_{0}^{n}, Y r_{1}^{n} : Y C_{n} → Y C_{0} = H_{0}.

II. Now, assume that 𝒞 has bounded transitive hulls of reflexive and symmetric graphs. We are going to prove that 𝒞_{ex} ≈ 𝒞_{coeq}. Let H : 𝒞 ^{op} →Set belong to 𝒞_{coeq}. Following Proposition 1.2, it suffices to prove that H belongs to 𝒞_{ex}. Since F P (𝒞 ^{op}) is a variety and, following Lemma 1.1, H is finitely presentable, H is presented by a coequalizer

\xymatrix{H_{1} \ar[r]^{γ_{0}} \ar[r]_{γ_{1}} & H_{0} \ar[r]^{γ} & H}  (4)

of a reflexive and symmetric graph in F P (𝒞 ^{op}) where H_{1} and H_{0} are free algebras in F P (𝒞 ^{op}) over finitely many generators (cf. [AR], Remark 3.13). Since finitely presentable free algebras in F P (𝒞 ^{op}) are precisely finite sums of representable functors and G𝒞 : 𝒞 → 𝒞_{coeq} preserves finite sums, the functors H_{0} and H_{1} are representable, H_{i} = Y C_{i}, i = 0, 1. Hence we get a reflexive and symmetric graph r_{0}, r_{1} : C_{1} → C_{0} in 𝒞 such that γ_{i} = Y r_{i}, i = 0, 1. Since (4) is a coequalizer in Set^{𝒞 ^{op}} too (by [PW]), it suffices to show that the kernel pair

\xymatrix{K \ar[r]^{α} \ar[r]_{β} & Y C_{0} \ar[r]^{γ} & H}

has K weakly representable.

Since the graph (r_{0}, r_{1}) has a bounded transitive hull, there is n such that, for any m > n, there exists a graph morphism Y f_{m} : Y C_{m} → Y C_{n} from the graph (Y r_{0}^{m}, Y r_{1}^{m}) to the graph (Y r_{0}^{n}, Y r_{1}^{n}). Following I., they induce morphisms I^{m} → I^{n} of the corresponding relations. Hence I^{n} is an equivalence relation and, consequently, it yields a kernel pair of γ

\xymatrix{I^{n} \ar[r]^{ι_{0}^{n}} \ar[r]_{ι_{1}^{n}} & H_{0} \ar[r]^{γ} & H}

Hence K ≅ I^{n} and since I^{n} is a quotient of Y C_{n}, K is weakly representable.

III. Conversely, let 𝒞_{ex} ≈ 𝒞_{coeq} and consider a reflexive and symmetric graph r_{0}, r_{1} : C_{1} → C_{0} in 𝒞. Take a coequalizer

\xymatrix{Y C_{1} \ar[r]^{Y r_{0}} \ar[r]_{Y r_{1}} & Y C_{0} \ar[r]^{γ} & H}

in Set^{𝒞 ^{op}}. Following [PW], it is a coequalizer in F P (𝒞 ^{op}) as well and, using Lemma 1.1, we get that H ∈ 𝒞_{coeq}. Hence H ∈ 𝒞_{ex} and therefore the kernel pair

\xymatrix{K \ar[r]^{α} \ar[r]_{β} & Y C_{0} \ar[r]^{γ} & H}

has K weakly representable. Hence K is finitely generated in Set^{𝒞 ^{op}} (see [AR] 1.69). Since K is a union of the chain of compositions I^{n}, n = 0, 1, …, there is n such that K ≅ I^{n}. Hence I^{m} ≅ I^{n} for all m ≥ n. Following I., I^{m} is the relation generated by the graph (Y r_{0}^{m}, Y r_{1}^{m}). Since Y C_{m} are regular projectives, there are graph morphisms Y C_{m} → Y C_{n} for all m > n. Hence, there are graph morphisms f_{m} : C_{m} → C_{n} for all m > n. We have proved that 𝒞 has bounded transitive hulls of reflexive and symmetric graphs.

2.4. Example. 1) Let 𝒱 be a variety in which finitely generated algebras are closed under finite products and subalgebras (like sets, vector spaces or abelian groups). Let 𝒞 be the full subcategory of 𝒱 consisting of finitely generated free algebras. Then 𝒞_{ex} ≈ 𝒞_{coeq}.

At first, following [AR] 3.16, 𝒱 ≅ F P (𝒞 ^{op}) and Y : 𝒞 → F P (𝒞 ^{op}) corresponds to the inclusion 𝒞 ⊆ 𝒱. Consider a reflexive and symmetric graph r_{0}, r_{1} : C_{1} → C_{0} in 𝒞. The equivalence relation K ⊆ C_{0} × C_{0} determined by it is finitely generated (as a subalgebra of C_{0} × C_{0}). Following III. of the proof of 2.3, the graph (r_{0}, r_{1}) has a bounded transitive hull.

Remark that 𝒞 has weak finite limits (following Proposition 1.3).

2) On the other hand, it is easy to find examples of a small category 𝒞 such that 𝒞_{ex} ≈ 𝒞_{coeq} does not hold. It suffices to consider the category 𝒞 of countable sets (and the infinite path as a reflexive and symmetric graph in it) and to use Theorem 2.3.

References

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

[BC] M. Bunge and A. Carboni, The symmetric topos, Jour. Pure Appl. Algebra 105 (1995), 233-249 [CV] A. Carboni and E. M. Vitale, Regular and exact completions, Jour. Pure Appl. Algebra 125

(1998), 79-117

[HT] H. Hu and W. Tholen, A note on free regular and exact completions and their infinitary generalizations, Theory and Applications of Categories, 2 (1996), 113-132

[PW] M. C. Pedicchio and R. Wood, A simple characterization theorem of theories of varieties, to appear [P] A. Pitts The lex reflection of a category with finite products, unpublished notes 1996

University of Trieste Masaryk University Ple Europa 1 Janáčkovo nám. 2a 34100 Trieste, Italy 66295 Brno, Czech Republic

Email: pedicchi@univ.trieste.it and rosicky@math.muni.cz

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

anonymous ftp at ftp://ftp.tac.mta.ca/pub/tac/html/volumes/6/n6/n6.{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 and Postscript format. Details will be e-mailed to new subscribers and are available by WWW/ftp. 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 LaTEX 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 URL http://www.tac.mta.ca/tac/ or by anonymous ftp from ftp.tac.mta.ca in the directory pub/tac/info. 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é de Paris 13: breen@math.univ-paris13.fr Ronald Brown, University of North Wales: r.brown@bangor.ac.uk Jean-Luc Brylinski, Pennsylvania State University: jlb@math.psu.edu Aurelio Carboni, Università dell Insubria: carboni@fis.unico.it P. T. Johnstone, University of Cambridge: ptj@pmms.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.ruu.nl Susan Niefield, Union College: niefiels@union.edu Robert Paré, Dalhousie University: pare@mscs.dal.ca Andrew Pitts, University of Cambridge: ap@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@charlie.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 Sydney: walters b@maths.usyd.edu.au R. J. Wood, Dalhousie University: rjwood@mscs.dal.ca