Theory and Applications of Categories, Vol. 2, No. 4, 1996, pp. 40– 54

AN ALGEBRAIC DESCRIPTION OF LOCALLY MULTIPRESENTABLE CATEGORIES

JIŘÍ ADÁMEK, JIŘÍ ROSICKÝ

Transmitted by Robert Paré

Abstract. Locally finitely presentable categories are known to be precisely the categories of models of essentially algebraic theories, i.e., categories of partial algebras whose domains of definition are determined by equations in total operations. Here we show an analogous description of locally finitely multipresentable categories. We also prove that locally finitely multipresentable categories are precisely categories of models of sketches with finite limit and countable coproduct specifications, and we present an example of a locally finitely multipresentable category not sketchable by a sketch with finite limit and finite colimit specifications.

Introduction.

We have shown in [AR_{1}] how each locally finitely presentable category K in the sense of [GU] can be described by an essentially algebraic theory. This means that there exists a (finitary, many-sorted) signature Σ = Σ_{t} ∪ Σ_{p} such that K is equivalent to the category of partial Σ-algebras A such that

(i) each operation σ_{A} with σ ∈ Σ_{t} is total (i.e., everywhere defined) (ii) for each σ ∈ Σ_{p} a finite set Def_{σ} of equations in signature Σ_{t} is given and

σ_{A}(a_{1} … a_{n}) is defined iff all equations of Def_{σ} are fulfilled in (a_{1}, …, a_{n}). and

(iii) a set of equations is given which all partial algebras of the given category satisfy. In the present paper we discuss locally finitely multipresentable categories, as introduced by Y. Diers [D]. Recall that a category is locally finitely multipresentable iff it has

(a) connected limits (or, equivalently, multicolimits)

Financial support of the Grant Agency of the Czech Republic under the grant no. 201/93/0950 is gratefully acknowledged.

Received by the Editors 11 May 1995, and in revised form 22 June 1996. Published on 5 July 1996. 1991 Mathematics Subject Classification: 18C99. Key words and phrases: locally multipresentable category, sketch. \begin{matrix}c \\ ◯ \end{matrix}Jiří Adámek, Jiří Rosický 1996. Permission to copy for private use granted.

and

(b) a set of finitely presentable objects A such that each object is a directed colimit

of A-objects. Examples: fields and homomorphisms, linearly ordered sets and strictly increasing maps. We describe a natural generalization of the concept of essentially algebraic theory, called essentially multialgebraic theory, and we show that a category is locally finitely multipresentable iff it is equivalent to the category of models of such a theory. Here we again work with partial algebras of signature Σ = Σ_{t} ∪Σ_{p} (where Σ_{t} are the total operations). But rather than having a finite set of equations for each element of Σ_{p}, we assume that Σ_{p} is decomposed into a doubly indexed union Σ_{p} = ⋃_{γ∈Γ} ⋃_{i∈I_{γ}} Σ_{γi} and for each γ ∈ Γ a

finite set Def_{γ} of equations in the signature Σ_{t} is given. In each model A the equations of Def_{γ} determine the domain of definition of all operations of ⋃_{i∈I_{γ}} Σ_{γi} as follows: if all

equations of Def_{γ} are fulfilled in (a_{1}, …, a_{n}) then there exists precisely one i ∈ I_{γ} such that σ_{A}(a_{1}, …, a_{n}) are defined for all σ ∈ Σ_{γi}, whereas all τ(a_{1}, …, a_{n}) for τ ∈ Σ_{γ} −Σ_{γi} are undefined.

We consider next sketches describing locally finitely multipresentable categories: we have shown in [AR_{1}] that a category is locally finitely multipresentable iff it can be sketched by a (finite limit, coproduct)-sketch. We now prove that, assuming the nonexistence of measurable cardinals, we can restrict ourselves to (finite limit, countable coproduct)-sketches. On the other hand, finite coproducts are not sufficient: a locally finitely multipresentable category K is exhibited which cannot be sketched by a (finite limit, finite coproduct)-sketch. Curiously, K can be sketched by a (finite limit, finite colimit)-sketch.

I. Essentially Multialgebraic Theory

Throughout the paper we work with partial Σ-algebras, where Σ is a many-sorted (finitary) signature. That is, if S is the set of sorts under consideration, then Σ is a set of operation symbols σ with prescribed arities

σ : s_{1} × ⋯ × s_{k} → s .

This means that a partial Σ-algebra A consists of an S-sorted set, i.e., a collection (A_{s})_{s∈S} of sets, together with partial maps

σ_{A} : A_{s_{1}} × ⋯ × A_{s_{k}} → A_{s}

for each σ : s_{1} ×⋯×s_{k} → s. A homomorphism from a partial Σ-algebra A into a partial Σ-algebra B is an S-sorted map h = (h_{s})_{s∈S} : A → B (i.e., h_{s} : A_{s} → B_{s} are maps) preserving the operations in the strong sense: whenever σ_{A}(a_{1}, …, a_{k}) is defined in A, it follows that σ_{B}(h_{s_{1}}(a_{1}), …, h_{s_{k}}(a_{k})) is defined in B and has the value h(σ_{A}(a_{1}, …, a_{k})). This results in the category PAlg Σ of partial algebras and homomorphisms.

A partial algebra is said to satisfy an equation provided that whenever a tuple is such that both sides of the equation are defined in it, then the results are equal.

Definition. By an essentially multialgebraic theory is understood a quadruple

T = (Σ, E, Γ, Def)

