Theory and Applications of Categories, Vol. 8, No. 9, 2001, pp. 253–283.

HOW ALGEBRAIC IS ALGEBRA ?

J. ADÁMEK^{∗}, F. W. LAWVERE AND J. ROSICKÝ^{∗}

ABSTRACT. The 2-category VAR of finitary varieties is not varietal over CAT . We introduce the concept of an algebraically exact category and prove that the 2-category ALG of all algebraically exact categories is an equational hull of VAR w.r.t. all operations with rank. Every algebraically exact category K is complete, exact, and has filtered colimits which (a) commute with finite limits and (b) distribute over products; besides (c) regular epimorphisms in K are product-stable. It is not known whether (a)

– (c) characterize algebraic exactness. An equational hull of VAR w.r.t. all operations is also discussed.

1. Introduction

1.1. Is algebra algebraic?. The purpose of our paper is to study the non-full embedding

U : VAR → CAT

of the 2-category of all finitary varieties into the 2-quasicategory of all categories. The morphisms (1-cells) of the former are indicated by the duality between varieties and algebraic theories introduced in [ALR_{1}]: they are the algebraically exact functors, i.e., finitary right adjoints preserving regular epimorphisms. And 2-cells are the natural transformations, of course. Is U monadic in some reasonable 2-categorical sense? (This is the precise meaning of the question in the subtitle.) The answer is negative, and we shortly explain it below.

Well, since algebra is not algebraic, what is an “algebraic hull” of algebra? To understand the question, let us use analogy with classical universal algebra: given a class C of algebras, considered as a concrete category w.r.t. the usual forgetful functor U : C → Set , we can form the equational theory of C whose k-ary operations are the natural transformations U^{k} → U, and whose clone is obtained by composition of n-tuples of k-ary operations (i.e., natural transformations from U^{k} to U^{n}). Here the arity k is a (usually finite) set. Now, for VAR, the arities k will be (usually small) categories, and a k-ary operation will be a natural transformation from U^{k} to U – no!, this is too strict. We will have to work with pseudonatural transformations from U^{k} to U. Example: for any small category k an operation “limits of type k” is a pseudonatural transformation from U^{k} to U, since (a) every variety has limits of type k and (b) every algebraically exact functor preserves them (non-strictly, of course). Analogously, for every small filtered category k we have an operation on VAR “filtered colimits of type k”. And one important operation (of arity • ⟵_{⟶}^{⟶} •) is “reflexive coequalizers”. In fact, we will see that all ranked operations are obtained by combining the three types just mentioned.

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

Received by the editors 2000 November 13 and, in revised form, 2001 April 3.

Transmitted by Walter Tholen. Published on 2001 April 11.

2000 Mathematics Subject Classification: 18C99, 18D99, 08B99.

Key words and phrases: variety, exact category, pseudomonad.

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

But let us come back to the negative answer to the question in the subtitle: U : VAR → CAT is not 2-monadic nor pseudomonadic. The argument (quite analogous to that for the 2-category of locally finitely presentable categories in place of VAR, see [ALR_{2}]), is that if we take the “posetal shadow” of U, we get the forgetful functor from the category ALat of algebraic lattices (= those posets which are equivalent to a variety) to the category Pos of all posets. Here morphisms of ALat are maps preserving meets and directed joins, and morphisms of Pos are order-preserving maps, of course. The forgetful functor ALat → Pos is not varietal; in fact, the varietal hull of ALat is formed by the category CLat of continuous lattices of D. Scott. Now take a continuous lattice L which is not algebraic. Express L as the split coequalizer of free continuous (= free algebraic) lattices in the standard way. This gives a split coequalizer in CAT which our forgetful functor U : VAR → CAT fails to create. Thus, U is not pseudomonadic, see [LV].

1.2. An equational hull of VAR. The aim of our paper is to describe an equational hull of the category VAR of varieties over CAT . Here we refer to equations between k-ary operations, where k is a category and a k-ary operation ω assigns to every variety V an operation functor ω_{V} : V^{k} → V in such a way that morphisms of VAR preserve ω; more precisely: that ω becomes a pseudonatural transformation from U^{k} : VAR → CAT into U. An equational hull is, roughly speaking, the smallest equationally defined quasicategory K containing VAR; or, a largest extension K of VAR such that every operation on VAR extends to K and all equations valid in VAR are also valid in K. Formally, K is described as the quasicategory of algebras of a pseudomonad 𝔻^{∗} on CAT which we describe in the last section of our paper.

The disadvantage of the pseudomonad 𝔻^{∗} is that, so far, we have not been able to describe the category of its algebras. The same is, unfortunately, true concerning the small-core 𝔻_{small}^{∗} of that pseudomonad which we obtain by restricting ourselves to all kary operations on VAR where the arity k is a small category. We therefore make a further restriction: to operations with rank. That is, we discuss k-ary operations ω, k small, for which there exists a cardinal λ such that each of the operation functors ω_{V} preserves λ-filtered colimits. (Examples: “limits of type k” is an operation with rank.) We obtain a rank-core pseudomonad 𝔻_{rank}^{∗} of 𝔻^{∗} whose quasicategory of algebras is an equational hull of VAR w.r.t. all operations with rank. We also present another construction of 𝔻_{rank}^{∗} which does not start with 𝔻^{∗}. And we are able to identify 𝔻_{rank}^{∗}-algebras as a subquasicategory of CAT consisting of so-called algebraically exact categories. That is, we introduce the 2-quasicategory

ALG

of algebraically exact categories, algebraically exact functors, and natural transformations, and we prove that ALG is an equational hull of VAR w.r.t. all operations with rank.

1.3. What are algebraically exact categories?. For the theory of varieties there is a concept of central importance generalizing filtered colimits:

sifted colimits.

A small category D is called sifted if D-colimits commute in Set with finite products. And colimits of such types D are then called sifted colimits. Besides filtered colimits, also reflexive coequalizers are sifted. And morphisms of VAR are precisely the functors preserving limits and sifted colimits (see [ALR_{1}]); in general, functors (in CAT ) with the last property will be called algebraically exact.

We have introduced in [AR_{1}] a free completion under sifted colimits, denoted by Sind (to remind of Grothendieck’s free completion Ind under filtered colimits). This completion forms a pseudomonad Sind on CAT . Also a free limit completion forms a pseudomonad on CAT which we denote by Lim . And we prove below that Sind distributes over Lim (in the sense of Beck’s distributive laws); thus, we obtain a composite pseudomonad

Sind ∘ Lim

on CAT . The main result of our paper is that the quasicategory of all algebras of this pseudomonad is an equational hull of VAR w.r.t. ranked operations. It is easy to identify these algebras with categories K which

(a) have limits and sifted colimits

and

(b) sifted colimits distribute over limits in the sense that the functor

Colim : Sind K → K

(of computation of sifted colimits in K) preserves limits.

Categories satisfying (a) and (b) are called algebraically exact. All varieties are, of course, algebraically exact, but also all essential localizations of varieties are. Recall here the classical result of Roos [R] characterizing all essential localizations of varieties of modules: they are complete abelian categories K with a generator such that

(1) filtered colimits commute with finite limits;

(2) filtered colimits distribute over products, i.e., given filtered diagrams D_{i} : D_{i} → K (i ∈ I), then for the filtered diagram D : ΠD → K, defined by

D(x_{i}) = ΠDx_{i}

we have a canonical isomorphism

colim D ≅ Π_{i∈I}(colim D_{i})

and

(3) regular epimorphisms are product-stable.

All algebraically exact categories are proved below to fulfil (1) – (3).

Open problem Is every complete category with sifted colimits satisfying (1) – (3) algebraically exact ? 1.4. A comparison to the case LFP. In [ALR_{2}] we have studied the analogous question for the non-full embedding U : LFP → CAT . Here LFP is the Gabriel-Ulmer 2-category of all locally finitely presentable categories, all finitary right adjoints, and all natural transformations. The functor U is not (pseudo-)monadic. An equational hull of LFP has been described in [ALR_{2}]. Let us shortly recall the result here. Free completions under filtered colimits form a pseudomonad Ind on CAT which distributes over Lim and thus yields a composite pseudomonad Ind ∘ Lim . Algebras of that pseudomonad form an equational hull of LFP w.r.t. ranked operations. These algebras are called precontinuous categories and they are precisely the categories K such that

(i) K has limits and filtered colimits

and

(ii) filtered colimits distribute over limits in the sense that the functor Colim : Ind K → K preserves limits.

Recall that K is continuous (in the sense of [JJ]) if Colim has a left adjoint. An important tool for this result was a description of a “free LFP category” on a given small category k : it is

Lex (Set^{k}) ,

