Theory and Applications of Categories, Vol. 8, No. 3, 2001, pp. 33–53.

ON SIFTED COLIMITS AND GENERALIZED VARIETIES

J. ADÁMEK AND J. ROSICKÝ

ABSTRACT. Filtered colimits, i.e., colimits over schemes D such that D-colimits in Set commute with finite limits, have a natural generalization to sifted colimits: these are colimits over schemes D such that D-colimits in Set commute with finite products. An important example: reflexive coequalizers are sifted colimits. Generalized varieties are defined as free completions of small categories under sifted-colimits (analogously to finitely accessible categories which are free filtered-colimit completions of small categories). Among complete categories, generalized varieties are precisely the varieties. Further examples: category of fields, category of linearly ordered sets, category of nonempty sets.

Introduction

Filtered colimits belong, no doubt, to the most basic concepts of category theory. Let us just recall the notion of a finitely presentable object as one whose hom-functor preserves filtered colimits. (This, in every variety of algebras, is equivalent to the usual – less elegant – algebraic definition.)

Now, filtered colimits are characterized as colimits with domains (or diagram schemes) D such that D-colimits commute in Set with finite limits. In the present paper we work with a wider class of colimits: sifted colimits, i.e., colimits of diagrams whose domain D is such that D-colimits commute with finite products in Set. Important example: reflexive coequalizers (i.e., coequalizers of pairs f_{1}, f_{2} : A → B for which d : B → A exists with f_{1}d = f_{2}d = id ). We call an object A strongly finitely presentable if its hom-functor preserves sifted colimits. This implies, of course, that A is finitely presentable. But, due to the reflexive coequalizers, A is also a regular projective. In a variety^{1}, strongly finitely presentable algebras are precisely the finitely presentable regular projectives (i.e., precisely the retracts of free algebras on finitely many generators). This is what H.-E. Porst calls varietal generator (see [P]) and M.-C. Pedicchio and R. Wood call effective projective in [PW].

Recall the concept of a finitely accessible category of C. Lair [L_{1}] and M. Makkai and R. Paré [MP]: it is a category K with filtered colimits and a set of finitely presentable objects whose closure under filtered colimits is all of K. We introduce the natural restriction by substituting “filtered” by “sifted”: We call a category K a generalized variety if it has sifted colimits and a set of strongly finitely presentable objects whose closure under sifted colimits is all of K. Every variety has this property, and among complete categories, varieties are the only ones. But there are other interesting examples: for categories with connected limits, to be a generalized variety is equivalent to being multialgebraic in the sense of Y. Diers (e.g., the category of fields and homomorphisms and the category of linearly ordered sets and order-preserving maps are multialgebraic).

Supported by the Grant Agency of the Czech Republic under the grant No. 201/99/0310.

Received by the editors 1999 August 30.

Transmitted by Peter Johnstone. Published on 2001 February 5. Pages 34,35 revised 2007-01-22.

\begin{matrix}c \\ ◯ \end{matrix} J. Adámek and J. Rosický, 2001. Permission to copy for private use granted.

1Throughout the paper by a variety we mean a category of finitary algebras (possibly many-sorted)

presented by equations.

An example of a generalized variety which is not multialgebraic is the category of all nonempty sets and functions. Acknowledgement. The authors have much benefited from discussions with J. Velebil concerning sifted colimits, in particular, their presentation of Lair’s proof (Theorem 1.6, implication 2 → 3), has been much influenced by Velebil’s analysis of that proof.

1. Sifted colimits

1.1. Definition. A small category D is called sifted if colimits over D commute in Set with finite products.

1.2. Remark. (a) Explicitly, D is sifted iff it is nonempty (and thus, colimits over D commute with empty product) and given diagrams D_{1}, D_{2} : D → Set, then the canonical map

colim(D_{1} × D_{2}) → colimD_{1} × colimD_{2}

is an isomorphism.

(b) By sifted colimits we mean colimits over sifted categories.

(c) Filtered colimits are sifted, of course. In fact, small filtered categories D can be defined by the property that colimits over D commute in Set with finite limits.

(d) Every category D with finite coproducts is sifted. This follows from Theorem 1.5 below.

(e) Commutation of D-colimits with products of pairs has been studied by C. Lair in [L_{2}]. There he introduced the concept of a tamisante category D as a category such that for every pair (A, B) of objects the category of all cospans with domains A, B is connected. And he proved that every tamisante category D has the property that Dcolimits commute in Set with products of pairs. We prove that this sufficient condition is in fact also necessary. We present a full proof of the necessity below based on a concept of “morphism of zig-zags”, but the main idea of that proof has been taken over from [L_{2}].

Explicitly: the category of cospans with domains A, B, denoted by (A, B) ↓ D, has as objects all cospans^{2}

\xymatrix{A \ar[r]_{φ_{0}} & Z & B \ar[l]^{φ_{1}}}

2Arrows in the diagram corrected 2007-01-22.

in D and as morphisms all commutative diagrams^{3}

\xymatrix{ & Z \ar[dd] \\ A \ar[ur]^{φ_{0}} \ar[dr]_{φ′_{0}} &  & B \ar[ul]_{φ_{1}} \ar[dl]^{φ′_{1}} \\  & Z′}

in D.

1.3. Example. Reflexive coequalizers are sifted colimits: they are easily seen to be precisely the colimits over the category D obtained from the following graph

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

modulo the equations

f_{1}d = f_{2}d = id .

In Set, reflexive coequalizers commute with finite products. In fact, given D_{i} : D → Set, a coequalizer of D_{i}f_{1} and D_{i}f_{2} is the canonical map c_{i} : DB → DB/ ∼_{i} where for two elements x, y ∈ DB we have x ∼_{i} y iff x can be connected with y by a (D_{i}f_{1}, D_{i}f_{2})-zig-zag. The reflexivity of the pair f_{1}, f_{2} guarantees that given x ∼_{1} y and u ∼_{2} v we can choose those two zig-zags to be of the same type and hence, to render a (D_{1}f_{1}×D_{2}f_{1}, D_{1}f_{2}×D_{2}f_{2})- zig-zag between (x, u) and (y, v).