where Σ is a signature; E is a set of equations (in the signature Σ); Γ is a set of collections γ = (Σ_{γ_{i}})_{i∈I_{γ}} of finite subsets Σ_{γ_{i}} ⊆ Σ such that Σ_{γ_{i}} are

pairwise disjoint for γ ∈ Γ, i ∈ I_{γ}; Def is a map assigning to each γ ∈ Γ a finite set Def_{γ} of equations in the signature

Σ_{t} =^{def} Σ − ⋃_{γ∈Γ} ⋃_{i∈I_{γ}} Σ_{γ_{i}}

such that variables appearing in the equations of Def_{γ} are the same as those used by any operation of ⋃_{i∈I_{γ}} Σ_{γ_{i}}.

Remark. (1) The collection γ can also be empty, i.e., the case I_{γ} = ∅ is not excluded.

(2) The last clause concerning variables is only needed because the set ⋃_{i∈I_{γ}} Σ_{γ_{i}} can be infinite.

Definition. By a model of an essentially multialgebraic theory T we understand a partial Σ-algebra A such that

(1) A satisfies all equations in E;

(2) σ_{A} is a total operation for each σ ∈ Σ_{t};

(3) Given γ ∈ Γ, then whenever σ_{A}(a_{1}, …, a_{n}) is defined for some σ ∈ ⋃_{i∈I_{γ}} Σ_{γ_{i}} then

all equations of Def_{γ} hold in the n-tuple (a_{1}, …, a_{n});

(4) Given γ ∈ Γ, then when all equations of Def_{γ} hold in some n-tuple (a_{1}, …, a_{n}), then there exists a unique i_{0} ∈ I_{γ} such that σ_{A}(a_{1}, …, a_{n}) is defined for each σ ∈ Σ_{γ_{i_{0}}} .

The category of all models of T and homomorphisms is denoted by Mod T.

Remark. In case I_{γ} = ∅, a model A of T has the property that for no n-tuple of A all equations of Def_{γ} are satisfied.

Examples. (1) Fields. We start with the algebraic theory (Σ_{t}, E_{t}) of rings with a unit element. We introduce two unary operation symbols o and i (where o(x) will be defined precisely when x = 0 and i(x) is the inverse of x for all x ≠ 0). We put

Σ = Σ_{t} ∪ {o, i}
Γ = {γ, γ′}

where

γ = {{o}, {i}}
γ′ = ∅
Def_{γ} = ∅
Def_{γ′} = {0 = 1}
E = E_{t} ∪ E′

where E′ are the following four equations:

i(x) · x = 1
x · i(x) = 1
o(x) = 1
x · o(x) = 0 .

Thus, a model of this theory is a ring with a unit and with two partial unary operations such that for each element x exactly one of i(x) and o(x) is defined, and 0 nonequal 1. Moreover, if i(x) is defined then i(x) = x^{−1} and if o(x) is defined, then x = 0 (and o(0) = 1). This precisely describes all fields.

(2) Graphs. The category of graphs, i.e., sets with a binary relation, and homomorphisms is locally finitely presentable. Thus, it can be described by an essentially algebraic theory. The following theory was presented in [AR_{1}]: we have sorts edge and vertex. We put Σ = {σ, τ, ρ} where

σ, τ : edge → vertex

are the operations of source and target, respectively, and

ρ : edge × edge → edge

is an auxiliary operation to express the implication

σ(x) = σ(y) ∧ τ(y) = τ(y) → x = y .

Thus, Σ_{t} = {σ, τ} and

Def_{{ρ}} = {σ(x) = σ(y), τ(x) = τ(y)}

whereas E consists of two equations

ρ(x, y) = x (1) ρ(x, y) = y . (2)

A model of this theory is a pair of sets A_{edge}, A_{vertex} together with two operations

σ_{A}, τ_{A} : A_{edge} → A_{vertex}

satisfying the above implications. This can be identified with the graph on the set A_{vertex} with vertices p, q connected by an edge iff p = σ(x) and q = τ(x) for some x ∈ A_{edge}.

(3) Linearly ordered sets. We will now model the full subcategory of the category of graphs consisting of all strictly linearly ordered sets. We extend the above essentially algebraic theory as follows:

(i) Linearity. We introduce two binary operations α_{1}, α_{2} of arity

vertex × vertex → edge

and one binary operation α_{3} of arity

vertex × vertex → vertex.

We put

γ = {{α_{i}}}_{i=1,2,3}
Def_{γ} = ∅

and add the following equations to E:

(3)  σα_{1}(u, v) = u and τα_{1}(u, v)=v
(4)  σα_{2}(u, v) = v and τα_{2}(u, v)=u
(5)  α_{3}(u, v) = u and α_{3}(u, v) =v .

Thus, in a model A, given vertices u and v precisely one of α_{i}(u, v) is defined for i = 1, 2, 3. In case i = 1 we have u < v (since α_{1}(u, v) is the edge u → v), if i = 2 we have v < u, and in case i = 3 we have u = v.

(ii) Irreflexivity. We introduce γ′ = ∅ with

Def_{γ′} = {σ(x) = τ(x)} .

(iii) Transitivity. Choose an operation β : edge × edge → edge and put

γ′′ = {{β}}
Def_{γ′′} = {τ(x) = σ(y)}

and add to E the equations

σβ(x, y) = σ(x) and τβ(x, y) = τ(y) . (6)

The theory of signature

Σ^{∗} = {σ, τ, ρ, α_{1}, α_{2}, α_{3}, β}

with the equation (1)-(6) forming E, with

Γ = {γ, γ′, γ′′}

and with the above Def axiomatizes linearly ordered sets.

