Algebraic Theories of Quasivarieties

Jiří Adámek^{∗}  Hans – E. Porst^{†}

Abstract

Analogously to the fact that Lawvere’s algebraic theories of (finitary) varieties are precisely the small categories with finite products, we prove that (i) algebraic theories of many–sorted quasivarieties are precisely the small, left exact categories with enough regular injectives and (ii) algebraic theories of many–sorted Horn classes are precisely the small left exact categories with enough M–injectives, where M is a class of monomorphisms closed under finite products and containing all regular monomorphisms. We also present a Gabriel–Ulmer–type duality theory for quasivarieties and Horn classes.

1 Quasivarieties and Horn Classes

The aim of the present paper is to describe, via algebraic theories, classes of finitary algebras, or finitary structures, which are presentable by implications. We work with finitary many–sorted algebras and structures, but we also mention the restricted version to the one–sorted case on the one hand, and the generalization to infinitary structures on the other hand.

Recall that Lawvere’s thesis [?] states that Lawvere–theories of varieties, i.e., classes of algebras presented by equations, are precisely the small categories with finite products, product–generated by a single object; for many–sorted varieties the analogous statement can be found in [?, 3.16, 3.17]. More in detail: If we denote, for small categories A, by P rod_{ω}A the full subcategory of Set^{A} formed by all functors preserving finite products, we obtain the following:

(i) If K is a variety, then its Lawvere–theory L(K), which is the full subcategory of K^{op} of all finitely generated free K–algebras, is essentially small, and has finite products. The variety K is equivalent to P rod_{ω}L(K).

∗This author acknowledges support of the Czech Grant Agency, Grant 201/96/0119.

†This author would like to thank the Department of Mathematics at the University of South Africa for its hospitality while doing the work presented here.

(ii) If A is a small category with finite products, then P rod_{ω}A is equivalent to a variety.

(Let us remark that, unless we consider varieties as concrete categories, the correspondence between between varieties and finite–product theories is not natural. For example, if A and B are small categories with finite products, then from the equivalence of P rod_{ω}A and P rod_{ω}B it does not follow that A and B are equivalent. In other words, one variety can have many non–equivalent theories.)

We are going to prove the analogous result for quasivarieties of algebras, i.e., classes which can be defined by implications of the form

α_{1} ∧ α_{2} ∧ … ∧ α_{n} ⟶ β (*)

where n ∈ ω and α_{i} and β are equations (with both sides of the same sort).

The role of L(K) is played here by the algebraic theory of the quasivariety K, which is the dual of the full subcategory K_{fp} of K formed by all finitely presentable algebras.

Remark 1 The notion of theory can be introduced more generally, when recalling first some basic facts from [?] needed throughout this paper:

(a) An object K of a category K is called finitely presentable provided that K(K, −) preserves directed colimits; more explicitely: given a directed colimit (D_{i} ⟶^{d_{i}} D)_{i∈I} for some directed poset I, then for every morphism f: K → D

(i) there exists a factorization f′: K → D_{i} through the colimit, i.e., f = d_{i} · f′ for some i ∈ I;

(ii) this factorization is essentially unique, i.e., if f′′: K → D_{i} also satisfies f = d_{i} · f′′, then there exists j ∈ I, j > i, such that the connecting map D_{i} → D_{j} merges f′ and f′′.

If K is a quasivariety, the usual concept of finite presentability (by generators and relations) is equivalent to the categorical one above.

(b) A category is called locally finitely presentable if it is cocomplete and has a set P of finitely presentable objects such that every K–object is a directed colimit of P–objects. Every quasivariety is locally finitely presentable.

(c) A finite colimit of finitely presentable objects is finitely presentable. In other words, the full subcategory K_{fp} of K formed by all finitely presentable objects is closed under finite colimits in K. Moreover, K_{fp} is dense in K, i.e., every object K is a colimit of its canonical diagram w.r.t. K_{fp} (formed by all arrows from finitely presentable objects into K).

Notation (1) For every locally finitely presentable category K we denote by T h(K) the dual of K_{fp}. T h(K) is called the algebraic theory of K.

(2) For every left exact (= finitely complete), small category A we denote by LexA the full subcategory of Set^{A} formed by all left exact (= finite–limits preserving) functors.

The rôle of the theory has been made clear by Gabriel and Ulmer in [?]:

(I) For every locally finitely presentable category K the theory T h(K) is an essentially small, left exact category, and K is equivalent to LexT h(K).

(II) For every small, left exact category A the category LexA is locally finitely presentable, and A is equivalent to the theory T h(LexA).

Remark 2 The equivalences (I) and (II) are just the “object part” of the wellknown Gabriel–Ulmer duality. We devote the last part of our paper to a detailed description of that duality because the existing descriptions in the literature are incorrect. At this stage let us mention only that the embedding K_{fp} ↪ K corresponds, under the equivalences above, to Yoneda embedding Y: A^{op} → LexA given by Y (A) = A(A, −). Observe that, because T h(K) is essentially small, forming LexT h(K) is essentially correct; see Section 4 for details. As a consequence of Gabriel–Ulmer duality we get

(III) A locally finitely presentable category K has an essentially unique theory. That is, if A is a left exact category with K ≅ LexA, then A ≅ T h(K).

Recall that an object A in a category A is M–injective w.r.t. a given class M ⊂ A^{mor} if for every member m: B ⟶ C of M the map A(m, A): A(C, A) → A(B, A) is surjective. A category has enough M–injectives provided that every object is an M–subobject of an M–injective object. In case M is the class of all regular monomorphisms, the category A is said to to have enough regular injectives. Projectivity is defined dually. Of particular importance will be, for any given class P ⊂ A^{obj}, the class P^{⊥} of all morphisms to which every P–object is projective. The following immediate consequence of the definition of finite presentability will be used in the sequel:

Lemma 1 For any class P of finitely presentable objects the class P^{⊥} is closed under directed colimits.

We will prove that algebraic theories of quasivarieties are precisely the small left exact categories with enough regular injectives, or, somewhat more explicitely (improving the main result of [?]) that the following hold:

(i’) If K is a quasivariety, then T h(K) is essentially small, left exact, and has enough regular injectives. The quasivariety K is equivalent to LexT h(K).

(ii’) If A is a small left exact category with enough regular injectives, then LexA is equivalent to a quasivariety.

Moreover, we present a duality for quasivarieties and small, left exact categories with enough regular injectives which, inter alia, shows that

(iii’) For any quasivariety K, the small, left exact category A with K ≅ LexA is essentially unique.

Our duality theory for quasivarieties is just a natural restriction of the Gabriel– Ulmer duality.

Finally, we turn to Horn classes of finitary structures. Here we assume that a signature of finitary (many–sorted) operations and relations is given, and a Horn class is presented by implications as in (*) above, where now α_{i} and β are atomic formulas (i.e., either equations, or formulas r(t_{1}, …, t_{n}) where r is an n–ary relation, and t_{1}, …, t_{n} are terms of the corresponding sorts). Horn classes are locally finitely presentable categories. We will prove that algebraic theories of Horn classes are precisely the small categories with finite limits and enough M–injectives. Here M can be an arbitrary class of monomorphisms which is closed under finite products (i.e., if for i = 1, 2, the morphisms m_{i}: A_{i} → B_{i} belong to M, then so does m_{1} × m_{2}: A_{1} × A_{2} → B_{1} × B_{2}) and contains all regular monomorphims; classes of monomorphisms with these two properties will be called left exact classes below. For example, in every Horn class K we can consider the collection of all homomorphisms which are surjective (more precisely: every sort yields a surjective function). This defines a left exact class of monomorphisms in T h(K) as we prove below.

Quite analogously to the case of quasivarieties, we will prove the following:

(i”) If K is a Horn class, then T h(K) is essentially small, left exact, and has enough M–injectives for the left exact class M of all surjective K– homomorphisms. The Horn class K is equivalent to LexT h(K).

(ii”) If A is a small, left exact category with enough M–injectives, for some left exact class M, then LexA is equivalent to a Horn class.

Again, the Gabriel–Ulmer duality yields a duality theory for Horn classes and small, left exact categories with enough M–injectives. In particular,

(iii”) For any quasivariety K, the small, left exact category A with K ≅ LexA is essentially unique.

Before proving the promised results, we turn to a theorem concerning locally finitely presentable categories in general, which will be used below.

Theorem 1 Let K be a locally finitely presentable category. For any finite category A we have

T h(K^{A}) = T h(K)^{A},

i.e., a functor F: A ⟶ K is finitely presentable in K^{A} iff F a is finitely presentable in K for every object a ∈ A^{obj}.

Proof. Let F a be finitely presentable for every a ∈ A. Then F is finitely presentable in K^{A} because colimits in K^{A} are formed pointwise.

Conversely, let F be finitely presentable in K^{A}. For each object a ∈ A we form the following diagram

D_{a}: D_{a} ⟶ K.

Objects of D_{a} are triples (X, x, i) where X ∈ K_{fp}, X \underrightarrow{x} F a is a K–morphism, and i = 0, 1. Besides the identity maps the morphisms of D_{a} are only

f : (X, x, 0) ⟶ (Y, y, 1)

where f: X ⟶ Y is a K–morphism with x = yf. Put D_{a}(X, x, i) = X and D_{a}f = f. The colimit of D_{a} obviously coincides with the colimit of the canonical diagram of F a and therefore

colimD_{a} = (D_{a}(X, x, i) \underrightarrow{x} F a)

since K is locally finitely presentable.

Denote by C the poset of all finite subcategories of ∐_{a∈A^{obj}} D_{a} (ordered by inclusion); C is directed. For each C ∈ C denote by C^{∗} ∈ C the full subcategory of all objects (X, F α · x, i) ∈ D_{a′}, where (X, x, i) ∈ C ∩ D_{a} and α: a ⟶ a′ ∈ A^{mor}. (Since A is a finite category, C^{∗} is finite.) The domain restriction of the functor induced by D_{a}, a ∈ A^{obj}, yields a forgetful functor D_{C}: C^{∗} ⟶ K. We define a functor F_{C}: A ⟶ K as follows: for each object a ∈ A^{obj} let F_{C}a be a colimit of D_{C,a}: C_{a}^{∗} ⟶ K which is the domain restriction of D_{C} to C^{∗}∩D_{a}; more precisely:

colimD_{C,a} = (D_{a}(X, x, i) \underrightarrow{d_{C,a}^{x}} F_{C}a)_{(X,x,i)∈C_{a}^{∗}}.

For each morphism α: a ⟶ b in A we define a functor H_{α}: C_{a}^{∗} ⟶ C_{b}^{∗} by H_{α}(X, x, i) = (X, F α · x, i) and H_{α}f = f; then the diagram

[figure: C_{a}^{∗}; H_{α}; C_{b}^{∗}; D_{C,a}; D_{C,b}; K]

commutes and we denote

F_{C}α = colimH_{α}: F_{C}a ⟶ F_{C}b

(i.e. F_{C}α · d_{C,a}^{x} = d_{C,b}^{F α·x}). It is easy to verify that F_{C} is a functor.

