Theory and Applications of Categories, Vol. 8, No. 1, 2001, pp. 1–15.

n-PERMUTABLE LOCALLY FINITELY PRESENTABLE CATEGORIES

MARINO GRAN AND MARIA CRISTINA PEDICCHIO

ABSTRACT. We characterize n-permutable locally finitely presentable categories Lex[C^{op}, Set] by a condition on the dual of the essentially algebraic theory C^{op}. We apply these results to exact Maltsev categories as well as to n-permutable quasivarieties and varieties.

Introduction

In recent years there has been a considerable interest in expressing properties of an essentially algebraic category (i.e. a locally finitely presentable category) in terms of properties of the corresponding essentially algebraic theory. From this point of view, complete answers have been given with respect to basic properties such as regularity, exactness, extensivity, cartesian closedness and so on (see [8], [9], [4] and [7]). In this note we analyse the condition of n-permutability of the composition of equivalence relations for a regular locally finitely presentable category K = Lex[C^{op}, Set].

It is known [5] that n-permutability can be equivalently stated by saying that, for any reflexive relation R, the corresponding generated equivalence relation \overline{R} is given by a finite construction, more precisely \overline{R} = R ∘ R^{o} ∘ R ∘ R^{o} ∘ … (n − 1)-times. So, if we want to characterize n-permutability of K in terms of a corresponding condition on the essentially algebraic theory C^{op}, or more simply on its dual C (where C is considered as a dense subcategory of K), we must interpret such a finiteness condition in C. The answer to this problem is given in theorem 2.5, where we show that K is (n+1)-permutable (n ≥ 1) if and only if C is weakly regular and certain relations R_{n}^{X,C}, defined for any reflexive graph X in C and C ∈ C, are transitive. The formal definition of R_{n}^{X,C} simply corresponds to the syntactic interpretation in C of the following relation: if X: \xymatrix{X_{1} \ar[r] \ar[r] & X_{0}} denotes a reflexive graph in C and I: \xymatrix{I \ar[r] \ar[r] & X_{0}} is its regular image in Lex[C^{op}, Set], two parallel

arrows \xymatrix{C \ar[r]^{f_{0}} \ar[r]_{f_{1}} & X_{0}} are R_{n}^{X,C}-related if and only if (f_{0}, f_{1}) factorizes through the n-iterated

composite I ∘ I^{o} ∘ I ∘ I^{o} ∘ … (n-times). Notice that in C we must now consider reflexive graphs instead of reflexive relations; in fact conditions on reflexive relations do not suffice to force permutability in K. This theorem admits interesting applications in the case of an exact K and mainly in the case of quasivarieties and varieties. In these two last contexts the existence of a projective cover of C makes the syntactic conditions on C much simpler: indeed, for any P regular projective, the functor Hom(P, −): C → Set will preserve images and generated equivalences.

Received by the editors 1999 November 15 and, in revised form, 2001 January 11.

Transmitted by Peter Johnstone. Published on 2001 January 29.

2000 Mathematics Subject Classification: 18C05, 18C10, 18C35, 08C15.

Key words and phrases: Locally finitely presentable categories, n-permutable and Maltsev varieties, quasivarieties.

\begin{matrix}c \\ ◯ \end{matrix} Marino Gran and Maria Cristina Pedicchio, 2001. Permission to copy for private use granted.

Acknowledgement: The authors would like to thank Francis Borceux for his useful comments on a earlier version of this article.

1. Preliminaries on regular n-permutable categories

In this section we fix the notations and recall some properties of regular categories. A category A is regular [3] if it is finitely complete, every kernel pair has a coequalizer and regular epimorphisms are stable under pullbacks. If A is regular, any arrow f: A → B can be factored as f = i ∘ p with p a regular epimorphism and i a monomorphism. A regular category A is exact when any equivalence relation is effective (a kernel pair).

A relation R from A to B will be denoted by (r_{0}, r_{1}): R ↣ A × B; for a relation

R on an object A we shall also write \xymatrix{R \ar[r]^{r_{0}} \ar[r]_{r_{1}} & A} . The set of equivalence relations on

an object A ∈ A is denoted by Eq(A). For any relation (r_{0}, r_{1}): R ↣ A × B we can consider the opposite relation R^{o} given by (r_{1}, r_{0}): R ↣ B × A. Given two relations (r_{0}, r_{1}): R ↣ A × B and (s_{0}, s_{1}): S ↣ B × C in a regular category A, the composite S ∘ R is defined as the image of the morphism (r_{0} ∘ u_{0}, s_{1} ∘ u_{1}): R ×_{B} S → A × C:

\xymatrix{ &  & R ×_{B} S \ar@{-->}[dl]^{u_{0}} \ar@{-->}[dr]_{u_{1}} \\  & R \ar[dl]^{r_{0}} \ar[dr]_{r_{1}} &  & S \ar[dl]^{s_{0}} \ar[dr]_{s_{1}} \\ A &  & B &  & C}