1.4. Remark. (a) In the following theorem we work with zig-zags in a category D, i.e., diagrams of the following form

(1) \xymatrix{Z_{0} \ar[r]^{φ_{0}} & Z_{1} & Z_{2} \ar[l]_{φ_{1}} \ar[r]^{φ_{2}} & ⋯ Z_{n−1} & Z_{n} \ar[l]_{φ_{n−1}}}

(where n = 0 represents Z_{0} as an “empty zig-zag” and n = 2 is just a (Z_{0}, Z_{2})-cospan). (b) A zig-zag morphism from the zig-zag (1) to the following zig-zag

(2) \xymatrix{Z′_{0} \ar[r]^{φ′_{0}} & Z′_{1} & Z′_{2} \ar[l]_{φ′_{1}} \ar[r]^{φ′_{2}} & ⋯ Z′_{m−1} & Z′_{m} \ar[l]_{φ′_{n−1}}}

is a collection h = (h_{i})_{i=0}^{m} of morphisms

h_{i} = Z_{r(i)} ⟶ Z′_{i} for i = 0, …, m

where r(0) ≤ r(1) ≤ … ≤ … r(m) and the following holds each i = 0, …, m − 1

3Vertical arrow added to the diagram 2007-01-22.

either r(i + 1) = r(i) and the triangle composed by h_{i+1}, h_{i}, φ′_{i} commutes,

(3)  or r(i + 1) = r(i) + 1 and the diagram composed of h_{i+1}, h_{i}, φ′_{i} and φ_{r(i)}

commutes.

Example of a zig-zag morphism:

\xymatrix{ & Z_{0} \ar[r] & Z_{1} \ar[dll]_{h_{0}} \ar[dl]_{h_{1}} \ar[d]_{h_{2}} & Z_{2} \ar[l] \ar[d]_{h_{3}} \ar[dr]^{h_{4}} \\ Z′_{0} \ar[r] & Z′_{1} & Z′_{2} \ar[l] \ar[r] & Z′_{3} & Z′_{4} \ar[l]}

(c) Composition of zig-zag morphisms as well as identity morphisms are defined component-wise.

1.5. Notation. (a) ZZ(D) denotes the category of zig-zags in D and zig-zag morphisms.

(b) For a functor F : A ⟶ Set the category el F of elements of F has objects (A, a) where A ∈ A and a ∈ F A; morphisms f : (A, a) → (A′, a′) are A-morphisms f : A → A′ with F f(a) = a′. The forgetful functor U : el F → A is given by U(A, a) = A.

1.6. Theorem. The following conditions on a small, nonempty category D are equivalent:

(1) D is sifted,

(2) the category (A, B) ↓ D of all (A, B)-cospans is connected for every pair A, B of objects of D

and

(3) every pair of zig-zags of D has a cospan in the category ZZ(D) of zig-zags.

Remark. Explicitly, (2) states that for every pair (A, B) of objects of D (i) an (A, B)- cospan exists and (ii) two (A, B)-cospans are always connected by a zig-zag in (A, B) ↓ D.

Proof. 1 → 2: Consider the diagrams D(A, −), D(B, −) : D → Set. They obviously both have a colimit isomorphic to 1 in Set, therefore, the diagram

D = D(A, −) × D(B, −)

has a colimit isomorphic to 1 × 1 = 1. This means that the category el D of elements D is connected. It is easily seen that el (D) ≅ (A, B) ↓ D.

2 → 3: Assuming (2) we prove the following strengthening of (3): (3^{∗}) Given zig-zags

Z – connecting A and B, Z′ – connecting A′ and B′, then for every pair of cospans

\xymatrix{A \ar[r]^{p} & A^{∗} & A′ \ar[l]_{p′} & and & B \ar[r]^{q} & B^{∗} & B′ \ar[l]_{q′}}

there exists a zig-zag

Z^{∗} − connecting A^{∗} and B^{∗}

and two zig-zag morphisms:

h : Z → Z^{∗} with the first component p and the last one q, h′ : Z′ → Z^{∗} with the first component p′ and the last one q′ .

It is clear that (2) and (3^{∗}) imply (3).

We proceed by induction on the sum of the lengths of Z and Z′. Denote these lengths by n and m, resp.

Initial step: n + m ≦ 2. Thus, n ≦ 2 and m ≦ 2 and the initial data can be presented as follows:

\xymatrix{A \ar[r]^{φ_{0}} \ar[d]_{p} & Z_{1} \ar[d]_{r} & B \ar[l]_{φ_{1}} \ar[d]^{q} \\ A^{∗} & C^{∗} & B^{∗} \\ A′ \ar[u]^{p′} \ar[r]_{φ′_{0}} & Z′_{1} \ar[u]^{r′} & B′ \ar[u]_{q′} \ar[l]^{φ′_{1}}}

The upper horizontal line is Z (if n = 0, put φ_{0} = φ_{1} = id _{A}), the lower horizontal line is Z′ (if m = 0, put φ′_{0} = φ′_{1} = id _{A′}). The (Z_{1}, Z′_{1})-cospan in the middle has been chosen arbitrarily, applying (2) to (Z_{1}, Z′_{1}) ↓ D.

Now we have two (A, A′)-cospans above: (p, p′) and (rφ_{0}, r′φ′_{0}). By applying (2) to (A, A′) ↓ D we connect these two cospans by a zig-zag whose objects are (h_{0}, h′_{0}) =^{def} (p, p′), (h_{1}, h′_{1}), …, (h_{k}, h′_{k}) =^{def} (rφ_{0}, r′φ′_{0}). Analogously, we have two (B, B′)-cospans (q, q′) and (rφ_{1}, r′φ′_{1}) which can be connected by a zig-zag in (B, B′) ↓ D, say, with

objects (h_{k}, h′_{k}) = (rφ_{1}, r′, φ′_{1}), (h_{k+1}, h′_{k+1}), …, (h_{l}, h′_{l}) =^{def} (q, q′). This defines a zig-zag

Z^{∗} with the desired properties indicated by the middle horizontal line in the following diagram:

\xymatrix{A \ar[rrrr]^{φ_{0}} \ar[d]_{p=h_{0}} \ar[dr] \ar[drr] \ar[drrr]^{h_{k−1}} &  &  &  & Z_{1} \ar[d]_{h_{k}}^{=r} &  &  &  & B \ar[llll]_{φ_{1}} \ar[d]^{q=h_{1}} \ar[dl] \ar[dll] \ar[dlll]_{h_{k+1}} \\ A^{∗} = Z_{0}^{∗} \ar[r] & Z_{1}^{∗} \ar[r] & Z_{2}^{∗} \ar[r] & ⋯Z_{k−1}^{∗} & Z_{k}^{∗} \ar[l] \ar[r] & Z_{k+1}^{∗} ⋯ & Z_{l−2}^{∗} \ar[l] & Z_{l−1}^{∗} \ar[l] & Z_{l}^{∗} = B^{∗} \ar[l] \\ A′ \ar[rrrr]_{φ′_{0}} \ar[u]^{p′=h′_{0}} \ar[ur] \ar[urr] \ar[urrr] &  &  &  & Z′_{1} \ar[u]^{h′_{k}}_{=r′} &  &  &  & B′ \ar[llll]^{φ′_{1}} \ar[u]^{q′=h′_{1}} \ar[ul] \ar[ull] \ar[ulll]_{h′_{k+1}}}

Induction step: n + m > 2. Suppose e.g. n > 2 and apply the induction hypothesis first on the pair of zig-zags

Z̃ ≡ A ⟶^{φ_{0}} Z_{1} ⟵^{φ_{1}} Z_{2} (the initial segment of Z)

and A′ (zig-zag of length 0) and the given cospan A ⟶^{p} A^{∗} ⟵^{p′} A′ together with an arbitrarily chosen (Z_{2}, A′)-cospan Z_{2} ⟶^{r} C^{∗} ⟵^{r′} A′. We obtain a zig-zag Z̃^{∗} connecting A^{∗} with C^{∗} and zig-zag morphisms

h̃ : Z̃ → Z̃^{∗} and h̃′ : A′ → Z̃^{∗}

with the specified first and last components.

Next, we apply the induction hypothesis on the rest Ẑ of Z (a zig-zag connecting Z_{2} with B) and the zig-zag Z′ using the following cospans:

\xymatrix{Z_{2} \ar[r]^{r} & C^{∗} & A′ \ar[l]_{r′} & and & B \ar[r]^{q} & B^{∗} & B′ \ar[l]_{q′}}

We obtain a pair of zig-zag morphisms

ĥ : Ẑ → Ẑ^{∗} and ĥ′ : Z′ → Ẑ^{∗} .

Here Ẑ^{∗} is a zig-zag connecting C^{∗} with B^{∗}, and by gluing Z̃^{∗} together with Ẑ^{∗} at C^{∗} (the end-object of the first one and the start object of the latter one), we obtain a zig-zag Z^{∗} connecting A^{∗} with B^{∗}. Also, the first component of ĥ is r, equal to the last component of h̃, thus, we obtain a morphism of zig-zags

h : Z → Z^{∗}

by using first the components of h̃ and then those of ĥ (except that the first component of ĥ is not repeated, of course). Analogously with

h′ : Z′ → Z^{∗} .

3 → 1: It suffices to prove that 3^{∗} → 1. We first observe that (3^{∗}) implies the following (4) Let Z and Z′ be zig-zags connecting A and B. Then there exists a zig-zag Z^{∗}

connecting A and B and zig-zag morphisms h : Z → Z^{∗}, h′ : Z′ → Z^{∗} which both have the first component id _{A} and the last one id _{B}.

In fact, apply (3^{∗}) to p = p′ = id _{A} and q = q′ = id _{B}.

Let D, D′ : D → Set be diagrams and suppose colimits of D, D′ and D × D′ are given as follows:

(Dd →^{c_{d}} C) = colimD
(D′d →^{c′_{d}} C′) = colimD′

and

(Dd × D′d →^{c_{d}^{∗}} C^{∗}) = colim(D × D′) .

We prove that the canonical map

f : C^{∗} → C × C′, f · c_{d}^{∗} = c_{d} × c′_{d}

is a bijection.

(a) f is surjective. In fact, given (x, x′) ∈ C × C′ there exist d, d′ ∈ D such that (x, x′) lies in the image of c_{d} × c′_{d}. By (4) there exists a (d, d′)-cospan in D, say, with codomain d^{∗}. Then c_{d} factors through c_{d^{∗}} and c′_{d′} through c′_{d^{∗}}, thus, (x, x′) lies in the image of c_{d^{∗}} × c′_{d^{∗}} = f · c_{d^{∗}}^{∗} - thus, f is surjective.

(b) f is injective. We prove that if two elements u, ū ∈ C^{∗} fulfill

(5) f(u) = f(ū)

then u = ū. We can express u and ū in the following form:

u = c_{d}^{∗}(v, v^{∗}) for d ∈ D, v ∈ Dd and v′ ∈ D′d
ū = c∗ ; d̄(w, w̄) for d̄∈ D, w ∈ Dd̄ and w′ ∈ D′d̄

Then (5) is equivalent to

(6) c_{d}(v) = cd̄(w) and c′ ; d̄(v′) = cd̄(w′) .

By the well known description of colimits in Set, this means that the elements (d, v) and (d̄, w) can be connected by a zig-zag Z in the category el D of elements of D, and the elements (d, v′) and (d̄, w′) can be connected by a zig-zag Z′ in el D′.

The forgetful functor

U : el D → D , (d, x) ⟼ d

can be applied component-wise to obtain a functor on zig-zags

ZZ(U) : ZZ(el D) → ZZ(D) .

Analogously for ZZ(U′).

Case 1: ZZ(U) maps the zig-zag Z to the same (underlying) zig-zag Z_{0} in D as ZZ(U′) maps Z′. In this case immediately combine Z and Z′ to a zig-zag connecting (d, (v, v′)) with (d̄, (w, w′)) in el (D × D′) (and having underlying zig-zag Z_{0}). This proves c_{d}^{∗}(v, v′) = c∗ ; d̄(w, w′), in other words, u = ū.