Given C ⊂ C′ in C there is an obvious natural transformation δ_{C,C′}: F_{C} ⟶ F_{C}′, defined by δ_{C,C′,a} · d_{C,a}^{x} = d_{C′,a}^{x}. This defines a directed diagram in K^{A}. We claim that a colimit of this diagram is formed by the natural transformations δC^{∗}: F_{C} ⟶ F, defined by δC^{∗} · d_{C,a}^{x} = x. In fact, let γ_{C}: F_{C} ⟶ G, C ∈ C, be a compatible cocone. We are looking for a natural transformation γ: F ⟶ G with γ_{C} = γ · δC^{∗} for all C ∈ C, i.e., with γ_{a} · x = γ_{C} · d_{C,a}^{x} for all x: X ⟶ F a in C. In fact, since K is locally finitely presentable, each F a is a canonical colimit of the digram K_{fp} ↓ F a ⟶ F a (assigning to each arrow its domain), thus, there is a unique γ_{a}: F a ⟶ Ga with γ_{a} · x = γ_{C} · δ_{C,a}^{x} for all C ∈ C and all x: X ⟶ F a in C. The unicity then guarantees that the γ’s form a natural transformation γ: F ⟶ G.

Since F is finitely presentable in K^{A}, there exists C ∈ C such that id_{F} factors through δC^{∗}. Then for each a ∈ A the object F a is a retract of the object F_{C}a. Since the latter, being a colimit of a finite diagram D_{C,a} in K_{fp}, is finitely presentable, so is the former. □

Corollary 1 Every regular epimorphism in a locally finitely presentable category K is a directed colimit (in K^{→}) of regular epimorphisms of K with all domains and codomains finitely presentable in K.

Proof. Given a coequalizer c: A ⟶ B of a pair f, g: D ⟶ A, apply Theorem ?? to the category A consisting of a single parallel pair to express (f, g) as a directed colimit of parallel pairs f_{i}, g_{i}: D_{i} ⟶ A_{i} with D_{i} and A_{i} finitely presentable. Form a coequalizer c_{i}: A_{i} ⟶ B_{i} of f_{i}, g_{i}. Then B_{i} is finitely presentable, and c is a directed colimit of c_{i} in the category K^{→} of morphisms in K.

□

Remark 3 (a) For infinite categories A the theorem is no longer true. For example, the embedding functor E ∈ Set^{ω} is not finitely presentable.

(b) Theorem ?? and its corollary immediately generalize to locally λ–presentable categories K, for any regular λ:

1. If A is a category with less than λ maps, then a functor F is λ–presentable in K^{A} iff F a is λ–presentable in K for every a ∈ A^{obj}.

2. Every regular epimorphism of K is a λ–directed colimit (in K^{→}) of regular epimorphisms of K with all domains and codomains λ–presentable in K.

Remark 4 We use various kinds of generators below (distinguishing between a generator, which is a set of objects with a certain property, and a generating object, if this set is a singleton) and here we want to recall some well–known concepts. Let G be a (small) set of objects in a category K with coproducts. Then G is

(a) a generator if, for each object K, the canonical morphism

e_{K}: ∐_{G∈G} ∐_{f:G→K} ⟶ K

is an epimorphism, (b) an extremal generator if, for each object K, e_{K} is an extremal epimorphism

(i.e., does not factor through any proper subobject of K),

(c) a regular generator if, for each object K, e_{K} is a regular epimorphism.

An equivalent formulation for (a) and (b) is: every object is an (extremal) quotient of a coproduct of G–objects. This simplification does not work for (c) in general, see [?], but this does not matter in the realm of quasivarieties, due to the following

Lemma 2 In any cocomplete category K with a generator P consisting of regularly projective objects, an epimorphism is regular iff it is extremal. Moreover, the regular epimorphisms are precisely the morphisms in P^{⊥}, provided P is even an extremal generator,

Proof. Let {G_{i} | i ∈ I} be a generator in K, where each G_{i} is regularly projective. Then the functor U = (K(G_{i}, −))_{I} : K → Set^{I} is faithful, has a left adjoint, and preserves regular epimorphisms. By the proof of [?, 23.38], U creates (regular epi, mono)–factorizations. But in any category with (regular epi, mono)–factorizations, extremal epimorphisms are regular. If P is even an extremal generator, i.e., if U in addition reflects isomorphisms, U — by the creation-property above — also reflects regular epimorphisms. This proves the final statement. □

2 Algebraic Theories of Quasivarieties

Our characterization of theories of quasivarieties relies on well–known categorical characterizations of quasivarieties. Since these (with or without minor modifications) tend to be reinvented now and again, we include a brief account.

Apparently Isbell was the first one to characterize quasivarieties in categorical terms as follows [?]:

A category K is equivalent to a quasivariety iff K satisfies the following conditions:

• K is cocomplete and has equalizers,

• K has an object P which is

(i) extremally projective,

(ii) extremally (= strongly) generating,

(iii) finitely presentable.

Actually, Isbell used instead of condition (iii) the somewhat weaker notion “abstractly finite” since he allowed for implications slightly more general than in (*) above.

Basically the same result was obtained by Linton [?] and later by Felscher [?]. Their characterizations are essentially translations of the properties of P in Isbell’s theorem into properties of the associated hom–functor K(P, −), by weakening at the same time Isbell’s (co–)completeness conditions to the existence of copowers of P, kernel pairs, and coequalizers of the latter. One can also use a regularly generating object instead of on extremally generating one, as justified by Lemma ??. Thus there is the following theorem:

Theorem 2 (Isbell–Linton–Felscher) For any category K the following are equivalent:

(i) K is equivalent to a one–sorted quasivariety,

(ii) K is cocomplete and has an extremally generating object which is regularly projective and finitely presentable.