In this section we always assume that the category A is regular: this assumption will assure that the composition of relations is associative. If R and S are equivalence relations on an object A, we have the increasing sequence

R ⊆ R ∘ S ⊆ R ∘ S ∘ R ⊆ R ∘ S ∘ R ∘ S ⊆ …

which we denote by

(R, S)_{1} ⊆ (R, S)_{2} ⊆ (R, S)_{3} ⊆ (R, S)_{4} ⊆ …

The smallest equivalence relation containing both R and S, denoted by R ∨ S (when it exists), contains all the terms of this sequence, and these terms are all different in general. If there is an n ≥ 2 for which the relation (R, S)_{n} is an equivalence relation, then R ∨ S = (R, S)_{n}.

1.1. Definition. A regular category A is n-permutable (n ≥ 2) if for any R, S ∈ Eq(A) and A ∈ A, it holds (R, S)_{n} = (S, R)_{n}.

Of course, if n = 2 we get the notion of Maltsev category: this notion was introduced in [6] as a weakening of the notion of abelian category. Since the Maltsev property can be expressed without the assumption of regularity of the category A, we shall adopt the simpler and classical

1.2. Definition. A category A is Maltsev if, for any A ∈ A, any reflexive relation R ↣ A × A on A is an equivalence relation.

The equivalence between the Maltsev axiom, the 2-permutability of the composition of equivalence relations and two other nice properties is recalled in the following

1.3. Theorem. [6] Let A be a regular category. The following statements are equivalent:

1. A is a Maltsev category

2. A is 2-permutable

3. for any A ∈ A any reflexive relation R on A is transitive

4. for any A ∈ A and for any R, S ∈ Eq(A), we have R ∘ S = R ∨ S

1.4. Examples. A classical result of Maltsev [12] asserts that a finitary variety is Maltsev precisely when its theory contains a ternary operation p(x, y, z) satisfying the axioms p(x, y, y) = x, p(x, x, y) = y; for instance in the variety of groups such a term p(x, y, z) is given by xy^{−1}z. Among Maltsev varieties are then those of groups, abelian groups, modules over a fixed ring, rings, commutative rings, associative algebras and Lie algebras. The variety of quasi-groups is also Maltsev, as is the variety of Heyting algebras. There are non-varietal examples of exact Maltsev categories: any abelian category is exact Maltsev, as is the dual of the category of sets and, more generally, the dual of any topos. Finally, the category of topological groups is regular Maltsev [5].

It is interesting to know that the properties in theorem 1.3 remain equivalent in the n-permutable case (n ≥ 2): indeed, we have the following

1.5. Theorem. [5] Let A be a regular category. The following statements are equivalent:

1. for any reflexive relation R on an object A ∈ A the relation (R, R^{o})_{n−1} is an equivalence relation

2. A is n-permutable

3. for any reflexive relation R on an object A ∈ A the relation (R, R^{o})_{n−1} is transitive

4. for any A ∈ A and for any R, S ∈ Eq(A), we have (R, S)_{n} = R ∨ S 1.6. Examples. Hagemann and Mitschke [11] proved that a finitary variety is n-per-mutable if and only if there exist n + 1 ternary terms p_{0}(x, y, z), p_{1}(x, y, z), …, p_{n}(x, y, z) satisfying

p_{0}(x, y, z) = x
p_{i}(x, x, y) = p_{i+1}(x, y, y) for 0 ≤ i ≤ n − 1
p_{n}(x, y, z) = z.

This result clearly includes Maltsev theorem, this latter being the special case where n = 2. The property of (n+1)-permutability can be shown to be strictly weaker than the one of npermutability for each n ≥ 2. In particular there are examples of 3-permutable varieties that fail to be Maltsev as, for instance, the variety of generalized right complemented semigroups: these algebras have two binary operations · and ∗ satisfying

x · (x ∗ y) = y · (y ∗ x)
x · (y ∗ y) = x.

In this case the theorem of Hagemann and Mitschke can be applied by choosing p_{1}(x, y, z) = x · (y ∗ z) and p_{2}(x, y, z) = z · (y ∗ x).

We recall that 3-permutable categories are called Goursat categories [5]. The property of 3-permutability, unlike 4-permutability, is strong enough to force the modularity of the lattice Eq(A) of equivalence relations on any object A of the category.

2. Regular locally finitely presentable categories

