Theory and Applications of Categories, Vol. 27, No. 3, 2012, pp. 27–46.

ON THE AXIOMS FOR ADHESIVE AND QUASIADHESIVE CATEGORIES

RICHARD GARNER AND STEPHEN LACK

Abstract. A category is adhesive if it has all pullbacks, all pushouts along monomorphisms, and all exactness conditions between pullbacks and pushouts along monomorphisms which hold in a topos. This condition can be modified by considering only pushouts along regular monomorphisms, or by asking only for the exactness conditions which hold in a quasitopos. We prove four characterization theorems dealing with adhesive categories and their variants.

1. Introduction

In the paper [5], a general framework was given for describing categorical structures consisting of the existence of finite limits as well as certain types of colimits, along with exactness conditions stating that the limits and colimits interact in the same way as they do in a topos. These exactness conditions always include the fact that the colimits in question are stable under pullback; usually, there are further conditions. We may sometimes speak of the colimits in question being “well-behaved” when the corresponding exactness conditions hold, it being understood that the paradigm for good behaviour is that which occurs in a topos.

Examples of colimit types considered in [5] include coequalizers of kernel pairs, coequalizers of equivalence relations, and finite coproducts; the corresponding exactness conditions are then regularity, Barr-exactness, and lextensivity. But for this paper, the key example from [5] is that in which the colimits in question are the pushouts along monomorphisms; the resulting categorical structure turns out to be that of an adhesive category, first introduced in [9]. Any small adhesive category admits a structure-preserving full embedding into a topos: this was proved in [8]. Since every topos is adhesive, and every small adhesive category admits a full structure-preserving embedding into a topos, we see that the exactness conditions between pushouts along monomorphisms and finite limits which hold in an adhesive category are indeed precisely those which hold in any topos. In fact terminal objects are not assumed in the definition of adhesive category, and we work with pullbacks rather than all finite limits. This does not affect the issues of limit-colimit compatibility.

Received by the editors 2012-01-07 and, in revised form, 2012-05-05.

Published on 2012-05-07 in the volume of articles from CT2011.

2000 Mathematics Subject Classification: 18A30, 18B15.

Key words and phrases: adhesive category, quasiadhesive category, pushout, exactness condition, embedding theorem.

\begin{matrix}c \\ ◯ \end{matrix} Richard Garner and Stephen Lack, 2012. Permission to copy for private use granted.

Adhesive categories were first introduced in order to simplify and unify various structures considered in the area of graph transformations [4], and it was clear from the start that some of the categories of interest failed to be adhesive but still shared many of the same properties. There are two ways in which one could weaken the notion of adhesive category so as to try to include more examples.

One possibility is to restrict the class of colimits which are required to be well-behaved. We shall characterize those categories with pullbacks and with pushouts along regular monomorphisms, in which the same exactness conditions hold as in a topos. They turn out to be precisely those categories which were called quasiadhesive in [10, 7]. The name quasiadhesive comes from the fact that a quasiadhesive category is defined similarly to an adhesive category except that one uses regular monomorphisms in place of monomorphisms, just as a quasitopos is defined similarly to a topos except that one uses regular monomorphisms in place of monomorphisms. But in fact this analogy is misleading, since quasiadhesive categories have little to do with quasitoposes; in particular, as shown in [7], a quasitopos need not be quasiadhesive. Rather than quasiadhesive, we shall use the name rm-adhesive for the categories occurring in this characterization; see below.

A second possibility would be to relax the requirements of good behaviour for the colimits in question. No doubt there are many possible such relaxations, but we shall consider just one: requiring only those exactness conditions which hold in a quasitopos. In fact we shall have nothing to say about the categories with pullbacks, pushouts along all monomorphisms, and the exactness conditions holding in a quasitopos. But we shall introduce a further structure, that of an rm-quasiadhesive category, which will turn out to be that obtained by applying both weakenings: thus a category is rm-quasiadhesive just when it admits pushouts along regular monomorphisms and pullbacks, with the same exactness properties holding between these as hold in a quasitopos.

In this paper, we prove four theorems about categorical structures involving pushouts along some class of monomorphisms (either all of them or just the regular ones) satisfying exactness conditions of either the stronger or the weaker type. We devote the remainder of the introduction to an explanation of the content and significance of these theorems.

We have discussed above notions of adhesive, rm-adhesive, and rm-quasiadhesive category in terms of exactness conditions holding in a topos or quasitopos, but the actual definitions of these notions are elementary, asserting properties of certain kinds of diagram in such categories. A category with pullbacks and with pushouts along monomorphisms is said to be adhesive when the pushouts along monomorphisms are van Kampen; the name coming from the fact that this condition is formally similar to the statement of the coverings form of the van Kampen theorem [2]. Explicitly, the condition says that for any cube

[figure: C′; m′; c; f′; B′; n′; b; A′; a; g′; D′; d; C; f; m; B; n; A; g; D]