the category of all accessible functors from Set^{k} to Set preserving finite limits. We have shown in [ALR_{2}] that ranked k-ary operations on LFP are essentially encoded by objects of Lex (Set^{k}). This has raised the following question: are there, for k small, functors preserving finite limits from Set^{k} to Set which are not accessible? More precisely, is the following statement

(∗) every functor Set^{k} → Set , k small, preserving finite limits is accessible consistent with set theory ? This has been answered affirmatively in [AK]. Thus, instead of “ranked operations” we may say “operations of small arity” — well, in some set theory at least.

Now below we make a similar identification by constructing a “free variety” on a small category k : it is

Mod (Set^{k}) ,

the category of all accessible functors from Set^{k} to Set preserving finite products. Here the analogous problem arises which has not been solved so far:

Open problem Is the following statement

(∗∗) every functor Set^{k} → Set , k small, preserving finite products is accessible consistent with set theory ?

1.5. Set-theoretical foundations. In the present paper we are not concerned with set theory beyond the open problem above, but here we want to make clear what (very meager) requirements are needed below. A chosen universe of small sets is assumed satisfying the Axiom of Choice (AC). In a higher universe categories (not assumed locally small in general) live. And when “categories” outside of this universe are considered, they are called quasicategories; example : CAT . Analogously with 2-categories and 2quasicategories. But where a 2-quasicategory is biequivalent to a 2-category (such as LFP, due to Gabriel-Ulmer duality, or VAR, due to the duality of [ALR_{1}]), we call them 2-categories. And we assume that every category is an ∞-filtered union of its small subcategories (i.e., a large union which is λ-filtered for every cardinal λ). All limits and colimits are meant to be small (unless explicitly stated large).

It is an open problem to what extent our results apply without the assumption of AC; or even over an arbitrary base topos.

2. Operations on VAR

2.1. In the present section we introduce operations on the 2-category VAR of varieties, and give some examples of operations and equations among them. In the subsequent sections we will show that the operations introduced here generate all ranked operations on VAR and lead to a description of the equational hull of VAR w.r.t. ranked operations.

Recall from [Law_{1}] the concept of a k-ary operation on a concrete category, i.e. category K equipped by a faithful functor U : K → Set : a k-ary operation ω is a natural transformation ω : U^{k} → U, i.e., to every object K of K an operation-map ω_{K} of arity k on the underlying set UK is assigned in such a way that all mappings Uf, where f : K → L is a morphism of K, preserve the operation maps in the expected sense: Uf · ω_{K} = ω_{L} · (Uf)^{k}. Observe that k can, in general, by any set, but we often want to restrict ourselves to k finite.

By analogy, we might at first want to introduce k-ary operations ω on VAR as natural transformations from U^{k} to U, where

U : VAR → CAT

is the (non-full) inclusion functor; here k is an arbitrary category. Such ω would assign to every variety V an “operation” functor ω_{V} : V^{k} → V in such a way that every algebraically exact functor F : V → W preserves the operation functor in the strict sense, i.e., F · ω_{V} = ω_{W} · F^{k}. However, this is too strict. We have, for example, an important k-ary operation “limits of type k” for any small category k : the operation functor ω_{V} : V^{k} → V assigns to every diagram of type k in V a limit in V. Since algebraically exact functors F : V → W preserve limits, we have a natural isomorphism F · ω_{V} ≅ ω_{W} · F^{k}, but not an equality. We thus have to work with pseudonatural transformations:

2.2. Definition. For every category k the pseudonatural transformations from U^{k} to U are called k-ary operations on VAR. remark. Explicitly, a k-ary operation ω assigns

(i) to every variety V an “operation” functor

ω_{V} : V^{k} ⟶ V

and

(ii) to every algebraically exact functor F : V → W a natural isomorphism ω̂_{F}:

\xymatrix{V^{k} \ar[d]^{\underrightarrow{ω̂_{F}}}_{F^{k}} \ar[r]^{ω_{V}} & V \ar[d]^{F} \\ W^{k} \ar[r]_{ω_{W}} & W}

such that the expected coherence conditions are satisfied: (a) ω̂_{id} = id and (b) if F = F_{2} · F_{1} then ω̂_{F} = (F_{2} ∗ ω̂_{F_{1}}) · (ω̂_{F_{2}} ∗ F_{1}^{k}).

2.3. Examples. of operations on VAR.

(a) Limit operations. For every small category k we have a k-ary operation

k- lim  (1)

of formation of limits of type k in varieties: to every variety V this assigns a functor

ω_{V} : V^{k} ⟶ V

choosing, for every diagram D : k → V, a limit ω_{V}(D) in V. To every algebraically exact functor F : V → W (which, being a right adjoint, preserves limits) it assigns the natural isomorphism

ω̂_{F} : ω_{W} · F^{k} → F · ω_{V}

defined as expected: given a diagram D : k → V, we have two limits of F D in W, viz, ω_{W}(F D) and F (ω_{W}D), and the connecting isomorphism of these two limits is the D-component of ω̂_{F}

In case k is discrete, we use the notation

Π_{k}  (2)

instead of k-lim (for the operation of k-ary products).

(b) Filtered-Colimit Operations. For every small filtered category f we have an f-ary operation

f-colim_{→}  (3)

of formation of filtered colimits of type f in varieties: to every variety V it assigns a functor ω_{V} choosing colimits of diagrams of type f in V. Since algebraically exact functors F : V → W preserve filtered colimits, ω̂_{F} is defined as above: the D-component is the connecting isomorphism of the colimits

ω_{W}(F D) and F (ω_{V}D) of the diagram F D in W .

(c) The Reflexive-Coequalizer Operation. This is one operation of arity r, the finite category given by the following graph

[figure: φ_{1}; 1 •; • 2; ψ; φ_{2}]

and the commutativity conditions

φ_{1}ψ = id = φ_{2}ψ .

We denote by

r-coeq  (4)

the operation ω whose operation functors are

ω_{V} : V^{r} → V , D ⟼ coeq(Dφ_{1}, Dφ_{2}) (for D : r → V) .

Then for every algebraically exact functor F : V → W (which preserves reflexive coequalizers, see [ALR_{2}]) we have the natural isomorphism ω̂_{F} : ω_{W} · F^{k} → F · ω_{V} whose D-component is the following isomorphism:

[figure: coeq(F Dφ_{1}, F Dφ_{2}) = ω_{W}(F D); ≅; F Dφ_{1}; F Dφ_{2}; F (coeq(Dφ_{1}, Dφ_{2})) = F (ω_{W}D)]

2.4. Remark. As mentioned above, in set-based (universal) algebra we can work with k-ary operations for any set k, but in a number of situations we want to restrict ourselves to k finite.

Analogously, we can (and will, in Section 6 below) work with k-ary operations for any category k. However, as already mentioned in the introduction, we have not been able to describe the corresponding category of algebras over CAT . We therefore restrict ourselves here to operations which (a) have small arities k and (b) the operation functors ω_{V}: V^{k} → V are accessible in a coherent sense, i.e., the accessibility rank is the same for all varieties V. Than we say that ω has a rank:

Definition. An operation ω on VAR is called ranked provided that its arity k is small and there exists an infinite regular cardinal λ such that ω_{V} : V^{k} → V preserves λ-filtered colimits for every variety V. (We call λ a rank of ω.)

Examples. (a) The operation k-lim is ranked: any infinite regular cardinal λ such that k has less than λ morphism is a rank of k-lim. In fact, k-limits commute with λ-filtered colimits in Set . Therefore, they commute in each variety V (in fact, in every locally finitely presentable category), i.e., the k-limit functor ω_{V} : V^{k} → V preserve λ-filtered colimits.

(b) The operations k-colim_{→} and r-coeq have rank ω since colimits commute with colimits.

Remark. As stated in the Introduction (1.4) we do not know at this moment whether it is consistent with set theory to assume that every operation of small arity on VAR is ranked. Let us remark that, however, this statement is not true absolutely: in any theory such that Set contains a proper class of measurable cardinals J. Reiterman has constructed in [Re] a functor F : Set → Set which is not accessible but preserves finite limits. This functor defines a non-ranked unary operation ω on VAR as follows:

Given a variety V = Mod T (where T is an algebraic theory for V) let ω_{V} : V → V be the functor which precomposes every model M : T → Set with F, i.e., ω_{V} : M ⟼ MF. Since F preserves finite products, MF is a model, and it is easy to see that ω_{V} is indeed an operation of arity 1 on VAR. It is not ranked because ω_{Set} is not accessible.

2.5. Composed operations. Besides operations as described above we want to work with composed operations, e.g., a limit of filtered colimits. Recall that in the classical case mentioned above the discovery of [Law_{1}] was that one can work with natural transformations