(iii) K is cocomplete and has a regularly generating object which is regularly projective and finitely presentable.

(iv) K has kernel pairs, coequalizers of kernel pairs, and a regularly generating object which is regularly projective, finitely presentable, and admits all copowers.

Not surprisingly, basically the same characterization theorem holds in the many–sorted case; here only “generating object” has to be replaced by “generator”. The crucial equivalence of (i) and (iv) is formulated in [?] as Theorem 3.24. A similar result appears in [?] (Theorem 2.3) where, however, it is incorrectly claimed that every (finitary) quasivariety has a finite regular generator; the category Set^{A}, where A is an infinite discrete category, is a counterexample.

Theorem 3 For any category K the following are equivalent:

(i) K is equivalent to a (many–sorted) quasivariety.

(ii) K is cocomplete and has a regular generator consisting of regularly projective, finitely presentable objects.

Proof. (i) implies (ii) since in any quasivariety K every algebra K is a regular quotient of a free algebra K^{∗} and K^{∗} is regularly projective (the regular epimorphisms are precisely the surjective ones). Hence the free algebras on finitely many generators form the required generator. To prove that (ii) implies (i) we use the following facts: (a) given a regular generator G of finitely presentable objects, all finite coproducts of G–objects form a dense subcategory of finitely presentable objects (see[?, 7.5]); (b) coproducts of regularly projectives are regularly projective again. Thus, K is cocomplete and has a small dense subcategory consisting of regularly projective, finitely presentable objects. That this implies (i) is just the essential statement of [?, 3.24]. □

Remark 5 By Lemma ?? condition (ii) above could obviously be replaced by the formally weaker condition (ii’) K is cocomplete and has an extremal generator consisting of regularly projective, finitely presentable objects.

Theorem 4 A small category A is equivalent to the theory of some quasivariety iff A is left exact and has enough regular injectives.

Proof. In any quasivariety K with a regular generator G consisting of finitely presentable objects, all finitely presentable objects are regular quotients of finite coproducts of members of G by [?, 7.6]. Moreover, if the members of G are regular projective so are their coproducts. Thus, in T h(K) every object is a regular subobject of some regularly injective object.

For the converse, it is sufficient to prove, by the remark following Theorem ?? and by (II) above, that, for any locally finitely presentable category K such that K_{fp} has enough regular projectives, the set

P = {K | K is regularly injective in T h(K)}
= {K | K is regularly projective in K_{fp}}

is an extremal generator of regular projectives in K. Since every object of K is a colimit of finitely presentable objects, i.e., a colimit of a diagram in K_{fp}, and since every object of K_{fp} is a regular quotient of some object of P, it is easy to see that P is an extremal generator. To prove that every object K of P is regularly projective in K, use Lemma ??, Corollary ??, and the fact that regular epimorphisms in K_{fp} are regular epimorphisms in K, too. □

Corollary 2 Every quasivariety is equivalent to LexA for some small, left exact category A with enough regular injectives.

Remark 6 For one–sorted quasivarieties the existence of enough regular injectives has to be strengthened to the existence of a single object I which

a. is regular injective

and thus, every power I^{n} is regular injective, and

b. every object is a regular subobject of I^{n} for some n ∈ ω.

That is,

a small category A is equivalent to the theory of some one–sorted quasivariety iff A is left exact and has an object I satisfying a. and b.

This follows from the arguments given in the proof of Theorem ?? by replacing the set P by {I} and using condition b. instead of the argument “every object of K_{fp} is a regular quotient of some object of P”.

Remark 7 The generalization to infinitary algebras is straightforward. Let λ be a regular cardinal. A λ–ary quasivariety is a class of Σ–algebras for a λ–ary, many–sorted signature Σ given by implications

⋀_{i∈I} α_{i} ⟶ β

where α_{i} and β are equations (with both sides of the same sort) and card I < λ.

For each small, λ–complete category A with enough regular injectives, the category Lex_{λ}A, i.e., the full subcategory of Set^{A} formed by all λ–continuous functors, is equivalent to a λ–ary quasivariety.

Conversely, if K is a λ–ary quasivariety, then the full subcategory T h_{λ}(K) of K^{op} formed by all λ–presentable K–algebras is essentially small, λ–complete, has enough regular projectives and fullfils

Lex_{λ}T h_{λ}(K) ≅ K.

(The proof is analogous to that of Theorem ??.) Similarly, Remark ?? generalizes to the λ–ary case.

3 Algebraic Theories of Horn Classes

The proof of the next theorem is based on a characterization of Horn classes proved by J. Rosický in [?]. Here a set P of objects is called additive provided that the class P^{⊥} of all morphisms to which every P–object is projective is closed under coproducts (in the usual sense, i.e., given e_{i}: K_{i} ⟶ L_{i} in P^{⊥} for i ∈ I, then ∐_{i∈I} e_{i}: ∐_{i∈I} K_{i} ⟶ ∐_{i∈I} L_{i} lies in P^{⊥}, too).

Theorem 5 ([?]) The following are equivalent for any category K:

(i) K is equivalent to a Horn class.

(ii) K is locally finitely presentable and has an additive generator consisting of regularly projective, finitely presentable objects.

(Rosický’s theorem states the equivalence of (i) and (ii) only, but is formulated for κ–presentable categories, we specify it to κ = ω here. )

Remark 8 The following list of examples of additive sets of regularly projective objects in a category K illustrates the above theorem:

POS In the Horn class POS of posets and monotone maps, 1 (a singleton poset) is regularly projective and the class {1}^{⊥} is the class of all surjective monotone maps, i.e., of all epimorphisms; thus 1 is a regularly projective, additive, generating object in POS.