Remark. We recall from [AR_{1}] 4.30 a characterization of locally finitely multipresentable categories as precisely the ω-cone-orthogonality classes in locally finitely presentable categories:

Let ℒ be a locally finitely presentable category. For each set M of cones m = (D_{m} →^{d_{mj}} D_{mj})_{j∈J_{m}} in ℒ we denote by M^{⊥} the full subcategory of ℒ consisting of all objects L such that given m ∈ M then L is orthogonal to m, i.e., given a morphism f : D_{m} → L, there exists a unique j ∈ J_{m} such that f factorizes through d_{mj}, and also the factorization is unique (i.e., there exists a unique morphism f′ : D_{mj} → L with f = f′ · d_{mj}). We call M^{⊥} a cone-orthogonality class, and in case each D_{m} and D_{mj} is finitely presentable in ℒ , M^{⊥} is called an ω-cone-orthogonality class. The latter subcategories of ℒ are locally finitely multipresentable. Conversely, every locally finitely multipresentable category is equivalent to an ω-cone-orthogonality class of some locally finitely presentable category.

Proposition 1. For every essentially multialgebraic theory T T T the category Mod T is locally finitely multipresentable.

Proof. Denote by ℒ the full subcategory of PAlg Σ which consists of all partial Σalgebras which satisfy all equations in E and in which all Σ_{t}-operations are everywhere defined. It is easy to see that ℒ is a locally finitely presentable category. We are now going to present a set M of cones such that M^{⊥} is equal to Mod T.

For each element γ ∈ Γ we construct a cone (F_{γ} →^{f_{γ_{i}}} F_{γ_{i}})_{i∈I_{γ}} in ℒ as follows. Let x_{0}, …, x_{n−1} be all variables which appear in Def_{γ}. (Since the same variables appear in operations of ⋃_{i∈I_{γ}} Σ_{γ_{i}}, we can consider each of these operations σ as n-ary, and write

σ(x_{0}, …, x_{n−1}). This is done for technical convenience only since we can simply forget those variables on which σ does not depend.) Denote by F′_{γ} the free algebra generated by {x_{0}, …, x_{n−1}} in the equational class of all (total) Σ_{t}-algebras satisfying the equations of Def_{γ}. We consider F′_{γ} as a partial Σ-algebra by leaving all operations of Σ − Σ_{t} nowhere defined. Then F′_{γ} has a reflection in ℒ , say, r_{γ} : F′_{γ} → F_{γ}. Since both the set of generators and Def_{γ} are finite sets, it follows that F_{γ} is finitely presentable in ℒ . Next, for each i ∈ I_{γ} we form a free algebra F′_{γ_{i}} generated by {x_{0}, …, x_{n−1}} ∪ Σ_{γ_{i}} in the above equational class, and we consider F′_{γi} as a partial Σ-algebra as follows: for any σ ∈ Σ_{γ_{i}} we define

σ_{F′_{γ_{i}}} ([x_{0}], …, [x_{n−1}]) = [σ]

(where [ ] denotes the inclusion of generators to F′_{γ_{i}}) and leave σ_{F_{γ_{i}}} undefined in all other n-tuples; for any σ ∈ Σ − (Σ_{t} ∪ Σ_{γ_{i}}) the operation σ_{F_{γ_{i}}} is nowhere defined. Let r_{γ_{i}} : F′_{γ_{i}} → F_{γ_{i}} be a reflection of F′_{γ_{i}} in ℒ ; again, F_{γ_{i}} is finitely presentable in ℒ . The inclusion of the sets of generators extends to a Σ-homomorphism f′_{γ_{i}} : F′_{γ} → F′_{γ_{i}} whose reflections is denoted by f_{γ_{i}} : F_{γ} → F_{γ_{i}}. Put

m_{γ} = (F_{γ} →^{f_{γ_{i}}} F_{γ_{i}})_{i∈I_{γ}} .

If an algebra A ∈ ℒ is orthogonal to the cone m_{γ} then it has the property that (∗) for each n-tuple (a_{0}, …, a_{n−1}) in which all Def_{γ}-equations are satisfied there exists

precisely one i ∈ I_{γ} such that σ_{A}(a_{0}, …, a_{n−1}) is defined for each σ ∈ Σ_{γ_{i}}. In fact, since the n-tuple is satisfied by all equations of Def_{γ}, we have a unique Σhomomorphism h′ : F′_{γ} → A with h′([x_{k}]) = a_{k} for k = 0, …, n − 1; let h : F_{γ} → A be the Σ-homomorphism with h′ = h · r_{γ}. We have a unique i ∈ I_{γ} such that h factorizes through f_{γ_{i}}. Let us show that, then, σ_{A}(a_{0}, …, a_{n−1}) is defined for each σ ∈ Σ_{γ_{i}}. Given a Σ-homomorphism h̄ : F_{γ_{i}} → A with h = h̄ · f_{γ_{i}}, then since σ_{F′_{γ_{i}}} ([x_{0}], …, [x_{n−1}]) = [σ], and since f′_{γ_{i}}([x_{k}]) = [x_{k}] for k = 0, …, n − 1, we obtain

σ_{A}(h̄ · r_{γ_{i}}([x_{0}]), …, h̄ · r_{γ_{i}}([x_{n−1}])) = h̄ · r_{γ_{i}}([σ]),

thus

σ_{A}(a_{0}, …, a_{n−1}) = h̄ · r_{γ_{i}}([σ]) .