Case 2: the underlying zig-zags of Z and Z′ are different. Denote by D[d, d̄] the subcategory of ZZ(D) of all zig-zags connecting d with d̄and all zig-zag morphisms with first component id _{d} and last one id d̄. Analogously el D[(d, v), (d̄, w)] and el D′[(d, v′), (d̄, w′)]. The forgetful functor U : el D → D is a cofibration. It is easy to verify that, then, ZZ(U) is a cofibration too, and so is the domain-codomain restriction

Ũ : el D[(d, v), (d̄, w)] → D[d, d̄] ,

Analogously, the cofibration U′ leads to a cofibration

Ũ′ : el D′[(d, v′), (d̄, w′)] → D[d, d̄] .

Applying (4) to the zig-zags Ũ(Z), Ũ′(Z′), we obtain a zig-zag Z_{0} in D(d, d̄) and zig-zag morphisms

h : Ũ(Z) → Z_{0} and h′ : Ũ(Z′) → Z_{0}

in D(d, d̄). Since Ũ is a cofibration, it lifts Z_{0} to a zig-zag Z̄ and it lifts h to a zig-zag morphism h̄ : Z → Z̄ with Ũ(h̄) = h; analogously we obtain h̄′ : Z′ → Z̄′. Now Z̄ and Z̄′ have the same underlying zig-zag, Z_{0}, and we can apply Case 1.

2. The Completion Sind

2.1. Analogously to the free completion

Ind A

of A under filtered colimits introduced by Grothendieck [AGV], we study a free completion

Sind A

of A under sifted colimits. For example, if A is a small category with finite colimits, then

Ind A = [A^{op}, Set]_{lex}

is the category of all presheaves on A^{op} preserving finite limits, see [AGV], and, as we will show,

Sind A = [A^{op}, Set]_{fp}

is the category of all presheaves on A^{op} preserving finite products. There are many more analogies between Ind and Sind .

2.2. Definition. For every category A we denote by

η_{A} : A → Sind A

a free completions of A under sifted colimits. That is, η_{A} is a full embedding into a category Sind A with sifted colimits with the following universal property:

For every category B with sifted colimits the functor category [A, B] is equivalent to the category [Sind A, B]_{sift} of all functors from Sind A to B preserving sifted colimits via the functor

(−) · η_{A} : [Sind A, B]_{sift} → [A, B] .

2.3. Examples. (1) If A is a poset then

Ind A = Sind A

is the ideal completion of A, i.e., the poset of all ideals (directed down-sets) ordered by inclusion.

(2) Let A be a category with finite coproducts. Denote by A^{∗} a free completion of A under reflexive coequalizers (this has been described explicitly by A. Pitts, see [BC]). Then

Sind A = Ind A^{∗} ,

as proved in 2.8 below.

(3) For the category A:

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

with the free composition modulo

(1) f_{1}d = f_{2}d = id we see that A is finite and has split idempotents, thus,

Ind A = A .

However, Sind A contains a coequalizer c : B → C of the reflexive pair f_{1}, f_{2}. In fact, Sind A is the extension of A as follows

\xymatrix{A \ar[r]^{f_{1}} \ar[r]_{f_{2}} & B \ar[l]_{d} \ar[r]^{c} & C}

with free composition modulo (1) and cf_{1} = cf_{2}.

(4) In general, the equation Sind A = Ind A^{∗} is not true. Consider the category A given by the following graph

\xymatrix{⋮ & ⋮ \\ A_{2} \ar[r]^{p_{2}} \ar[r]_{q_{2}} & B_{2} \\ A_{1} \ar[u]_{a_{1}} \ar[r]^{p_{1}} \ar[r]_{q_{1}} & B_{1} \ar[ul]_{d_{1}} \ar[u]_{b_{1}} \\ A_{0} \ar[u]_{a_{0}} \ar[r]^{p_{0}} \ar[r]_{q_{0}} & B_{0} \ar[ul]_{d_{0}} \ar[u]_{b_{0}}}

and the following commutativity conditions for all n ∈ ω:

p_{n+1}a_{n} = b_{n}p_{n} , q_{n+1}a_{n} = b_{n}q_{n} , a_{n+1}d_{n} = d_{n+1}b_{n} ,

and

b_{n} = p_{n+1}d_{n} = q_{n+1}d_{n} .

Since A has no reflexive pairs, A = A^{∗}. The category Ind A is obtained by adding to A a colimit A_{ω} of the chain (A_{n})_{n∈ω}, a colimit B_{ω} of the chain (B_{n})_{n∈ω}, and three morphisms p_{ω} = colimp_{n}, q_{ω} = colimq_{n}, d_{ω} = colimd_{n}. Since p_{ω}d_{ω} = q_{ω}d_{ω} = id , we obtain a reflexive pair without a coequalizer in Ind A, thus, Ind A ≠ Sind A.

2.4. Remark. Let D be a small category. Recall that a presheaf D in Set^{D} is called flat if it is a filtered colimit of hom-functors. Or, equivalently, if the dual of the category el D of elements of D is filtered. The completion Ind A can be, for A small, described as the category of all flat presheaves on A^{op}, see [B].

Recall further that if D is small, than F is flat iff Lan_{Y} F preserves finite limits; here Lan_{Y} F denotes a left Kan extension of F along the Yoneda embedding Y : D → Set^{D^{op}}. We now generalize this to sifted colimits.

2.5. Definition. A functor D : D → Set is called sifted-flat provided that it is a sifted colimit of hom-functors.

2.6. Theorem. The following conditions on a functor F : D → Set, D small, are equivalent:

(i) F is sifted-flat, (ii) the dual of the category of elements of F is sifted,

(iii) F lies in the (iterated) closure of hom-functors under sifted colimits,

(iv) Lan_{Y} F preserves finite products.

Remark. (iv) can be weakened to (iv)^{∗} Lan_{Y} F preserves finite products of hom-functors.

(iv)^{∗} →(ii): Proof. For two hom-functors hom(−, A_{1}), hom(−, A_{2}) put

D = hom(−, A_{1}) × hom(−, A_{2}).