QV In every quasivariety any regular generator G consisting of regular projectives is additive: G^{⊥} here is the class of all regular epimorphisms (see Lemma ??).

Cat In the locally finitely presentable category Cat of small categories and functors, the only regularly projective objects are the discrete categories. For any set P of those, P^{⊥} is the class of all functors which are surjective on objects, thus closed under coproducts; however, no such set P is a generator, see [?]. In particular, Cat is not a Horn class.

Top In the category Top of topological spaces and continuous maps, 1 is a regularly projective, additive, generating object. Note that Top fails to be locally finitely presentable.

The following lemma generalizes the first example above, and its corollary is crucial for the theorem to follow.

Lemma 3 Let K be a Horn class. Then the class of all surjective homomorphisms in K is closed under coproducts and contains all regular epimorphisms.

Proof. Let K be given in terms of some signature Σ; denote by StrΣ the category of all Σ–structures and all homomorphisms.

(a) The statement of the lemma holds for StrΣ. In fact, let Σ_{0} be the signature obtained from Σ by deleting all operational symbols. Then there is a natural forgetful functor

V: StrΣ ⟶ AlgΣ_{0}

into the category of all Σ_{0}–algebras, which has a right adjoint (assigning to every Σ_{0}–algebra A the “largest” Σ–structure over A, i.e., all relations are maximal). Since in AlgΣ_{0} surjective homomorphisms are precisely the regular epimorphisms, the class of all surjective homomorphisms in StrΣ is V^{−1}[RegEpi(AlgΣ_{0})]. Since V, as a left adjoint, preserves coproducts and regular epimorphisms, the statement follows.

(b) The Horn class K, being closed under products and strong subobjects in StrΣ, is an epi–reflective subcategory of StrΣ. Thus, for homomorphisms e_{i}: A_{i} → B_{i} (i ∈ I) of K, a coproduct ê in K is obtained from a coproduct ∐_{i∈I} e_{i}: ∐_{i∈I} A_{i} → ∐_{i∈I} B_{i} in StrΣ by forming reflections r_{A}: ∐_{i∈I} A_{i} → RA and r_{B}: ∐_{i∈I} B_{i} → RB:

[figure: ∐_{i∈I} B_{i}; r_{B}; RB; ∐_{i∈I} e_{i}; ê; ∐_{i∈I} A_{i}; RA; r_{A}]

By (a), ∐_{i∈I} e_{i} is surjective, as is r_{B} as an epimorphism in StrΣ; thus, ê is surjective.

The proof that regular epimorphisms of K are surjective is analogous. □

Corollary 3 Let K be a Horn class. Then all surjective homomorphisms between finitely presentable K–objects form a left exact class of monomorphisms in T h(K).

Theorem 6 A small category A is equivalent to the theory of some Horn class iff A is left exact and has enough M–injectives with respect to some left exact class M of monomorphisms.

Proof. Given a Horn class K, its theory A = T h(K) has enough M–injectives, where M is the set of all surjective K_{fp}–homomorphisms. In fact, since K is an epireflective subcategory of StrΣ, the natural forgetful functor U from K to Set^{S} (where S is the set of all sorts of the signature Σ) has a left adjoint F: Set^{S} ⟶ K. Each object F X, where X is finitely presentable in Set^{S}, is M– injective in T h(K). Every finitely presentable object K of K is an M–quotient of some F X with X finitely presentable: consider the directed family of all regular subobjects of K generated by some finitely presentable X, then K equals to one of them (since it is a directed colimit of the diagram formed by inclusion maps). Thus T h(K) has enough M–injectives, which proves the implication by Corollary ??.

For the converse it is sufficient to prove, by Theorem ?? and (II) above, that, for any locally finitely presentable category K and any left exact class M of monomorphisms in T h(K), the set

P = {K | K is M–injective in T h(K)}
= {K | K is M–projective in K_{fp}}

is a finitely additive generator consisting of regular projectives.

Regular projectivity of the objects of P follows by the same argument as in the proof of Theorem ??, since M contains all regular epimorphisms in K_{fp}. Also, P is obviously generating.

Finally, we prove that P^{⊥} is closed under coproducts. By Lemma ?? it is sufficient to prove that P^{⊥} is closed under finite coproducts. Let

u: U ⟶ U′ and v: V ⟶ V′

be two arrows in P^{⊥}. We will prove that, for every M–projective object K of K_{fp}, each morphism

h: K ⟶ U′ + V′

factors through u+v in K. Since K, and hence K^{→}, is locally finitely presentable, u is a directed colimit of finitely presentable objects, which, by Theorem ??, means that there exists a directed family of maps u_{i}: U′_{i} ⟶ U_{i} (i ∈ I) in K\overrightarrow{fp} such that u = colim u_{i}; analogously v = colim v_{j} for a directed family v_{j}: V′_{j} ⟶ V_{j} (j ∈ J) in K\overrightarrow{fp}. We denote the colimit maps as follows:

[figure: U; u; U′; p_{i}; p′_{i}; U_{i}; U′_{i}; u_{i}; V; v; V′; q_{j}; q′_{j}; V_{j}; V′_{j}; v_{j}]

Consequently, U′ + V′ = colim (U′_{i} + V′_{j}) and, since K is finitely presentable, h factors through some U′_{i} + V′_{j}, i.e., there exist i ∈ I, j ∈ J, and k: K ⟶ U′_{i} + V′_{j} with

h = (p′_{i} + q′_{j}) · k.

Since K_{fp} has enough M–projectives, there exist M–maps

m: Ū ⟶ U′_{i} and n: V̄ ⟶ V′_{j}