Conversely, if j ∈ I_{γ} has the property that all σ_{A}(a_{0}, …, a_{n−1}) with σ ∈ Σ_{γ_{i}} are defined, then i = j because the unique Σ_{t}-homomorphism h̄′ : F′_{γ_{i}} → A with h̄′([x_{k}]) = a_{k} and h̄′([σ]) = σ_{A}(a_{0}, …, a_{n}) for all σ ∈ Σ_{γ_{j}} then is, obviously, a homomorphism h̄′ : F′_{γ_{j}} → A of partial Σ-algebras. Let h̃ : F_{γ_{j}} → A be the Σ-homomorphism with h̄′ = h̃ · r_{γ_{j}}, then we have

h · r_{γ}([x_{k}]) = h̃ · r_{γ_{j}} · f′_{γ_{j}}([x_{k}]) for k = 0, …, n − 1,

thus h · r_{γ} = h̃ · r_{γ_{j}} · f′_{γ_{j}} = h̃ · f_{γ_{j}} · r_{γ}, from which it follows that h = h̃ · f_{γ_{j}}. Therefore, h factorizes through f_{γ_{j}}, which proves i = j. Thus, (∗) is established.

Conversely, let A ∈ ℒ have the property (∗), then A is orthogonal to m_{γ}. In fact, for each homomorphism h : F_{γ} → A the n-tuple a_{k} = h · r_{γ}([x_{k}]), k = 0, …, n − 1 satisfies all the equations of Def_{γ}. Thus, there is a unique i ∈ I_{γ} with all σ_{A}(a_{0}, …, a_{n−1}), σ ∈ Σ_{γ_{i}}, defined. It follows that h factorizes through f_{γ_{i}}: let h̄′ : F′_{γ_{i}} → A be the unique Σ_{t}-homomorphism with h̄′([x_{k}]) = a_{k} and h̄′([σ]) = σ_{A}(a_{0}, …, a_{n−1}) for all σ ∈ Σ_{γ_{i}}, then h̄′ = F′_{γ_{i}} → A is a homomorphism of P Alg Σ, thus, h̄′ = h̄·r_{γ_{i}} for a homomorphism h̄ : F_{γ_{i}} → A; it follows that h = h̄ · f_{γ_{i}}. Moreover, this factorization is unique: suppose h = h^{∗} · f_{γ_{i}}, then we prove h^{∗} · r_{γ_{i}} = h̄ · r_{γ_{i}} (which implies h^{∗} = h̄) by showing that these homomorphisms agree on all the generators of F′_{γ_{i}}. In fact,

h^{∗} · r_{γ_{i}}([x_{k}]) = h^{∗} · r_{γ_{i}} · f′_{γ_{i}}([x_{k}])
= h^{∗} · f_{γ_{i}} · r_{γ}([x_{k}])
= h · r_{γ}([x_{k}])
= a_{k}

and for [σ], where σ ∈ Σ_{γ_{i}}, the equality σ_{F′_{γ_{i}}} ([x_{0}], …, [x_{k−1}]) = [σ] implies

h^{∗} · r_{γ_{i}}([σ]) = σ_{A}(h^{∗} · r_{γ_{i}}([x_{0}]), … h^{∗} · r_{γ_{i}}([x_{n−1}]))
= σ_{A}(a_{0}, …, a_{n−1}) .

This shows that h factorizes uniquely through f_{γ_{i}}. Conversely, if h factorizes through f_{γ_{i}}, we show that j = i by verifying that σ_{A}(a_{0}, …, a_{n−1}) is defined for all σ ∈ Σ_{γ_{j}} – this is performed precisely as in the above proof that h^{∗} · r_{γ_{i}}([σ]) = σ_{A}(a_{0}, …, a_{n−1}).

We conclude that

Mod T = {m_{γ}; γ ∈ Γ}^{⊥} .

Since all domains and codomains appearing in m_{γ} are finitely presentable (for all γ ∈ Γ), we conclude by the preceding Remark that Mod T is locally finitely multipresentable.

Remark. Locally finitely multipresentable categories were also characterized in [AR_{1}] 4.30 as multireflective subcategories of Alg Σ (categories of total Σ-algebras) closed under directed colimits. More precisely, a category is locally finitely multipresentable iff there exists a finitary signature Σ and a full subcategory K of Alg Σ equivalent to the given category, which has the following properties:

(i) Every Σ-algebra A has a multireflection in K, i.e., a cone (A →^{r_{i}} A_{i})_{i∈I} such that all A_{i} lie in K and any homomorphism h : A → B with B in K factorizes through a unique r_{i}, i ∈ I, and the factorization h′ with h = h′r_{i} is also unique;

(ii) K is closed under directed colimits, or, equivalently, a Σ-algebra K lies in K whenever it is orthogonal to the multireflection of each finitely presentable Σ-algebra A. If (A →^{r_{i}} A_{i})_{i∈I} is such a multireflection, then it is easy to verify that A_{i} are also finitely presentable for all i.

Theorem 1. A category is locally finitely multipresentable iff it is equivalent to the category of models of some essentially multialgebraic theory.