U^{k} → U^{n}

(which, since U^{n} = U × U × ⋯ × U, are just n-tuples of k-ary operations). This makes the task of composing operations very easy: they were just composites of natural transformations between powers of U.

Analogously in our case of U : VAR → CAT : we work with n-tuples of k-ary operations (where n and k are categories), which are pseudonatural transformations

ω : U^{k} → U^{n}

2.6. Examples. (a) Morphisms of operations. Let n = → (the chain of length 1). A pseudonatural transformation

ω : U^{k} → U^{→}

consists of two k-ary operations

ω_{1}, ω_{2} : U^{k} → U

obtained by composing ω with the obvious natural transformation U^{d}, U^{c} : U^{→} → U. (Here d, c : 1 → (→) are the domain and codomain functors, respectively.) Plus a modification

ω_{1} ⇒ ω_{2}

which is formed by the values of ω_{V} : V^{k} → V^{→} at the unique nonidentity arrow of →. Thus, the pseudonatural transformation ω is what we will call a morphism of k-ary operations from ω_{1} to ω_{2}. Notation: ω : ω_{1} ⇒ ω_{2}. The constant functor t : (→) → 1 gives identity morphisms U^{k} → U ⟶^{U^{t}} U^{→}.

(b) Composing morphisms. Let n = →→ (the chain of length 2). A pseudonatural transformation

ω : U^{k} ⟶ U^{→→}

consists of three k-ary operations ω_{1}, ω_{2}, ω_{3} : U^{k} → U (obtained by composing ω with the three canonical projections U^{→→} → U) together with three modifications u : ω_{1} ⇒ ω_{2}, v : ω_{2} ⇒ ω_{3} and w = vu : ω_{1} ⇒ ω_{3} corresponding to the three non-identity morphisms of →→. Thus, the pseudonatural transformation ω is what we will call a composite w of morphisms u and v of k-ary operations.

(c) Kernel pair is an example of an r-tuple of operations of arity →, where r denotes the category of 2.3 (c). More precisely, we have a pseudonatural transformation

ker : U^{→} → U^{r}

whose components ker_{V} : V^{→} → V^{r} assign to every morphism of V a kernel pair. Given an algebraically exact functor F : V → W then F preserves (limits thus) kernel pairs which yields a unique invertible 2-cell k̂er_{F}: F^{r} · ker_{v} → ker_{w} · F^{→}.

(d) Trivial operations. As in any category of “two-dimensional” algebras, we have a trivial n-tuple of k-ary operations associated with an arbitrary functor H : n → k: to every variety V assign the functor V^{H} : V^{k} → V^{n} of precomposition with H.

2.7. Equations. between k-ary operations on VAR. We want to investigate an equational hull of VAR. What do we understand as equation ω ≈ ω′ (for operations ω, ω′ : U^{k} → U) ? Certainly not the strict equality: ω_{V} = ω′_{V} for all varieties V. We of course mean the non-strict variant of natural isomorphisms ω_{V} ⟶^{≅} ω′_{W} satisfying the appropriate coherence conditions. Our concept of morphism and composition above makes this quite formal as follows:

2.8. Definition. By an equation between k-ary operations on VAR is meant an invertible morphism ω_{1} ⇒ ω_{2}.

2.9. Examples of equations. (1) Filtered colimits commute with finite limits. This is a property that all varieties have. The commutation of f-colim_{→} (f small, filtered) with k-lim (k finite) can be expressed by an equation as follows: we can form an operation of arity f × k by composing the k-tuple

(f-colim_{→})^{k} : (V^{f})^{k} → V^{k}

with k-lim. And another operation of the same arity f × k by composing the f-tuple

(k- lim)^{f} : (V^{k})^{f} → V^{f}

with f-lim. The fact that f-colimits commute with k-limits is expressed by the following equation

(k- lim) · (f-colim_{→})^{k} ≈ (f-colim_{→}) · (k- lim)^{f}  (f filtered, k finite)  (E1)

since the required naturality conditions are easy to verify.

(2) Filtered colimits distribute over (infinite) products. This, less famous, property of all varieties (in fact, of all locally finitely presentable categories) has been observed already in [AGV]: given a set D_{i} : f_{i} → K (i ∈ k) of filtered diagrams in K, denote by D : Π_{i∈k}f_{i} → K the diagram obtained by forming products in K:

(d_{i})_{i∈k} ⟼ Dd_{i} .

then the canonical morphism colim D → Π_{i∈k} colim D_{i} is invertible.

To express this as an equation, denote by f the product of the categories f_{i} (for i ∈ k) and by g their coproduct; observe that f is filtered (due to the Axiom of Choice).

The passage from (D_{i})_{i∈k} to Π colim D_{i} is the composite of the product operation Π_{k} : V^{k} → V (k considered as a discrete category) with the product of the operations f_{i}-colim:

V^{g} ≅ Π_{i∈k}V^{f_{i}} ⟶^{Π(f_{i}-colim_{→})} V^{k} ⟶^{Π_{k}} V

And the passage to colim D is expressed by using the trivial operations o_{i} : V^{f_{i}} → V^{f} corresponding to the i-th projection of f, and composing them with f-colim_{→} : V^{f} → V:

V^{g} ≅ Π_{i∈k}V^{f_{i}} ⟶^{(o_{i})_{i∈k}} V^{f} ⟶^{f-colim_{→}} V

This gives an equation expressing distributivity of filtered colimits over products as follows

Π_{k} · Π_{i∈k}(f_{i}-colim_{→}) ≈ ( Π_{i∈k}f_{i}-colim_{→}) · (o_{i})_{i∈k}  (k a set, f_{i} filtered for i ∈ k) . (E2)

Again, the naturality conditions for the above canonical morphisms are easy to verify.

(3) Regular epimorphisms are product-stable. That is, given regular epimorphisms e_{i} : A_{i} → B_{i} (i ∈ k, k a set) in a variety, the product morphism

Π_{i∈k}e_{i} : Π_{i∈k}A_{i} → Π_{i∈k}B_{i}

is a regular epimorphism. The reason why this holds in every variety is that products commute with coequalizers of equivalence relations: form a kernel pair E_{i} ⇉ A_{i} of e_{i}, then a product Π E_{i} ⇉ ΠA_{i} yields a kernel pair of Π_{i∈k}e_{i} whose coequalizer is Π_{i∈k}e_{i}.

To express this as an equation, combine the above operations Π_{k} : U^{k} → U, coeq : U^{r} → U and ker : U^{→} → U^{r} as follows: we first multiply e_{i}, then form kernel pair and finally a coequalizer:

(U^{k})^{→} ⟶^{(Π_{k})^{→}} U^{→} \underrightarrow{ker} U^{r} \underrightarrow{coeq} U .

This is an operation of arity (→)×k on VAR. Or we first form kernel pairs, then multiply and then form a coequalizer:

(U^{→})^{k} \underrightarrow{ker^{k}} (U^{r})^{k} ≅ (U^{k})^{r} ⟶^{(Π_{k})^{r}} U^{r} \underrightarrow{coeq} U .

Thus, product-stability of regular epimorphisms is expressed by the following equation

coeq · ker · (Π_{k})^{→} ≈ coeq · (Π_{k})^{r} · ker^{k} (k a set) .  (E3)

(4) There is a collection (E4) of equations which stem from the general fact that limits commute with limits, and colimits commute with colimits. Remark. We will later see our reasons for believing it possible that

(1) there are no other ranked operations on VAR than those obtained by composing the three types above: k-lim, f-colim_{→} and coeq,

and

(2) there are no other equations between ranked operations on VAR than those which follow from (E1) – (E4).

We will see that the process of composition of the three types of operations has a particularly simple structure due to the fact, proved below, that both filtered colimits and reflexive coequalizers distribute over limits in varieties.

3. Limits and Sifted colimits

In the present section we consider two pseudomonads on CAT : Lim , the pseudomonad of free limit-completions of categories, and Sind , the pseudomonad of free completions under sifted colimits. The first one is well-known and the second one is closely related to Grothendieck’s free completion Ind under filtered colimits. The main result is that

Sind distributes over Lim ,

which implies, as proved in [M_{3}], that the composite Sind ∘ Lim obtains a structure of a pseudomonad on CAT . In subsequent sections we show that algebras of that pseudomonad form an equational hull of VAR with respect to ranked operations.

3.1. Pseudomonads and Algebras. (1) Recall the concept of a pseudomonad on a 2-category K, as introduced by B. Day and R. Street [DS]; we use the notation of F. Marmolejo [M_{2}]. A pseudomonad 𝔻 = (D, d, m, η, β, μ) consists of a bifunctor

D : K → K

with 1-cells

d : id_{K} → D and m : D · D → D