A locally finitely presentable category K (see [10] or [2]) is a cocomplete category which admits a small set S of finitely presentable objects such that any object K ∈ K is a filtered colimit of objects of S. Any such category is equivalent to a category Lex[C^{op}, Set] of finite limit preserving functors from a small finitely complete category C^{op} to the category of sets. Via the Yoneda embedding sending an object C ∈ C to the functor Hom(−, C) the category C is a full subcategory of Lex[C^{op}, Set] and the objects of C form a family of dense generators. The dual category of C is called the essentially algebraic theory, while Lex[C^{op}, Set] is the category of models of the theory. Many properties of a locally finitely presentable category can be expressed just in terms of its essentially algebraic theory C and various results in this direction can be found in the literature, for instance in [7], [8],[9] and [4]. In this paper we are interested in the property of n-permutability of the composition of the equivalence relations; the regularity of Lex[C^{op}, Set] will be always required in order to express this kind of property.

Regular locally finitely presentable categories have been characterized in [7] as categories of finite limit preserving functors from the dual of a finitely cocomplete “weakly regular” category to the category of sets. We recall the definition:

Theory and Applications of Categories, Vol. 8, No. 1 5

2.1. Definition. [7] A category C is weakly regular if every commutative diagram

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

in C in which f is a regular epi factors through a commutative diagram

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

where \overline{f} is a regular epi.

Observe that any regular category is weakly regular: moreover one has the following 2.2. Theorem. [7] Let C be a category with finite colimits. The following conditions are equivalent:

1. Lex[C^{op}, Set] is regular

2. C is weakly regular

In order to express our main results we now introduce two important notions. The first one is the notion of n-iterated graph: 2.3. Definition. Let X

\xymatrix{X_{1} \ar[r]^{x_{0}} \ar[r]|{x_{1}} & X_{0} \ar[l]_{e}}

be a reflexive graph, x_{0} ∘ e = 1_{X_{0}} = x_{1} ∘ e. A graph K

\xymatrix{K_{1} \ar[r]^{k_{0}} \ar[r]_{k_{1}} & X_{0}}

is a n-iterated of X (where n ≥ 1) if there exist n arrows h_{0}, h_{1}, …, h_{n−1} from K_{1} to X_{1} such that x_{0} ∘ h_{0} = k_{0}, x_{1} ∘ h_{0} = x_{1} ∘ h_{1}, x_{0} ∘ h_{1} = x_{0} ∘ h_{2}, …, x_{i} ∘ h_{n−2} = x_{i} ∘ h_{n−1}, x_{j} ∘ h_{n−1} = k_{1} with i = 1 and j = 0 if n is even, while i = 0 and j = 1 if n is odd.

The conditions above can be expressed by the commutativity of the diagram below (in which we assume that n is odd)

[figure: K_{1}; h_{n−1}; h_{2}; h_{1}; h_{0}; k_{1}; k_{0}; X_{1}; x_{0}; x_{1}; X_{1}; x_{1}; x_{0}; X_{1}; x_{0}; x_{1}; X_{1}; x_{0}; x_{1}; X_{0}; X_{0}; X_{0}; X_{0}; X_{0}; X_{0}]

By means of the notion of n-iterated graph, we now define a relation on the set Hom(C, X_{0}):

2.4. Definition. Let X

\xymatrix{X_{1} \ar[r]^{x_{0}} \ar[r]|{x_{1}} & X_{0} \ar[l]_{e}}

be a reflexive graph and n ≥ 1. Two arrows \xymatrix{C \ar[r]^{f_{0}} \ar[r]_{f_{1}} & X_{0}} are defined to be in the relation

R_{n}^{X,C}, and we write f_{0}R_{n}^{X,C}f_{1}, if there exists a factorisation of the graph \xymatrix{C \ar[r]^{f_{0}} \ar[r]_{f_{1}} & X_{0}}

through a regular quotient \xymatrix{B \ar[r]^{b_{0}} \ar[r]_{b_{1}} & X_{0}} of a n-iterated graph \xymatrix{K \ar[r]^{k_{0}} \ar[r]_{k_{1}} & X_{0}} of X:

\xymatrix{K \ar[r]^{k_{0}} \ar[r]_{k_{1}} \ar@{->>}[d]_{β} & X_{0} \\ B \ar[ur]^{b_{0}} \ar[ur]_{b_{1}} & C \ar[l]^{γ} \ar[u]^{f_{0}} \ar[u]_{f_{1}}}

where

b_{0} ∘ γ = f_{0}, b_{1} ∘ γ = f_{1}, b_{0} ∘ β = k_{0}, b_{1} ∘ β = k_{1},

and β is a regular epi.

Remark that the relation R_{n}^{X,C} is always reflexive: indeed, for any arrow f_{0} : C → X_{0} the arrow e ∘ f_{0} : C → X_{1} shows that f_{0}R_{n}^{X,C}f_{0}.

2.5. Theorem. Let C be a category with finite colimits. The following conditions are equivalent (n ≥ 1):

1. Lex[C^{op}, Set] is regular (n + 1)-permutable