with Ū and V̄ both M–projective (in K_{fp}). Then, since M is closed under finite coproducts in K_{fp} and K is M–projective, there exists k̄ such that the following triangle

[figure: Ū + V̄; m + n; U′_{i} + V′_{j}; k̄; k; K]

commutes. Furthermore, Ū lies in P and u in P^{⊥}, thus, p′_{i} · m factors through u; analogously, q′_{j} · n factors through v:

[figure: U; u; U′; p′′_{i}; p′_{i}; Ū; U′_{i}; m; V; v; V′; q′′_{j}; q′_{j}; V̄; V′_{j}; n]

This yields the desired factorization of h through u + v:

h \begin{matrix}= & (p′_{i} + q′_{j}) · k \\ = & (p′_{i} + q′_{j}) · (m + n) · k̄ \\ = & (u · p′′_{i} + v · q′′_{j}) · k̄ \\ = & (u + v) · (p′′_{i} + q′′_{j}) · k̄. \end{matrix}

□

Corollary 4 Every Horn class is equivalent to LexA for some small, left exact category A with enough M–injectives, where M is a left exact class of monomorphisms in A.

Remark 9 For one–sorted Horn classes the existence of enough M–injectives has to be strengthened to the existence of a single object I which

a. is M–injective

and thus, every power I^{n} is M–injective, and

b. every object is an M–subobject of I^{n} for some n ∈ ω.

That is,

a small category A is equivalent to the theory of some one–sorted Horn class iff A is left exact and has an object I satisfying a. and b. for some left exact class M of monomorphisms.

This is essentially the result of Keane [?] and follows by modifications of the arguments in the proof of Theorem ?? analogously as in Remark ??.

Remark 10 The generalization to infinitary structures is straightforward: let λ be a regular cardinal. A Horn class of λ–ary structures is a set of Σ–structures, for a given many–sorted λ–ary signature Σ, given by implications

⋀_{i∈I} α_{i} ⟶ β

where α_{i} and β are atomic formulas with card I < λ.

Suppose A is a small, λ–complete category. Let M be a class of monomorphisms containing all regular ones and closed under coproducts of less than λ members. Then if A has enough M–injectives, the category Lex_{λ}A is equivalent to a Horn class of λ–ary structures.

Conversely, every Horn class of λ–ary structures has the above form Lex_{λ}A. The proof is quite analoguous to that of Theorem ??.

Similarly, Remark ?? generalizes to the λ–ary case.

Remark 11 Obviously every small complete category A has a smallest and a largest left exact class of monomorphisms: the class of all regular monomorphisms and of all monomorphisms, respectively. If A has enough injectives w.r.t. the smallest left exact class, the corresponding generator P in LexA is regular and consists of regular projectives (see proof of Theorem ??) and hence one gets here P^{⊥} = RegEpi(LexA) (see Lemma ??), which is automatically additive.

4 Gabriel–Ulmer Duality

It was probably conceived very early that Gabriel and Ulmer’s fundamental equivalences (I) and (II) of Section 1

LexT h(K) ≅ K and T h(LexA) ≅ A

have a certain kind of (contravariant) functionality. More precisely: Let Lex denote the category of all small, left exact categories and all left exact functors. Let LFP be the quasicategory^{1} of all locally finitely presentable categories and all functors preserving limits and directed colimits (in other words: the morphisms in LFP are precisely the right adjoints between finitely locally presentable categories, see [?, 1.66]). One obtains a functor

Lex: Lex^{op} ⟶ LFP

assigning to every A in Lex the category LexA and defined on morphisms F: A ⟶ B by composites with F on the right:

Lex(F) = (−)F: LexB ⟶ LexA.

What is generally known as Gabriel–Ulmer duality (and what, in the strongest 2–categorical sense has been explicitly stated in [?]) is the statement that Lex is an equivalence of categories. This, however, is wrong (note that Lex is category):

Lemma 4 LFP is not equivalent to a category.

Proof. Whereas in a category hom–sets are sets (or classes, in the Bernays– Gödel terminology), LFP does not have this property. In fact, here a hom–set LFP(K, L) can be as large as the collection of all subclasses of the class of all sets: if K = L = Set, then, for each class C ⊂ Set, there obviously exists a functor

F_{C}: Set ⟶ Set with F_{C} ≅ Id and F_{C}X = X iff X ∈ C.

1Recall from [?] that quasicategory is defined as category except that all objects do not necessarily form a class, but a conglomerate (i.e., this belongs to a higher universe), and also hom’s are conglomerates, in general; see [?] for a detailed discussion.

These functors F_{C} are endomorphisms of Set in LFP which are pairwise distinct. □

For this reason we have decided to devote the present section to the development of a formally correct version of the Gabriel–Ulmer duality theorem. Observe that the above functor Lex is faithful, but it is neither full (though it is “full up to natural isomorphism”) nor isomorphism dense (though it is “isomorphism dense up to equivalence of categories”).

The proper setting for the duality is that of 2–categories and bifunctors (see e.g. [?] for basic notions). Recall from [?] that if K and L are 2–categories, then a 2–functor (or, more generally, a lax functor) R: K ⟶ L is called a biequivalence if

(a) for each object X of L there exists an object A of K such that RA ≈ X (i.e., there exist 1–cells f: RA ⟶ X and g: X ⟶ RA and invertible 2–cells fg ⟹ 1_{X} and 1_{RA} ⟹ gf), and

(b) for each pair A, B of objects of K the functor

R_{A,B}: K(A, B) ⟶ L(RA, RB)

is an equivalence of categories.

As remarked in [?], this implies that R has a left biadjoint which is also a biequivalence (so being biequivalent is an equivalence relation on the conglomerate of all 2–categories).