with the bottom face as the given square and with the left and back faces as pullbacks, the top face is a pushout if and only if the front and right faces are pullbacks. An elegant reformulation of the van Kampen condition was given in [6], where it was shown that a pushout along a monomorphism is van Kampen just when it is also a (bicategorical) pushout in the bicategory of spans.

The “if” part of the van Kampen condition says that the pushout is stable under pullback. We shall from now on use the adjective “stable” to mean “stable under pullback”. It is easy to see that a van Kampen square is a pullback as well as a stable pushout; in general, however, there can be stable pushouts which are pullbacks but fail to be van Kampen.

We now collect together the elementary definitions of our various notions.

1.1. Definition. A category with pullbacks is said to be:

(i) adhesive if it has pushouts along monomorphisms and these are van Kampen;

(ii) rm-adhesive if it has pushouts along regular monomorphisms and these are van Kampen;

(iii) rm-quasiadhesive if it has pushouts along regular monomorphisms and these are stable and are pullbacks.

It might appear that we should have considered a fourth possibility, namely the categories which have pushouts along monomorphisms that are stable and are pullbacks, but need not be van Kampen. Our first theorem states that in this case the pushouts along monomorphisms must in fact be van Kampen, and so this apparently different notion coincides with that of adhesive category. It will be proved as part of Theorem 3.2 below.

Theorem A. A category with pullbacks is adhesive if and only if it has pushouts along monomorphisms, and these pushouts are stable and are pullbacks.

In fact this characterization was observed in [5], with an indirect proof based on the fact that the proof of the embedding theorem for adhesive categories given in [8] used only the elements of the new characterization, not the van Kampen condition. The proof given below, however, is direct. If we take the equivalent condition given in the theorem as the definition of adhesive category, then the fact that every topos is adhesive [11, 8] becomes entirely standard.

Our second main result, proved as Corollary 3.4 below, describes the relationship between rm-adhesive and rm-quasiadhesive categories:

Theorem B. A category is rm-adhesive just when it is rm-quasiadhesive and regular subobjects are closed under binary union.

This is a sort of refinement of the result in [7] which states that a quasitopos is rmadhesive (there called quasiadhesive) if and only if regular subobjects are closed under binary union. As observed in [7, Corollary 20], the category of sets equipped with a binary relation is a quasitopos, and so rm-quasiadhesive, but fails to be rm-adhesive.

The remaining two theorems are embedding theorems, and complete the characterizations of rm-adhesive and rm-quasiadhesive categories as those with pushouts along regular monomorphisms satisfying the exactness conditions which hold in a topos or a quasitopos.

Theorem C. Let 𝒞 be a small category with all pullbacks and with pushouts along regular monomorphisms. Then 𝒞 is rm-adhesive just when it has a full embedding, preserving the given structure, into a topos.

It follows from the theorem that the condition of being rm-adhesive can be seen as an exactness condition in the sense of [5]. The theorem also clinches the argument that the name quasiadhesive does not really belong with the condition that all pushouts along regular monomorphisms be van Kampen; this condition is related to toposes rather than quasitoposes.

Theorem D. Let 𝒞 be a small category with all pullbacks and with all pushouts along regular monomorphisms. Then 𝒞 is rm-quasiadhesive just when it has a full embedding, preserving the given structure, into a quasitopos.

One direction of each theorem is immediate, since every topos is adhesive and every quasitopos is rm-quasiadhesive. The converse implications are proved in Theorems 4.2 and 4.6 respectively; the theorems themselves are stated as Corollaries 4.3 and 4.7.

We have found it convenient to give the name adhesive morphism to a morphism m (necessarily a regular monomorphism) with the property that pushouts along any pullback of m are stable and are pullbacks. One aspect of the convenience is that we can then deal simultaneously with the context where all monomorphisms are adhesive and that where all regular monomorphisms are adhesive. Other authors have defined adhesiveness with respect to an abstract class of morphisms—see [4] and the references therein—but this is subtly different. Rather than specifying a class of morphisms and asking that pushouts along them be suitably well behaved, we are instead considering the class of all morphisms along which pushouts are suitably well behaved.

We introduce and study these adhesive morphisms in Section 2. Then in Section 3 we look at when pushouts along adhesive morphisms are van Kampen squares, and prove the first two theorems described above. Finally in Section 4 we look at structure preserving embeddings of rm-adhesive and rm-quasiadhesive categories, and prove the last two theorems.

Acknowledgements. The second-named author is grateful to Peter Johnstone and Paweł Sobociński for helpful conversations in relation to the content of the paper.

This research was supported under the Australian Research Council’s Discovery Projects funding scheme, project numbers DP110102360 (Garner) and DP1094883 (Lack).

2. Adhesive morphisms

Let 𝒞 be a category with pullbacks. Say that a morphism m is pre-adhesive, if pushouts along m exist, are stable, and are pullbacks. Say that m is adhesive if all of its pullbacks are pre-adhesive.

2.1. Proposition. All isomorphisms are adhesive. All adhesive morphisms are preadhesive. All pre-adhesive morphisms are regular monomorphisms.

