Theory and Applications of Categories, Vol. 13, No. 3, 2004, pp. 41–60.

ON EXTENSIONS OF LAX MONADS

Dedicated to Aurelio Carboni on the occasion of his sixtieth birthday

MARIA MANUEL CLEMENTINO AND DIRK HOFMANN

Abstract. In this paper we construct extensions of Set-monads – and, more generally, of lax Rel-monads – into lax monads of the bicategory Mat(V) of generalized V-matrices, whenever V is a well-behaved lattice equipped with a tensor product. We add some guiding examples.

Introduction

Extensions of Set-monads into lax monads in bicategories of generalized matrices have been used recently to study categories of lax algebras [5, 10, 9], generalizing Barr’s [1] description of topological spaces as lax algebras for the ultrafilter monad and Lawvere’s [16] description of metric spaces as V-categories for V the extended real half-line. The recent interest in this area had its origin in the use of the description of topological spaces via ultrafilter convergence to characterize special classes of continuous maps, such as effective descent morphisms, triquotient maps, exponentiable maps, quotient maps and local homeomorphisms [18, 15, 4, 7, 14, 6].

In this area, one of the difficulties one has to deal with is the construction of lax extensions of Set-monads into a larger bicategory. Contrarily to the extensions studied so far, with ad-hoc constructions, here we present a uniform construction of an extension of a Set-monad, satisfying (BC), into a lax monad of the bicategory Mat(V) of generalized V-matrices. This construction consists of three steps: first we apply Barr’s extension of the monad into the category Rel of relations (in Section 1) and then we extend this into Mat(2^{V^{op}}) and finally into Mat(V) (as described in Section 3). This construction includes, for instance, Clementino-Tholen construction of an extension of the ultrafilter monad in case V is a lattice (Example 6.4). The techniques used here can be used also to extend lax monads from Rel into Mat(V). We find particularly interesting the presentation of the Hausdorff metric on subsets of a metric space as an extension of the lax powerset monad (Example 6.3).

The authors acknowledge partial financial assistance by Centro de Matemática da Universidade de Coimbra/FCT and Unidade de Investigação e Desenvolvimento Matemática e Aplicações da Universidade de Aveiro/FCT.

Received by the editors 2003-09-29 and, in revised form, 2004-08-13.

Published on 2004-12-05.

2000 Mathematics Subject Classification: 18D05, 18C20, 18D10.

Key words and phrases: relation, lax algebra, lax monad.

\begin{matrix}c \\ ◯ \end{matrix} Maria Manuel Clementino and Dirk Hofmann, 2004. Permission to copy for private use granted.

1. From Set to Rel

1.1. The 2-category Rel. We recall that Rel has as objects sets and as morphisms r : X ↛ Y relations r ⊆ X × Y (or equivalently r : X × Y → 2). With the hom-sets Rel(X, Y) partially ordered by inclusion, Rel is a 2-category.

Using its natural involution ( )^{∘}, that assigns to each relation r : X ↛ Y its inverse r^{∘} : Y ↛ X, and the embedding Set ↪ Rel, it is easily seen that every relation r can be written as g · f^{∘}:

[figure: X; r; Y; r; f; g]  (1)

where f and g are the projections.

1.2. Barr’s extension. In order to extend a Set-monad (T, η, μ) into Rel, Barr [1] defined first \overline{T} (f^{∘}) := (T f)^{∘} for any map f, and then made use of the factorization (1) of the relation r : X ↛ Y to define

\overline{T} r := T g · \overline{T} f^{∘},

that does not depend on the chosen factorization and extends naturally to 2-cells. Hence the following diagram