Then (Lan_{Y} F)(D) is a colimit of F ·E_{D} (where E_{D} : el D → D is the diagram of elements of D; observe that objects of el D are spans A_{1} ←^{x_{1}} X →^{x_{2}} A_{2}). Denote by

c(x_{1}, x_{2}) : F X → Lan_{Y} F (D)

a colimit cocone of F · E_{D} in Set. Now (iv)^{∗} states that for arbitrary objects A_{1} and A_{2} the maps

π_{i} : Lan_{Y} F (D) → F A_{i} (i = 1, 2)

defined by

π_{i} · c(x_{1}, x_{2}) = F x_{i} for all spans (x_{1}, x_{2})

form a product in Set. We will prove that this implies that the dual of the category el F of elements of F is sifted.

For arbitrary elements (A_{1}, a_{1}) and (A_{2}, a_{2}) of F (i.e., objects of el F) we know that (a_{1}, a_{2}) ∈ F A_{1} × F A_{2} has the form (π_{1}(ā), π_{2}(ā)) for some ā ∈ Lan_{Y} F (D). And since Lan_{Y} F (D) = colimF E_{D}, ā has the form ā = c(x_{1}, x_{2})(a) for some span A_{1} ←^{x_{1}} X →^{x_{2}} A and some a ∈ F A. Thus a_{i} = π_{i} · c(x_{1}, x_{2})(ā) = F x_{i}(a) and we proved the existence of a cospan in (el F)^{op}

(A_{1}, a_{1}) →^{x_{1}} (X, a) ←^{x_{2}} (A_{2}, a_{2}) .

Let another cospan

(A_{1}, a_{1}) →^{x′_{1}} (X′, a′) ←^{x′_{2}} (A_{2}, a_{2})

be given. Then

π_{i}c(x_{1}, x_{2})(a) = a_{i} = π_{i}c(x′_{1}, x′_{2})(a′) for i = 1, 2

implies (since π_{1}, π_{2} are projections of a product) that

c(x_{1}, x_{2})(a) = c(x′_{1}, x′_{2})(a′) .

By construction of colimits in Set, the latter means that the two elements of F E_{D}, ((x_{1}, x_{2}), a) and ((x′_{1}, x′_{2}), a′), are connected by a zig-zag in (el (F E_{D}))^{op}. Now we have an obvious forgetful functor (el (F E_{D}))^{op} → (el F)^{op} which maps that zig-zag onto a zig-zag connecting (x, a) with (x′, a′) in (A_{1}, A_{2}) ↓ D.

(ii) → (i) → (iii) is trivial

(iii) → (iv) Since Lan_{Y} (−) preserves colimits, (iii) implies that Lan_{Y} F is obtained as an iterated sifted colimit from the set of functors Lan_{Y} D(−, A). The last functor preserves finite products (since this is just the evaluation-at-A functor from Set^{D^{op}} to Set). And a sifted colimit of functors preserving finite products preserves finite products too. This proves (iv).

2.7. Corollary. For every small category A we can describe Sind A as the full subcategory of Set^{A^{op}} of all sifted-flat functors (with respect to the codomain restriction of the Yoneda embedding Y : A → Set^{A^{op}}).

Proof. Following 2.6 (iii), the full subcategory Ā of Set^{A^{op}} consisting of all sifted-flat functors has sifted colimits. Following 2.6 (ii), a left Kan extension Lan_{Y} H : Ā → B exists for each functor H : A → B where B has sifted colimits. Since Lan_{Y} H clearly preserves sifted colimits, Ā ≈ Sind A.

2.8. Corollary. If A is a small category with finite coproducts then

Sind A = [A^{op}, Set]_{fp}

Proof. Since Y : A^{op} → Set^{A} preserves finite products, any sifted-flat functor F : A^{op} → Set preserves finite products following 2.6 (iv). Conversely, if F preserves finite products then Lan_{Y} F preserves finite products of hom-functors because

(Lan_{Y} F)(hom(−, A_{1}) × hom(−, A_{2})) ≅ (Lan_{Y} F)(hom(−, A_{1} × A_{2}))
≅ F (A_{1} × A_{2})
≅ F (A_{1}) × F (A_{2})
≅ Lan_{Y} (F)(hom(−, A_{1})) × (Lan_{Y} F)(hom(−, A_{1})).

Hence F is sifted-flat following 2.6 (iv)^{∗}.

Remark. The last corollary proves the claim of Example 2.3 (2): the categories [(A^{∗})^{op}, Set]_{lex} and [A^{op}, Set]_{fp} are equivalent.

2.9. Remark. Corollary 2.8 immediately generalizes to small categories A with finite multicoproducts. (A multicoproduct of a finite set A_{1}, …, A_{n} is a set of cocones (c_{ij} : A_{j} → C_{i})_{j=1,...,n}, i ∈ I such that every cocone of A_{1}, …, A_{n} factors through precisely one of these, and the factorization is unique). A functor F : A^{op} → Set is said to preserve multiproducts provided that for each finite set A_{1}, …, A_{n} of objects in A the cone

π_{j} : ∐_{i∈I} F C_{i} → F A_{j} (j = 1, …, n)

where π_{j} has components F c_{ij}, is a product in Set. Then

Sind A = [A^{op}, Set]_{fmp}

is the full subcategory of Set^{A^{op}} formed by all functors preserving finite multiproducts.

In fact, Y : A^{op} → Set^{A} preserves finite multiproducts. Since Lan_{Y} F preserves for any F : A^{op} → Set arbitary coproducts, any sifted-flat functor F preserves finite multiproducts following 2.6.(iv). Conversely, if F preserves finite multiproducts then Lan_{Y} F preserves finite products because

(Lan_{Y} F)(∏_{j=1}^{n} hom(−, A_{j})) ≅ (Lan_{Y} F) ∐_{i∈I} hom(−, C_{i}))
≅ ∐_{i∈I}(Lan_{Y} F)(hom(−, C_{i}))
≅ ∐_{i∈I} F C_{i}

≅ ∏_{j=1}^{n} F A_{j}

≅ ∏_{j=1}^{n}(Lan_{Y} F) hom(−, A_{j}).