2. C is weakly regular and the relation R_{n}^{X,C} is transitive for any reflexive graph X in C and C ∈ C.

Proof. We first prove that R_{n}^{X,C} = Hom(C, (I, I^{o})_{n}) for any C ∈ C and any reflexive

graph \xymatrix{X_{1} \ar[r]^{x_{0}} \ar[r]_{x_{1}} & X_{0}} in C with regular image in Lex[C^{op}, Set] given by \xymatrix{I \ar[r]^{^{\overline{x}^{0}}} \ar[r]_{_{\overline{x}_{1}}} & X_{0}} .

For this, we consider (f_{0}, f_{1}) in R_{n}^{X,C} and we’re going to show that (f_{0}, f_{1}) belongs to Hom(C, (I, I^{o})_{n}). By assumption there is a factorisation as in the diagram

\xymatrix{K \ar[r]^{k_{0}} \ar[r]_{k_{1}} \ar@{->>}[d]_{β} & X_{0} \\ B \ar[ur]^{b_{0}} \ar[ur]_{b_{1}} & C \ar[l]^{γ} \ar[u]^{f_{0}} \ar[u]_{f_{1}}}

where \xymatrix{K \ar[r]^{k_{0}} \ar[r]_{k_{1}} & X_{0}} is a n-iterated of the reflexive graph \xymatrix{X_{1} \ar[r]^{x_{0}} \ar[r]_{x_{1}} & X_{0}} . Remark then that

any n-iterated \xymatrix{K \ar[r]^{k_{0}} \ar[r]_{k_{1}} & X_{0}} factors through the limit (L; l_{0}, l_{1}, …, l_{n−1})

[figure: L; l_{n−1}; l_{2}; l_{1}; l_{0}; X_{1}; x_{0}; x_{1}; X_{1}; x_{1}; x_{0}; X_{1}; x_{0}; x_{1}; X_{1}; x_{0}; x_{1}; X_{0}; X_{0}; X_{0}; X_{0}; X_{0}; X_{0}]

over the diagram

[figure: X_{1}; x_{0}; x_{1}; X_{1}; x_{1}; x_{0}; X_{1}; x_{0}; x_{1}; X_{1}; x_{0}; x_{1}; X_{0}; X_{0}; X_{0}; X_{0}; X_{0}; X_{0}]

(in the diagrams above we have assumed that n is odd). This limit can be clearly obtained by iterated pullbacks in Lex[C^{op}, Set]. There is then an arrow η: K → L verifying, in particular, x_{0} ∘ l_{0} ∘ η = k_{0} and x_{1} ∘ l_{n−1} ∘ η = k_{1}.

The regularity of Lex[C^{op}, Set] implies that the induced arrow ϵ from (L; l_{0}, l_{1}, …, l_{n−1}) to the limit (M; m_{0}, m_{1}, …, m_{n−1})

[figure: M; m_{n−1}; m_{2}; m_{1}; m_{0}; I; _{\overline{x}_{0}}; _{\overline{x}_{1}}; I; _{\overline{x}_{1}}; _{\overline{x}_{0}}; I; _{\overline{x}_{0}}; _{\overline{x}_{1}}; I; _{\overline{x}_{0}}; _{\overline{x}_{1}}; X_{0}; X_{0}; X_{0}; X_{0}; X_{0}; X_{0}]

over the diagram

[figure: I; _{\overline{x}_{0}}; _{\overline{x}_{1}}; I; _{\overline{x}_{1}}; _{\overline{x}_{0}}; I; _{\overline{x}_{0}}; _{\overline{x}_{1}}; I; _{\overline{x}_{0}}; _{\overline{x}_{1}}; X_{0}; X_{0}; X_{0}; X_{0}; X_{0}; X_{0}]

is a regular epi. By recalling the definition of the composite of relations in a regular category, one then has a regular epi q ∘ ϵ: L ↠ (I, I^{o})_{n} as in the diagram

[figure: L; ϵ; M; (\overline{x}_{0}∘m_{0},\overline{x}_{1}∘m_{n−1}); q; X_{0} × X_{0}; (I, I^{o})_{n}; (i_{0},i_{1})]

The arrow q ∘ ϵ ∘ η: K → (I, I^{o})_{n} is such that

i_{0} ∘ q ∘ ϵ ∘ η = \overline{x}_{0} ∘ m_{0} ∘ ϵ ∘ η = x_{0} ∘ l_{0} ∘ η = k_{0} = b_{0} ∘ β

and similarly i_{1} ∘ q ∘ ϵ ∘ η = b_{1} ∘ β. The commutativity of the diagram

[figure: K; β; q∘ϵ∘η; B; (b_{0},b_{1}); (I, I^{o})_{n}; (i_{0},i_{1}); X_{0} × X_{0}]