together with invertible 2-cells

\xymatrix{D \ar[r]^{dD} \ar[dr]_{Id_{D}} & DD \ar[d]_{⇐_{β}}_{m} & D \ar[l]^{⇐_{η}}_{Dd} \ar[dl]^{Id_{D}} & DDD \ar[r]_{⇐_{η}}^{Dm} \ar[d]_{mD} & DD \ar[d]^{m} \\  & D &  & DD \ar[r]_{m} & D ,}

such that the following two equalities are satisfied:

[figure: DDDD; ⇐^{Dμ}; ⇐^{μD}; mDD; DmD; DDm; DDD; Dm; DDD; ⇐^{μ}; Dm; mD; DD =; m; DDD; mD; DD; m; D; DDDD; ⇐^{m{−1 \atop m}}; mDD; DDm; DDD; ⇐^{μ}; mD; Dm; DD; m; DDD; ⇐^{μ}; Dm; mD; DD; m; DD; m; D ,]

\xymatrix{ &  & DD \ar[dr]_{μ ⇓}^{m} &  &  & DDD \ar[dr]_{Dβ ⇓}^{Dm} \\ DD \ar[r]^{DdD} & DDD \ar[ur]^{Dm} \ar[dr]_{mD} &  & D & = DD \ar[ur]^{DdD} \ar[dr]_{DdD} \ar[rr] &  & DD \ar[r]^{m} & D . \\  &  & DD \ar@{-->}[ur]_{m} &  &  & DDD \ar[ur]^{ηD ⇓}_{mD}}

(2) Recall further the concept of an algebra for a pseudomonad 𝔻: it is a quadruple

(X, x, ψ, χ)

consisting of an object (0-cell) X,

a morphism (1-cell) x : DX → X and

invertible 2-cells

[figure: X; dX; Id_{X}; DX; ⇐^{ψ}; x; X; DDX; ⇐^{χ}; Dx; mX; DX; x; DX; x; X ,]

This data must satisfy the following two equations

[figure: DDDX; ⇐^{Dχ}; ⇐^{μX}; mDX; DmX; DDx; DDX; Dx; DDX; ⇐^{χ}; Dx; mX; DX =; x; DDX; mX; DX; x; X; DDDX; ⇐^{m{−1 \atop x}}; mDX; DDx; DDX; ⇐^{χ}; mX; Dx; DX; x; DDX; ⇐^{χ}; Dx; mX; DX; x; DX; x; X ,]

\xymatrix{ &  & DX \ar[dr]_{χ ⇓}^{x} &  &  & DDX \ar[dr]_{Dψ ⇓}^{Dx} \\ DX \ar[r]^{DdX} & DDX \ar[ur]^{Dx} \ar[dr]_{mX} &  & X & = DX \ar[ur]^{DdX} \ar[dr]_{DdX} \ar[rr] &  & DX \ar[r]^{x} & X . \\  &  & DX \ar@{-->}[ur]_{x} &  &  & DDX \ar[ur]^{ηX ⇓}_{mX}}

We denote by

K^{𝔻}

the 2-category of 𝔻-algebras. Its 1-cells, called homomorphisms, from (X, x, ψ, χ) to (Z, z, ξ, θ) are pairs (h, ϱ) where

h : X → Z

is a 1-cell of K and

\xymatrix{DX \ar[r]_{⇐^{ρ}}^{Dh} \ar[d]_{x} & DZ \ar[d]^{x} \\ X \ar[r]_{h} & Z}

is an invertible 2-cell, such that the following two equations are satisfied.

\xymatrix{X \ar[r]^{dX} \ar[dr]_{Id_{X}} & DX \ar[d]^{⇐^{ρ}}^{x}_{⇐^{ψ}} \ar[r]^{Dh} & DZ \ar[d]^{z} &  &  & DX \ar[dr]^{Dh} \\  & X \ar[r]_{h} & Z & = & X \ar[ur]_{d_{h} ⇓}^{dX} \ar[dr]_{h} &  & DZ \ar[dr]^{z}_{ζ ⇓} \\  &  &  &  &  & Z \ar[rr]_{Id_{Z}} \ar[ur]^{dZ} &  & Z}

\xymatrix{ & DDX \ar[dl]^{⇐^{χ}}_{mX} \ar[dr]^{Dx} \ar[rr]^{DDh} &  & DDZ \ar[dr]_{⇐^{Dρ}}^{Dz} &  &  &  & DDX \ar[dl]^{⇐^{m{−1 \atop h}}}_{mX} \ar[rr]^{DDh} &  & DDZ \ar[dl]^{⇐^{θ}}_{mZ} \ar[dr]^{Dz} \\ DX \ar[dr]_{x} &  & DX \ar[dl]^{x} \ar[rr]^{Dh} &  & DZ \ar[dl]_{⇐^{ρ}}^{z} & = & DX \ar[dr]^{⇐^{ρ}}_{x} \ar[rr]_{Dh} &  & DZ \ar[dr]_{z} &  & DZ \ar[dl]^{z} \\  & X \ar[rr]_{h} &  & Z &  &  &  & X \ar[rr]_{h} &  & Z .}

The 2-cells of K^{𝔻} are defined as follows:

Given homomorphisms (h, ρ), (h′, ρ′) : (X, x, ψ, χ) ⟶ (Z, z, ζ, θ), a 2-cell

ξ : (h, ρ) ⟶ (h′, ρ′)

is a 2-cell ξ : h ⟶ h′ of K such that (ξ ∘ x) · ρ = ρ′ · (z ∘ Dξ). Vertical composition is the obvious one.

Horizontal composition: for (h, ρ) : (ψ, χ) ⟶ (ζ, θ) and (k, π) : (ζ, θ) ⟶ (τ, σ) we define (k, π) ∘ (h, ρ) = (k ∘ h, (k ∘ ρ) · (π ∘ Dh)).

3.2. Example: Free limit completion Lim . This is a well-known pseudomonad on CAT of freely completing categories under limits. In fact, A. Kock has described it as a strict 2-monad in [K]. Recall that for small categories we have

Lim K = (Set^{K})^{op}.

The pseudomonad Lim is a co-KZ-doctrine (see [K], [M_{1}]), i.e.

μ_{K}^{Lim} ⊢ Lim η_{K}^{Lim}  (5)

for every category K.

If K is locally small then Lim K is well-known to be equivalent to the closure of representable functors in (Set^{K})^{op} under limits.

3.3. Sifted colimits play a very analogous role in the theory of varieties to the role of filtered colimits in the theory of locally finitely presentable categories, see [ALR_{1}].

The following has been introduced by C. Lair [L] under the name tamisante:

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

Colimits of diagrams with sifted domains are called sifted colimits.

3.4. Example. (1) Filtered categories are sifted.

(2) The category r of 2.3 (c) is sifted – that is, reflexive coequalizers are sifted colimits.

(3) Every small category with finite coproducts is sifted, see [AR_{1}].

3.5. Lemma. (see [ALR_{1}]) A functor between varieties is algebraically exact iff it preserves limits and sifted colimits.

Remark. For categories other than varieties we extend the terminology and call a functor algebraically exact if it preserves limits and sifted colimits. Observe that due to 3.4 (2) every algebraically exact functor is exact.

3.6. Example. of an operation on VAR: for every small sifted category s we can form the operation

s-colim

of colimits of type s, analogously to 2.3 (b) above (and generalizing 2.3 (c), of course).

3.7. Example: Free completion Sind under sifted colimits. This is a pseudomonad on CAT quite analogous to Grothendieck’s free completion Ind K under filtered colimits. The latter can be identified, for locally small categories K, with the category of all flat presheaves in Set^{K^{op}} (i.e., a closure of representable functors under filtered colimits in Set^{K^{op}}), with the universal map ηInd_{K} : K → Ind K being a codomain restriction of the Yoneda embedding Y_{K} : K → Set^{K^{op}}. And whenever K is small and has finite colimits, then

Ind K = Lex K^{op}

is the category of all presheaves preserving finite limits. In general Ind K can be, for any category K, described as a suitable category of all filtered diagrams in K, see [JJ].

Quite analogously, we can introduce a free completion

η_{K}^{Sind} : K → Sind K

of any category K under sifted colimits.

3.8. Lemma. (1) For every locally small category K, Sind K can be identified with the category of all presheaves in Set^{K^{op}} which are sifted colimits of representables (where η_{K}^{Sind} is a codomain restriction of Y_{K}).

(2) If K^{op} is locally presentable, then Sind K can be identified with the category of all accessible presheaves in Set^{K^{op}} preserving finite products.

Proof. The proof of (1) for K small has been performed in [AR_{1}], the generalization to K locally small is straightforward.