We will modify the above notation: By Lex we denote the 2–category of all small, left exact categories (as objects), all left exact functors (as arrows), and all natural transformations (as 2–cells).

For LFP we need to work with the concept of 2–quasicategory: this is defined precisely as 2–category except that the set–theoretical restrictions on the sizes of the conglomerates of i–cells are lifted (for i = 0, 1, 2). (Thus, 2–quasicategories are related to 2–categories exactly as quasicategories are to categories.)

We denote by LFP the 2–quasicategory of all locally finitely presentable categories (as objects), all functors preserving limits and directed colimits (as arrows), and all natural transformations (as 2–cells).

We denote by

Lex: Lex^{op} ⟶ LFP

the 2–functor assigning to each object A the category LexA, and with

Lex_{A,B}: Lex(A, B) ⟶ LFP(LexB, LexA)

defined by

Lex_{A,B}(F ⟶^{σ} F′)_{H} = HF ⟶^{Hσ} HF′

for F: A ⟶ B in LexA and H ∈ LexB.

Theorem 7 (Gabriel–Ulmer Duality) The 2–category Lex is dually biequivalent to LFP. More in detail: The functor

Lex: Lex^{op} ⟶ LFP

is a biequivalence.

Proof. (a) For each object K of LFP there exists an equivalent object of the form Lex(A), namely LexT h(K) — see (I) in Section 1.

(b) Lex_{A,B} is an equivalence functor for each pair A, B of left exact categories. Proof: (b 1) Lex_{A,B} is faithful. In fact, let σ, τ: F ⟶ F′ (for F, F′: A ⟶ B) be natural transformations with Lex(σ) = Lex(τ). For each object A we are to show σ_{A} = τ_{A}. This follows from the fact that the component of Lex(σ) at H = B(F A, −) is Hσ: B(F A, F −) ⟶ B(F A, F′−) and σ_{A} = (Hσ)_{A}(1_{F A}); analogously with τ. Thus, Hσ = Hτ implies σ_{A} = τ_{A}. (b 2) Lex_{A,B} is full. That is, given F, F′: A ⟶ B in LFP, then every natural transformation

τ: (−)F ⟶ (−)F′,

i.e., every collection of natural transformations

τ_{H}: HF ⟶ HF′ for H ∈ LexB

which, moreover, is natural in the variable H, has the form τ = Lex(σ) for some 2–cell σ: F ⟶ F′ in Lex.

To prove this, observe that for each object A of A we have H = B(F A, −) in LexB, and hence

τ_{H}: B(F A, F −) ⟶ B(F A, F′−)

We define

σ_{A} = (τ_{H})_{A}(id_{A}): F A ⟶ F′A.  (1)

It is obvious that, then,

(τ_{H})_{B}(f) = F′f · σ_{A} for all f: A ⟶ B in A.  (2)

Let us verify that σ_{A} is natural in A: given α: A_{1} ⟶ A_{2} in A the corresponding Yoneda transformation

α^{∗}: B(F A_{2}, −) ⟶ B(F A_{1}, −)

is a map of LexB, and since τ_{H} is natural in H,

τ_{B(F A_{1},−)} · α^{∗}F = α^{∗}F′ · τ_{B(F A_{2},−)}.  (3)

Applying (3) to id_{F A_{2}}, we get, by using (2):

σ_{A_{2}} · F′α = F α · σ_{A_{1}}.

Let us further verify that

τ = Lex(σ),

i.e. that τ_{H} = Hσ for each H ∈ LexB. In fact, the equality

(τ_{H})_{A}(α) = Hσ_{A}(α)  (4)

for all H ∈ ContB, A ∈ A, and α ∈ HF A, follows from the naturality of τ_{H} in H, applied to the unique LexB–map

φ: B(F A, −) ⟶ H

given by φ_{A}(id_{F A}) = α: apply τ_{H} · φF = φF′τ_{B(F A,−)} to id_{F A} (using again (2)). (b 3) Lex_{A,B} is isomorphism–dense, i.e., every map

T: LexB ⟶ LexA

in LFP is naturally isomorphic to Lex(F) for some map F: A ⟶ B in Lex. To prove this, recall that T is a right adjoint, and choose a left adjoint S of T; recall also that every left adjoint preserves the property of being a finitely presentable object. Since finitely presentable objects of LexA (or LexB) are precisely the representable functors, see [?], it follows that for every A(A, −) ∈ LexA we can choose an object B =^{def} F A in B such that B(B, −) ≅ S(A(A, −)). Let us fix a natural isomorphism

i_{A}: S(A(A, −)) ⟶ B(F A, −) for all A ∈ A.

Given a morphism f: A ⟶ A′ in A, the Yoneda lemma guarantees that there is a unique map F f: F A ⟶ F A′ for which the natural transformation

i_{A}^{−1} · S( hom(f, −)) · i_{A′}: B(F A′, −) ⟶ B(F A, −)

is given by composites with F f. It is easy to verify that this defines a functor F: A ⟶ B. To prove that

T ≅ Lex(F),

it is sufficient to show that Lex(F) is a right adjoint to S, i.e., that there is an isomorphism

\frac{S(H) ⟶ K}{H ⟶ KF}

natural in the variables H ∈ LexA and K ∈ LexB. Since LexA is locally finitely presentable, thus every object H is a directed colimit of finitely presentable (= representable) objects, it is sufficient to find such a natural isomorphism for H = A(A, −) where A ∈ A is arbitrary. And this is just Yoneda lemma: we have a natural isomorphism between A(A, −) ⟶ KF and B(F A, −) ⟶ K, and the latter is (via the i_{A}’s) naturally isomorphic to S(A(A, −)) ⟶ K. □