gives a unique σ: B → (I, I^{o})_{n} with σ ∘ β = q ∘ ϵ ∘ η and (i_{0}, i_{1}) ∘ σ = (b_{0}, b_{1}). It follows then that i_{0} ∘ σ ∘ γ = b_{0} ∘ γ = f_{0} and i_{1} ∘ σ ∘ γ = b_{1} ∘ γ = f_{1}. This shows that (f_{0}, f_{1}) ∈ Hom(C, (I, I^{o})_{n}).

Let us then prove that (f_{0}, f_{1}) ∈ Hom(C, (I, I^{o})_{n}) implies (f_{0}, f_{1}) ∈ R_{n}^{X,C}. Indeed, let α: C → (I, I^{o})_{n} be an arrow with i_{0} ∘ α = f_{0} and i_{1} ∘ α = f_{1}. Keeping in mind that the regular epi q ∘ ϵ: L → (I, I^{o})_{n} is a directed colimit of regular epis (q ∘ ϵ)_{j}: L_{j} → [(I, I^{o})_{n}]_{j} in C (see for instance [1]) and that C is finitely presentable, we obtain an arrow α_{j} as in the diagram

\xymatrix{L \ar@{->>}[r]^{q∘ϵ} & (I, I^{o})_{n} \ar[r]^{i_{0}} \ar[r]_{i_{1}} & X_{0} \\ L_{j} \ar@{->>}[r]_{(q∘ϵ)_{j}} \ar[u]^{n_{j}} & [(I, I^{o})_{n}]_{j} \ar[u]^{m_{j}} & C \ar[u]^{f_{0}} \ar[u]_{f_{1}} \ar[ul]^{α} \ar[l]^{α_{j}}}

with α = m_{j} ∘ α_{j}. Since the graph \xymatrix{L_{j} \ar[r]^{i_{0}∘q∘ϵ∘n_{j}} \ar[r]_{i_{1}∘q∘ϵ∘n_{j}} & X_{0}} is a n-iterated of \xymatrix{X_{1} \ar[r]^{x_{0}} \ar[r]_{x_{1}} & X_{0}} , it follows

that f_{0}R_{n}^{X,C}f_{1}.

1. ⇒ 2. By theorem 2.2 we know that C is weakly regular. The relation (I, I^{o})_{n} is transitive in Lex[C^{op}, Set] by assumption (and by theorem 1.5): this implies that Hom(C, (I, I^{o})_{n}) = R_{n}^{X,C} is a transitive relation in the category of sets.

2. ⇒ 1. By theorem 2.2, the category Lex[C^{op}, Set] is regular. By theorem 1.5 we just

need to show that any reflexive relation \xymatrix{A \ar[r]^{d} \ar[r]_{c} & A_{0}} is such that (A, A^{o})_{n} is transitive.

Since any reflexive relation in Lex[C^{op}, Set] can be written as a filtered colimit of reflexive graphs in C and a filtered colimit of transitive relations is a transitive relation, then it

suffices to check the property for a reflexive graph in C. Let \xymatrix{X_{1} \ar[r]^{x_{0}} \ar[r]_{x_{1}} & X_{0}} be a reflexive

graph and let \xymatrix{I \ar[r]^{^{\overline{x}^{0}}} \ar[r]_{_{\overline{x}_{1}}} & X_{0}} denote its regular image in Lex[C^{op}, Set]. We must prove that

\xymatrix{(I, I^{o})_{n} \ar[r]^{i_{0}} \ar[r]_{i_{1}} & X_{0}} is transitive. We recall that the category C is a dense generator in

K = Lex[C^{op}, Set]: this means that the inclusion of K into Set^{C^{op}} (via the restriction of the Yoneda embedding) is fully faithful. From this it follows that the relation (I, I^{o})_{n} ↣ X_{0} × X_{0} is transitive in K if and only if the relation Hom(C, (I, I^{o})_{n}) ↣ Hom(C, X_{0}) × Hom(C, X_{0}) is transitive in Set for any C ∈ C. Since R_{n}^{X,C} is exactly Hom(C, (I, I^{o})_{n}), the result follows from R_{n}^{X,C} transitive.

2.6. Corollary. Let C be a category with finite colimits. The following conditions are equivalent:

1. Lex[C^{op}, Set] is regular Maltsev

2. C is weakly regular and the relation R_{1}^{X,C} is transitive for any reflexive graph X in C.

3. Exact locally finitely presentable categories

We now turn to the problem of characterizing the locally finitely presentable categories that are exact Maltsev. From this point of view the property described in the following definition will have an essential role:

3.1. Definition. A category C with coequalizers is pro-maltsev if for any reflexive graph X

\xymatrix{X_{1} \ar[r]^{x_{0}} \ar[r]|{x_{1}} & X_{0} \ar[l]_{e}}