Proof. Due to the preceding Proposition and Remark, it is sufficient to show that any full subcategory K of Alg Σ satisfying (i) and (ii) above is equivalent to Mod T for some essentially multialgebraic theory T. The signature Σ^{∗} of the theory T we define now will be an extension of the given signature Σ (where the operations of Σ will be precisely the total operations, Σ = Σ_{t}^{∗}). Let (A_{i})_{i∈I} be a set of representatives of all finitely presentable Σ-algebras w.r.t. isomorphism. For each i ∈ I we have, since A_{i} is finitely presentable, a finite set of variables x_{1}, …, x_{k} (of sorts t_{1}, …, t_{k}, respectively) and a finite set called Def_{i} of equations in those variables such that A_{i} is presented by those variables and equations. That is, A_{i} can be identified with the quotient algebra of the free Σ-algebra F (x_{1}, …, x_{k}) generated by {x_{1}, …, x_{k}} modulo the congruence ∼_{i} generated by Def_{i}. We also form a multireflection (A_{i} →^{m_{ij}} A_{ij})_{j∈J_{i}} and, since A_{ij} is finitely presentable, we can choose a finite set G_{ij} of generators of A_{ij} for each j ∈ J_{i} (containing m_{ij}([x_{n}]), n = 1, …, k where [x_{n}] is the congruence class of x_{n} in A_{i} = F (x_{1}, …, x_{k})/ ∼_{i}).

We now extend Σ to Σ^{∗} by adding, for each i ∈ I, j ∈ J_{i} and each element a of sort s(a) in A_{ij}, an operation

σ_{ija} : t_{1} × ⋯ × t_{k} → s(a) .

(The informal idea of σ_{ija} in models K is the following: the defining equations Def_{i} guarantee that if σ_{ija} (x_{1}, …, x_{k}) is defined, then the interpretation of the variables x_{1}, …, x_{k} yields a homomorphism h : A_{i} → K. Then h factors as h = h′ m_{ij} and the result of σ_{ija} will be the image of a under h′.) Thus, we put Σ^{∗} = Σ∪{σ_{ija}; i ∈ I, j ∈ J_{i} and a ∈ G_{ij}} and

Σ_{ij}^{∗} = {σ_{ija}; a ∈ G_{ij}}.

We defined Def_{i} above for each i ∈ I. It remains to define the set E of equations in the signature Σ^{∗}. These will be of two types:

(a) x_{n} = σ_{ijx_{n}^{∗}}(x_{1}, …, x_{k}) for all i ∈ I, j ∈ J_{i}, n = 1, …, k where x_{1}, …, x_{k} are the variables of the given presentation of A_{i}, and x_{n}^{∗} = m_{ij}([x_{n}]).

(b) Since A_{ij} is generated by G_{ij} = {g_{1}, …, g_{m}}, we can choose, for each element a ∈ A_{ij}, a Σ-term ρ′_{a}(x_{1}, …, x_{m}) such that (ρ′_{a})_{A_{ij}}(g_{1}, …, g_{m}) = a; we denote by ρ_{a} = ρ′_{a}(σ_{ijg_{1}}, …, σ_{ijg_{m}}) the corresponding Σ^{∗}-term. For each τ ∈ Σ and each instance of computation of τ_{A}, say, τ_{A}(a_{1}, …, a_{n}) = a, we add to E the equation

τ(ρ_{a_{1}}, …, ρ_{a_{n}}) = ρ_{a}.

We thus defined an essentially multialgebraic theory

T = (Σ^{∗}, E, Γ, Def)

where Γ = {{Σ_{ij}^{∗}}_{j∈J_{i}}}_{i∈I}. We will prove that K is equivalent to Mod T. For each Σalgebra K in K we define a partial Σ^{∗}-algebra H(K) as follows. Given i ∈ I and j ∈ J_{i} then for a ∈ G_{ij} we define (σ_{ija})_{K} in a tuple (b_{1}, …, b_{k}) iff there exists a homomorphism h : A_{ij} → K with (h · m_{ij})_{t_{n}}([x_{n}]) = b_{n}, and then

(σ_{ija})_{K}(b_{1}, …, b_{k}) = h_{s(a)}(a) .

Let us verify H(K) is a model of T. It satisfies the equations of E:

(a) If (σ_{ijx_{n}^{∗}})_{K} is defined in (b_{1}, …, b_{k}), then we have h : A_{ij} → K with (h · m_{ij})_{t_{n}}([x_{n}]) = b_{n} and

(σ_{ijx_{n}^{∗}})_{K}(b_{1}, …, b_{n}) = h_{t_{n}}(x_{n}^{∗}) = h_{t_{n}}(m_{ij})_{t_{n}}([x_{n}]) = b_{n} .

(b) The equations τ_{A}(ρ_{a_{1}}, …, ρ_{a_{n}}) = ρ_{a} are satisfied since h is a Σ-homomorphism. Furthermore, if all equations of Def_{i} are satisfied in (b_{1}, …, b_{k}), then the homo-

morphism f : F (x_{1}, …, x_{k}) → K determined by f_{t_{n}}(x_{n}) = b_{n}, n = 1, …, k, factorizes through A_{i} = F (x_{1}, …, x_{k})/ ∼_{i}, i.e., we have a homomorphism g : A_{i} → K with g_{t_{n}}([x_{n}]) = b_{n}. Since K ∈ K, there exists a unique j such that g = h m_{ij} for a unique Σ-homomorphism h : A_{ij} → K. Since (h · m_{ij})_{t_{n}}([x_{n}]) = b_{n}, we conclude that (σ_{ija})_{K}(b_{1}, …, b_{k}) is defined for each a ∈ G_{ij}. Conversely, given j′ such that (σ_{ij′a′})_{K}(b_{1}, …, b_{k}) is defined for each a′ ∈ G_{ij′}, it follows that a homomorphism h′ : A_{ij′} → K exists with h′ · m_{ij′} = h · m_{ij} – consequently, j = j′ and h = h′. (In fact, define h′ by h′_{s(a)}(a) = σ_{ij′a′}(b_{1}, …, b_{k}); the equations in (b) guarantee that h′ is a Σ-homomorphism and those of (a) guarantee h = h′ · m_{ij′}.)

We conclude that H(K) is a model of T. We obtain a functor