Proof. Any isomorphism is obviously pre-adhesive, but the pullback of an isomorphism is still an isomorphism, and so isomorphisms are adhesive. The second statement is a triviality. As for the third, if m is pre-adhesive, then it is the pullback of its pushout along itself. This says that it is the equalizer of its cokernel pair, and so is a regular monomorphism.

We shall repeatedly use the standard results about pasting and cancellation of pullbacks and pushouts: if in a diagram

[figure: r]

the right square is a pullback, then the left square is a pullback just when the composite rectangle is one; dually, if the left square is a pushout, then the right square is a pushout just when the composite rectangle is one. It is well known that there is another cancellation result for pullbacks: if the left square and the composite rectangle are pullbacks, and the arrow r is a stable regular epimorphism, then the right square is a pullback. This is proved in [3, Lemma 4.6] under the assumption that r is an effective descent morphism, but also follows from the special case a_{1} = a_{2} = r of the following closely related result, which we shall use repeatedly.

2.2. Lemma. Consider the following diagrams

\xymatrix{A_{0} \ar[r]^{b_{2}} \ar[d]_{b_{1}} & A_{2} \ar[d]^{a_{2}} & A′_{i} \ar[d]_{p_{i}} \ar[r]^{a′_{i}} & A′ \ar[d]^{p} \ar[r]^{f′} & B′ \ar[d]^{q} \\ A_{1} \ar[r]_{a_{1}} & A & A_{i} \ar[r]_{a_{i}} & A \ar[r]_{f} & B}

in a category 𝒞 with pullbacks. Suppose that the square on the left is a stable pushout, and the the two diagrams on the right (i = 1, 2) have left square a pullback and composite a pullback. Then the square on the right is also a pullback.

Proof. Consider the diagrams (i = 1, 2)

[figure: A′_{0}; b′_{i}; A′_{i}; a′_{i}; A′; f′; p′; B′; A′_{0}; b′_{i}; p_{0}; A′_{i}; a′′_{i}; p_{i}; A′′; f′′; q′; B′; q; A_{0}; b_{i}; A_{i}; a_{i}; A; f; B]

in which the squares along the bottom are all pullbacks, and p′ is the unique morphism satisfying f′′p′ = f′ and q′p′ = p. We need to show that p′ is invertible.

By the standard properties of pullbacks, the left and middle squares on the top row are pullbacks; thus in the diagram

\xymatrix{A′_{0} \ar[r]^{b′_{2}} \ar[d]_{b′_{1}} & A′_{2} \ar[d]_{a′_{2}} \ar[ddr]^{a′′_{2}} \\ A′_{1} \ar[r]^{a′_{1}} \ar[drr]_{a′′_{1}} & A′ \ar[dr]^{p′} \\  &  & A′′}

both the interior and the exterior square are pullbacks of a stable pushout, hence are pushouts. Since p′ is the canonical comparison between two pushouts, it is invertible.

The class of adhesive morphisms is of course stable under pullback, since it consists of precisely the stably-pre-adhesive morphisms. We also have:

2.3. Proposition. The class of adhesive morphisms is closed under composition and stable under pushout.

Proof. Closure under composition follows immediately from the pasting properties of pullbacks and pushouts.

As for stability, suppose that m: C → A is adhesive, and consider a pushout

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

which is also a pullback, since m is adhesive. First we show that n is mono. Pull back this pushout along n to get a cube

[figure: C; B′; n_{1}; n_{2}; C; m; f; B; n; C; f; m; B; n; A; g; D]

in which the top face, like the bottom, is a pushout, and the four vertical faces are pullbacks; and in which n_{1} and n_{2} are the kernel pair of n. Since n_{1} is a pushout of an isomorphism it is an isomorphism. This implies that the kernel pair of n is trivial, and so that n is a monomorphism; thus any pushout of an adhesive morphism is a monomorphism.

Next we show that the monomorphism n is pre-adhesive. Given any h: B → E we can push out m along hf, and so by the cancellativity property of pushouts obtain pushout squares

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

where the pushout on the right is stable, since the left and composite pushouts are so. We must show that the square on the right is also a pullback. Since the square on the left is a stable pushout, we may use Lemma 2.2. We know that the composite rectangle is a pullback, so it will suffice to show that in the diagram below

[figure: B; B; n; h; E; p; B; n; D; k; F]

the left square and the composite rectangle are pullbacks. The left square is indeed a pullback because n is monic; the composite is a pullback because p is is monic.

Finally, to see that n is adhesive, let n′: B′ → D′ be a pullback of n along d: D′ → D. Then we have a cube

[figure: C′; m′; c; f′; B′; n′; b; A′; a; g′; D′; d; C; f; m; B; n; A; g; D]

in which the bottom face is a stable pushout since m is pre-adhesive, so that the top face is a pushout. But m′ is adhesive since m is adhesive, and so n′ is also pre-adhesive. This now proves that n is adhesive.