\xymatrix{Set \ar@{^{(}->}[d] \ar[r]^{T} & Set \ar@{^{(}->}[d] \\ Rel \ar[r]^{\overline{T}} & Rel}

is commutative.

Barr proved that \overline{T} : Rel → Rel is an op-lax functor and that the natural transformations η and μ become op-lax in Rel; that is:

• \overline{T} (r · s) ≤ \overline{T} r · \overline{T} s for any pair of composable relations r, s;

• for every r : X ↛ Y, one has

[figure: X; ≤; η_{X}; r; T X; \overline{T} r; T^{2}X; ≤; μ_{X}; \overline{T}^{2}r; T X; \overline{T} r; Y; η_{Y}; T Y; T^{2}Y; μ_{Y}; T Y.]

1.3. The role of the Beck-Chevalley Condition. As Barr pointed out, this extension may fail to be a functor. The missing inequality depends on the behaviour of the functor T : Set → Set: it holds if and only if T satisfies the Beck-Chevalley Condition (BC), that is, if (T f)^{∘} · T g = T k · (T h)^{∘} for every pullback diagram

\xymatrix{W \ar[r]^{k} \ar[d]_{h} & X \ar[d]^{f} \\ Z \ar[r]^{g} & Y}

in Set. (Under the Axiom of Choice, (BC) is equivalent to the preservation of weak pullbacks.)

Theorem. For a functor T : Set → Set, the following assertions are equivalent:

i. There is a (unique) 2-functor \overline{T} : Rel → Rel, preserving the involution, that extends T;

ii. T satisfies the Beck-Chevalley Condition.

We also have:

Proposition. Given functors S, T : Set → Set satisfying (BC) and a natural transformation φ : S → T, the following assertions are equivalent:

i. \overline{φ} : \overline{S} → \overline{T} is a natural transformation;

ii. for every map f : X → Y, the Set-diagram

\xymatrix{SX \ar[r]^{φ_{X}} \ar[d]_{Sf} & T X \ar[d]^{T f} \\ SY \ar[r]^{φ_{Y}} & T Y}

satisfies (BC), i.e. (T f)^{∘} · φ_{Y} = φ_{X} · (Sf)^{∘}.

2. The extended setting: Mat(V) and lax monads

Throughout we will be concerned with the construction of lax extensions of a Set-monad to more general 2-categories. In this section we describe the 2-categories as well as the lax axioms for a monad we will deal with.

2.1. The category of V-matrices. We consider a complete and cocomplete lattice V as a category, and assume that it is symmetric monoidal-closed, with tensor product ⊗ and unit k_{V}. We denote its initial and terminal objects by ⊥_{V} and ⊤_{V}, respectively. The 2-category Mat(V) has as objects sets and as 1-cells r : X ↛ Y V-matrices, that is, maps r : X × Y → V; given r, r′ : X ↛ Y, there is a (unique) 2-cell r → r′ if, for every (x, y) ∈ X × Y, r(x, y) ≤ r′(x, y) in V. Composition of 1-cells r : X ↛ Y and s : Y ↛ Z is given by matrix multiplication, i.e.

s · r(x, z) = ⋁_{y∈Y} r(x, y) ⊗ s(y, z),

for every x ∈ X and z ∈ Z. Further information about this category can be found in [2] and [10].

Rel is a crucial example of a 2-category of this sort, obtained when V = 2 = {⊥, ⊤}, with ⊗ = ∧. The monoidal map 2 ↪ V, with ⊥ ↦ ⊥_{V} and ⊤ ↦ k_{V} naturally gives rise to an embedding Rel ↪ Mat(V) whenever ⊥_{V} ≠ k_{V}, condition assumed from now on. By relation in Mat(V) we mean any V-matrix with entries ⊥_{V} and k_{V}; that is, any image of a relation by this embedding.

2.2. Lax monads. Here we propose a definition of lax monad different from Barr’s [1]; namely, we assume that the functor is lax (and not necessarily op-lax).

By a lax monad (T, η, μ) in Mat(V) we mean:

− a lax functor T : Mat(V) → Mat(V) (so that 1_{T X} ≤ T 1_{X} and T s · T r ≤ T (s · r) for composable V-matrices r, s), and

− op-lax natural transformations η : 1_{Mat(V)} → T and μ : T^{2} → T,

such that μ · T μ ≤ μ · μT, Id T ≤ μ · T η ≤ T Id and Id T ≤ μ · ηT ≤ T Id; that is, for every set X,

[figure: T^{3}X; ≤; μ_{T X}; T μ_{X}; T^{2}X; μ_{X}; T X; T η_{X}; η_{T X}; 1_{T X}; T 1_{X}; T^{2}X; μ_{X}; T X; ≤; T^{2}X; μ_{X}; ≤; T X]  (2)

We point out that this definition does not coincide with Bunge’s [3], although the only differences occur in the right-hand diagram. In the final section we present an example of a lax monad (in our sense) which is not a lax monad à la Bunge (see Example 6.3).

3. The strategy

3.1. The monoidal closed category 2^{V^{op}}. It is straightforward to check that the formula:

f ⊗ g(v) = ⋁_{v′,v′′: v′⊗v′′≥v} f(v′) ∧ g(v′′),  (3)

for any f, g ∈ 2^{V^{op}} and v ∈ V, defines a tensor product in 2^{V^{op}} that preserves joins, with unit element

k : V^{op} → 2
v ↦ \{ \begin{matrix}⊤ & if v ≤ k_{V} \\ ⊥ & elsewhere. \end{matrix}

(We point out that this tensor product is a particular case of Day’s convolution [11].) Symmetry of this tensor is also inherited from symmetry of the tensor product of 2 and V, so that we have:

Proposition. Given a symmetric monoidal closed lattice V, formula (3) gives a symmetric monoidal closed structure on 2^{V^{op}}.

We remark that, in case the tensor product in V is its categorical product, then f ⊗ g = f ∧ g as well.

ON EXTENSIONS OF LAX MONADS  45

3.2. 2^{V^{op}}-matrices versus V^{op}-indexed relations. The embedding

E : 2 → 2^{V^{op}}
w ↦

E(w) : V^{op} → 2
v ↦ E(w)(v) = \{ \begin{matrix}w & if v ≤ k_{V} \\ ⊥ & elsewhere \end{matrix}

preserves the tensor product, the unit element and infima. It preserves suprema if and only if k_{V} = ⊤_{V}. Therefore, as detailed in [10], it induces a 2-functor

E : Mat(2) → Mat(2^{V^{op}}).

Denoting the set of functors from A to B by [A, B], the composition of the natural bijections

[X × Y, [V^{op}, 2]] ≅ [X × Y × V^{op}, 2] ≅ [V^{op} × X × Y, 2] ≅ [V^{op}, [X × Y, 2]] assigns to any 2^{V^{op}}-matrix a : X × Y → 2^{V^{op}} a V^{op}-indexed family of relations (a_{v} : X × Y → 2)_{v∈V}, defined by

a_{v}(x, y) = a(x, y)(v).

Lemma. For a, a′ : X ↛ Y, b : Y ↛ Z in Mat(2^{V^{op}}) and v, v′ ∈ V, one has: a. v ≤ v′ ⇒ a_{v} ≥ a_{v′}; b. a ≤ a′ ⇒ a_{v} ≤ a′_{v}; c. b_{v} · a_{v′} ≤ (b · a)_{v⊗v′}; d. if ⊗ = ∧ in V, then b_{v} · a_{v} = (b · a)_{v}.

Proof. The only non-trivial assertion is (d). When ⊗ = ∧, for each x ∈ X and z ∈ Z,

(b · a)_{v}(x, z) = (b · a)(x, z)(v)
= ⋁_{y∈Y} (a(x, y) ∧ b(y, z))(v)
= ⋁_{y∈Y} a(x, y)(v) ∧ b(y, z)(v)
= b_{v} · a_{v}(x, z).

3.3. The Yoneda embedding. We consider now the Yoneda embedding

Y : V → 2^{V^{op}}
v ↦

Y(v) : V^{op} → 2
u ↦ \{ \begin{matrix}⊤ & if u ≤ v \\ ⊥ & otherwise, \end{matrix}

and its left adjoint

\begin{matrix}L : 2^{V^{op}} & → & V \\ f & ↦ & ⋁\{v ∈ V ; f(v) = ⊤\}. \end{matrix}

Proposition. The functors Y and L are strict monoidal functors.

Proof. The functor Y is monoidal: from Y(k_{V})(v) = ⊤ if and only if v ≤ k_{V}, it follows that Y(k_{V}) = k; moreover,

(Y(v) ⊗ Y(v′))(u) = ⊤ ⇔ ⋁_{r⊗s≥u} Y(v)(r) ∧ Y(v′)(s) = ⊤
⇔ ∃r, s ∈ V : r ⊗ s ≥ u, r ≤ v and s ≤ v′
⇔ u ≤ v ⊗ v′ ⇔ Y(v ⊗ v′)(u) = ⊤.

The functor L is monoidal, since:

L(k) = ⋁{v ∈ V ; k(v) = ⊤} = k_{V}, and
L(f) ⊗ L(g) = ⋁{r ∈ V ; f(r) = ⊤} ⊗ ⋁{s ∈ V ; g(s) = ⊤}
= ⋁{r ⊗ s ; r, s ∈ V, f(r) = ⊤ = g(s)}
= ⋁{v ∈ V ; (f ⊗ g)(v) = ⊤} = L(f ⊗ g).

These two strict monoidal functors induce a pair of lax functors

\xymatrix{Mat(V) \ar[r]^{Y} & Mat(2^{V^{op}}), \ar[l]^{L}}

L being in fact a 2-functor.

3.4. The use of the embeddings to construct the extension. The construction of the extension of a lax monad (T, η, μ) in Rel = Mat(2) into Mat(V) we will describe in the next two sections consists of two steps.

First we use the interpretation of a 2^{V^{op}}-matrix as a V^{op}-indexed family of relations and the embedding described in 3.2, obtaining a commutative diagram

\xymatrix{Mat(2) \ar[r]^{T} \ar[d]_{E} & Mat(2) \ar[d]^{E} \\ Mat(2^{V^{op}}) \ar[r]^{T̂} & Mat(2^{V^{op}}).}  (4)

Secondly, we use the adjunction L ⊣ Y of Section 3.3 to transfer a lax monad (S, δ, ν) in Mat(2^{V^{op}}) into Mat(V), defining S̃ := LSY and showing that, under some conditions on V, the following diagram

\xymatrix{Mat(2^{V^{op}}) \ar[r]|{S} \ar[d]_{L} & Mat(2^{V^{op}}) \ar[d]^{L} \\ Mat(V) \ar[r]^{S̃} & Mat(V)}  (5)

is commutative and (S̃, δ̃, ν̃) is a lax monad in Mat(V).

Finally, gluing these constructions, since LE is the embedding Rel ↪ Mat(V), we obtain a commutative diagram

\xymatrix{Rel \ar[r]^{T} \ar@{^{(}->}[dd] \ar@{^{(}->}[d]_{E} & Rel \ar@{^{(}->}[dd] \ar@{^{(}->}[d]^{E} \\ Mat(2^{V^{op}}) \ar[r]^{T̂} \ar[d]_{L} & Mat(2^{V^{op}}) \ar[d]^{L} \\ Mat(V) \ar[r]^{˜T̂} & Mat(V),}

and corresponding op-lax natural transformations ˜ η̂ and ˜ μ̂.

We point out that in the construction sketched in diagram (4), and described in the next section, one can replace, without much effort, the lattice 2 by a general symmetric monoidal closed category. Moreover, in the construction (5) carried out in Section 5 one can easily replace the monoidal adjunction L ⊣ Y by any other such adjunction.

4. From Mat(2) to Mat(2^{V^{op}})

4.1. Extension of a lax endofunctor. Given a lax functor T : Mat(2) → Mat(2), for each a : X ↛ Y and (𝔵, 𝔶) ∈ T X × T Y, we define

T̂a(𝔵, 𝔶)(v) := T (a_{v})(𝔵, 𝔶).

Theorem. Let T : Rel → Rel be a lax functor.

a. The assignments X ↦ T̂X := T X and a ↦ T̂a define a lax functor T̂ : Mat(2^{V^{op}}) →

Mat(2^{V^{op}}) such that

[figure: Rel; T; E; Rel; E; ≥; Mat(2^{V^{op}}); T̂; Mat(2^{V^{op}});]

that is, the functors T̂E and ET agree on objects and, for each relation r : X ↛ Y, ET (r) ≤ T̂E(r).

48  MARIA MANUEL CLEMENTINO AND DIRK HOFMANN

b. T̂ preserves the involution whenever T does.

c. If k_{V} = ⊤_{V} or T preserves the ⊥-relation, then T̂ is an extension of T, that is, the

following diagram commutes

\xymatrix{Rel \ar[r]^{T} \ar@{^{(}->}[d]_{E} & Rel \ar@{^{(}->}[d]^{E} \\ Mat(2^{V^{op}}) \ar[r]^{T̂} & Mat(2^{V^{op}}).}

d. If ⊗ = ∧, then T̂ is a (strict) 2-functor if T is one. Proof. To prove (a), we have to show that T̂(b) · T̂(a) ≤ T̂(b · a), 1_{T̂X} ≤ T̂1_{X} and that ET ≤ T̂E. To show the first inequality, consider a : X ↛ Y and b : Y ↛ Z in Mat(2^{V^{op}}), and 𝔵 ∈ T X, 𝔷 ∈ T Z and v ∈ V. Then:

T̂b · T̂a(𝔵, 𝔷)(v) = ( ⋁_{𝔶∈T Y} T̂a(𝔵, 𝔶) ⊗ T̂b(𝔶, 𝔷)) (v)
= ⋁_{𝔶∈T Y} ⋁_{v′⊗v′′≥v} T̂a(𝔵, 𝔶)(v′) ⊗ T̂b(𝔶, 𝔷)(v′′)
= ⋁_{v′⊗v′′≥v} (T b_{v′′} · T a_{v′})(𝔵, 𝔷)
≤ ⋁_{v′⊗v′′≥v} T (b · a)_{v′⊗v′′}(𝔵, 𝔷) ≤ T (b · a)_{v}(𝔵, 𝔷).

Now, for a relation r : X ↛ Y,

T̂E(r) = \{ \begin{matrix}T r & if v ≤ k_{V} \\ T ⊥ & otherwise \end{matrix} while ET (r) = \{ \begin{matrix}T r & if v ≤ k_{V} \\ ⊥ & otherwise, \end{matrix}

hence T̂E ≥ ET follows. This inequality implies that 1_{T̂X} ≤ T̂1_{X}, since

T̂1_{X} = T̂E1_{X} ≥ ET 1_{X} ≥ E1_{T X} = 1_{T X}.

The proofs of (b) and (c) are now straightforward. One concludes (d) using Lemma 3.2(d) in the calculation of T̂b · T̂a presented in the proof of (a).

Now we prove some auxiliary results. Lemma. For a : X ↛ Y in Mat(2^{V^{op}}), r : Y ↛ Z, s : W ↛ X in Rel, and v ∈ V:

a. (T̂a)_{v} = T a_{v};

b. (Er · a)_{v} = r · a_{v} and (a · Es)_{v} = a_{v} · s.

Proof. (a) is straightforward.

(b): For x ∈ X and z ∈ Z,

\begin{aligned}(Er · a)_{v}(x, z) & = & (Er · a)(x, z)(v) = ⋁_{y∈Y} (a(x, y) ⊗ Er(y, z))(v) \\ & = & ⋁_{v′⊗v′′≥v} ⋁_{y∈Y} (a(x, y)(v′) ⊗ Er(y, z)(v′′)). \end{aligned}

In this join it is enough to consider:

• v′′ ≤ k_{V}, since elsewhere Er(y, z)(v′′) = ⊥ and the tensor product is ⊥ as well, and • v′ = v, due to monotonicity of a(x, y); hence,

(Er · a)_{v}(x, z) = ⋁_{y∈Y} a(x, y)(v) ⊗ r(y, z) = (r · a_{v})(x, z).

The other equality is proved analogously. Proposition. If T : Rel → Rel preserves composition on the left (right) with r : Y × Z → 2, then T̂ preserves composition with Er. Proof. For any a : X ↛ Y in Mat(2^{V^{op}}) and v ∈ V,

T̂(Er · a)_{v} = T ((Er · a)_{v}) = T (r · a_{v}) = T r · T a_{v} = T r · (T̂a)_{v}.

The stability under composition on the right has an analogous proof. 4.2. Extension of a lax monad. Given a natural transformation α : S → T between lax functors S, T : Rel → Rel, we define α̂ : Ŝ → T̂ by α̂_{X} := Eα_{X} for every set X; that is

α̂_{X} : SX × T X → 2^{V^{op}}
(𝔵, 𝔵′) ↦

α̂_{X}(𝔵, 𝔵′) : V^{op} → 2
v ↦ \{ \begin{matrix}α_{X}(𝔵, 𝔵′) & if v ≤ k_{V} \\ ⊥ & elsewhere. \end{matrix}

Proposition. Let S, T : Rel → Rel be lax functors. Then:

a. Îd = Id.

b. Ŝ · T̂ = { \atop S · T}.

c. If α : S → T is a (lax, op-lax) natural transformation, so is α̂ : Ŝ → T̂. Proof. Straightforward.

Theorem. Let (T, η, μ) be a lax monad in Rel. If k_{V} = ⊤_{V} or T preserves the ⊥-matrix, then (T̂, η̂, μ̂) is a lax monad that extends the former one.

Proof. We only have to check diagrams (2) for (T̂, η̂, μ̂), which follow directly from the corresponding diagrams for (T, η, μ) once one observes that the former ones are obtained from the latter applying the 2-functor E.

5. From Mat(2^{V^{op}}) into Mat(V)

5.1. Transfer of a lax endofunctor. Using the monoidal adjunction of 3.3, for a lax endofunctor S in Mat(2^{V^{op}}), we define

\xymatrix{Mat(V) \ar[r]^{S̃} & Mat(V) := (Mat(V) \ar[r]^{Y} & Mat(2^{V^{op}}) \ar[r]|{S} & Mat(2^{V^{op}}) \ar[r]|{L} & Mat(V)).}

Proposition. Let S : Mat(2^{V^{op}}) → Mat(2^{V^{op}}) be a lax functor. Then S̃ = LSY is such that

[figure: Mat(2^{V^{op}}); S; L; Mat(2^{V^{op}}); L; ≥; Mat(V); S̃; Mat(V).]

The inequality in the diagram becomes an equality whenever SYL ≤ YLS.

Proof. By the adjointness property, LS ≤ LSYL, the required inequality. In addition, if SYL ≤ YLS, then LSYL ≤ LYLS ≤ LS, and the equality follows.

Analogously to the previous construction, we can easily check that:

Lemma. For S : Mat(2^{V^{op}}) → Mat(2^{V^{op}}), if S preserves composition on the left (right) with a matrix a : X ↛ Y, then so does S̃, with a replaced by La.

Proof. Indeed,

S̃(b · La) = LSY(b · La) ≤ LSY(LYb · La)
= LSYL(Yb · a) ≤ LS(Yb · a)
= LSYb · LSa ≤ LSYb · LSYLa
= S̃b · S̃(La).

5.2. Transfer of a lax monad. First we analyse the behaviour of the construction with respect to the composition of functors and natural transformations. For any (lax, op-lax) natural transformation α : R → S between lax functors R, S : Mat(2^{V^{op}}) → Mat(2^{V^{op}}), we define α̃ : R̃ → S̃ by α̃_{X} := Lα_{YX}, for every set X; that is,

α̃_{X} : R̃X ↛ S̃X, (𝔵, 𝔵′) ↦ ⋁{v ∈ V ; α_{X}(𝔵, 𝔵′)(v) = ⊤}.

Lemma. Let R, S : Mat(2^{V^{op}}) → Mat(2^{V^{op}}) be lax functors. Then:

a. Ĩd = Id.

b. R̃S ≤ R̃S̃, with equality in case RYL ≤ YLR.

c. If α : R → S is a (lax, op-lax) natural transformations, so is α̃ : R̃ → S̃.

Proof. It is straightforward.

Theorem. For each lax monad (S, δ, ν) in Mat(2^{V^{op}}), (S̃, δ̃, ν̃) is a lax monad in Mat(V) provided that SYL ≤ YLS.

Proof. We already know that S̃ = LSY is a lax functor, δ̃ = Lδ : LY = Id → S̃ and ν̃ = Lν : S̃S = S̃S̃ → S̃ are op-lax natural transformations. It remains to be shown that they fulfil the conditions of diagram (2): for each set X,

ν̃_{X} · S̃ν̃_{X} = Lν_{X} · LSYLν_{X} ≤ Lν_{X} · LYLSν_{X} = L(ν_{X} · Sν_{X})
≤ L(ν_{X} · ν_{SX}) = Lν_{X} · Lν_{SX} = ν̃_{X} · ν̃_{S̃X};
ν̃_{X} · S̃δ̃_{X} = Lν_{X} · LSYLδ_{X} ≥ Lν_{X} · LSδ_{X} = L(ν_{X} · Sδ_{X})
≥ L1_{SX} ≥ 1_{S̃X};
ν̃_{X} · S̃δ̃_{X} = Lν_{X} · LSYLδ_{X} ≤ Lν_{X} · LYLSδ_{X} = L(ν_{X} · Sδ_{X})
≤ LS1_{X} ≤ S̃L1_{X} = S̃1_{X};
ν̃_{X} · δ̃_{S̃X} = L(ν_{X} · δ_{SX}) ≤ L1_{SX} = 1_{S̃X}.

5.3. An extra condition on V. In order to guarantee that SYL ≤ YLS we will impose an extra condition on V which we analyse in the sequel. It was used in [10] under the designation V is ⊏-atomic, and it was formulated there as: for all u, v, w ∈ V,

a. u ⊏ v ≤ w ⇒ u ⊏ w,

b. v = ⋁ At(v), where At(v) = {u ∈ V ; u ⊏ v & ∀S ⊆ V u ⊏ ⋁ S ⇒ ∃s ∈ S : u ≤ s} is the set of ⊏-atoms of v.

It was pointed out to us by Dexue Zhang that this condition is equivalent to V being a completely distributive lattice, i.e. the functor ⋁ : 𝔻V → V, where 𝔻V is the lattice of downsets of V, has a left adjoint. (For the connection between this constructive formulation of complete distributivity and the classical one see [19].) In order to show this, we first observe that the lattice 2^{V^{op}} is isomorphic to the lattice 𝔻V and that the following diagram commutes:

[figure: 𝔻V; ≅; ⋁; ⊤; 2^{V^{op}}; L; ⊤; V.; ↓−; Y]

Proposition. The following conditions are equivalent:

i. V is ⊏-atomic for a transitive relation ⊏ in V;

ii. V is ⊏-atomic for a relation ⊏ in V;

iii. V is completely distributive;

iv. there exists a family (A(v))_{v∈V} of subsets of V such that, for each f ∈ 2^{V^{op}} and

v ∈ V,

YL(f)(v) = ⋀_{u∈A(v)} f(u).

Proof. (i) ⇒ (ii) is obvious.

(ii) ⇒ (iii): Given a relation ⊏ such that V is ⊏-atomic, we define the left adjoint A : V → 𝔻V of the functor ⋁ : 𝔻V → V by

A(v) := At(v) = {u ∈ V ; u ⊏ v & ∀S ⊆ V u ⊏ ⋁ S ⇒ ∃s ∈ S : u ≤ s}.

By definition of ⊏-atomic, this is a monotone map such that ⋁ ·A = Id_{V}. Moreover, it is obvious that, for any S ∈ 𝔻V, A · ⋁(S) ⊆ S.

(iii) ⇒ (iv): Given A ⊣ ⋁, the family of images (A(v))_{v∈V} satisfies the condition stated in (iv). Indeed, the adjunction gives

∀v ∈ V ∀S ∈ 𝔻V v ≤ ⋁ S ⇔ A(v) ⊆ S.

Hence, one has

YL(f)(v) = ⊤ ⇔ v ≤ ⋁{w ∈ V ; f(w) = ⊤}
⇔ A(v) ⊆ {w ∈ V ; f(w) = ⊤}
⇔ ∀u ∈ A(v) f(u) = ⊤.

(iv) ⇒ (i): Let ⊏ be defined by

u ⊏ v :⇔ ∃w ∈ V : u ∈ A(w) and w ≤ v.

Then it clearly satisfies condition (a) of the definition of ⊏-atomic. Moreover, for any u ∈ A(v), u ⊏ v.

To show that ⊏ is transitive, it is enough to notice that, since YLY = Y, we have

⊤ = Y(v)(v) = YLY(v)(v) ⇒ ⋀_{u∈A(v)} Y(v)(u) = ⊤ ⇒ ∀u ∈ A(v) : u ≤ v.

To show equality (b) we first observe that v = ⋁ A(v), as stated above. We then show that A(v) ⊆ At(v). Let u ∈ A(v) and u ⊏ ⋁ S for some subset S of V. By definition of ⊏, there exists v′ ∈ V such that u ∈ A(v′) and v′ ≤ ⋁ S. Let

f : V^{op} → 2
w ↦ \{ \begin{matrix}⊤ & if ∃s ∈ S : w ≤ s \\ ⊥ & elsewhere. \end{matrix}

Then YL(f)(v′) = ⊤, since v′ ≤ L(f) = ⋁ S, and therefore f(u) = ⊤, that is, there exists s ∈ S such that u ≤ s as claimed.

Lemma. If V is completely distributive, one has, for each 2^{V^{op}}-matrix a : X ↛ Y and each element v of V,

(YLa)_{v} = ⋀_{u∈A(v)} a_{u}.

Proof. For each x ∈ X and y ∈ Y, using the proposition above, we have

(YLa)_{v}(x, y) = YL(a(x, y))(v) = ⋀_{u∈A(v)} a(x, y)(u) = ⋀_{u∈A(v)} a_{u}(x, y).

5.4. The extension. Next we will show that ˜ ˆ( ) extends each lax monad in Rel into Mat(V). We start outlining this construction.

Let (T, η, μ) be a lax monad in Rel. Then ˜ T̂ : Mat(V) → Mat(V) agrees with T on

objects. To define ˜ T̂(a) for a morphism a : X ↛ Y in Mat(V), we consider the relation

Ya_{v} : X × Y → 2
(x, y) ↦ \{ \begin{matrix}⊤ & if v ≤ a(x, y) \\ ⊥ & elsewhere; \end{matrix}

it is straightforward that

\begin{matrix}˜T̂(a) : T X × T Y & → & V \\ (𝔵, 𝔶) & ↦ & ⋁\{v ∈ V ; T (Ya_{v})(𝔵, 𝔶) = ⊤\}. \end{matrix}

In the op-lax natural transformations η : Id → T and μ : T^{2} → T, ˜ ˆ( ) acts as

X × T X →^{η_{X}} 2 ↦ X × T X →^{˜η̂_{X}} V
(x, 𝔵) ↦ \{ \begin{matrix}k_{V} & if η_{X}(x, 𝔵) = ⊤ \\ ⊥ & elsewhere, \end{matrix}

T^{2}X × T X →^{μ_{X}} 2 ↦ T^{2}X × T X →^{˜μ̂_{X}} V
(𝔛, 𝔵) ↦ \{ \begin{matrix}k_{V} & if μ_{X}(𝔛, 𝔵) = ⊤ \\ ⊥ & elsewhere. \end{matrix}

Theorem. Let (T, η, μ) be a lax monad in Rel. If V is completely distributive, k_{V} = ⊤_{V}

or T preserves the ⊥-matrix, then (˜T̂, ˜ η̂, ˜ μ̂) is a lax monad in Mat(V), that extends the former one.

Proof. Using Theorems 4.1, 4.2, and Proposition 5.1 and Theorem 5.2, it is enough to show that T̂YL ≤ YLT̂, whenever V is completely distributive. For a : X ↛ Y ∈ Mat(2^{V^{op}}), v ∈ V, 𝔵 ∈ T X, 𝔶 ∈ T Y:

\begin{aligned}(T̂YL(a))(𝔵, 𝔶)(v) & = & T (YL(a))_{v}(𝔵, 𝔶) = T ( ⋀_{u∈A(v)} a_{u})(𝔵, 𝔶) \\ & ≤ & ⋀_{u∈A(v)} T a_{u}(𝔵, 𝔶) = YLT a(𝔵, 𝔶)(v). \end{aligned}

Corollary. Let (T, η, μ) be a monad in Set. If T satisfies (BC), V is completely

distributive, and k_{V} = ⊤_{V} or ⊤ preserves the ⊥-matrix, then (˜ˆ\overline{T}, ˜ ˆ \overline{η}, ˜ ˆ \overline{μ}) is a lax monad in Mat(V), that extends the given one. Moreover, if the tensor product ⊗ in V is its

categorical product, then ˜ ˆ \overline{T} is in fact a functor.

Proof. The first assertion follows from Theorem 1.3 together with the theorem above.

To show that ˜ ˆ \overline{T} is a functor in case ⊗ = ∧, we first show that, for each a : X ↛ Y and b : Y ↛ Z in Mat(V) and each u, v ∈ V with u ∈ A(v), Y(b · a)_{v} ≤ Yb_{u} · Ya_{u}. Indeed, for every x ∈ X and z ∈ Z,

Y(b · a)(x, z)(v) = ⊤ ⇔ v ≤ (b · a)(x, z)
⇒ u ⊏ (b · a)(x, z) = ⋁_{y∈Y} a(x, y) ∧ b(y, z)
⇒ ∃y ∈ Y : u ≤ a(x, y) ∧ b(y, z)
⇔ ∃y ∈ Y : Ya(x, y)(u) = ⊤ = Yb(y, z)(u)
⇔ (Yb · Ya)(x, z)(u) = ⊤.

Finally, to check that ˜ ˆ \overline{T}(b · a) ≤ ˜ ˆ \overline{T}b · ˜ ˆ \overline{T}a, we consider 𝔵 ∈ T X, 𝔷 ∈ T Z and v ∈ A(˜ˆ\overline{T}(b · a)(𝔵, 𝔷)). Hence ⊤ = \overline{T} (Y(b · a)_{v})(𝔵, 𝔷). Then, for any u ∈ A(v), ⊤ = (\overline{T} Yb_{u} · \overline{T} Ya_{u})(𝔵, 𝔷). But then there exists 𝔶 ∈ T Y such that \overline{T} Yb_{u}(𝔵, 𝔶) = ⊤ = \overline{T} Ya_{u}(𝔶, 𝔷). Therefore u ≤

˜ˆ\overline{T}(b) · ˜ ˆ \overline{T}(a)(𝔵, 𝔷) and then ˜ ˆ \overline{T}(b · a) ≤ ˜ ˆ \overline{T}b · ˜ ˆ \overline{T}a as claimed.

6. Examples

In this section we present examples of extensions. Our main examples are based on the category Mat(\overline{ℝ}_{+}), where ([0, ∞], ≥) is endowed with the tensor product +. We remark that in this situation the terminal object is also the unit element 0 and that \overline{ℝ}_{+} is >- atomic (see [12] for further information about this sort of lattices), hence we may apply our results. For simplicity, we use the same notation for the given (lax) monad and its extension.

6.1. The identity monad. Barr’s extension of the identity monad (Id, 1, 1) in Set into Rel gives the identity monad. The same occurs in the next step: its extension into Mat(V) as defined here is the identity monad. (We remark that this monad may have other lax extensions, as it is shown in [8].)

6.2. The powerset monad. The powerset monad (P, η, μ) in Set is defined by:

- P is the powerset functor, assigning to each set X its powerset P X and to each map its direct image,

- η_{X}(x) = {x} for every x ∈ X ∈ Set, and

- μ_{X}(A) = ⋃ A for every set A of subsets of X.

It is easy to check that the functor P satisfies (BC), hence this monad can be extended to Rel, with

A(P r)B ⇔ ∀x ∈ A ∃y ∈ B : xry and ∀y ∈ B ∃x ∈ A : xry.

For V = \overline{ℝ}_{+}, d : X × Y → \overline{ℝ}_{+}, A ⊆ X and B ⊆ Y, the extension P d(A, B) is defined by

inf\{v ∈ \overline{ℝ}_{+} | ∀x ∈ A ∃y ∈ B : d(x, y) ≤ v and ∀y ∈ B ∃x ∈ A : d(x, y) ≤ v\}.

In case d is a premetric in X, P̃d is the usual premetric in P X.

6.3. The lax powerset monad. If we consider now H : Rel → Rel with HX := P X the powerset of X and

A(Hr)B if for each b ∈ B there exists a ∈ A such that a r b, it is easy to check that 1_{HX} ≤ H1_{X} and Hr · Hs ≤ H(r · s), hence H is a lax functor. We may equip H with the structure of a lax monad, considering the (strict) natural transformations η : Id_{Rel} → H and μ : H^{2} → H, defined by

x(η_{X})A if x ∈ A and A(μ_{X})A if ⋃ A ⊆ A,

for x ∈ X, A ⊆ X and A ⊆ HX. It is easy to check that, for every set X, A, A′ ⊆ X and 𝔄 ⊆ HHX,

A(μ_{X} · η_{HX})A′ ⇔ A(μ_{X} · Hη_{X})A′ ⇔ A(H1_{X})A′ ⇔ A ⊆ A′, and
𝔄(μ_{X} · Hμ_{X})A ⇔ 𝔄(μ_{X} · μ_{HX})A ⇔ ⋃ ⋃ 𝔄 ⊆ A.

Hence, 1_{HX} ≤ μ_{X} · η_{HX} = μ_{X} · Hη_{X} = H1_{X} and μ_{X} · Hμ_{X} = μ_{X} · μ_{HX}, and then (H, η, μ) is a lax monad in Rel. (We remark that it is not a lax monad in the sense of Bunge [3], since μ_{X} · Hη_{X} ≰ 1_{HX}.)

It has an interesting lax extension to Mat(\overline{ℝ}_{+}): given d : X ↛ Y in Mat(\overline{ℝ}_{+}), for each A ⊆ X and B ⊆ Y,

Hd(A, B) = inf{v ≥ 0 | A(Hd_{v})B} = inf{v ≥ 0 | ∀x ∈ A ∃y ∈ B : d(x, y) ≤ v}.

For a premetric d : X ↛ X, Hd assigns to each pair of subsets A, B of X, its Hausdorff (non-symmetric) premetric

d_{H}(A, B) = sup_{x∈A} inf_{y∈B} d(x, y).

This identification holds in the general case of a V-matrix d : X ↛ Y, considering d_{H} defined as above. Indeed, for v ∈ \overline{ℝ}_{+},

\begin{aligned}∀x ∈ A ∃y ∈ B : d(x, y) ≤ v & ⇒ & ∀x ∈ A inf_{y∈B} d(x, y) ≤ v ⇒ d_{H}(A, B) ≤ v \\ & ⇒ & d_{H}(A, B) ≤ Hd(A, B). \end{aligned}

On the other hand,

\begin{aligned}d_{H}(A, B) < v & ⇒ & ∀x ∈ A inf_{y∈B} d(x, y) < v ⇒ ∀x ∈ A ∃y ∈ B : d(x, y) ≤ v \\ & ⇒ & Hd(A, B) ≤ v. \end{aligned}

Hence, d_{H} = Hd as claimed.

6.4. The ultrafilter monad. We consider now the ultrafilter monad (U, η, μ) in Set, with:

- the functor U : Set → Set such that UX is the set of ultrafilters of X for every set X, and Uf(𝔵) the ultrafilter generated by f(𝔵), for every map f : X → Y and every ultrafilter 𝔵 in X.

- η_{X} : X → UX assigns to each point x the principal ultrafilter

x^{•} = {A ⊆ X | x ∈ A};

- μ_{X} : U^{2}X → UX is the Kowalsky multiplication, i.e.

μ_{X}(𝔛) = ⋃_{X ∈𝔛} ⋂_{𝔵∈X} 𝔵.

The functor U satisfies (BC), hence it has an extension in Rel, given by

𝔵(Ur)𝔶 ⇔ r[𝔵] ⊆ 𝔶 ⇔ r^{∘}[𝔶] ⊆ 𝔵,

for every relation r : X ↛ Y, 𝔵 ∈ UX and 𝔶 ∈ UY. This can be equivalently described by

𝔵(Ur)𝔶 ⇔ ∀A ∈ 𝔵 ∀B ∈ 𝔶 ∃x ∈ A ∃y ∈ B : xry.

Its lax extension U to Mat(V) coincides with Clementino-Tholen lax extension [10] (which we will denote below by U′), as we show next.

For each d : X ↛ Y in Mat(V),

\begin{aligned}Ud(𝔵, 𝔶) & = & ⋁\{v ∈ V | 𝔵(Ud_{v})𝔶\} \\ & = & ⋁\{v ∈ V | ∀A ∈ 𝔵 ∀B ∈ 𝔶 ∃x ∈ A ∃y ∈ B : d(x, y) ≥ v\}, \end{aligned}

while

U′d(𝔵, 𝔶) = ⋀_{A∈𝔵,B∈𝔶} ⋁_{x∈A,y∈B} d(x, y).

For each v ∈ V such that 𝔵(Ud_{v})𝔶, v ≤ ⋁_{x∈A,y∈B} d(x, y), hence v ≤ U′d(𝔵, 𝔶), and therefore

Ud(𝔵, 𝔶) ≤ U′d(𝔵, 𝔶).

If w is a ⊏-atom and w ⊏ U′d(𝔵, 𝔶), then w ⊏ ⋁_{x∈A,y∈B} d(x, y) for each A ∈ 𝔵 and B ∈ 𝔶.

Hence there exists x ∈ A and y ∈ B such that w ≤ d(x, y), and therefore w ≤ Ud(𝔵, 𝔶). Hence, U′d(𝔵, 𝔶) ≤ Ud(𝔵, 𝔶) and the equality follows.

We point out that, although U : Rel → Rel is a (strict) functor, its extension U : Mat(V) → Mat(V) is not always op-lax. It is the case when V = ([−∞, +∞], ≥), with tensor product ⊗ = + (where −∞ + (+∞) = +∞), as we show next.

Consider X = {n | n ∈ ℕ, non-zero and even}, Z = {−m | m ∈ ℕ, non-zero and odd} and Y = X ∪ Z. For

\begin{matrix}d_{1} : X × Y & → & [−∞, +∞] & and & d_{2} : Y × Z & → & [−∞, +∞], \\ (x, y) & ↦ & xy & & (y, z) & ↦ & yz \end{matrix}

and free ultrafilters 𝔵 ∈ UX and 𝔷 ∈ UZ, we have

\begin{aligned}U(d_{2} · d_{1})(𝔵, 𝔷) & = inf\{v ∈ V | ∀A ∈ 𝔵 ∀C ∈ 𝔷 ∃x ∈ A ∃z ∈ C : (d_{2} · d_{1})(x, z) ≥ v\} \\ & = −∞, \end{aligned}

since (d_{2} · d_{1})(x, z) = inf_{y∈Y} y(x + z) = −∞. To calculate (Ud_{2} · Ud_{1})(𝔵, 𝔷), let 𝔶 ∈ UY. If

X ∈ 𝔶, then Ud_{1}(𝔵, 𝔶) = +∞ since every A ∈ 𝔵 is unlimited and every B ∈ 𝔶 has a positive element. If X ∉ 𝔶, then Z ∈ 𝔶; hence Ud_{2}(𝔶, 𝔷) = +∞ since every C ∈ 𝔷 is unlimited and every B ∈ 𝔶 contains a negative element. Now

(Ud_{2} · Ud_{1})(𝔵, 𝔷) = inf_{𝔶∈UY} Ud_{1}(𝔵, 𝔶) + Ud_{2}(𝔶, 𝔷) = +∞,

and therefore U(d_{2} · d_{1}) ≰ Ud_{2} · Ud_{1}; that is U is not op-lax.

6.5. The filter monad. The filter monad (F, η, μ) in Set, with F X the set of filters of X, F f(𝔵) = {B ⊆ Y | f^{−1}(B) ∈ 𝔵} for every f : X → Y and 𝔵 ∈ F X, and η and μ defined as in the example above, satisfies (BC). Hence F can be extended into an endofunctor of Rel, that may be described by

𝔵(F r)𝔶 ⇔ r[𝔵] ⊆ 𝔶 and r^{∘}[𝔶] ⊆ 𝔵,

for every relation r : X ↛ Y, 𝔵 ∈ F X and 𝔶 ∈ F Y. We observe that, contrarily to the case of the ultrafilter monad, in this situation we have to impose both conditions, r[𝔵] ⊆ 𝔶 and r^{∘}[𝔶] ⊆ 𝔵, since each of them does not follow from the other. This was the reason why Pisani in [17] had to restrict the codomain in order to get a functor extension with the “non-symmetric” definition. Indeed, if we define G : Rel → Rel, ε : Id_{Rel} → G and ν : GG → G by GX = F X,

\begin{aligned}𝔵(Gr)𝔶 & ⇔ & r^{∘}[𝔶] ⊆ 𝔵, \\ x ε_{X} 𝔵 & ⇔ & 𝔵 ⊆ η_{X}(x), \\ 𝔛 ν_{X} 𝔵 & ⇔ & 𝔵 ⊆ μ_{X}(𝔛), \end{aligned}

we obtain a lax monad (G, ε, ν) in Rel.

6.6. The double powerset monad. Finally we present an example that shows that the Beck-Chevalley condition used throughout is not always satisfied. In the double powerset monad (D, η, μ) in Set induced by the adjunction

\xymatrix{Set^{op} \ar[r]^{Set(−,2)} & Set \ar[l]^{Set(−,2)}}

the functor D does not satisfy (BC) (see [13]). Indeed, it is easy to check that the D-image of the following pullback

\xymatrix{∅ \ar[r] \ar[d] & \{0, 1\} \ar[d]^{g} \\ \{0, 1\} \ar[r]^{f} & \{0, 1\},}

ON EXTENSIONS OF LAX MONADS  59

where f(0) = f(1) = 0 and g(0) = g(1) = 1, does not satisfy (BC):

Df({∅, {0, 1}}) = Dg({∅, {0, 1}}) = P ({0, 1}),

although there is no element on D(∅) mapped into {∅, {0, 1}} by the pullback projections.

References

[1] M. Barr, Relational algebras, in: Springer Lecture Notes in Math. 137 (1970), 39-55.

[2] R. Betti, A. Carboni, R. Street and R. F. C. Walters, Variation through enrichment, J. Pure Appl. Algebra 29 (1983), 109-127.

[3] M. Bunge, Coherent extensions and relational algebras, Trans. Am. Math. Soc. 197 (1974), 355-390.

[4] M. M. Clementino and D. Hofmann, Triquotient maps via ultrafilter convergence, Proc. Am. Math. Soc. 130 (2002), 3423-3431.

[5] M. M. Clementino and D. Hofmann, Topological features of lax algebras, Appl. Categ. Struct. 11 (2003), 267-286.

[6] M. M. Clementino, D. Hofmann and G. Janelidze, Local homeomorphisms via ultrafilter convergence, Proc. Am. Math. Soc. 133 (2005), 917-922.

[7] M. M. Clementino, D. Hofmann and W. Tholen, The convergence approach to exponentiable maps, Port. Math. 60 (2003), 139-160.

[8] M. M. Clementino, D. Hofmann and W. Tholen, Exponentiability in categories of lax algebras, Theory Appl. Categories 11 (2003), 337-352.

[9] M. M. Clementino, D. Hofmann and W. Tholen, One setting for all: metric, topology, uniformity, approach structure, Appl. Categ. Struct. 12 (2004), 127-154.

[10] M. M. Clementino and W. Tholen, Metric, Topology and Multicategory – a Common Approach, J. Pure Appl. Algebra 179 (2003), 13-47.

[11] B. Day, On closed categories of funtors, in: Lecture Notes in Math. 137 (Springer, Berlin 1970), pp. 1-38.

[12] B. Flagg and R. Kopperman, Continuity spaces: Reconciling domains and metric spaces, Theoret. Comput. Sci. 177 (1997), 111-138.

[13] H. P. Gumm, Functors for coalgebras, Algebra Universalis 45 (2001), 135-147.

[14] D. Hofmann, An algebraic description of regular epimorphisms in topology, J. Pure Appl. Algebra (to appear).

[15] G. Janelidze and M. Sobral, Finite preorders and topological descent I, J. Pure Appl. Algebra 175 (2002), 187-205.

[16] F. W. Lawvere, Metric spaces, generalized logic, and closed categories, Rend. Sem. Mat. Fis. Milano 43 (1973), 135-166.

[17] C. Pisani, Convergence in exponentiable spaces, Theory Appl. Categories 5 (1999), 148-162.

[18] J. Reiterman and W. Tholen, Effective descent maps of topological spaces, Top. Appl. 57 (1994), 53-69.

[19] R. J. Wood, Ordered Sets via Adjunction, in: M. C. Pedicchio and W. Tholen (eds), Categorical Foundations. Special Topics in Order, Topology, Algebra, and Sheaf Theory, Encyclopedia of Mathematics and its Applications, 97 (Cambridge Univ. Press, 2004).

Dep. de Matemática, Universidade de Coimbra, 3001-454 Coimbra, Portugal

Dep. de Matemática, Universidade de Aveiro, 3810-193 Aveiro, Portugal

Email: mmc@mat.uc.pt, dirk@mat.ua.pt

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/13/3/13-03.{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}TEX2e 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.

Michael Barr, McGill University: barr@barrs.org, Associate Managing Editor Lawrence Breen, Université Paris 13: breen@math.univ-paris13.fr Ronald Brown, University of Wales Bangor: r.brown@bangor.ac.uk Jean-Luc Brylinski, Pennsylvania State University: jlb@math.psu.edu Aurelio Carboni, Università dell Insubria: aurelio.carboni@uninsubria.it Valeria de Paiva, Palo Alto Research Center: paiva@parc.xerox.com Martin Hyland, University of Cambridge: M.Hyland@dpmms.cam.ac.uk 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 Stephen Lack, University of Western Sydney: s.lack@uws.edu.au F. William Lawvere, State University of New York at Buffalo: wlawvere@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 Robert Rosebrugh, Mount Allison University: rrosebrugh@mta.ca, Managing Editor Jiri Rosicky, Masaryk University: rosicky@math.muni.cz James Stasheff, University of North Carolina: jds@math.unc.edu Ross Street, Macquarie University: street@math.mq.edu.au Walter Tholen, York University: tholen@mathstat.yorku.ca Myles Tierney, Rutgers University: tierney@math.rutgers.edu Robert F. C. Walters, University of Insubria: robert.walters@uninsubria.it R. J. Wood, Dalhousie University: rjwood@mathstat.dal.ca