Theory and Applications of Categories, Vol. 25, No. 7, 2011, pp. 180–188.

AN EMBEDDING THEOREM FOR ADHESIVE CATEGORIES

STEPHEN LACK

Abstract. Adhesive categories are categories which have pushouts with one leg a monomorphism, all pullbacks, and certain exactness conditions relating these pushouts and pullbacks. We give a new proof of the fact that every topos is adhesive. We also prove a converse: every small adhesive category has a fully faithful functor in a topos, with the functor preserving the all the structure. Combining these two results, we see that the exactness conditions in the definition of adhesive category are exactly the relationship between pushouts along monomorphisms and pullbacks which hold in any topos.

1. Introduction

Many different categorical structures involve certain limits and colimits connected by exactness conditions which state, roughly speaking, that limits and colimits in the category interact in the same way that they do in the category of sets; or better perhaps, that they interact in the same way that they do in any topos.

For example, we have the structure of regular category, which can be characterized as the existence of finite limits and coequalizers of kernel pairs, along with the condition that these coequalizers are stable under pullback. As evidence that this condition characterizes the interaction between finite limits and coequalizers of kernel pairs in a topos, we have on the one hand, the fact that any topos is a regular category, and on the other hand, the theorem of Barr [2] which asserts that any small regular category has a fully faithful embedding in a topos, and this embedding preserves coequalizers of kernel pairs and finite limits.

Then again, there is the structure of extensive category, which can be characterized as the existence of finite coproducts and pullbacks along coproduct injections, along with the condition that these coproducts are stable under pullback and disjoint. Once again, every topos is extensive, and every small extensive category has a fully faithful embedding in a topos, and this embedding preserves finite coproducts and all existing (finite) limits [11].

Adhesive categories are the analogue of extensive categories where one works with pushouts along a monomorphism rather than coproducts; the definition is recalled in the following section. The notion of adhesive category was introduced in [8] as a categorical framework for graph transformation and rewriting; see the volumes [1, 3] for more on this point of view. The ambient categories (typically labelled graphs of some sort or other) of the original applications are mostly toposes, but each particular application involves only a few objects, which transform into each other by means of the basic operations that were made explicit by the notion of adhesion. The notion of adhesive category also has one important stability property not shared by toposes: if 𝒞 is adhesive then so is any coslice X/𝒞.

The support of the Australian Research Council and DETYA is gratefully acknowledged.

Received by the editors 2011-03-03 and, in revised form, 2011-03-07.

Transmitted by F. W. Lawvere. Published on 2011-03-10.

2000 Mathematics Subject Classification: 18A30, 18B15, 18B25.

Key words and phrases: adhesive category, topos, embedding theorem.

\begin{matrix}c \\ ◯ \end{matrix} Stephen Lack, 2011. Permission to copy for private use granted.

Once again, every topos is adhesive, as shown in [10] and in Theorem 3.1 below, and it is natural to ask whether there is a corresponding embedding theorem. The purpose of this paper is to show that this is the case: every small adhesive category has a fully faithful embedding in a topos, and this embedding preserves pushouts along monomorphisms and all existing finite limits. I am grateful to Bill Lawvere for suggesting the question.

For each of the embeddings mentioned above, the construction is essentially the same. The Yoneda embedding Y : 𝒞 → [𝒞^{op}, Set] preserves all existing limits, but few colimits; in order to correct this we replace [𝒞^{op}, Set] by the full subcategory of sheaves for a topology on 𝒞 chosen so that the representables are sheaves and the restricted Yoneda embedding 𝒞 → Sh 𝒞 preserves the colimits in question. A general analysis of the sorts of colimits and exactness properties that can be dealt with in this way will be given in [5].

From a model-theoretic point of view, these embedding theorems can be viewed as completeness results. In the case of adhesive categories, for instance, since every topos is adhesive, and every (small) adhesive category has a fully faithful embedding into a topos preserving pushouts along monomorphisms and pullbacks, the adhesive category axioms capture that fragment of the structure of a topos which involves pushouts along monomorphisms and pullbacks. See [12] for a detailed treatment of this point of view.

2. Adhesive categories

Recall that a category 𝒞 with finite coproducts is extensive if for all objects A and B the coproduct functor 𝒞 /A × 𝒞 /B → 𝒞 /(A + B) is an equivalence of categories. This is equivalent to saying that 𝒞 has finite coproducts and pullbacks along coproduct injections, and in a commutative diagram

\xymatrix{A′ \ar[r] \ar[d] & E \ar[d] & B′ \ar[l] \ar[d] \\ A \ar[r] & A + B & B \ar[l]}