For (2), observe that a sifted colimit of representables preserves finite products (since they commute in Set^{K^{op}} with sifted colimits) and is accessible. Conversely, given a λaccessible functor F : K^{op} → Set where K^{op} is locally λ-presentable, then in the usual diagram El(F) of elements of F (i.e., pairs (K, x) with K ∈ obj K and x ∈ F K) all objects (K, x) with K λ-presentable obviously form a cofinal, essentially small subdiagram El_{λ}(F). If F preserves finite products, then El(F) has finite coproducts, and a closure of El_{λ}(F) under finite coproducts yields an essentially small diagram of representables with colimit object F; that diagram is sifted by 3.4 (3).

3.9. Lemma. ([AR_{1}]) For every algebraic theory K, Sind K^{op} is a variety. Conversely, every variety is a free sifted-colimit completion of the dual of any of its algebraic theories.

3.10. Sifted Colimits Distribute Over Limits. A crucial fact that enables us to describe an equational hull of VAR w.r.t. ranked operations is that the 2-monad Sind distributes over the 2-monad Lim . Recall that for “ordinary” (1-dimensional) monads 𝕋 and 𝕊 over a category K, a distributive law of J. Beck [B] is, equivalently, one of the following structures:

(i) a natural transformation from S ∘ T to T ∘ S compatible with the units and multiplications of 𝕋 and 𝕊,

or

(ii) a lifting 𝕋̂ of the monad 𝕋 to the category K^{𝕊} of algebras of 𝕊.

Given (i) or (ii), the composite T ∘ S obtains a structure of a monad, say 𝕋 ∘ 𝕊, whose category of algebras is equivalent to the category of algebras of the lifted monad 𝕋̂, i.e.,

K^{𝕋∘𝕊} is equivalent to (K^{𝕊})𝕋̂ over K .

We now want to apply all this to 𝕋 = Sind and 𝕊 = Lim : we prove below that Sind lifts to the quasicategory CAT^{Lim} of algebras of Lim (= the quasicategory of all complete categories and functors preserving limits). And we would like to conclude that the composite Sind ∘ Lim is a pseudomonad over CAT whose algebras are precisely the algebras of Sind lifted to complete categories.

Distributive laws for pseudomonads have been studied by F. Marmolejo in [M_{2}] and [M_{3}]. We want to apply his results to a distributive law of Sind (a KZ-doctrine) over Lim (a co-KZ-doctrine). In that case there exists at most one distributive law, as proved in [M_{2}], so that we can formulate the result by saying that

Sind distributes over Lim .

The form we prove this is by exhibiting a lifting of Sind from CAT to CAT^{Lim} :

3.11. Theorem. (Sind distributes over Lim )

(1) For every complete category K the category Sind K is complete.

(2) For every functor F : K → L preserving limits, where K and L are complete, the functor Sind F : Sind K → Sind L also preserves limits.

(3) Both η_{K}^{Sind} and μ_{K}^{Sind} preserve limits (for any category K).

Proof. I. We first prove the statements (1) and (2) for the case that K = Lim K_{0} is a free completion of a category K_{0} under limits, and analogously L = Lim L_{0}, and F = Lim F_{0} for some F_{0} : K_{0} → L_{0}.

(I.A) Suppose that K_{0} and L_{0} are small. Then Lim K_{0} ≅ (Set^{K_{0}})^{op} is locally presentable, therefore, Sind K is the category of all accessible functors in Set^{K^{op}} preserving finite products. Having a diagram D : D → Sind K, there is a cardinal λ such that D has less than λ morphisms and, for each object d ∈ D, the functor Dd is λ-accessible. Since limits over categories having less than λ morphisms commute in Set with λ-filtered colimits, lim D is λ-accessible. We have proved that limits of accessible functors from K^{op} to Set are accessible. Consequently, Sind K is closed under limits in Set^{K^{op}}, see 3.7, thus, Sind K is complete.

For every functor F_{0} : K_{0} → L_{0} the functor Lim F_{0} : (Set^{K_{0}})^{op} → (Set^{L_{0}})^{op} is right adjoint to (Set^{F_{0}})^{op} : (Set^{L_{0}})^{op} → (Set^{K_{0}})^{op}. Sind is a pseudofunctor, thus, Sind (Lim F_{0}) is a right adjoint to Sind (Set^{F_{0}})^{op}; consequently, Sind F = Sind (Lim F_{0}) preserves limits.

(I.B) Let K_{0} and L_{0} be arbitrary categories. Express K_{0} as an ∞-filtered colimit of small categories K_{0i} ⊆ K_{0} (i ∈ I), see Introduction, 1.5. The connecting morphisms of that colimit are the inclusions E_{ij} : K_{0i} ↪ K_{0j} for i ≤ j. Both Lim and Sind obviously preserve ∞-filtered colimits (in fact, any free completion functor dealing with small diagrams does). Thus,

Sind (Lim K_{0}) = colim_{i∈I} Sind (Lim K_{0i})

is an ∞-filtered colimit of categories Sind (Lim K_{0i}) which are complete, due to I.A, with the connecting functors Sind (Lim E_{ij}) preserving limits, also by I.A. It follows that Sind (Lim K_{0}) is complete.

Analogously do we derive that Sind (Lim F_{0}) preserves limits: express K_{0} and L_{0} as ∞-filtered colimits of small subcategories

K_{0i} ⊆ K_{0} and L_{0i} ⊆ L_{0} (i ∈ I)

such that F_{0} restricts to

F_{0i} : K_{0i} → L_{0i} (i ∈ I) .

Then F_{0} = colim_{i∈I}F_{0i} implies Sind (Lim F_{0}) = colim_{i∈I} Sind (Lim F_{0i}). The latter is an

∞-filtered colimit of functors Sind (Lim F_{0i}) which, by I.A, preserve limits. And the connecting functors of that colimit also preserve limits. Consequently, Sind (Lim F_{0}) preserves limits.

II. We prove (1) generally: let K be complete, and let

L_{K} : Lim K → K

be a functor of computation of limits in K. Then

L_{K}η_{K}^{Lim} ≅ id and η_{K}^{Lim} ⊣ L_{K} .

Since Sind is a pseudofunctor, we conclude

Sind L_{K} Sind η_{K}^{Lim} ≅ id and Sind η_{K}^{Lim} ⊣ Sind L_{K} .

Thus a limit of a diagram D : D → Sind K can be computed from a limit of Sind η_{K}^{Lim} ·D in the (complete, see I.) category Sind Lim K as follows:

Sind L_{K}(lim[Sind η_{K}^{Lim} · D])  (6)
≅ lim[Sind L_{K} · Sind η_{K}^{Lim} · D]
≅ lim D .

Analogously we prove (2) generally: let F : K → L preserve limits, and let

L_{K} : Lim K → K and L_{L} : Lim L → L

be as above. Since F preserves limit, we have a natural isomorphism

\xymatrix{Lim K \ar[d]^{⇒^{≅}}_{L_{K}} \ar[r]^{Lim F} & Lim L \ar[d]^{L_{L}} \\ K \ar[r]_{F} & L}

This yields a natural isomorphism

\xymatrix{Sind (Lim K) \ar[d]^{⇒^{≅}}_{Sind L_{K}} \ar[r]^{Sind (Lim F)} & Sind (Lim L) \ar[d]^{Sind (L_{L})} \\ Sind K \ar[r]_{Sind F} & Sind L}

Since Sind L_{L} and Sind (Lim F) preserve limits, by I., and limits in Sind K are computed as above, see (6), we conclude that Sind F preserves limits:

Sind F (lim D) ≅ Sind F ( Sind L_{K}(lim[Sind η_{K}^{Lim} · D]))
≅ Sind L_{L} · Sind (Lim F)( lim[Sind η_{K}^{Lim} · D])
≅ lim ( Sind L_{L} · Sind (Lim F) · Sind η_{K}^{Lim} · D)
≅ lim(Sind L_{L} · Sind η_{L}^{Lim} · Sind F · D)
≅ lim(Sind F · D) .

III. The proof of (3) is clear: if K is (locally) small then η_{K}^{Sind} preserves limits because it is a codomain restriction of the Yoneda embedding Y_{K} : K → Set^{K^{op}} and the category Sind K is closed under limits in Set^{K^{op}} (since it contains all representable functors). In a general case, we express K as an ∞-filtered colimit of small subcategories.

And μ_{K}^{Sind} preserves limits because it is a right adjoint, see 3.2.

3.12. Corollary. Sind ∘ Lim is a pseudomonad over CAT whose quasicategory of algebras is equivalent to the quasicategory of algebras of { \atop Sind} . The latter is the lifting of Sind to the quasicategory of complete categories.