3. Generalized Varieties

3.1. Recall from [L_{1}] and [MP] the fruitful concept of a finitely accessible category, i.e., a category K such that

(a) K has filtered colimits

and

(b) K has a (small) set A of finitely presentable objects such that every object of K is a filtered colimit of objects in A.

Moreover, finitely presentable objects are, of course, precisely those whose hom-functors preserve filtered colimits. We now substitute “filtered” by “sifted” and obtain the following concepts.

3.2. Definition. An object of a category is called strongly finitely presentable provided that its hom-functor preserves sifted colimits.

3.3. Lemma. Let K be a category with kernel pairs. An object which is strongly finitely presentable is

(i) finitely presentable and

(ii) a regular projective.

If K is a variety of finitary algebras, (i) and (ii) are equivalent to strong finite presentability.

Proof. If K is strongly finitely presentable, then hom(K, −) preserves coequalizers of kernel pairs, since these are reflexive coequalizers (see 1.3 (1)), thus, K is a regular projective.

Suppose K is a variety. Then for every object K with (i) and (ii), the functor hom(K, −) : K → Set preserves limits, filtered colimits and regular epimorphisms. Hence it is a completely exact functor, which implies that it preserves sifted colimits, see [ALR].

3.4. Examples. (1) In Set, finitely presentable = strongly finitely presentable, the same holds in the category K-Vec of vector spaces over a field K.

(2) In Ab the category of Abelian groups, strongly finitely presentable objects are precisely the free Abelian groups on finitely many generators.

(3) In Pos the category of posets, strongly finitely presentable objects are the finite discretely ordered ones (=finitely presentable regular projectives).

3.5. Remark. (i) A finite coproduct of strongly finitely presentable objects is strongly finitely presentable.

(ii) For finite colimits this is no longer true (see 3.4.2)

(iii) A finite multicoproduct of strongly finitely presentable objects has all components strongly finitely presentable.

In fact, let A_{j}, j = 1, …, n be strongly finitely presentable objects in K and (c_{ij} : A_{j} → C_{i}), i ∈ I be a multicoproduct in K. Let (s_{t} : X_{t} → X)_{t∈T} be a sifted colimit in K. Then

∐_{i∈I} hom(C_{i}, colim_{t∈T} X_{t}) ≅ ∏_{j=1}^{n} hom(A_{j}, colim_{t∈T} , X_{t})

≅ colim_{t∈T} ∏_{j=1}^{n} hom(A_{j}, X_{t})
≅ colim_{t∈T} ∐_{i∈I} hom(C_{i}, X_{t})
≅ ∐_{i∈I} colim_{t∈T} , hom(C_{i}, X_{t})

and this canonical isomorphism has canonical components

hom(C_{i}, colim_{t∈T} X_{t}) ≅ colim_{t∈T} hom(C_{i}, X_{t})

for each i ∈ I. Hence C_{i} is strongly finitely presentable (for each i ∈ I).

3.6. Definition. By a generalized variety is meant a category which has

(a) sifted colimits and

(b) a (small) set A of strongly finitely presentable objects such that every object is a sifted colimit of objects in A.

3.7. Examples. (1) Every variety V is a generalized variety. In fact, choose a set A of representatives for finitely presentable regular projectives. Every object K is a canonical colimit of the forgetful functor A ↓ K → V (since A is dense) and since A has finite coproducts, so does A ↓ K, thus, the canonical colimits are sifted (1.3 (2)).

(2) In the next section we will see other examples of generalized varieties: fields, linearly ordered sets, sets and injective functions. These are generalized varieties with connected limits.

(3) The category of non-empty sets and functions is, obviously, a generalized variety (and does not have connected limits).

(4) Let us mention an interesting non-example: the category Gra_{c} of connected graphs and graphs homomorphisms. This category has sifted colimits because it is closed under sifted colimits in Gra, the category of all graphs. (In fact, let D be a small category such that every pair of objects has a cospan, then a D-colimit of connected graphs in Gra is connected). It is easy to see that the “obvious” dense set A in Gra, consisting of (a) a single vertex (no edges) and (b) a single edge, lies in Gra_{c} and forms a strong generator of strongly finitely presentable objects of Gra_{c}. Nevertheless, Gra_{c} fails to be a generalized variety. In fact, the only regular projectives in Gra_{c} are the graphs with a single vertex, and they do not generate other graphs by sifted colimits in Gra_{c}.

(5) The category Gra_{c}^{∗} of connected graphs and injective graph homomorphisms is a generalized variety. The existence of sifted colimits is clear, and strongly finitely presentable objects are precisely finite connected graphs. Any connected graph is a sifted union of finite connected graphs.

3.8. Lemma. In every generalized variety K the collection K_{0} of all strongly finitely presentable objects is essentially small and dense, and the comma-categories K_{0} ↓ K are sifted for all objects K of K.

Proof. Let A be set as in 3.5 (b). Let K_{0} ∈ K_{0} be expressed as a sifted colimit (A_{i} →^{a_{i}} K_{0})_{i∈I} with A_{i} ∈ A for each i ∈ I. Since hom(K_{0}, −) preserves that colimit, id _{K_{0}} factors through some A_{i}. Thus, K_{0} consists of retracts of objects in A. Since A is small, this proves that K_{0} is essentially small.

Let K ∈ K be an arbitrary object and express K as a sifted colimit (A_{i} →^{a_{i}} K)_{i∈I} with A_{i} ∈ A. Every morphism f : K_{0} → K, K_{0} ∈ K_{0}, factors through some a_{i} and given two such factorizations:

f = a_{i} · f′ = a_{j} · f′′ (i, j ∈ I)

then they are connected by a zig-zag in A ↓ K – this follows from the fact that hom(K, −) preserves the above colimit. We conclude that K is a canonical colimit of the diagram K_{0} ↓ K → K. And that diagram is sifted because the original sifted diagram of all A_{i} →^{a_{i}} K is a cofinal subdiagram in it.

3.9. Remark. (1) Finitely accessible categories are precisely the categories Ind A, A small. Quite analogously: generalized varieties are precisely the categories

Sind A , A small .