H : K → Mod T

defined on homomorphisms by H(h) = h. To show that H is an equivalence of categories, it is sufficient to verify that whenever a partial Σ^{∗}-algebra B is a model of T then its Σ-reduct B_{0}, i.e., the Σ-algebra obtained by forgeting the operations in Σ^{∗} −Σ, lies in K – it then follows that B = H(B_{0}). We can assume, without loss of generality, that B_{0} is a finitely presentable Σ-algebra. In fact, since B is a model of T, for each Σ-subalgebra C of B_{0} the restriction of the partial operations of B to C defines a partial Σ^{∗}-algebra C′ which is also a model of K. Suppose that we know already that this implies that C (the reduct of C′) lies in K, then B_{0} also lies in K since K is closed under directed colimits (and B_{0} is a directed colimit of all such C.) Thus, B_{0} can be assumed to be A_{i} for some i ∈ I. The equations of Def_{i} are all satisfied in the tuple ([x_{1}], …, [x_{k}]) of B, thus, there exists j ∈ J_{i} such that (σ_{ija})_{B} are defined in that tuple for each element a of G_{ij} (because B is a model of T) and thus, also (ρ_{a})_{B}([x_{1}], …, [x_{n}]) are defined. This allows us to define

k(a) = (σ_{ija})_{B}([x_{1}], …, [x_{k}]) for all a ∈ G_{ij} .

The equations of E guarantee that k is a Σ-homomorphism k : A_{ij} → B satisfying

k · m_{ij} = id_{A_{i}} .

In fact, let τ_{A_{ij}}(a_{1}, …, a_{n}) = a for some τ : s_{1} × ⋯ × s_{n} → s in Σ, then from the equation in (b) above we conclude that