Recall that a union of two subobjects is said to be effective if it can be constructed as the pushout over the intersection of the subobjects. This will be the case provided that the pushout exists, and the induced map out of the pushout is a monomorphism.

2.4. Proposition. Binary unions are effective provided that at least one of the subobjects is adhesive.

Proof. Consider a subobject h: A → E and an adhesive subobject p: B → E, and form their intersection C, and their pushout D over C, as in the diagram

\xymatrix{C \ar[r]^{f} \ar[d]_{m} & B \ar[d]_{n} \ar[ddr]^{p} \\ A \ar[r]^{g} \ar[drr]_{h} & D \ar[dr]^{x} \\  &  & E}

in which x: D → E is the induced map; we must show that x is a monomorphism. Observe that g and f are monomorphisms since h is one, while n and m are adhesive since p is so.

Pulling back the external part of the diagram along h: A → E gives the external part of the diagram

[figure: C; m; C; m; m; A; A; A]

but pulling back the pushout in the interior of the original diagram must give a pushout, which must then be the square in the interior of the diagram above. It follows that we have a pullback

[figure: A; g; D; x; A; h; E.]

Similarly, pulling back the original diagram along p: B → E gives the diagram

[figure: C; f; B; C; f; f; B; B]

and we have a pullback

[figure: B; n; D; x; B; p; E.]

We now use Lemma 2.2 to prove that

[figure: D; D; x; D; x; E]

is a pullback, and so that x is a monomorphism, using the stable pushout

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

This is done by observing that in the rectangles

[figure: B; n; D; D; x; B; n; D; x; E; A; g; D; D; x; A; g; D; x; E]

the left square and the composite are pullbacks, hence the (common) right square is one.

The following lemma will be used several times in later sections of the paper; the argument in the proof goes back to [11], where it was used in the context of adhesive categories; for a general framework which explains the origin of the condition itself, see [5, Section 6].

2.5. Lemma. Suppose that adhesive subobjects are closed under binary union, and that all split monomorphisms are adhesive. Let m: C → A be an adhesive morphism and f: C → B any morphism. 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, (f_{1}, f_{2}) and (g_{1}, g_{2}) are the kernel pairs of f and g, with m_{2} the induced map, while γ and δ are the diagonal maps. Then the left square, the right square, and the two central squares are all both pushouts and pullbacks.

Proof. Since m is adhesive, the right hand square is a stable pushout. We may pull it back along g so as to give one of the central squares

\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 and a pullback; the case of the other central square is similar. Furthermore m_{2} is adhesive, since it is a pullback of m. 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.4, the morphism k: E → A_{2} is the union of δ: A → A_{2} and the adhesive subobject m_{2} : C_{2} → A_{2}; since δ is split, it is adhesive by one of our hypotheses on the category, thus the union k of δ and m_{2} is adhesive by the other hypothesis. We are to show that k 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 adhesive, the lower right square is a pullback. Thus k is invertible, and our square is indeed a pushout.

3. The van Kampen condition

We recalled in the introduction the notion of a van Kampen square, which appears in the definition of adhesive and rm-adhesive category. In this section we give various results showing how this condition can be reformulated.

3.1. Proposition. Suppose that adhesive subobjects are closed under binary union and that split subobjects are adhesive. Then pushouts along adhesive morphisms are van Kampen.

Proof. Consider a cube

[figure: C′; f′; m′; c; B′; n′; b; A′; g′; a; D′; d; C; f; m; B; n; A; g; D]

in which m is adhesive, the bottom face is a pushout, and the left and back faces are pullbacks. We are to show that the top face is a pushout if and only if the front and right faces are pullbacks.

Since m is adhesive, the pushout on the bottom face is stable, thus if the front and right faces are pullbacks, then the top face is also a pushout.

Suppose conversely that the top face is a pushout, noting also that m′ is a pullback of the adhesive morphism m so is itself adhesive, and so that n′ and n are also adhesive. We are to show that the front and right faces are pullbacks. We do this using various applications of Lemma 2.2.

To see that the right face is a pullback, apply Lemma 2.2 with the top face as stable pushout. We know that the top face, the left face and the bottom face are pullbacks; thus also the composite of top and right faces are pullbacks. Thus it remains to show that the composite and the left square in the diagram on the left

[figure: B′; B′; b; n′; B; n; B′; n′; D′; d; D; B′; b; B; B; n; B′; b; B; n; D]

are pullbacks. Of these, the left square is a pullback since n′ is monic, while the composite is equally the composite of the diagram on the right, in which both squares are pullbacks (because n is monic).

This proves that the right face is a pullback; now consider the front face

\xymatrix{A′ \ar[d]_{g′} \ar[r]^{a} & A \ar[d]^{g} \\ D′ \ar[r]_{d} & D}

(here reflected about the diagonal). We shall show that it is a pullback using Lemma 2.2 with the stable pushout

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