In fact, Sind A is a generalized variety because, by 2.6, every object of Sind A is a sifted colimit of objects of A (or, the corresponding hom-functors), and since Sind A is closed under sifted colimits in Set^{A^{op}}, and hom-functors are strongly finitely presentable in Set^{A^{op}}, they are also strongly finitely presentable in Sind A.

Conversely, if K is a generalized variety, let A be a full subcategory representing all strongly finitely presentable objects. By Lemma 3.8, all objects of K are canonical sifted colimits of A-objects. This implies K ≈ Sind A quite analogously to the proof of K ≈ Ind A in case K is finitely accessible (see e.g. [AR_{1}], Theorem 2.26).

(2) Recall that among complete or cocomplete categories, finitely accessible ones are precisely the locally finitely presentable categories of Gabriel and Ulmer. This has a direct analogy:

3.10. Theorem. A cocomplete category is a generalized variety iff it is equivalent to a variety.

Remark. In fact, every generalized variety with finite coproducts is a variety: from the existence of sifted colimits follow all coproducts (=filtered colimits of finite coproducts) and reflexive coequalizers – thus, cocompleteness.

Proof. Any variety is a cocomplete generalized variety. Let K be a cocomplete generalized variety. Then the full subcategory K_{0} representing all strongly finitely presentable objects of K has finite coproducts (following Remark 3.5(i)). Using Remark 3.9 and Corollary 2.8, we get that

K ≈ Sind K_{0} ≈ [K_{0}^{op}, Set]_{fp}

and K is therefore equivalent to a variety.

4. Multialgebraic categories

4.1. Since the dissertation of F.W.Lawvere [La] it is well known that varieties are precisely categories sketchable by FP-sketches. That is, given an FP-sketch S, i.e., a small category A with chosen finite discrete cones, we form the category

ModS ⊆ Set^{A}

of all functors turning the given cones into (finite) products in Set. Then

(1) ModS is equivalent to a variety and

(2) every variety is equivalent to some ModS. (In [La] the case of one-sorted varieties and FP-sketches generated by a single object is treated. See [AR_{1}] for the many-sorted case.)

Y. Diers presented in [D] a generalization to sketches using finite multiproducts, and called the categories of models multialgebraic categories. In [AR_{2}] we have shown that instead of the (non-standard) multiproducts the following standard concept can be used: by an FPC-sketch (for “finite products and [arbitrary] coproducts”) S is meant a small category A with chosen

(a) discrete finite cones and

(b) discrete cocones. We denote by

ModS ⊆ Set^{A}

the category of all models of S, i.e., the full subcategory of Set^{A} of all functors turning the given cones into (finite) products and the given cocones to coproducts. The following concept is then identical with that of Y. Diers:

Definition. A category is called multialgebraic if it is FPC-sketchable, i.e., equivalent to the category of models of an FPC-sketch.

Characterization Theorem (Y. Diers, [D]). A category is multialgebraic iff it has (i) multicolimits, (ii) filtered colimits, (iii) effective equivalence relations, (iv) a regular generator formed by finitely presentable regular projectives.

Remark. Y. Diers has another condition, viz, the existence of kernel pairs, but it follows from (i)-(iii) that all connected limits exist (see [AR_{1}], 4.30).

4.2. Remark. Multialgebraic categories have, in contrast to varieties, no kind of “equational presentation”. In [AR_{2}] we have introduced multivarieties: these are classes of algebras presented by exclusive-or’s of equations. Every multivariety with effective equivalence relations is multialgebraic, and vice versa. An example of a multivariety which is not multialgebraic is the category of unary algebras on one injective operations.

The following examples demonstrate how natural the syntax via FPC-sketches is for important multialgebraic theories.

4.3. Examples. (1) Fields.

Let S_{0} be the usual FP-sketch for rings. We thus have, among others, morphisms

+, ∗ : X × X → X
π_{1}, π_{2} : X × X → X
0 : 1 → X

and others needed to express the ring equations. We now add a new object Y (representing all non-zero elements of X) and morphisms

e : Y → X (embedding)
i : Y → X (multiplication inverse)

and denote by ⟨e, i⟩ : Y → X ×X the corresponding pair. Next we put one commutativity condition

\xymatrix{Y \ar[r]^{⟨e,i⟩} \ar[dr]_{e} & X × X \ar[d]^{∗} \\  & X}

and one cocone

\xymatrix{1 \ar[dr]_{0} &  & Y \ar[dl]^{e} \\  & X}

The resulting sketch S has the category of fields and field homomorphisms as ModS. (3) Linearly ordered sets (see [AR_{1}], 2.57). Let S_{0} be the usual FP-sketch for sup-semilattices. We thus have, among others,

morphisms

∨ : X × X → X
π_{1}, π_{2} : X × X → X
Δ : X → X × X

and others expressing the commutativity, associativity, and idempotency of ∨. We now add to S_{0} two new objects E and Ē and morphisms

e : E → X × X and ē: Ē → X × X

subject to

π_{1}e = π_{2}ē and π_{2}e = π_{1}ē

as well as

π_{2}e = σe.

Finally, we add a cocone

\xymatrix{E \ar[dr]_{e} & X \ar[d]_{Δ} & Ē \ar[dl]^{ē} \\  & X × X}

In a model M, we have a relation ME on MX whose inverse relation MĒ fulfills: MX × MX = ME ∪ MĒ ∪ Δ_{MX} and which, due to π_{2}e = σe, is just the strict order relation of the semilattice (MX, M∨). Thus, we obtain a sketch S whose category ModS is the category of linearly ordered sets and order-preserving mappings.

(5) Sets and injective functions.

Let S be the sketch with objects

X, X × X, Y (= complement of the diagonal)

and morphisms

π_{1}, π_{2} : X × X → X ,
Δ : X → X × X

and

y : Y → X × X

subject to

π_{1}Δ = π_{2}Δ = id .

There is one product specification

\xymatrix{ & X × X \ar[dl]_{π_{1}} \ar[dr]^{π_{2}} \\ X &  & X}

and one coproduct specification

\xymatrix{X \ar[dr]_{Δ} &  & Y \ar[dl]^{y} \\  & X × X}