Remark 12 We can, by Theorem ??, restrict the biequivalence Lex: Lex^{op} ⟶ LFP to a dual biequivalence between the quasicategory of all quasivarieties (a full sub–quasicategory of LFP) — sorry for the two independent uses of “quasi” here! — and the category of all small, left exact categories with enough regular injectives (a full subcategory of Lex).

As a corollary we get immediately from the properties of the 2–functor Lex:

Corollary 5 For every quasivariety K there exists a unique, up to equivalence of categories, small left exact category A with enough regular injectives such that K ≅ LexA.

Analogously, Theorem ?? yields a dual biequivalence for Horn classes, thus:

Corollary 6 For every Horn class K there exists a unique, up to equivalence of categories, small left exact category A with enough M–injectives for some left exact class M of monomorphisms in A such that K ≅ LexA.

Remark 13 As observed above the functor Lex has an adjoint biequivalence LFP ⟶ Lex^{op} (which, however, cannot be a functor, see Lemma ??). In order to characterize this biequivalence we turn to a description of the Gabriel–Ulmer duality as presented in [?]. There the authors work with the 2–quasicategory LEX, defined as Lex except that the objects are allowed to be (large) categories. Then they observe that the category Set serves as a schizophrenic object for LEX and LFP. That is, the functors

LFP(−, Set): LFP ⟶ LEX^{op}, LEX(−, Set): LEX^{op} ⟶ LFP

form a dual 2–adjunction. Observe that, for every locally finitely presentable category K, we have

T h(K) ≅ LFP(K, Set).

In fact, every LFP–map F: K → Set is a right adjoint, thus is representable, and since F preserves directed colimits, it is represented by a finitely presentable object of K. Thus, T h(K) is equivalent, by Yoneda lemma, to LFP(K, Set).

Consequently, one can restrict the above functors to the full subcategory LeX of LEX over all essentially small left exact categories. One then obtains a dual 2–adjunction (claimed to be an equivalence — the Gabriel–Ulmer duality — in [?])

LFP(−, Set): LFP ⟶ LeX^{op}, LeX(−, Set): LeX^{op} ⟶ LFP

The trouble is that, in order to get from LeX to Lex, we have to choose a skeleton, and this cannot be performed functorially. However, we can choose (one of equivalent) bifunctors

Sk: LeX^{op} ⟶ Lex^{op}

such that SkA is a skeleton of A and, on morphisms, SkF (A) ≅ F (A) for each A in A. This leads to the following diagram

[figure: LeX(−, Set); LFP; LFP(−, Set); LeX^{op}; Sk; Lex; Lex^{op}]

Then Sk ∘ LFP(−, Set) is a biequivalence biadjoint to Lex.

Let us remark that the equivalence (I) in Section 1 was not precisely formulated (since Lex cannot be composed with T h(−) ≅ LFP(−, Set), and LeX(K, Set) will, for K not in Lex, only be a quasicategory equivalent to an LFP–object). More precisely should (I) state that

K ≅ Lex(Sk(T hK)).

Unfortunately, size is not the only trouble with the above description of Gabriel– Ulmer duality: though — neglecting size problems — the functors LFP(−, Set) and LeX(−, Set) are dually 2–adjoint with front and back adjunctions given by the equivalences (I) and (II) of Section 1, they do not form a (2–) equivalence, since these equivalences fail to be isomorphisms in LFP and LeX respectively.

References

[1] J. Adámek, How to sketch quasivarieties, J. Algebra, to appear

[2] J. Adámek, H. Herrlich, and J. Reiterman, Cocompleteness almost implies completeness, in: Proc. Conf. Categorical Topology. Prague 1988, World Scientific, Singapore 1989, 246–256

[3] J. Adámek, H. Herrlich, and G.E. Strecker, Abstract and Concrete Categories, Wiley Interscience, New York 1990

[4] J. Adámek and J. Rosický, Locally Presentable and Accessible Categories, Cambridge University Press 1994, Corrections at ftp.iti.cs.tu-bs.de

[5] M. Barr, Models of Horn theories, Contemp. Math. 92 (1989), 1–7

[6] F. Borceux, Handbook of Categorical Algebra, Cambridge University Press 1994, [7] W. Felscher, Kennzeichnung von primitiven und quasiprimitiven Kategorien

von Algebren, Arch. Math. (Basel) XIX (1968), 390–397

[8] P. Gabriel und F. Ulmer, Lokal präsentierbare Kategorien, Lecture Notes in Math. 221, Springer, Berlin - New York 1971

[9] J. R. Isbell, Subobjects, adequacy, completeness, and categories of algebras, Rozprawy Matem. 36, Warszawa, 1964

[10] O. Keane, Abstract Horn Theories, in: Model Theory and Topoi,Lecture Notes in Math. 445, Springer 1975, 15–50

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

[12] F. E. J. Linton, Some aspects of Equational Categories, in: Proc. Conf. Categorical Algebra. La Jolla 1965, Springer, Berlin–Heidelberg 1966, 84–94

[13] M. Makkai and A. M. Pitts, Some results on locally presentable categories, Trans. Amer. Math. Soc. 299 (1987), 473–496

[14] J. Rosický, Models of Horn theories revisited, J. Pure Appl. Algebra 92 (1994), 185–190

[15] R. Street, Fibrations in bicategories, Cahiers Topol. Géom. Différentielles Catégoriques XXI (1980), 111–160

Technical University of Braunschweig University of Bremen
P.O. Box 3329  P.O. Box 330440
38023 Braunschweig, Germany  28334 Bremen, Germany

adamek@iti.cs.tu-bs.de            porst@mathematik.uni-bremen.de