We know that the back and bottom faces of the cube are pullbacks, and so the composite of the top and front faces is a pullback. Thus it will suffice to show that if, in the diagram below on the left,

\xymatrix{A′_{2} \ar[r]^{g′_{1}} \ar[d]_{g′_{2}} & A′ \ar[r]^{a} \ar[d]_{g′} & A \ar[d]^{g} & A′_{2} \ar[r]^{a_{2}} \ar[d]_{g′_{2}} & A_{2} \ar[r]^{g_{1}} \ar[d]_{g_{2}} & A \ar[d]^{g} \\ A′ \ar[r]_{g′} & D′ \ar[r]_{d} & D & A′ \ar[r]_{a} & A \ar[r]_{g} & D}

the left square is a pullback, then so is the composite. To see that this is so, consider the diagram on the right in which the right square is a pullback, and a_{2} is the unique morphism making the square on the left commute, and the composite rectangle equal the composite rectangle on the left. It will now suffice to show that the left square of the right diagram (here reflected in the diagonal)

\xymatrix{A′_{2} \ar[d]_{a_{2}} \ar[r]^{g′_{2}} & A′ \ar[d]^{a} \\ A_{2} \ar[r]_{g_{2}} & A}

is a pullback. We do this using Lemma 2.2 once again, this time using the stable pushout

\xymatrix{C \ar[r]^{γ} \ar[d]_{m} & C_{2} \ar[d]^{m_{2}} \\ A \ar[r]_{δ} & A_{2}}

constructed in Lemma 2.5 (it is here that we need the assumption that adhesive subobjects are closed under binary union, and contain the split subobjects).

First of all, in the diagram

\xymatrix{A′ \ar[r]^{δ′} \ar[d]_{a} & A′_{2} \ar[d]_{a_{2}} \ar[r]^{g′_{2}} & A′ \ar[d]^{a} \\ A \ar[r]_{δ} & A_{2} \ar[r]_{g_{2}} & A,}

the horizontal composites are identities, and so the composite is a pullback, while the left square is equally the right face of the cube

[figure: C′; m′; γ′; c; A′; δ′; a; C′_{2}; m′_{2}; c_{2}; A′_{2}; a_{2}; C; m; γ; A; δ; C_{2}; m_{2}; A_{2}]  (1)

and so is a pullback by the earlier part of the proof, since in this cube the top and bottom faces are pushouts along adhesive morphisms, and the left and back faces are pullbacks. Since m is also adhesive, by the earlier part of the proof once again we may deduce that the front square is also a pullback.

Thus it remains to show that the composite and the left square in the diagram on the left

\xymatrix{C′_{2} \ar[r]^{m′_{2}} \ar[d]_{c_{2}} & A′_{2} \ar[r]^{g′_{2}} \ar[d]_{a_{2}} & A′ \ar[d]^{a} & C′_{2} \ar[r]^{f′_{2}} \ar[d]_{c_{2}} & C′ \ar[r]^{m′} \ar[d]_{c} & A′ \ar[d]^{a} \\ C_{2} \ar[r]_{m_{2}} & A_{2} \ar[r]_{g_{2}} & A & C_{2} \ar[r]_{f_{2}} & C \ar[r]_{m} & A}

are pullbacks. Of these, the left square is equally the front face of the cube (1), which we already saw to be a pullback. On the other hand, the composite is equally the composite of the diagram on the right, in which both squares are pullbacks.

We are now ready to give our first main theorem, providing a new characterization of adhesive categories.

3.2. Theorem. For a category 𝒞 with pullbacks, the following conditions are equivalent:

(i) 𝒞 is adhesive;

(ii) all monomorphisms are adhesive;

(iii) 𝒞 has pushouts along monomorphisms, and these pushouts are stable and are pullbacks.

Proof. Here condition (iii) says that all monomorphisms are pre-adhesive. Clearly (i) implies (ii) and (ii) implies (iii). If all monomorphisms are pre-adhesive, then since the pullback of a monomorphism is a monomorphism, all monomorphisms are in fact adhesive; this shows that (iii) implies (ii). Finally if all monomorphisms are adhesive, then certainly the adhesive subobjects are closed under binary union, so all pushouts along monomorphisms are van Kampen by Proposition 3.1. Thus (ii) implies (i).

We recall from the introduction that we define a category to be rm-adhesive if it has all pullbacks and all pushouts along regular monomorphisms, and these pushouts are van Kampen; while if instead these pushouts are only assumed to be stable and to be pullbacks, then the category is called rm-quasiadhesive. Thus a category with pullbacks is rm-quasiadhesive if and only if all regular monomorphisms are adhesive. We also reiterate the warning that the notion here being called rm-adhesive was formerly known as quasiadhesive.

3.3. Theorem. For a category 𝒞 with pullbacks, the following conditions are equivalent:

(i) 𝒞 is rm-adhesive; (ii) all regular monomorphisms are adhesive, and regular subobjects are closed under

binary union;

(iii) 𝒞 has pushouts along regular monomorphisms, these pushouts are stable and are pullbacks, and regular subobjects are closed under binary union.