and for any pair of arrows f_{0}, f_{1} : C → X_{0} with q ∘ f_{0} = q ∘ f_{1}, where q is the coequalizer of x_{0} and x_{1}, (f_{0}, f_{1}) is in the relation R_{1}^{X,C}, i.e. there exists a factorization of C through

a quotient of a 1-iterated \xymatrix{K \ar[r]^{k_{0}} \ar[r]_{k_{1}} & X_{0}} of X:

\xymatrix{K \ar[r]^{k_{0}} \ar[r]_{k_{1}} \ar@{->>}[d]_{β} & X_{0} \\ B \ar[ur]^{b_{0}} \ar[ur]_{b_{1}} & C \ar[l]^{γ} \ar[u]^{f_{0}} \ar[u]_{f_{1}}}

We first remark that this property is stronger than the one expressed by the transitivity of the relation R_{1}^{X,C}:

3.2. Lemma. If C is a pro-maltsev category, then the relation R_{1}^{X,C} is transitive, for any reflexive graph X in C and any C ∈ C.

Proof. Let X

\xymatrix{X_{1} \ar[r]^{x_{0}} \ar[r]|{x_{1}} & X_{0} \ar[l]_{e}}

be a reflexive graph and let (f_{0}, f_{1}) ∈ R_{1}^{X,C} and (f_{1}, f_{2}) ∈ R_{1}^{X,C}; this means that there exist two configurations in C as in the diagrams

\xymatrix{K \ar[r]^{k_{0}} \ar[r]_{k_{1}} \ar@{->>}[d]_{β} & X_{0} & K′ \ar[r]^{k′_{0}} \ar[r]_{k′_{1}} \ar@{->>}[d]_{β′} & X_{0} \\ B \ar[ur]^{b_{0}} \ar[ur]_{b_{1}} & C \ar[l]^{γ} \ar[u]^{f_{0}} \ar[u]_{f_{1}} & B′ \ar[ur]^{b′_{0}} \ar[ur]_{b′_{1}} & C \ar[l]^{γ′} \ar[u]^{f_{1}} \ar[u]_{f_{2}}}

where both \xymatrix{K \ar[r]^{k_{0}} \ar[r]_{k_{1}} & X_{0}} and \xymatrix{K′ \ar[r]^{k′_{0}} \ar[r]_{k′_{1}} & X_{0}} are 1-iterated of the reflexive graph \xymatrix{X_{1} \ar[r]^{x_{0}} \ar[r]_{x_{1}} & X_{0}} .

If q: X_{0} ↠ Q denotes the coequalizer of x_{0} and x_{1}, then

q ∘ b_{0} ∘ β = q ∘ b_{1} ∘ β,

hence, since β is a regular epi,

q ∘ b_{0} ∘ γ = q ∘ b_{1} ∘ γ,

so that q ∘ f_{0} = q ∘ f_{1}. Similarly q ∘ f_{1} = q ∘ f_{2} and then q ∘ f_{0} = q ∘ f_{2}: by the pro-maltsev assumption f_{0}R_{1}^{X,C}f_{2}, proving that the relation R_{1}^{X,C} is transitive.

3.3. Lemma. Let Lex[C^{op}, Set] be an exact category. If the relation R_{1}^{X,C} is transitive for any reflexive graph X in C, then C is pro-maltsev.

Proof. By corollary 2.6 the category Lex[C^{op}, Set] is exact Maltsev. With the same notations as in the lemma 3.2, if there are two arrows f_{0}, f_{1} : C → X_{0} such that q ∘ f_{0} =

q ∘ f_{1}, these must factorize through the regular image \xymatrix{I \ar[r]^{^{\overline{x}^{0}}} \ar[r]_{_{\overline{x}_{1}}} & X_{0}} in Lex[C^{op}, Set] of the

reflexive graph \xymatrix{X_{1} \ar[r]^{x_{0}} \ar[r]_{x_{1}} & X_{0}} , since this relation is necessarily the kernel pair of q. Hence

(f_{0}, f_{1}) is in R_{1}^{X,C} = Hom(C, I).

We then get the following

3.4. Proposition. Let C be a category with finite colimits. The following conditions are equivalent:

1. Lex[C^{op}, Set] is exact Maltsev

2. C is weakly regular and pro-maltsev

Proof. 1. ⇒ 2. It follows by corollary 2.6 and lemma 3.3.

2. ⇒ 1. By corollary 2.6 and lemma 3.2 one knows that Lex[C^{op}, Set] is regular Maltsev. By using

the pro-maltsev property it is possible to show that, given a reflexive graph \xymatrix{X_{1} \ar[r]^{x_{0}} \ar[r]_{x_{1}} & X_{0}}

in C, its image factorisation \xymatrix{I \ar[r]^{^{\overline{x}^{0}}} \ar[r]_{_{\overline{x}_{1}}} & X_{0}} in Lex[C^{op}, Set] is an effective equivalence relation.