In fact, given pseudomonads 𝕊 and 𝕋 on a 2-category K, then a lifting 𝕊̂ of 𝕊 to the category K^{𝕋} of algebras for 𝕋 is equivalent to providing a pseudomonad structure 𝕊 ∘ 𝕋 of the corresponding composite endofunctor of K – see [M_{2}]. And the category of algebras for 𝕊 ∘ 𝕋 is biequivalent to that of 𝕊̂ as proved in [M_{3}].

4. Equational Hull of VAR

4.1. We are going to describe an equational hull of VAR w.r.t. all operations with rank. Before proceeding formally, let us informally say that the basic observation is that for every small category k we can almost form a “free variety” on k: it is the category

Mod (Set^{k})

of all accessible functors from Set^{k} to Set preserving finite products. Well, that category is not a variety (unless k = ∅) because it does not have a small regular generator. But we have a canonical embedding

ev : k ⟶ Mod (Set^{k})

assigning to every object x of k the evaluation-at-x functor

ev(x) : Set^{k} ⟶ Set .

And ev has the following universal property:

Let V be a variety, say V = Mod T for a (small) algebraic theory T . We have natural bijections as follows:

k

H

[figure]

V = Mod T

an arbitrary functor

k × T

H′

[figure]

Set preserves finite products in the 2nd coordinate

T H′′ [figure]

Set_{k}

preserves finite products

Mod (Set^{k})

Mod H′′

[figure]

Mod T = V

algebraically exact functor

Let us explain the last step, in which Mod H′′ is the functor F ⟼ F · H′′:

(1) The functor Mod H′′ is algebraically exact.

In fact, it is a domain-codomain restriction of the functor

− · H′′ : Set^{Set^{k}} → Set^{T}

(which, obviously, preserves limits and colimits). Now Mod T is clearly closed under limits and sifted colimits in Set^{T} – recall that sifted colimits commute in Set with finite products, thus, they commute with them in Set^{T} too. And Mod (Set^{k}) is closed in Set^{Set^{k}} under limits and sifted colimits. Thus our restricted functor preserves limits and sifted colimits.

(2) Every algebraically exact functor F : Mod (Set^{k}) → V is naturally equivalent to Mod H′′ where H = F · ev. In fact, every object of Mod (Set^{k}), i.e., accessible, finiteproduct preserving functor D : Set^{k} → Set , is a sifted colimit of representables, see 3.8; say

D = colim_{i∈I}Set^{k}(X_{i}, −) (I small, sifted) .

And every X_{i} ∈ Set^{k} is, of course, a small colimit of representables

X_{i} = colim_{j∈J_{i}}k(x_{ij}, −) (J_{i} small) .

Since ev(x_{i,j}) ≅ Set^{k}(k(x_{ij}, −), −), we obtain

D ≅ colim_{i∈I} lim_{j∈J} Set^{k}(k(x_{i,j}, −), −)

≅ colim_{i∈I} lim_{j∈J_{i}} ev(x_{ij}) .

Since F preserves sifted colimits and limits, we conclude

F D ≅ colim_{i∈I} lim_{j∈J_{i}} Hx_{ij} .

It is easy to verify the same formula for Mod H′′:

Mod H′′D ≅ colim_{i∈I} lim_{j∈J_{i}} Hx_{ij} .

Consequently, F ≅ Mod H′′.

4.2. Corollary. Ranked k-ary operations on VAR are encoded by Mod (Set^{k}) as follows:

(i) every object D of Mod (Set^{k}) defines a k-ary operation

D̂ : U^{k} → U

whose components are given by

D̂_{V} : V^{k} → V : H ⟼ Mod H′′(D) (H : k → V)

(ii) every morphism d : D_{1} → D_{2} of Mod (Set^{k}) defines a morphism

d̂: D̂_{1} ⇒ D̂_{2}

of k-ary operations, i.e., a pseudonatural transformation

d̂: U^{k} → U^{→}

whose components are

d̂_{V} : (D̂_{1})_{V} → (D̂_{2})_{V} , H ⟼ (D_{1}H′′ ⟶^{dH′′})D_{2}H′′

(iii) Every k-ary operation of rank is equal (in the sense of 2.7) to some D̂ for D ∈ Mod (Set^{k}). That is, given

ω : U^{k} → U of rank λ

we can find D with ω ≈ D̂.

The last statement would be trivial if V = Mod (Set^{k}) would be a variety: then we could evaluate ω_{V} : V^{k} → V in ev ∈ V^{k} and obtain D = ω_{V}(ev). The equality ω ≈ D̂ then follows from the fact that for every H ∈ V^{k} the functor −.H′′ : Mod (Set^{k}) → V, being algebraically exact, must preserve ω.

To overcome the difficulty, denote by

E_{λ} : Set _{λ}^{k} → Set^{k} (λ ∈ Card)

the inclusion functor of the subcategory of all functors in Set^{k} preserving λ-filtered colimits. Since each Set _{λ}^{k} is essentially small, V_{λ} = Mod (Set _{λ}^{k}) is a variety. And Mod (Set^{k}) is a limit of these varieties, with a limit cone

Mod E_{λ} : Mod (Set^{k}) → Mod (Set _{λ}^{k})

formed by algebraically exact functors (and the connecting morphisms Mod (Set _{λ}^{k}) → Mod (Set _{μ}^{k}) for μ ≤ λ are all algebraically exact). We obtain objects

D_{λ} = ω_{V_{λ}}(Mod E_{λ} · ev) in V_{λ} ,

and if ω has a rank λ_{0}, then in fact D_{λ} = D_{λ_{0}} for all λ ≥ λ_{0}, and ω ≈ D̂_{λ_{0}}.

4.3. Remark. Observe that for small categories k,

(Set^{k})^{op} ≅ Lim k

is a free limit-completion, and since this category is locally presentable, its free completion under sifted colimits is precisely Mod (−), see 3.7:

Mod (Set^{k}) ≅ Sind (Lim k) k small .

Thus we see that ”free varieties” are precisely the free algebras of the composite pseudomonad Sind ∘ Lim of Section 3. Moreover, for k small, all ranked k-ary operations are encoded by Sind (Lim k), thus, they are the sifted-colimits operations applied to the limit operations. It follows that the appropriate homomorphisms are the functors preserving limits and sifted colimits – but these are precisely the homomorphisms (1-cells) of the 2quasicategory of algebras of Sind ∘ Lim . All this proves that the algebras of Sind ∘ Lim form an equational hull of VAR w.r.t. ranked operations. Well, except that, strictly speaking, we have not verified that this equational hull is presented by a pseudomonad; this will be done in the last section, where we introduce that pseudomonad as the ”ranked core” of the pseudomonad representing the equational hull w.r.t. all operations. But modulo this result, we conclude the following

4.4. Corollary. The 2-quasicategory of algebras of the pseudomonad Sind ∘ Lim is an equational hull of VAR w.r.t. all operations with rank.

We are now ready to describe the algebras of the pseudomonad Sind ∘ Lim :

4.5. Definition. A category K is called algebraically exact if it is complete, has sifted colimits, and these distribute over limits in the following sense: the functor Colim : Sind K → K computing sifted colimits in K preserves limits.

4.6. Remark. (1) A more precise definition of Colim is: this is the essentially unique functor preserving sifted colimits with

Colim ·η_{K} = Ind_{K} .

(2) It is evident that algebraic exactness is precisely the property of being an algebra of the lifting of Sind to the 2-quasicategory of all complete categories. Since the latter is the 2-quasicategory of all algebras of Lim , we have just described the algebras of Sind ∘ Lim , see 3.12.

(3) We denote by ALG

the 2-quasicategory of all algebraically exact categories, all algebraically exact functors (i.e., functors preserving limits and sifted colimits) and all natural transformations.

This is biequivalent to the quasicategory of all algebras of the composite pseudomonad Sind ∘ Lim .

5. Properties of Algebraically Exact Categories

5.1. Theorem. Every algebraically exact category K has the following properties:

(a) K is complete,

(b) K is exact,

(c) filtered colimits commute in K with finite products,

(d) filtered colimits distribute in K over all products (see 2.8 (2)) and

(e) regular epimorphisms in K are product-stable.

Proof. Assume at first that K is a locally small algebraically exact category. The category Set fulfills (a)-(e) and therefore so does Set^{K^{op}}. Following 3.11, Sind K is closed under limits and sifted colimits in Set^{K^{op}} (see part II. of the proof of 3.11). Therefore Sind K satisfies (a)-(e) as well. Since Colim is left adjoint to η_{K}, K is a reflective subcategory of Sind K and the reflector Colim preserves all limits. Hence K satisfies (a)-(e) too.