Proof. The downward implications are all straightforward, once we note the fact, proved in [7], that in an rm-adhesive category, the union of two regular subobjects is again regular. The upward implications are proved just as in the proof of the previous theorem.

In particular, we have the following result, which refines the fact [7] that a quasitopos is rm-adhesive if and only if the union of two regular subobjects is again regular.

3.4. Corollary. A category is rm-adhesive just when it is rm-quasiadhesive and regular subobjects are closed under binary union.

Any locally presentable locally cartesian closed category of course has all colimits and these are all stable under pullback. This is not enough to imply that the category is rm-quasiadhesive, as the following example shows. The example was originally given in [1], attributed to Adámek and Rosický, as an example of a locally presentable and locally cartesian closed category which is not a quasitopos.

3.5. Example. Let ℰ be the category of sets equipped with a reflexive binary relation with the property that

x_{1}Rx_{2}Rx_{1} ⇒ x_{1} = x_{2}
x_{1}Rx_{2}Rx_{3}Rx_{1} ⇒ x_{1} = x_{2} = x_{3}
⋮ ⋮
x_{1}Rx_{2}R … Rx_{n}Rx_{1} ⇒ x_{1} = x_{2} = … = x_{n}

for all n ≥ 2. As observed in [1, Section 4], this is locally cartesian closed and locally presentable, but the regular monomorphism given by the inclusion ({0, 2}, R) → ({0, 1, 2}, S) is not classified, where R consists only of the diagonal, and where S consists of the diagonal as well as 0S1 and 1S2. In fact the pushout of this inclusion along the unique map from ({0, 2}, R) to the terminal object is clearly just the terminal object, and so this pushout is not also a pullback. Thus ℰ is not rm-quasiadhesive.

4. Embeddings

In this section we prove various embedding theorems. In each case, the category 𝒞 will be fully embedded into a full subcategory ℰ of the presheaf category [𝒞^{op}, Set], via the corresponding restricted Yoneda functor; the category ℰ will be a topos or a quasitopos, as appropriate; and the embedding will preserve the relevant colimits. The Yoneda functor 𝒞 → [𝒞^{op}, Set], of course, preserves limits but not colimits; we fix this by choosing ℰ appropriately. The preservation of colimits will occur provided that all presheaves F: 𝒞^{op} → Set lying in ℰ send the relevant colimits in 𝒞 to limits in Set. In order to guarantee that ℰ is a topos, we take it to be the category of sheaves for a topology j; we choose j in such a way that the representables are sheaves, and all sheaves send the relevant colimits in 𝒞 to limits in Set. If instead we only need ℰ to be a quasitopos, then we need only take ℰ to be the category of j-sheaves which are also k-separated, where j and k are topologies, with k containing j: such quasitoposes are called Grothendieck quasitoposes, and were studied in [1]. In each case j will be a cd-topology, in the sense of [12].

Suppose that 𝒞 is a small category with pullbacks. Since pushouts along adhesive morphisms are stable, there is a topology j on 𝒞 in which the covering families are those of the form {g, n} for some pushout

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

with m adhesive.

The sheaves for the topology are those functors F: 𝒞^{op} → Set for which, given a diagram of the above form, the induced diagram

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

in which (g_{1}, g_{2}) is the kernel pair of g, exhibits F D as the limit in Set of the remainder of the diagram.

First suppose that split monomorphisms are adhesive, and adhesive subobjects are closed under binary union. Then by Lemma 2.5, the diagram

\xymatrix{C \ar[r]^{γ} \ar[d]_{m} & C_{2} \ar[d]^{m_{2}} \\ A \ar[r]_{δ} & A_{2}}

is a pushout along the adhesive morphism m, and so {δ, m_{2}} is a covering family. Since both δ and m_{2} are monomorphisms, any sheaf F sends this pushout to a pullback in Set, and so in particular F δ and F m_{2} are jointly monic. As explained in [8], this now allows the sheaf condition given in terms of the diagram (2) above to be simplified to the requirement that the square in that diagram be a pullback; the argument is sufficiently short that it is worth repeating here. Suppose that x ∈ F A and y ∈ F B are given, with F m.x = F f.y; we must show that also F g_{1}.x = F g_{2}.x, so that by the sheaf condition there is a unique z ∈ F D with F g.z = x and F n.z = y. To do this, observe that

F δ.F g_{1}.x = F (g_{1}δ).x = x = F (g_{2}δ).x = F δ.F g_{2}.x

and

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

thus since F δ and F m_{2} are jointly monic, F g_{1}.x = F g_{2}.x as required.

The sheaves are therefore precisely those presheaves which send pushouts along adhesive morphisms to pullbacks. Then the restricted Yoneda embedding 𝒞 → Sh(𝒞) preserves such pushouts as well as any existing limits. This proves:

4.1. Theorem. For any small category 𝒞 with pullbacks, in which split monomorphisms are adhesive, and adhesive subobjects are closed under binary union, there is a full embedding of 𝒞 into a topos, and this embedding preserves pushouts along adhesive morphisms as well as all existing limits.

Thus we recover the result of [8] that any small adhesive category has a full structurepreserving embedding in a topos. But we also obtain:

4.2. Theorem. Any small rm-adhesive category can be fully embedded in a topos, via an embedding which preserves pushouts along regular monomorphisms as well as all existing limits.

Conversely, it is well-known that every topos satisfies the conditions in the definition of rm-adhesive category, hence so will any full subcategory closed under the relevant limits and colimits. Thus we have:

4.3. Corollary. Let 𝒞 be a small category with all pullbacks and with pushouts along regular monomorphisms. Then 𝒞 is rm-adhesive just when it has a full embedding, preserving the given structure, into a topos.

We now turn to the embedding theorem for rm-quasiadhesive categories. First, however, we need to develop the theory of such categories a little. The next result is essentially contained in [7], although the context there was slightly different.

4.4. Proposition. If m: A → X is the union of regular subobjects m_{1} : A_{1} → X and m_{2} : A_{2} → X in an rm-quasiadhesive category, then m has a stable (epi,regular mono) factorization.

Proof. We construct the union as the pushout square in

\xymatrix{A_{0} \ar[r]^{m′_{1}} \ar[d]_{m′_{2}} & A_{2} \ar[d]_{n_{2}} \ar[ddr]^{m_{2}} \\ A_{1} \ar[r]^{n_{1}} \ar[drr]_{m_{1}} & A \ar[dr]^{m} \\  &  & X}

where A_{0} is the intersection of A_{1} and A_{2}. First let i, j: X ⇉ X_{1} be the cokernel pair of m_{1}, and e_{1} : X_{1} → X the codiagonal. We can pull all these maps back along m_{2} to get the diagram

\xymatrix{A_{0} \ar[r]^{m′_{1}} \ar[d]_{m′_{2}} & A_{2} \ar[d]_{m_{2}} \ar[r]^{i_{2}} \ar[r]_{j_{2}} & X_{2} \ar[r]^{e_{2}} \ar[d]_{ℓ} & A_{2} \ar[d]^{m_{2}} \\ A_{1} \ar[r]^{m_{1}} & X \ar[r]^{i} \ar[r]_{j} & X_{1} \ar[r]^{e_{1}} & X}

in which ℓ is a pullback of the regular monomorphism m_{2} and so is itself a regular monomorphism. Since cokernel pairs of regular monomorphisms are pushouts along a regular monomorphism, they are stable under pullback, and so i_{2}, j_{2} : A_{2} ⇉ X_{2} is the cokernel pair of m′_{1}, and e_{2} : X_{2} → A_{2} is the codiagonal.

Since ℓ is a regular monomorphism, we can form the pushout

\xymatrix{X_{2} \ar[r]^{e_{2}} \ar[d]_{ℓ} & A_{2} \ar[d]^{k} \\ X_{1} \ar[r]_{q} & Y.}

We shall see that the maps qi, qj: X → Y are the cokernel pair of the union m: A → X.

To do this, suppose that u, v: X → Z are given with um = vm, or equivalently with um_{1} = vm_{1} and um_{2} = vm_{2}. Since um_{1} = vm_{1}, there is a unique w: X_{1} → Z with wi = u and wj = v. On the other hand wℓi_{2} = wim_{2} = um_{2} = vm_{2} = wjm_{2} = wℓj_{2} and so the morphism wℓ out of the cokernel pair X_{2} of m′_{1} agrees on the coprojections i_{2} and j_{2} of the cokernel pair, and therefore factorizes through the codiagonal e_{2}, say as wℓ = w′e_{2}. By the universal property of the pushout Y, there is a unique w′′: Y → Z with w′′q = w and w′′k = w′. Now w′′qi = wi = u and w′′qj = wj = v, and it is easy to see that w′′ is unique with the property, thus proving that qi and qj give the cokernel pair of m.

Since qi and qj are a cokernel pair, they have a common retraction (the codiagonal), and so we can form their equalizer n: B → X as their intersection; this is of course a regular monomorphism. Since qim = qjm, there is a unique map e: A → B with ne = m; we must show that e is a stable epimorphism. In fact it will suffice to show that it is an epimorphism, since all these constructions are stable under pullback along a map into X, thus if e is an epimorphism so will be any pullback.

To see that e is an epimorphism, first note that m_{1} and m_{2} factorize as m_{i} = mn_{i} = nen_{i}, and now en_{1} and en_{2} are regular monomorphisms with union e. So once again we can factorize e as n′e′, where n′ is a regular monomorphism constructed as before.