Indeed, one can easily prove that the pro-maltsev property implies that the kernel pair

in Lex[C^{op}, Set] of the coequalizer of the arrows x_{0} and x_{1} factorizes through \xymatrix{I \ar[r]^{^{\overline{x}^{0}}} \ar[r]_{_{\overline{x}_{1}}} & X_{0}} :

this certainly suffices to conclude that I is a kernel pair in Lex[C^{op}, Set].

Now, for any equivalence relation \xymatrix{A \ar[r]^{d} \ar[r]_{c} & A_{0}} in Lex[C^{op}, Set], write it as a filtered

colimit of reflexive graphs in C: since the regular image of any of these reflexive graphs

is an effective equivalence relation, we get that \xymatrix{A \ar[r]^{d} \ar[r]_{c} & A_{0}} is an effective equivalence

relation.

More generally, one can define the notion of pro-n-permutable category:

3.5. Definition. A category C is pro-n-permutable (n ≥ 2) if for any reflexive graph X

\xymatrix{X_{1} \ar[r]^{x_{0}} \ar[r]|{x_{1}} & X_{0} \ar[l]_{e}}

and for any pair of arrows f_{0}, f_{1} : C → X_{0} with q ∘ f_{0} = q ∘ f_{1}, where q is the coequalizer of x_{0} and x_{1}, (f_{0}, f_{1}) is in the relation R_{n−1}^{X,C}.

By adopting the same technique as above, theorem 2.5 allows to generalize these results to the n-permutable case (n ≥ 2):

3.6. Proposition. Let C be a category with finite colimits. The following conditions are equivalent:

1. Lex[C^{op}, Set] is exact n-permutable

2. C is weakly regular and pro-n-permutable

3.7. Remark. The notion of weakly regular pro-n-permutable category is clearly stronger than the one of pro-exact category in the sense of [7]: to see it, one just needs to remark that any n-iterated graph (in our sense) of a reflexive and symmetric graph X is an “iteration” of X as defined in that paper. Observe that pro-exactness corresponds, with the same notations as in definition 3.5, to

q ∘ f_{0} = q ∘ f_{1}  ⇒  ∃n ≥ 1, (f_{0}, f_{1}) ∈ R_{n}^{X,C}.

The pro-n-permutability of a weakly regular category C can be accordingly thought as a synthetic way to express at the same time the “exactness” of the category Lex[C^{op}, Set] and the fact that the join of two equivalence relations in Lex[C^{op}, Set] can be obtained in a “finite number of steps”. This last condition precisely expresses the n-permutability of the composition of equivalence relations.

4. Quasivarieties and varieties

By a quasivariety is meant a class of many-sorted finitary algebras that 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). Any quasivariety is a locally finitely presentable category; in [1] Adámek and Porst characterized (the dual of) those essentially algebraic theories whose models form a quasivariety as being the finitely cocomplete categories which have enough regular projectives:

4.1. Theorem. [1] Let C be a category with finite colimits. The following conditions are equivalent:

1. Lex[C^{op}, Set] is a quasivariety

2. C has enough regular projectives

Any quasivariety is a regular category: it seems then natural to investigate the condition of n-permutability for quasivarieties. For this, we begin with the following

4.2. Definition. Let A be a regular category and n ≥ 1. A n-pseudo transitive relation

is a reflexive graph \xymatrix{X_{1} \ar[r]^{x_{0}} \ar[r]_{x_{1}} & X_{0}} such that its image factorisation \xymatrix{I \ar[r]^{^{\overline{x}^{0}}} \ar[r]_{_{\overline{x}_{1}}} & X_{0}} has the

property that (I, I^{o})_{n} is a transitive relation.

Of course, if A is regular Maltsev, any reflexive graph is a 1-pseudo transitive relation, since I = (I, I^{o})_{1} is an equivalence relation. We then define a notion of n-permutable object:

4.3. Definition. An object P in a category C is n-permutable (n ≥ 2) if the functor Hom(P, −) sends reflexive graphs to (n − 1)-pseudo transitive relations (in Set).

We can then give our characterization of n-permutable quasivarieties:

4.4. Proposition. Let C be a category with finite colimits and n ≥ 2. The following conditions are equivalent:

1. Lex[C^{op}, Set] is a n-permutable quasivariety

2. C has enough n-permutable regular projectives

Proof. 1. ⇒ 2. By theorem 4.1 the category C has enough regular projectives. It suffices

to prove that, for any regular projective P and for any reflexive graph X : \xymatrix{X_{1} \ar[r]^{x_{0}} \ar[r]_{x_{1}} & X_{0}} ,

the relation

(J, J^{o})_{n−1} ↣ Hom(P, X_{0}) × Hom(P, X_{0})