For general algebraically exact categories K it is sufficient to prove that they are ∞- filtered colimits of locally small algebraically exact categories with connecting functors algebraically exact. This follows from 1.5 and the observation that given a small subcategory A of K, then the closure of A under limits and filtered colimits in K (with transfinitely many iterations) is locally small and algebraically exact.

5.2. Open problem. Is every category with properties (a)-(e) above algebraically exact?

5.3. Examples. (1) Every variety is algebraically exact. In fact, this follows from 3.8 and the next example:

(2) Every complete category of the form Sind K is algebraically exact. In fact, here Colim ≅ μ_{K}^{Sind} preserves limits by 3.11 (3).

(3) Torsion-free abelian groups fulfill (a)-(d) above but not (e), thus they do not form an algebraically exact category.

(4) Essential localizations of varieties are algebraically exact (see [ARV] for a description of these categories). In more generality:

5.4. Proposition. Let K be an algebraically exact category. Then all complete localizations of K (i.e. full reflective subcategories whose reflector preserves limits) are algebraically exact.

Proof. Let E : L ↪ K be a complete localization with a reflector R : K → L; thus

R ⊣ E and RE = id .

Each of the following three functors

Sind L ⟶^{Sind E} Sind K ⟶^{Colim} K ⟶^{R} L  (7)

preserves sifted colimits. Hence the composite functor of (7) preserves sifted colimits. We will show that this composite is a functor computing sifted colimits in L – for this, it is only necessary to observe that η_{L}^{Sind} composed with (7) yields the identity on L:

(R · Colim · Sind E) · η_{L}^{Sind}
≅ R · Colim ·η_{K}^{Sind} · E
≅ R · E
≅ id .

Thus, we are to prove that the composite functor (7) preserves limits: Sind E preserves limits by 3.11, Colim does by assumption on K and R does by assumption on L.

5.5. Corollary. Essential localizations of the category R-Mod of right R-modules are algebraically exact categories for every ring R.

Those essential localizations have been described in [R] as follows: Let I be an idempotent ideal of R. Let K_{I} be the full subcategory of R-Mod formed by all modules orthogonal to the embedding I ↪ R. Then K_{I} is an essential localization of R-Mod , and there are no other (up to equivalence of categories).

More about algebraically exact categories can be found in [ARV].

6. A full equational hull of VAR

6.1. In the present section we exhibit a pseudomonad 𝔻^{∗} on CAT , such that the category of algebras of 𝔻^{∗} is an equational hull of VAR w.r.t. all operations. Here, arities are not assumed to be small (nor the operations to have rank, of course). This is based on the formation of dual monads on the cartesian closed 2-quasicategory CAT . The whole procedure is completely analogous to that used in [ALR_{2}] to describe the full equational hull of LFP. We will first recall, as we have already done in [ALR_{2}], the concept of a dual monad on a cartesian closed 2-category from [Law_{2}].

6.2. Enriched Monads in CCC. By an enriched monad 𝔻 over a cartesian closed category C we understand an enriched functor D : C → C together with enriched natural transformations η : 1_{C} → D and μ : DD → D satisfying the usual monad axioms. The category

C^{𝔻}

of (strict) algebras and homomorphisms is then also enriched over C: the internal homfunctor

Hom_{𝔻} : (C^{𝔻})^{op} × C^{𝔻} → C

is defined by means of the following equalizer for 𝔻-algebras (A, α) and (B, β):

\xymatrix{Hom_{𝔻}((B, β), (A, α)) \ar[r]^{e} & A^{B} \ar[rr]^{A^{β}} \ar[dr]^{D} &  & A^{(DB)} \\  &  & (DA)^{(DB)} \ar@{-->}[ur]_{α^{(DB)}}}

The Dual Monad 𝔻^{∗}. We now fix a 𝔻-algebra

DS ⟶^{σ} S

called dualizer, and observe that the enriched hom-functor

Hom_{𝔻}(−, (S, σ)) : (C^{𝔻})^{op} → C

has a left adjoint which can be constructed as follows (see [L]): for every object C ∈ C we denote by

eval_{C}^{∗} : C → (DS)^{D(S^{C})}

the composite of the evaluation map C → S^{(S^{C})} and the D-map S^{(S^{C})} ↦ DS^{D(S^{C})}, and we consider the following adjunctions:

[figure: C; ^{eval{∗ \atop C}}; (DS)^{D(S^{C})}; C × D(S^{C}); DS; D(S^{C}); ϱ_{C}; (DS)^{C}]

We now define a functor

S^{(−)} : C → (C^{𝔻})^{op}

by assigning to C ∈ C the 𝔻-algebra

D(S^{C}) ⟶^{ϱ_{C}} (DS)^{C} ⟶^{σ^{C}} S^{C}

and to every morphism f : C → C̄ in C the 𝔻-homomorphism

S^{f} : (SC̄, σC̄ · ϱC̄) → (S^{C}, σ^{C} · ϱ_{C}) .

Then we get an enriched adjoint situation

S^{(−)} → Hom_{𝔻}(−, S)

(the argument in this general case is analogous to that in 2.2 above).

Notation. The enriched monad generated by the last adjoint situation is denoted by 𝔻^{∗} = (D^{∗}, η^{∗}, μ^{∗}) and is called the dual monad of 𝔻 w.r.t. the dualizer (S, σ). Thus,

D^{∗}C = Hom_{D}(S^{C}, S)

Equational Hull of the category dual to C^{𝔻}, the category of 𝔻-algebras w.r.t. the “forgetful” functor Hom_{𝔻}(−, (S, σ)) : (C^{𝔻})^{op} → C) is given by the comparison functor

K : (C^{𝔻})^{op} → C^{𝔻^{∗}} .

6.3. Doctrine of finite products. We apply the above to C = CAT and to the pseudomonad induced by the forgetful 2-functor

U : CAT_{fpc} ⟶ CAT

where CAT_{fpc} is the 2-category of all Cauchy complete categories with finite products (as objects), all functors preserving finite products (as 1-cells)

and

all natural transformations. The functor U is pseudomonadic: consider free completions of categories under finite products and limits of idempotents (= equalizers of id_{A}, e : A → A for idempotents e : A → A). This, like Lim in 3.9, can be considered as a pseudomonad 𝔻 on CAT . Obviously, the 2-quasicategory CAT_{fpc} is biequivalent to the 2-quasicategory of algebras for 𝔻.

We denote by

𝔻^{∗}

the dual pseudomonad with the dualizer Set . That is, we consider the 2-adjoint situation

\xymatrix{ & CAT _{fpc}^{op} \ar[dd]_{⊢} \\ CAT_{fpc}(−, Set ) &  & CAT (−, Set ) \\  & CAT \ar[uu]}

generating the pseudomonad 𝔻^{∗} = (D^{∗}, η^{∗}, μ^{∗}) over CAT . It means that

D^{∗}X = MOD (Set^{X})

for any category X, where MOD T denotes the category of all set-valued functors on T preserving finite products. Further,

D^{∗}F : H ⟼ H · Set (H ∈ MOD (Set^{X}))

for each functor F : X → Y, and

(D^{∗}φ)_{F} = H · Set^{φ}

for each natural transformation φ : F → F′. The unit

η_{K}^{∗} : X → MOD (Set^{X})

is given by

X ⟼ ev_{X}

where ev_{X} is the functor of evaluation-at-X, i.e.,

ev_{X} : Set^{X} (X (X, −), −) .

The multiplication

μ_{X}^{∗} : MOD (Set^{D^{∗}X}) → MOD (Set^{X})

is defined by means of the evaluation functor

ev : Set^{X} → Set^{MOD (Set^{X})}

as

μ_{X}^{∗} (G) = G · ev

for each G : MOD (Set^{X}) → Set preserving finite products. The pseudomonad 𝔻^{∗} is dual to 𝔻 (when using Set as the dualizing object).

6.4. The comparison functor

K : CAT _{fpc}^{op} → CAT^{𝔻^{∗}}

assigns to every Cauchy-complete category A with finite products a 𝔻^{∗}-algebra whose underlying category is MOD A. For every functor F : A → B preserving finite products we have

K(F) : KB → KA

defined by

K(F) : H ⟼ H · F (H ∈ MOD B)

We observe that varieties are precisely the categories

KA for A in CAT_{fpc} ,

and in fact the duality of [ALR_{1}] is just a domain-codomain restriction of K to CAT _{fpc}^{op} ⟶ VAR.

6.5. Observation. The 2-category

CAT^{𝔻^{∗}}

of algebras of the dual pseudomonad 𝔻^{∗} is an equational hull of VAR over CAT . That is, given a pseudomonad 𝕋 over CAT , and a functor

E : VAR → CAT^{𝕋}