Observe that e is an epimorphism if and only if its cokernel pair is trivial, which in turn is equivalent to the equalizer n′ of this cokernel pair being invertible. In an rmadhesive category the regular monomorphisms are precisely the adhesive morphisms, and so are closed under composition. Thus the composite nn′ of the regular monomorphisms n and n′ is itself a regular monomorphism. We conclude, using a standard argument, by showing that n′ is invertible and so that e is an epimorphism. Observe that qi and qj are the cokernel pair of m = ne = nn′e′, as well as of their equalizer n. But then they are also certainly the cokernel pair of nn′. Since this last is a regular monomorphism, it must be the equalizer of qi and qj, but then it must be (isomorphic to) n, so that n′ is invertible as claimed.

4.5. Proposition. If m: C → A is a regular monomorphism and f: C → B an arbitrary morphism in an rm-quasiadhesive category, then the induced maps δ: A → A_{2} and m_{2} : C_{2} → A_{2} are stably jointly epimorphic.

Proof. Form, as in the proof of Lemma 2.5, 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}

with all squares pushouts, and note that k: E → A_{2} is the union of the regular monos δ: A → A_{2} and m_{2} : C_{2} → A_{2}. Thus we can factorize it as a stable epimorphism e: E → \overline{E} followed by a regular monomorphism \overline{k}: \overline{E} → A_{2}. Since e is an epimorphism, the square

\xymatrix{\overline{E} \ar[r]^{g_{1}\overline{k}} \ar[d]_{\overline{k}} & A \ar[d]^{1} \\ A_{2} \ar[r]_{g_{1}} & A}

is also a pushout. Since \overline{k} is a regular monomorphism, the square is also a pullback, but then \overline{k} is a pullback of an invertible morphism (an identity), so is invertible. Thus k is a stable epimorphism, and so δ and m_{2} are stably jointly epimorphic as claimed.

Let 𝒞 be a small rm-adhesive category. We have already described a topology j for which the representables are j-sheaves, and any j-sheaf F: 𝒞^{op} → Set will send each pushout along a regular monomorphism to a pullback, provided that the induced morphisms F m_{2} and F δ are jointly monic. We therefore seek a topology k containing j, with the property that each representable is k-separated and each pair {m_{2}, δ} is a covering family.

There are various possible choices for such a k, but perhaps it is easiest to take the topology whose covering families are generated by those in j along with all pullbacks of those of the form {m_{2}, δ}. Since each such pair {m_{2}, δ} is stably jointly epimorphic by Proposition 4.5, the representables will indeed be k-separated. On the other hand, each kseparated F certainly has F m_{2} and F δ jointly monomorphic, and so the j-sheaf condition for such an F becomes the condition that F send pushouts along regular monomorphisms to pullbacks.

This gives:

4.6. Theorem. Any small rm-quasiadhesive category 𝒞 has a full embedding, preserving pushouts along regular monomorphisms and all existing limits, into a Grothendieck quasitopos.

Conversely, it is well-known that every quasitopos satisfies the conditions in the definition of rm-quasiadhesive category, hence so will any full subcategory closed under the relevant limits and colimits. Thus we have:

4.7. Corollary. Let 𝒞 be a small category with all pullbacks and with all pushouts along regular monomorphisms. Then 𝒞 is rm-quasiadhesive just when it has a full embedding, preserving the given structure, into a quasitopos.

References

[1] Francis Borceux and Maria Cristina Pedicchio. A characterization of quasi-toposes. J. Algebra, 139(2):505–526, 1991.

[2] Ronald Brown and George Janelidze. Van Kampen theorems for categories of covering morphisms in lextensive categories. J. Pure Appl. Algebra, 119(3):255–263, 1997.

[3] A. Carboni, G. Janelidze, G. M. Kelly, and R. Paré. On localization and stabilization for factorization systems. Appl. Categ. Structures, 5(1):1–58, 1997.

[4] H Ehrig, K Ehrig, U Prange, and G Taentzer. Fundamentals of Algebraic Graph Transformation. Monographs in Theoretical Computer Science. Springer, Berlin Heidelberg, 2006.

[5] Richard Garner and Stephen Lack. Lex colimits. J. Pure Appl. Algebra, 216(6):1372– 1396, 2012.

[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. An embedding theorem for adhesive categories. Theory and Applications of Categories, 25(7):180–188, 2011.

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

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

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

[12] Vladimir Voevodsky. Homotopy theory of simplicial sheaves in completely decomposable topologies. J. Pure Appl. Algebra, 214(8):1384–1398, 2010.

Computing Department, Macquarie University, NSW 2109 Australia and Mathematics Department, Macquarie University, NSW 2109 Australia.

Email: richard.garner@mq.edu.au
      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/27/3/27-03.{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

Valeria de Paiva: valeria.depaiva@gmail.com

Ezra Getzler, Northwestern University: getzler(at)northwestern(dot)edu Kathryn Hess, Ecole Polytechnique Fédérale de Lausanne : kathryn.hess@epfl.ch 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 Giuseppe Rosolini, Università di Genova: rosolini@disi.unige.it Alex Simpson, University of Edinburgh: Alex.Simpson@ed.ac.uk James Stasheff, University of North Carolina: jds@math.upenn.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