k(a) = k((ρ′_{a})_{A_{ij}}(g_{1}, …, g_{m}))
= (ρ′_{a})_{B}(k(g_{1}), …, k(g_{m}))
= (ρ′_{a})_{B}((σ_{ijg_{1}})_{B}([x_{1}], …, [x_{k}]), …, (σ_{ijg_{m}})_{B}([x_{1}], …, [x_{k}])
= (ρ_{a})_{B}([x_{1}], …, [x_{k}])
= τ_{B}((ρ_{a_{1}})_{B}([x_{1}], …, [x_{k}]), …, (ρ_{a_{n}})_{B}([x_{1}], …, [x_{k}]))
= τ_{B}((ρ′_{a_{1}})_{B}((σ_{ijg_{1}})_{B}([x_{1}], …, [x_{k}]), …, (σ_{ijg_{n}})_{B}([x_{1}], …, [x_{k}])), …)
= τ_{B}((ρ′_{a_{1}})_{B}(k(g_{1}), …, k(g_{m})), …, (ρ_{a_{n}})_{B}(k(g_{1}), …, k(g_{m}))
= τ_{B}(k(a_{1}), …, k(a_{n})),

thus, k is a homomorphisms. To verify k · m_{ij} = id_{A_{i}}, it is thus sufficient to prove that k · m_{ij} ([x_{n}]) = [x_{n}] for all n = 1, …, k, and this follows from the equation (a). This shows that m_{ij} is an isomorphism: from

(m_{ij} · k) · m_{ij} = m_{ij} = id_{A_{ij}} · m_{ij}

and from A_{ij} ∈ K we get, by the definition of multireflection, that m_{ij} · k = id_{A_{ij}}, thus k = m_{ij}^{−1}. This proves that B_{0} = A_{i} ≅ A_{ij} lies in K. Consequently, H : K → Mod T is an equivalence of categories.

Remark. The above theorem has an immediate generalization to infinitary algebras; given a regular cardinal λ, we can introduce essentially multialgebraic theories of λ-ary partial algebras – here Def_{γ} is a set of less than λ equations and Γ is a collection of subsets of Σ of cardinality less than λ, otherwise the definition is quite analogous. A category is locally λ-multipresentable iff it is equivalent to the category of models of some essentially multialgebraic λ-ary theory.

II. Finitary Sketches for Locally Multipresentable categories

Recall that a sketch is a quadruple 𝒮 = (A, L, C, σ) where A is a small category, L and C are sets of diagrams in A and σ assigns to each diagram D ∈ L a cone σ(D) and to each diagram D ∈ C a cocone σ(D). A model of 𝒮 is a functor F : A → Set such that for each diagram D ∈ L the image of σ(D) under F is a limit of F D and for each diagram D ∈ C the image of σ(D) is a colimit of F D.

A category is said to be sketchable by 𝒮 if it is equivalent to the full subcategory of Set^{A} consisting of all models of 𝒮 . It is proved in [AR_{1}] 4.32 that a category is locally finitely multipresentable iff it is sketchable by a (finite limit, coproduct)-sketch (i.e. a sketch with all diagrams in L finite and all diagrams in C discrete). We will now present an example showing that it is, in general, not sufficient to work with finite limits and finite coproducts:

Example. (4) The following locally finitely multipresentable category is not sketchable by a (finite limit, finite coproduct) - sketch.

Objects: 0 and all primes p > 2.

Morphisms: (a) a unique morphism 0 → p for each object p (b) hom (p, p) is the cyclic group of order p

(c) no other morphisms except those in (a), (b).

This category has only trivial directed colimits, thus, each object is finitely presentable. It has connected limits: an equalizer of any pair of distinct morphisms in hom (p, p) is 0 → p, analogously with pullbacks. Thus, the category is locally finitely multipresentable.

Any (finite limit, finite coproduct)-sketchable category K an be axiomatized by a first-order theory. That is, there exists a many-sorted, finitary signature Σ and a theory T of the first-order logic of Σ-structures such that K is equivalent to the category of all T -models and Σ-homomorphisms – see [MP]. Thus, it is sufficient to prove that our category K cannot be axiomatized. In fact, suppose that E is an equivalence between K and the category Mod T of all models of T. It is well-known that Mod T is closed under ultraproducts in the category Str Σ of all Σ-structures. Let U be a free ultrafilter on the set of all objects of K. Since the ultraproduct ∏_{U} E(p) lies in Mod T, there exists an object q with E(q) isomorphic to ∏_{U} E(p). To obtain the desired contradiction, we will show that the above ultraproduct has infinitely many endomorphisms, although hom (E(q), E(q)) ≅ hom (q, q) is finite. In fact, for each element f of the product ∏_{p∈K} hom (p, p) we obtain an endomorphism f′ of the ultraproduct, defined by

f′([x_{p}]) = [Ef_{p}(x_{p})], and for two such elements f, g we have f′ = g′ iff U contains the set {p; f_{p} = g_{p}}. It is sufficient to choose an infinite set M ⊆ ∏ hom (p, p) such that for f, q ∈ M with f ≠ q the set of all p′s with f_{p} = g_{p} is always finite, then {f′; f ∈ M} is an infinite set of endomorphisms of ∏_{U} E(p). This proves that K is not axiomatizable in first-order logic.

Theorem 2. Assuming the non-existence of measurable cardinals, each locally finitely multipresentable category can be sketched by a (finite limit, countable coproduct)-sketch.

Proof. Let K be a locally finitely multipresentable category. By [AR_{1}] 4.32 there exists a (finite limit, coproduct)-sketch 𝒮 with K equivalent to Mod 𝒮 . Let α be a cardinal such that each coproduct-specification of 𝒮 has less than α objects. We will construct a (finite limit, countable coproduct)-sketch 𝒮 ^{∗} with Mod 𝒮 ≅ Mod 𝒮 ^{∗}.

Since no cardinal is measurable, for each cardinal β there exists a basic theory T_{β} which is one-sorted, has constants c_{i} (i ∈ β) in the signature, and has, up to isomorphism, a unique model B such that (c_{i})_{B} ≠ (c_{j})_{B} for i ≠ j and {(c_{i})_{B}}_{i∈β} is the underlying set of B. In fact, T_{β} is explicitely described in [AJMR]. By inspecting that description, it can be easily seen that all disjunctions used in all sentences of T_{β} are actually disjoint. This means that whenever p ∨ q was used we can write, instead,

(p∨q)∧(p∧q → ⊥) and where ⋁_{n∈ω} p_{n} was used, we can write ⋁_{n∈ω} p_{n}∧ ⋀_{n≠m}(p_{n}∧p_{m} → ⊥).

Here ⊥ denotes the formula false. It means that T_{β} uses only

(a) finite conjunctions

(b) finite quantifications

and

(c) finite or countable disjunctions which are disjoint.

We now apply the procedure of [MP] 3.2.5 associating with each basic theory a sketch 𝒮 with Mod 𝒮 equivalent to the category of all models of that theory. Let 𝒮 _{β} be the sketch associated to T_{β}. Due to (a)–(c), 𝒮 _{β} is a (finite limit, countable coproduct)-sketch. 𝒮 _{β} contains the object A_{β} describing the unique sort, and each of the constants c_{i} gives us a morphism c_{i}^{β} : 1_{β} → A_{β} such that the (essentially unique) model of 𝒮 _{β} has the above properties.

II. The rest of the proof is analogous to that of Theorem 12 of [AJMR]. Let K be a locally finitely multipresentable category. There exists a (finite limit, coproduct)-sketch 𝒮 sketching K, see [AR_{1}] 4.32. For each uncountable coproduct-specification

(B_{i} →^{b_{i}} B)_{i∈β} (β a uncountable cardinal)

of 𝒮 we take a copy of the above sketch 𝒮 _{β} and we denote by𝒮̄ the disjoint union of the sketch 𝒮 and all these sketches 𝒮 _{β}. Let 𝒮 ^{∗} be the sketch we obtain from𝒮̄ by deleting all of the uncountable coproduct specifications and, instead, by adding to 𝒮̄

(a) a formal new morphism f : B → A_{β}

(b) the following pullback-specifications for all i ∈ β

B_{i}  \overline{b_{i}} \overline{>} B

t_{i}∨  ∨f

1_{α}  \overline{c_{i}^{α}} \overline{>} A_{β}

where t_{i} = t_{β} · f · b_{i}.

It is easy to see that the sketches 𝒮 ,𝒮̄, and 𝒮 ^{∗} have equivalent categories of models.

Remark. The statement of the Theorem 2 is actually logically equivalent to the nonexistence of measurable cardinals. That is, assuming that a measurable cardinal λ exists, there are locally finitely multipresentable categories not sketchable by (finite limit, countable coproduct)-sketch. In fact, not sketchable by λ-ary sketches, i.e., sketches in which all diagrams in L ∪ C have sizes smaller than λ:

Example. (5) If λ is a measurable cardinal, the following category is locally finitely multipresentable, but it is not sketchable by a λ-ary sketch:

Objects: all ordinals i < λ.

Morphisms: (a) a unique morphism 0 → i for each object i (b) hom (i, i) is a group of cardinality ℵ_{i} for all i > 0 (c) no other morphisms except those in (a), (b).

The proof of local finite multipresentability is analogous to that in Example (4). Also the proof that the category is not sketchable by a λ-ary sketch is quite analogous: by [MP], any λ-ary sketchable category can be axiomatized by infinitary first-order theory of the λ-ary logic L_{λ,λ}. Thus, if our category K would be sketchable by a λ-ary sketch, there would exist an equivalence E between K and Mod T for some first-order theory in a λ-ary signature Σ. Then E(K) would be closed in Mod Σ under ultraproducts over all λ-complete ultrafilters. Since λ is measurable, there exists a nontrivial λ-complete ultrafilter U on the set of all objects of K. The proof is then concluded by showing that the ultraproduct ∏_{U} E(i) has ℵ_{λ} pairwise distinct endomorphisms (whereas hom (i, i) has cardinality ℵ_{i} < ℵ_{λ} for each object i of K).

Remark. The category K of Example (4) has the following remarkable property: we have seen above that

(a) K is sketchable by a (finite limit, coproduct)-sketch and

(b) K is not sketchable by a (finite limit, finite coproduct)-sketch. We now show that, nevertheless,

(c) K is sketchable by a (finite limit, finite colimit)-sketch. In fact, as proved in Theorem 3 of [AJMR], for (c) it is sufficient to find an axiomatization of K by a σ-coherent theory in the logic L_{ω_{1},ω}. A σ-coherent theory consists of sentences

(∀x_{1}, …, x_{n})(φ → ψ)

where φ and ψ are formulas built from atomic formulas by finite conjunctions, countable disjunctions, and finite existential quantification. Now observe that K is equivalent to the category of all graphs (i.e. Σ-structures where Σ consists of one binary relation symbol R) isomorphic either to G_{0}, the empty graph, or G_{p}, the circuit of length p (with vertices 0, 1, …, p − 1 and edges i → i + 1 for all i < p − 1 and p − 1 → 0) for all primes p > 2. The latter category has the following σ-coherent axiomatization in which R^{2}(x, y) is a shorthand for (∃z)(R(x, z) ∧ R(z, y)), analogously with R^{3}, R^{4}, …:

(1) (∀x)(∃!y)R(x, y)

(2) (∀y)(∃!x)R(x, y)

(3) (∀x)(R^{nm}(x, x) → R^{n}(x) ∨ R^{m}(x))

where n, m are arbitrary natural numbers

(4) (∀x)(∃y)((x = y) → ⊥)

(5) (∀x, y) ⋁_{n∈ω} R^{2m}(x, y) (R^{0}(x, y) means x = y).

In fact, each G_{n} is a model of (1)–(5). Let G ≠ G_{0} be a model of (1)–(5). By (5), each pair of vertices can be connected by a path of even length. By (1) and (2), G is a circuit or an infinite path, but (5) excludes the latter and forces the length P of the circuit to be larger than 2. Finally, by (3) we know that p is a prime. Thus, G ≅ G_{p}, and G_{p} is a model of (1)–(5).

References

[AJMR] J. Adámek, P. T. Johnstone, J. Makowsky, J. Rosický, Finitary sketches, to appear in J. Symb. Logic.

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

Press, Cambridge 1994.

[AR_{2}] J. Adámek and J. Rosický, Finitary sketches and finitely accessible categories, Math. Str. in

Comp. Sci., accepted for publication.

[D] Y. Diers, Catégories localement multiprésentables, Arch. Math. 34 (1980), 344–356.

[GU] P. Gabriel and F. Ulmer, Lokal Präsentierbare Kategorien, Lect. Notes in Math. 221, Springer-Verlag, Berlin 1971.

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

J. Adámek J. Rosický Technical University Braunschweig Masaryk University Postfach 3329 Janáčkovo nám. 2a, 662 95 Brno 38023 Braunschweig, Germany Czech Republic

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

This article may be accessed via WWW at http://www.tac.mta.ca/tac/ or by anonymous ftp at ftp://ftp.tac.mta.ca/pub/tac/html/volumes/1996/n4/n4.{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 and Postscript format. Details will be e-mailed to new subscribers and are available by WWW/ftp. 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 LaTeX 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 URL http://www.tac.mta.ca/tac/ or by anonymous ftp from ftp.tac.mta.ca in the directory pub/tac/info. 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@triples.math.mcgill.ca Lawrence Breen, Université de Paris 13: breen@dmi.ens.fr Ronald Brown, University of North Wales: r.brown@bangor.ac.uk Jean-Luc Brylinski, Pennsylvania State University: jlb@math.psu.edu Aurelio Carboni, University of Genoa: carboni@vmimat.mat.unimi.it P. T. Johnstone, University of Cambridge: ptj@pmms.cam.ac.uk G. Max Kelly, University of Sydney: kelly m@maths.su.oz.au Anders Kock, University of Aarhus: kock@mi.aau.dk F. William Lawvere, State University of New York at Buffalo: mthfwl@ubvms.cc.buffalo.edu Jean-Louis Loday, Université de Strasbourg: loday@math.u-strasbg.fr Ieke Moerdijk, University of Utrecht: moerdijk@math.ruu.nl Susan Niefield, Union College: niefiels@gar.union.edu Robert Paré, Dalhousie University: pare@cs.dal.ca Andrew Pitts, University of Cambridge: ap@cl.cam.ac.uk Robert Rosebrugh, Mount Allison University: rrosebrugh@mta.ca Jiri Rosicky, Masaryk University: rosicky@math.muni.cz James Stasheff, University of North Carolina: jds@charlie.math.unc.edu Ross Street, Macquarie University: street@macadam.mpce.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 Sydney: walters b@maths.su.oz.au R. J. Wood, Dalhousie University: rjwood@cs.da.ca