such that the composition U_{𝕋} · E : VAR → CAT is naturally isomorphic to the forgetful functor U : VAR → CAT , then there exists an essentially unique pseudofunctor

E^{∗} : CAT^{𝔻^{∗}} → CAT^{𝕋}

with

E ≅ KE^{∗} and U_{𝔻^{∗}} ≅ U_{𝕋} · E^{∗} .

The verification is completely analogous to the case LFP (cf. [ALR_{2}], Remark 4.7). Every 𝔻^{∗}-algebra is an absolute pseudocolimit of free 𝔻^{∗}-algebras (see [LV]) and every free 𝔻^{∗}-algebra is a limit of varieties. The second statement follows from

MOD (Set^{X}) ≅ lim MOD (C)

where the limit is induced by expressing Set^{X} as a colimit of small Cauchy-complete subcategories closed under finite products.

6.6. Open problem. Characterize 𝔻^{∗}-algebras. Is the 2-quasicategory CAT^{𝔻^{∗}} biequivalent to a (non-full) subcategory of CAT ? That is, is “to be a 𝔻^{∗}-algebra” a property of categories ?

6.7. The Pseudomonad 𝔻_{small}^{∗}. We can introduce the small core of the pseudomonad 𝔻^{∗} by defining, for every category K = colim_{I}K_{i} (where K_{i} are small subcategories of K, and I is ∞-filtered)

𝔻_{small}^{∗}K = colim_{I} 𝔻^{∗}K_{i} = colim_{I} MOD (Set^{K_{i}}) .

In other words, for small categories K we have 𝔻_{small}^{∗}K = 𝔻^{∗}K = MOD (Set^{K}). For large categories,

𝔻_{small}^{∗}K = colim_{I} MOD (Set^{K_{i}}) .

This yields a pseudomonad 𝔻_{small}^{∗} which preserves ∞-filtered colimits. And the quasicategory

CAT^{𝔻_{small}^{∗}}

is a small equational hull of VAR over CAT . That is, given a pseudomonad 𝕋 over CAT preserving ∞-filtered colimits, then for every functor E : VAR → CAT^{𝕋} with U_{𝕋}·E ≅ U there exists an essentially unique pseudofunctor E^{∗} : CAT^{𝔻_{small}^{∗}} → CAT^{𝕋} with E ≅ K_{small} · E^{∗} and U_{𝔻_{small}^{∗}} ≅ U_{𝕋} · E^{∗} (for the comparison 2-functor K_{small}).

As in 6.6, we have not been able to characterize CAT^{𝔻_{small}^{∗}}. Thus, we restrict further:

6.8. The Pseudomonad 𝔻_{rank}^{∗}. This is the pseudomonad corresponding to restricting ourselves to operations on VAR with rank. Thus, for small categories K, 𝔻_{rank}^{∗}K = Mod (Set^{K}) and for large categories K = colim_{I}K_{i} (K_{i} small and I ∞-filtered)

𝔻_{rank}^{∗}K = colim_{I} Mod (Set^{K_{i}}) .

Lemma. 𝔻_{rank}^{∗} and Sind ∘ Lim are biequivalent pseudomonads, i.e., there exists a biequivalence

E : ALG = CAT^{Sind ∘ Lim} → CAT^{𝔻_{rank}^{∗}}

such that the following triangle

[figure: ALG = Cat^{Sind ∘ Lim}; E; V; CAT^{𝔻_{rank}^{∗}}; W_{𝔻{∗ \atop rank}}; CAT; ≅]

commutes.

This follows easily from the monadicity of the two categories, ALG and CAT^{𝔻_{rank}^{∗}}, over CAT and the fact that the free algebras over K coincide for all small categories K:

(Sind ∘ Lim )K ≅ Sind (Set^{K})^{op} ≅ Mod (Set^{K})

by 3.8 (2).

6.9. ALG is not an equational hull of VAR. Let us finally observe that ALG is not equivalent to CAT^{𝔻^{∗}} nor to CAT^{𝔻_{small}^{∗}} provided that we assume that Set contains arbitrarily large measurable cardinals. In fact, as recalled in 2.4, this assumption implies

Mod (Set ) ⫋ MOD (Set ) ,

i.e., there exists a non-accessible functor H : Set → Set preserving finite products. Denote by ω^{H} the corresponding unary operation on VAR, i.e., for every variety V = Mod T we have the operation functor

(ω^{H})_{V} : Mod T → Mod T , F ↦ HF .

Lemma. The operation ω^{H} cannot be extended from VAR to ALG.

Proof. Let K_{i} (i ∈ I) be an ∞-filtered collection of full subcategories of Set closed under finite products such that Set = colim K_{i}. Each V_{i} = Mod K_{i} is a variety, and if k_{i} : K_{i} → Set denotes the inclusion, then Mod (Set ) is a limit of V_{i} (i ∈ I) with the limit-cone Mod k_{i} (F ↦ F/k_{i}).

Assuming that ω^{H} has an extension to ALG, then for the algebraically exact category K = Mod (Set ) we have an operation-functor (ω^{H}) such that the squares

\xymatrix{Mod (Set ) \ar[r]_{≅}^{(ω^{H})K} \ar[d]_{Mod k_{i}} & Mod (Set ) \ar[d]^{Mod k_{i}} \\ Mod K_{i} \ar[r]^{(ω^{H})V_{i}} & Mod K_{i}}

commute up to isomorphism. Applied to the object Id : Set → Set of Mod (Set ), we get

H · k_{i} ≅ (ω^{h})_{K}(Id)/k_{i} for all i ∈ I

and we conclude that

H ≅ (ω^{H})_{K}(Id) .

This is a contradiction since H is not accessible and (ω^{H})_{K} takes values in Mod (Set ), thus, (ω^{H})_{K}(Id) is accessible.

Remark. If MOD (Set^{K}) = Mod (Set^{K}) would hold for all small categories K, then, of course, ALG would be small-equational hull of VAR. As remarked in 1.4 we do not know whether this assumption is consistent with set theory.

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.

[AK] J. Adámek, V. Koubek, How large are left exact presheaves? personal communication. [ALR_{1}] J. Adámek, F. W. Lawvere and J. Rosický, On the duality between varieties and algebraic theories,

submitted. [ALR_{2}] J. Adámek, F. W. Lawvere and J. Rosický, Continuous categories revisited, submitted. [AR_{1}] J. Adámek and J. Rosický, On sifted colimits and generalized varieties, Theory and Applications

of Categories. 8 (2001), 33–53. [AR_{2}] J. Adámek and J. Rosický, Locally presentable and accessible categories, Cambridge University

Press 1994.

[ARV] J. Adámek, J. Rosický and E. Vitale, Algebraically exact categories, to appear in J. Alg.

[B] J. Beck, Distributive laws, Lect. Notes in Math. 80 (1969), 119–140.

[JJ] P. Johnstone and A. Joyal, Continuous categories and exponentiable toposes, J. Pure Appl. Algebra 25 (1982), 255-296.

[K] A. Kock, Monads for which structures are adjoint to units, J. Pure Appl. Alg. 104 (1995), 41–59.

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

[Law_{1}] F. W. Lawvere, Functorial semantics of algebraic theories, Proc. Nat. Acad. Soc. 50 (1963), 865–872.

[Law_{2}] F. W. Lawvere, Ordinal sums and equational doctrines, Lect. Notes in Math. 80 (1969), 141–155.

[LV] I. J. Le Creurer and E. M. Vitale, Beck’s theorem for pseudo-monads, preprint.

[M_{1}] F. Marmolejo, Doctrines whose structure forms a fully faithful adjoint string, Theory and Applications of Categories. 3 (1997), 24–44.

[M_{2}] F. Marmolejo, Distributive laws for pseudomonads, Theory and Applications of Categories. 5 (1999), 91–147.

[M_{3}] F. Marmolejo, Distributive laws for pseudomonads II, to appear.

[R] J. E. Roos, Caractérization des catégories qui sont quotients des catégoris des modules par des souscatégories bilocalisantes, C. R. Acad. Sci. Paris 261 (1965), 4954–4957.

[Re] J. Reitermann, An example concerning set functors, Comm. Math. Univ. Carol. 12 (1971), 227–233.

[TT] W. Tholen and A. Tozzi, Completions of categories and initial completions, Cahiers Top. Geom. Diff. Categ. 30 (1989), 127–156.

Technical University Braunschweig Postfach 3329 38023 Braunschweig, Germany

Diefendorf Hall, State University of New York at Buffalo Buffalo, N.Y. 14214, U.S.A.

Masaryk University, Janáčkovo nám. 2a 662 95 Brno, Czech Republic

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

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

ftp://ftp.tac.mta.ca/pub/tac/html/volumes/8/n9/n9.{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