It is obvious that ModS is equivalent to the category of all sets and injective functions.

4.4. Theorem. A category with multicolimits is a generalized variety iff it is multialgebraic.

Proof. This is completely analogous to that of Theorem 3.10 (we use 3.5(iii) and 2.9 instead of 3.5(i) and 2.8).

4.5. Remark. Thus, we see that in the presence of multicolimits, generalized varieties are precisely the categories which are (finite product, coproduct)-sketchable. For generalized varieties without completeness assumptions we know at least one implication in case coproducts are substituted by colimits:

4.6. Proposition. Every generalized variety can be sketched by a (finite product, colimit)- sketch.

Proof. Let K = Sind A be a generalized variety. By 2.7 and Remark 2.6, Sind A consists of those functors F ∈ Set^{A^{op}} such that Lan_{Y} F preserves finite products of homfunctors. Denote by B a small full subcategory of Set^{A^{op}} representing finite products of hom-functors. Let S be the sketch on B whose cones are the finite products of homfunctors, and whose cocones represent every finite product of hom-functors as a colimit of hom-functors. Since Lan_{Y} F preserves all colimits, it immediately follows from 2.6 (iv)^{∗} that

ModS ≈ Sind A.

4.7. Example. The converse to 4.6 does not hold. For example, consider the sketch S with one object and one endomorphism specified to be epi. This is a (∅, colimit)-sketch whose category of models is the category of unary algebras on one surjective operation. This category is not a generalized variety.

4.8. Remarks. (1) Following Proposition 4.6, any generalized variety K is accessible. Hence K is complete iff it is cocomplete and K has connected limits iff it has multicolimits (cf. [AR_{1}], 2.47 and 4.30). This may be added to the characterization theorems 3.10 and 4.4.

(2) In fact, every generalized variety is ω_{1}-accessible: by 3.8 (1) it has the form K = Sind A, A small, i.e., K is the closure of hom-functors under sifted colimits in Set^{A^{op}} (see 2.7). For every sifted category D it is clear that D is an ω_{1}-directed union of its full, countable, sifted subcategories (see 1.6), thus, objects of K are ω_{1}-directed colimits of ω_{1}-presentable objects (since a countable colimit of hom-functors is ω_{1}-presentable in Set^{A^{op}}, thus, in K too).

4.9 Open problems. (1) Is every generalized variety finitely accessible?

(2) Is there a full description of generalized varieties by means of sketches?

References

[AGV] M. Artin, A. Grothendieck and J. L. Verdier, Théorie des topos et cohomologie étale des schémas, Lect. Notes in Math. 269, Springer-Verlag, Berlin 1972.

[ALR] J. Adámek, F. W. Lawvere and J. Rosický, On the duality between varieties and algebraic functors, to appear.

[AR_{1}] J. Adámek and J. Rosický, Locally presentable and accessible categories, Cambridge University Press, Cambridge 1994.

[AR_{2}] J. Adámek and J. Rosický, On multivarieties and multialgebraic categories, accepted in Jour. Pure Appl. Alg.

[B] F. Borceux, Handbook of categorical algebra1, Cambridge Univ. Press 1994.

[BC] M. Bunge and A. Carboni, The symmetric topos , Jour. Pure Appl. Algebra 105 (1995), 233–249.

[D] Y. Diers, Catégories multialgébriques, Arch. Math. (Basel) 34 (1980), 193–209.

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

[L_{1}] C. Lair, Catégories modelables et catégories esquissables, Diagrammes 6, (1981) 1–20.

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

[MP] M. Makkai and R. Paré, Accessible categories: the foundations of categorical model theory, Contemp. Math. 104, Amer. Math. Soc., Providence 1989.

[P] H.-E. Porst, Minimal generators in varieties, preprint 1997.

[PW] M. C. Pedicchio and R. J. Wood, A simple characterization of theories of varieties, Journal of Algebra 233 (2000), 483–501.

Technical University Braunschweig Postfach 3329 38023 Braunschweig, Germany and Masaryk University Janáčkovo nám. 2a 662 95 Brno, Czech Republic

Email: adamek@iti.cs.tu-bs.de and rosicky@math.muni.cz

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

mous ftp at ftp://ftp.tac.mta.ca/pub/tac/html/volumes/8/n3/n3.{dvi,ps}

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

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

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

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

rrosebrugh@mta.ca.

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

Editorial board.

John Baez, University of California, Riverside: baez@math.ucr.edu Michael Barr, McGill University: barr@barrs.org, Associate Managing Editor Lawrence Breen, Université Paris 13: breen@math.univ-paris13.fr Ronald Brown, University of North Wales: r.brown@bangor.ac.uk Jean-Luc Brylinski, Pennsylvania State University: jlb@math.psu.edu Aurelio Carboni, Università dell Insubria: aurelio.carboni@uninsubria.it P. T. Johnstone, University of Cambridge: ptj@dpmms.cam.ac.uk G. Max Kelly, University of Sydney: maxk@maths.usyd.edu.au Anders Kock, University of Aarhus: kock@imf.au.dk F. William Lawvere, State University of New York at Buffalo: wlawvere@acsu.buffalo.edu Jean-Louis Loday, Université de Strasbourg: loday@math.u-strasbg.fr Ieke Moerdijk, University of Utrecht: moerdijk@math.uu.nl Susan Niefield, Union College: niefiels@union.edu Robert Paré, Dalhousie University: pare@mathstat.dal.ca Andrew Pitts, University of Cambridge: Andrew.Pitts@cl.cam.ac.uk Robert Rosebrugh, Mount Allison University: rrosebrugh@mta.ca, Managing Editor Jiri Rosicky, Masaryk University: rosicky@math.muni.cz James Stasheff, University of North Carolina: jds@math.unc.edu Ross Street, Macquarie University: street@math.mq.edu.au Walter Tholen, York University: tholen@mathstat.yorku.ca Myles Tierney, Rutgers University: tierney@math.rutgers.edu Robert F. C. Walters, University of Insubria: walters@fis.unico.it R. J. Wood, Dalhousie University: rjwood@mathstat.dal.ca