in which the bottom row is a coproduct, the top row is a coproduct if and only if the squares are pullbacks.

In a pushout square

\xymatrix{C \ar[r]^{g} \ar[d]_{f} & B \ar[d] \\ A \ar[r] & D}

the role of the morphisms f and g is entirely symmetric, but sometimes we wish to think of it non-symmetrically, and call it a pushout along f, or alternatively a pushout along g. If either f or g is a monomorphism, we call it a pushout along a monomorphism.

A category with pullbacks is said to be adhesive if it has pushouts along monomorphisms, every such pushout is stable under pullback, and in a cube

\xymatrix{ & C′ \ar[rr] \ar@{-->}[dl] \ar[dd] &  & B′ \ar@{-->}[dl] \ar[dd] \\ A′ \ar[rr] \ar[dd] &  & D′ \ar[dd] \\  & C \ar[rr] \ar@{-->}[dl] &  & B \ar@{-->}[dl] \\ A \ar[rr] &  & D}

in which the top and bottom squares are pushouts along monomorphisms, and the back and left squares are pullbacks, then the remaining squares are pullbacks. Alternatively, one can combine the stability condition and the other condition into the single requirement that in such a cube, if the bottom square is a pushout along a monomorphism, and the left and back squares are pullbacks, then the top square is a pushout if and only if the front and right squares are pullbacks.

Various simple facts follow; for example the following are both proved in [8]:

2.1. Proposition. In any adhesive category, the pushout of a monomorphism along any map is a monomorphism, and the resulting square is also a pullback.

Proof. Suppose that

\xymatrix{ & C \ar[rr] \ar[dl]_{m} &  & B \ar[dl]^{n} \\ A \ar[rr] &  & D}

is a pushout in which m is a monomorphism. We have to show that n is a monomorphism and that the square is also a pullback. Expand the given square into a cube, as in the diagram

[figure: C; B; C; B; C; B; A; D]

in which the front and bottom faces are both the original square. The top face is a pushout, the back face a pullback, the left also a pullback (because m is a monomorphism), and so the front and right faces are pullbacks. The front face being a pullback means that the original square is a pullback; the right face being a pullback means that n is a monomorphism.

The proof of the following result is slightly more complicated; it can be found in [9].

2.2. Proposition. An adhesive category has binary unions of subobjects, and they are effective.

The claim that the unions are effective means that the union of a pair of subobjects is constructed as the pushout over their intersection.

There is a variant of adhesive categories called quadiadhesive categories, which uses pushouts along regular monomorphisms rather than along all monomorphisms. Perhaps suprisingly, and contrary to what is claimed in [9], it is not the case that every quasitopos is quasiadhesive: see [7].

An elegant reformulation of the adhesive condition was given in [6] using the bicategory Span(𝒞) of spans in 𝒞. This bicategory has the same objects as 𝒞, while a morphism from A to B is a diagram A ← E → B, with composition given by pullback. There is an inclusion pseudofunctor 𝒞 → Span(𝒞) sending a morphism f : A → B to the span from A = A → B with left leg the identity on A and right leg just f. The reformulation then says that a category 𝒞 with pullbacks is adhesive if and only if it has pushouts along monomorphisms, and these are sent by the inclusion 𝒞 → Span(𝒞) to bicolimits in Span(𝒞).

A functor between adhesive categories is called adhesive if it preserves pushouts along monomorphisms and pullbacks.

3. Adhesive categories and toposes

In this section we see that every topos is adhesive, and so every full subcategory of a topos, closed under pushouts along monomorphisms and pullbacks, is adhesive. Then we see the converse: every (small) adhesive category has a fully faithful adhesive functor into a topos.

First we give a proof, different to that of [10], that every topos is adhesive. It uses one of the Freyd embedding theorems to reduce to the case of a Boolean topos. It is also possible to give direct proofs, but these all seem to be rather longer — see [10] for one possibility.

3.1. Theorem. Every topos ℰ is adhesive.

Proof. Recall that a topos is Boolean when every subobject is complemented, in the sense that it is a coproduct injection. By a theorem of Freyd [4], for every topos ℰ there is a Boolean topos ℬ and a faithful functor from ℰ to ℬ which preserves finite limits and finite (in fact any) colimits. Since the functor is faithful and preserves finite limits and colimits, it also reflects isomorphisms, and so it reflects finite limits and colimits. Thus the adhesive category axioms for ℰ will follow from those for ℬ, and it suffices to prove that any Boolean topos is adhesive.

In a Boolean topos, any monomorphism m : C → A is a coproduct injection m : C → C + X, and now for any map f : C → B the corresponding pushout is the square