is transitive (where \xymatrix{J \ar[r]^{j_{0}} \ar[r]_{j_{1}} & Hom(P, X_{0})} is the image factorisation in Set of the reflexive

graph \xymatrix{Hom(P, X_{1}) \ar[r] \ar[r] & Hom(P, X_{0})} ). Since P is regular projective then (J, J^{o})_{n−1} =

Hom(P, (I, I^{o})_{n−1}), where \xymatrix{I \ar[r]^{^{\overline{x}^{0}}} \ar[r]_{_{\overline{x}_{1}}} & X_{0}} is the image of X in Lex[C^{op}, Set]. The result then

follows from theorem 2.5 and R_{n−1}^{X,P} = Hom(P, (I, I^{o})_{n−1}).

2. ⇒ 1. By theorems 2.5 and 4.1 we just have to prove that the relation R_{n−1}^{X,C} is transitive for any reflexive graph X in C and C ∈ C. Since C has a regular projective cover by assumption, it suffices to check that R_{n−1}^{X,P} is transitive for P regular projective. This follows by R_{n−1}^{X,P} = Hom(P, (I, I^{o})_{n−1}) = (J, J^{o})_{n−1} and P is n-permutable.

As a corollary of this result, we now give a characterization of n-permutable finitary varieties. For this, we first recall the notion of effective projective object, due to Pedicchio and Wood:

4.5. Definition. An object P in a category C is an effective projective object if the functor Hom(P, −) preserves coequalizers of reflexive graphs.

This notion plays an essential role in a recent work [14] by Pedicchio and Wood. In this paper the authors characterized (the dual of) those essentially algebraic theories whose models form a finitary variety of algebras: these are precisely the finitely cocomplete categories which have enough effective regular projectives:

4.6. Theorem. [14] Let C be a category with finite colimits. The following conditions are equivalent:

1. Lex[C^{op}, Set] is a variety

2. C has enough effective regular projectives

This theorem, together with proposition 4.4, gives the following corollary:

4.7. Corollary. Let C be a category with finite colimits. The following conditions are equivalent:

1. Lex[C^{op}, Set] is a n-permutable variety

2. C has enough n-permutable effective regular projectives

References

[1] J. Adámek and H. Porst, Algebraic Theories of Quasivarieties, Journal of Algebra, 208, 379-398, 1998.

[2] J. Adámek and J. Rosický, Locally presentable and accessible categories, Lond. Math. Soc. Lect. Notes, 189, Cambridge University Press, 1994.

[3] M. Barr, Exact Categories, LNM, 236, Springer-Verlag, Berlin, 1971, 1-120.

[4] F. Borceux and M.C. Pedicchio, Left exact presheaves on a small pretopos, J. Pure Appl. Algebra, 135, 9-22, 1999.

[5] A. Carboni, G.M. Kelly and M.C. Pedicchio, Some remarks on Maltsev and Goursat categories, Appl. Categ. Structures, 1, 1993, 385-421.

[6] A. Carboni, J. Lambek and M.C. Pedicchio, Diagram chasing in Mal’cev categories, J. Pure Appl. Algebra, 69, 1990, 271-284.

[7] A. Carboni, M.C. Pedicchio and J. Rosický, Syntactic characterizations of various classes of locally presentable categories, to appear.

[8] B. Day and R. Street, Localisation of locally presentable categories, J. Pure Appl. Algebra, 58, 1989, 227-233.

[9] B. Day and R. Street, Localisation of locally presentable categories II, J. Pure Appl. Algebra, 63, 1990, 225-229.

[10] P. Gabriel and F. Ulmer, Lokal präsentierbare Kategorien, LNM 221, Springer-Verlag, Berlin 1971.

[11] J. Hagemann and A. Mitschke, On n-permutable congruences, Algebra Universalis, 3, 1973, 8-12.

[12] A.I. Mal’cev, On the general theory of algebraic systems, Mat. Sbornik N. S., 35, 1954, 3-20.

[13] M.C. Pedicchio and R. Wood, A simple characterization of theories of varieties, to appear.

[14] M.C. Pedicchio and R. Wood, A note on effective projectives, J. Pure Appl. Algebra, to appear.

[15] J.D.H. Smith, Mal’cev Varieties, Springer Lecture Notes in Mathematics 554, Berlin 1976.

Chargé de recherches du F.N.R.S. Département de Mathématique - UCL Chemin du Cyclotron, 2 1348 Louvain-la-Neuve, Belgium and Dipartimento di Scienze Matematiche Università degli studi di Trieste Via Valerio, 12 34127 Trieste, Italy

Email: gran@agel.ucl.ac.be and pedicchi@univ.trieste.it

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

mous ftp at ftp://ftp.tac.mta.ca/pub/tac/html/volumes/8/n1/n1.{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 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: carboni@fis.unico.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 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