\xymatrix{C \ar[d]_{m} \ar[r]^{f} & B \ar[d]^{n} \\ C + X \ar[r]_{f+X} & B + X}

with n : B → B + X once again the coproduct injection.

Now consider a cube over this square, with back and left faces pullbacks. By extensivity, this has the form

\xymatrix{ & C′ \ar[rr]^{f′} \ar[dl]_{m′} \ar[dd]^{c} &  & B′ \ar[dl]_{n′} \ar[dd]^{b} \\ C′ + X′ \ar[rr]^{g′} \ar[dd]_{c+x} &  & D \ar[dd]^{d} \\  & C \ar[rr]^{f} \ar[dl]_{m} &  & B \ar[dl]^{n} \\ C + X \ar[rr]_{f+X} &  & B + X}

in which m′ : C′ → C′ + X′ is the coproduct injection.

Of course if the front and right faces are pullbacks, then the top face is a pushout, by stability of colimits under pullback. Conversely, if the top face is a pushout, then it has the form

\xymatrix{C′ \ar[r]^{f′} \ar[d]_{m′} & B′ \ar[d]^{n′} \\ C′ + X′ \ar[r]_{f′+X′} & B′ + X′}

and now d is just b + x : B′ + X′ → B + X by commutativity of the front and right faces. The fact that the front and right faces are pullbacks then follows by extensivity.

Before we prove the embedding theorem, we need the following lemma.

3.2. Lemma. Let a monomorphism m : C → A and a map f : C → B be given in any adhesive category 𝒞, and construct the diagram

\xymatrix{C \ar[r]^{γ} \ar[d]_{m} & C_{2} \ar[d]_{m_{2}} \ar[r]^{f_{1}} \ar[r]_{f_{2}} & C \ar[r]^{f} \ar[d]_{m} & B \ar[d]^{n} \\ A \ar[r]_{δ} & A_{2} \ar[r]^{g_{1}} \ar[r]_{g_{2}} & A \ar[r]_{g} & D}

in which the right hand square is a pushout, C_{2} and A_{2} are the kernel pairs of f and g, and γ and δ are the diagonal maps. Then the left hand square is a pushout and a pullback.

Proof. Pulling back the right hand square along g : A → D gives the square

\xymatrix{C_{2} \ar[r]^{f_{1}} \ar[d]_{m_{2}} & C \ar[d]^{m} \\ A_{2} \ar[r]_{g_{1}} & A}

which is therefore a pushout. Form the diagram

\xymatrix{C \ar[r]^{γ} \ar[d]_{m} & C_{2} \ar[r]^{f_{1}} \ar[d]^{j} & C \ar[d]^{m} \\ A \ar[r]^{i} \ar@{.>}[dr]_{δ} & E \ar[r]^{h_{1}} \ar[d]^{k} & A \ar[d]^{1} \\  & A_{2} \ar[r]_{g_{1}} & A}

in which the top left square is a pushout, h_{1} is the unique morphism satisfying h_{1}i = 1 and h_{1}j = mf_{1}, and k is the unique morphism satisfying ki = δ and kj = m_{2}. By Proposition 2.2, the morphism k : E → A_{2} is the union of the subobjects δ : A → A_{2} and m_{2} : C_{2} → A_{2}, and so in particular is a monomorphism. The lemma asserts that it is invertible.

Now the top left square and the composite of the upper squares are both pushouts, so the top right square is also a pushout, by the cancellativity properties of pushouts. The composite of the two squares on the right is the pushout constructed at the beginning of the proof, so finally the lower right square is a pushout by the cancellativity property of pushouts once again.

Since k is a monomorphism, the lower right square is a pullback by Proposition 2.1. Thus k is invertible, and our square is indeed a pushout. It is a pullback by Proposition 2.1 again along with the fact that m is a monomorphism.

3.3. Theorem. Any small adhesive category admits a full adhesive embedding into a topos.

Proof. Let 𝒞 be a small adhesive category. Consider the topology generated by all pairs (g, n) arising as above in a pushout

\xymatrix{C \ar[r]^{f} \ar[d]_{m} & B \ar[d]^{n} \\ A \ar[r]_{g} & D}

in which m is a monomorphism. The pushout square is also a pullback by Proposition 2.1, thus f and m are determined up to isomorphism by g and n. These (g, n) generate a topology since pushouts along monomorphisms are stable under pullback, thus the category ℰ of sheaves for the topology is a topos. We shall show that the Yoneda embedding lands in ℰ, giving a fully faithful functor Y : 𝒞 → ℰ, and that Y is adhesive.

To do this, we need to understand the sheaf condition. Consider a pair (g, n) arising as above. Since n is a monomorphism, by Proposition 2.1 once again, the kernel pair of n is just B. Let g_{1}, g_{2} : A_{2} ⇉ A be the kernel pair of g. Then a functor F : 𝒞^{op} → Set satisfies the sheaf condition precisely when, for each such (g, n), the morphisms F g and F n exhibit F D as the limit of the diagram

\xymatrix{ & F C & F B \ar[l]_{F f} \\ F A_{2} & F A \ar[l]^{F g_{1}} \ar[l]_{F g_{2}} \ar[u]^{F m} & F D \ar[l]_{F g} \ar[u]_{F n}}

in Set.

Clearly the representables satisfy this condition, so the Yoneda embedding lands in ℰ, giving a fully faithful functor Y : 𝒞 → ℰ, which preserves all existing limits, and in particular all finite limits. We must show that it also preserves pushouts along monomorphisms. This is equivalent to the condition that every sheaf F sends pushouts along monomorphisms in 𝒞 to limits in Set. If g were monomorphic, so that the kernel pair A_{2} of g were just A, this would be immediate, but in general there is a little work to do.

We must show that if x ∈ F A and y ∈ F B satisfy F m.x = F f.y, then also F g_{1}.x = F g_{2}.x, so that by the sheaf condition x and y arise from some (necessarily unique) z ∈ F D.

To do this, we use Lemma 3.2. This tells us that A_{2} is the pushout of A and C_{2} over C, and all maps in this pushout are monomorphisms, so by the sheaf condition

\xymatrix{F C & F C_{2} \ar[l]_{F γ} \\ F A \ar[u]^{F m} & F A_{2} \ar[l]^{F δ} \ar[u]_{F m_{2}}}

is a pullback, and so F δ and F m_{2} are jointly monic. Now

F δ.F g_{1}.x = F (g_{1}δ).x = x = F (g_{1}δ).x = F δ.F g_{2}.x
F m_{2}.F g_{1}.x = F f_{1}.F m.x = F f_{1}.F f.y = F f_{2}.F f.y = F f_{2}.F m.x = F m_{2}.F g_{2}.x

and so F g_{1}.x = F g_{2}.x as required.

References

[1] Andrea Corradini et al, editor. Graph Transformations, volume 4178 of Lecture Notes in Comput. Sci. Springer, 2006.

[2] Michael Barr. Exact categories and categories of sheaves. Lecture Notes Math. 236:1– 120, Springer, Berlin, 1971.

[3] H. Ehrig et al, Fundamentals of Algebraic Graph Transformations, volume XIV in Monographs in Theoretical Computer Science, Springer, 2006.

[4] Peter Freyd. Aspects of topoi. Bull. Austral. Math. Soc., 7:1–76, 1972.

[5] Richard Garner and Stephen Lack. Lex colimits, in preparation.

[6] Tobias Heindel and Paweł Sobociński. Van Kampen colimits as bicolimits in span. In Algebra and coalgebra in computer science, volume 5728 of Lecture Notes in Comput. Sci., pages 335–349. Springer, Berlin, 2009.

[7] Peter T. Johnstone, Stephen Lack, and Paweł Sobociński. Quasitoposes, quasiadhesive categories and Artin glueing. In Algebra and coalgebra in computer science, volume 4624 of Lecture Notes in Comput. Sci., pages 312–326. Springer, Berlin, 2007.

[8] Stephen Lack and Paweł Sobociński. Adhesive categories. In Foundations of software science and computation structures, volume 2987 of Lecture Notes in Comput. Sci., pages 273–288. Springer, Berlin, 2004.

[9] Stephen Lack and Paweł Sobociński. Adhesive and quasiadhesive categories. Theor. Inform. Appl., 39(3):511–545, 2005.

[10] Stephen Lack and Paweł Sobociński. Toposes are adhesive. In Graph transformations, volume 4178 of Lecture Notes in Comput. Sci., pages 184–198. Springer, Berlin, 2006.

[11] F. William Lawvere. Some thoughts on the future of category theory. In Category theory (Como, 1990), volume 1488 of Lecture Notes in Math., pages 1–13. Springer, Berlin, 1991.

[12] Michael Makkai and Robert Paré. Accessible categories: the foundations of categorical model theory, volume 104 of Contemporary Mathematics. American Mathematical Society, Providence, RI, 1989.

Mathematics Department Macquarie University NSW 2109 Australia

Email: steve.lack@mq.edu.au

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/25/7/25-07.{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: valeria.depaiva@gmail.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, Macquarie University: steve.lack@mq.edu.au F. William Lawvere, State University of New York at Buffalo: wlawvere@buffalo.edu Tom Leinster, University of Glasgow, Tom.Leinster@glasgow.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