Theory and Applications of Categories, Vol. 18, No. 14, 2007, pp. 372–399.

DENSE MORPHISMS OF MONADS

PANAGIS KARAZERIS, JIŘÍ VELEBIL

Abstract. Given an arbitrary locally finitely presentable category 𝒦 and finitary monads 𝕋 and 𝕊 on 𝒦 , we characterize monad morphisms α : 𝕊 ⟶ 𝕋 with the property that the induced functor α_{∗} : 𝒦 ^{𝕋} ⟶ 𝒦 ^{𝕊} between the categories of Eilenberg-Moore algebras is fully faithful. We call such monad morphisms dense and give a characterization of them in the spirit of Beth’s definability theorem: α is a dense monad morphism if and only if every 𝕋-operation is explicitly defined using 𝕊-operations. We also give a characterization in terms of epimorphic property of α and clarify the connection between various notions of epimorphisms between monads.

1. Introduction

We study embedding functors Φ : 𝒱_{1} ⟶ 𝒱_{2}, where 𝒱_{1} and 𝒱_{2} are finitary varieties, such that Φ does not change the underlying sets of respective algebras. More precisely: we study situations

\xymatrix{𝒱_{1} \ar[rr]^{Φ} \ar[dr]_{U_{1}} &  & 𝒱_{2} \ar[dl]^{U_{2}} \\  & Set}  (1.1)

where U_{1} and U_{2} are underlying functors with the additional property that

every 𝒱_{2}-homomorphism between 𝒱_{1}-algebras is a 𝒱_{1}-homomorphism.  (1.2)

Situations (1.1) satisfying (1.2) abound — let us point out two trivial examples:

1.1. Examples.

1. 𝒱_{1} is the variety of Abelian groups, 𝒱_{2} is the variety of all groups. That (1.2) holds is trivial: 𝒱_{1} arises by adding just the commutativity law to the equational presentation of 𝒱_{2} and such process does not affect the notion of a homomorphism.

2. 𝒱_{1} is the variety of groups, 𝒱_{2} is the variety of monoids. Condition (1.2) holds since the inverse operation can be defined explicitly in the language of monoids. More

The second author acknowledges the support of the grant No. 201/06/664 of the Grant Agency of the Czech Republic. Received by the editors 2007-03-06 and, in revised form, 2007-08-10. Transmitted by Walter Tholen. Published on 2007-08-27. 2000 Mathematics Subject Classification: 18C20, 18C35. Key words and phrases: Definable operation, monad morphism, locally finitely presentable category. \begin{matrix}c \\ ◯ \end{matrix} Panagis Karazeris, Jiří Velebil, 2007. Permission to copy for private use granted.

precisely, the sentence

∀x∀y (y = x^{−1} ⇔ (x ∗ y = e ∧ y ∗ x = e))

holds in every group (G, ∗, e, (−)^{−1}). Thus, the predicate y = x^{−1} (i.e., “to be an inverse”) is preserved by any monoid homomorphism.

In fact, the above example of groups and monoids is a good illustration of a general characterization of condition (1.2):

For every 𝒱_{1}-operation τ, the predicate “to be τ” must be explicitly definable by a system of equations in the language of 𝒱_{2}-operations.

This result is a special case covered by the famous Beth’s Definability Theorem of model theory, see [Be].

We prove Beth’s Definability Theorem in Theorem 4.3 below in a more general setting than (1.1). To be more specific, we replace the base category Set of sets and mappings by an essentially algebraic category 𝒦 (see Definition 2.6 below) and we replace finitary varieties 𝒱_{1}, 𝒱_{2} by categories 𝒦 ^{𝕋}, 𝒦 ^{𝕊} of Eilenberg-Moore algebras for finitary monads 𝕋 and 𝕊, respectively, on the category 𝒦 , studying thus situations

[figure: 𝒦 ^{𝕋}; Φ; U^{𝕋}; 𝒦 ^{𝕊}; U^{𝕊}; 𝒦]  (1.3)

where U^{𝕋} and U^{𝕊} denote the underlying functors. By putting 𝒦 = Set, the situation (1.1) is recovered, since finitary varieties are precisely the categories of Eilenberg-Moore algebras for suitable finitary monads on Set, as proved by Fred Linton in [Li_{1}].

This level of generality has also the advantage that the situation (1.3) is equivalent to having a monad morphism

α : 𝕊 ⟶ 𝕋  (1.4)

and we may ask which property of monad morphisms singles out the property

every 𝕊-homomorphism between 𝕋-algebras is a 𝕋-homomorphism.  (1.5)

We call such monad morphisms dense. We introduce, using the formalism of monads, a notion of explicit definability of operations and show in Theorem 4.3 below that α is dense exactly when every n-tuple of m-ary 𝕋-operations is explicitly 𝕊-definable. Furthermore, we characterize dense monad morphisms in terms of an orthogonality condition (Theorem 5.4 below), locating them strictly in between strong epimorphisms and epimorphisms in the category of finitary monads and their morphisms.

Organization of the Paper. In Section 2 we gather notions that we will need in the sequel. Various useful sufficient conditions for density of a monad morphism are given in Section 3. Section 4 is devoted to the theorem of Beth type characterizing dense monad morphisms, whereas in Section 5 we characterize dense monad morphisms in the category of finitary monads. We also show that dense monad morphisms are “epis” of a factorization system on the category of finitary monads. Finally, in Section 6 we briefly indicate how one can state and prove the results of the paper in a yet more general setting than that of locally finitely presentable categories and finitary monads.

Related Work. Quite a few of sufficient conditions for density of morphisms of finitary monads on sets can be found in textbooks by Ernest Manes [M] (see, e.g., Exercise 6, Section 3, Chapter 3) and by Gavin Wraith [W] (Chapter 12). Beth’s Definability Theorem for (possibly infinitary) varieties on sets was proved by John Isbell in [I_{2}] and our proof of Theorem 4.3 was much inspired by Isbell’s approach. Morphisms of finitary algebraic theories on Set (i.e., morphisms of finitary monads on Set) that satisfy (1.2) were called positive epis by John Isbell in [I_{3}]. We do not adhere to this terminology since we do not work in the internal logic of the ambient category, hence our “definability formula” in Theorem 4.3 below is not, strictly speaking, positive.

Acknowledgement. We would like to thank the referee for valuable comments, for bringing our attention to Isbell’s paper [I_{3}] and for asking the question about factorization systems.

2. Preliminaries

In this section we fix the (mostly standard) notation and terminology we will need later. We do not give any proofs, we refer the reader to corresponding publications instead.

2.1. Monads, Their Morphisms and Their Algebras. The relevance of monads to universal algebra is treated in great detail in the book [M] by Ernest Manes. Therefore we just recall the definitions, the proofs of statements below can all be found in Manes’ book.

A monad on a category 𝒦 is a triple 𝕊 = (S, η^{S}, μ^{S}) consisting of a functor S : 𝒦 ⟶ 𝒦 and natural transformations η^{S} : Id ⟶ S, μ^{S} : SS ⟶ S such that the following diagrams

[figure: S; η^{S}S; SS; μ^{S}; S; Sη^{S}; SSS; Sμ^{S}; μ^{S}S; SS; μ^{S}; S; SS; μ^{S}; S]  (2.1)

commute.

An Eilenberg-Moore algebra for a monad 𝕊 on 𝒦 (or 𝕊-algebra) is a pair (A, a), where a : SA ⟶ A is a morphism in 𝒦 subject to commutativity of the diagrams

[figure: A; η_{A}^{S}; SA; a; SSA; Sa; μ_{A}^{S}; SA; a; A; SA; a; A]  (2.2)

An 𝕊-homomorphism from (A, a) to (B, b) is a morphism h : A ⟶ B making the square

\xymatrix{SA \ar[r]^{Sh} \ar[d]_{a} & SB \ar[d]^{b} \\ A \ar[r]_{h} & B}  (2.3)

commutative.

Algebras for 𝕊 and their homomorphisms form an Eilenberg-Moore category 𝒦 ^{𝕊} equipped with a natural underlying functor U^{𝕊} : 𝒦 ^{𝕊} ⟶ 𝒦 sending (A, a) to A. The functor U^{𝕊} has always a left adjoint sending A to (SA, μ_{A}^{S}) — a free 𝕊-algebra on A.

The full subcategory of 𝒦 ^{𝕊} spanned by free 𝕊-algebras is called the Kleisli category 𝒦_{𝕊} of 𝕊. We will denote the full embedding by

K_{𝕊} : 𝒦_{𝕊} ⟶ 𝒦 ^{𝕊}  (2.4)

A monad morphism between monads 𝕊 = (S, η^{S}, μ^{S}) and 𝕋 = (T, η^{T} , μ^{T}) on 𝒦 is a natural transformation α : S ⟶ T making the following diagrams

\xymatrix{S \ar[rr]^{α} &  & T & SS \ar[r]^{αα} \ar[d]_{μ^{S}} & T T \ar[d]^{μ^{T}} \\  & Id \ar@{-->}[ul]^{η^{S}} \ar@{-->}[ur]_{η^{T}} &  & S \ar[r]_{α} & T}  (2.5)

commutative (where αα denotes the horizontal composition of α with itself, i.e., αα = αT · Sα = T α · αS).

It can be proved that monad morphisms α : 𝕊 ⟶ 𝕋 are in one-to-one correspondence with functors α_{∗} : 𝒦 ^{𝕋} ⟶ 𝒦 ^{𝕊} that commute with the underlying functors, i.e., they correspond to commutative triangles

[figure: 𝒦 ^{𝕋}; α_{∗}; U^{𝕋}; 𝒦 ^{𝕊}; U^{𝕊}; 𝒦]  (2.6)

The functor α_{∗} is given by (A, a) ↦ (A, a · α_{A}) on objects and will be referred to as restriction along α.

Unlike U^{𝕊} and U^{𝕋}, the functor α_{∗} need not have a left adjoint in general. In fact α_{∗} has a left adjoint α^{∗} if and only if coequalizers of the pairs

\xymatrix{(T SA, μ_{SA}^{T}) \ar[r]^{T a} \ar[r]_{μ_{A}^{T}·T α_{A}} & (T A, μ_{A}^{T})}  (2.7)

exist in 𝒦 ^{𝕋} for every 𝕊-algebra (A, a). The value of α^{∗} : 𝒦 ^{𝕊} ⟶ 𝒦 ^{𝕋} at an 𝕊-algebra (A, a) is then the value of the above coequalizer and α^{∗} is defined on morphisms using the universal property of coequalizers.

2.2. Equations w.r.t. a Monad. Example 1.1(2) suggests that we will have to deal with more complex formulae than just identities between terms as it is done in classical universal algebra.

Thus, we are going to consider 𝕊-algebras as first order structures for the first order language having 𝕊-equations as atomic formulae. An 𝕊-equation is a pair

\xymatrix{X \ar[r]^{λ} \ar[r]_{ρ} & SY}

of parallel morphisms. Intuitively, λ picks up an “X-tuple” of 𝕊-terms on Y that form the left-hand sides of the respective system of equations. Similarly, ρ picks up the right-hand sides of the respective system of equations.

Suppose x : Y ⟶ A is given, where (A, a) is an 𝕊-algebra. We say that (A, a) satisfies λ(x) = ρ(x), denoted by

(A, a) ⊧ λ(x) = ρ(x)

if x^{♯} · λ = x^{♯} · ρ holds where x^{♯} : (SY, μ_{Y}^{S}) ⟶ (B, b) denotes the unique extension of x to an 𝕊-homomorphism (recall that (SY, μ_{Y}^{S}) is a free 𝕊-algebra on Y).

The satisfaction of a general sentence in an 𝕊-algebra (B, b) is defined inductively in the usual way. Examples:

1. (B, b) ⊧ ∀x (λ(x) = ρ(x)) means that x^{♯} · λ = x^{♯} · ρ holds for every x : Y ⟶ B.

2. (B, b) ⊧ ∃x (λ(x) = ρ(x)) means that x^{♯} · λ = x^{♯} · ρ holds for some x : Y ⟶ B.

3. (B, b) ⊧ ∃x (λ(x) = ρ(x) ⇒ (σ(x) = τ(x))) means that there exists some x : Y ⟶ B such that x^{♯} · λ = x^{♯} · ρ implies x^{♯} · σ = x^{♯} · τ.

2.3. Example. Let 𝕊 be the monad of semigroups. We show how to express the commutative law for semigroups as an 𝕊-equation.

Denote by 2 the two-element set {x_{1}, x_{2}} and let 1 denote the one-element set {∗}. The mappings

λ : ∗ ↦ x_{1}x_{2} ρ : ∗ ↦ x_{2}x_{1}

are then a parallel pair

\xymatrix{1 \ar[r]^{λ} \ar[r]_{ρ} & S2}

thus, we defined an 𝕊-equation.

Let (B, b) be any semigroup. Then

(B, b) ⊧ ∀x (λ(x) = ρ(x))

holds, if, for every map x : 2 ⟶ B (i.e., for every interpretation of x_{1}, x_{2} in B), the equality x^{♯} ·λ = x^{♯} ·ρ holds. This means precisely that (B, b) is a commutative semigroup.

2.4. Locally Finitely Presentable Categories and Dense Functors. Locally finitely presentable categories were introduced by Peter Gabriel and Friedrich Ulmer in their book [GU]. This concept generalizes the useful property of the category Set: every set can be reconstructed by knowing its finite subsets. It turns out that a set M can be recognized as finite when its hom-functor Set(M, −) : Set ⟶ Set preserves colimits of a certain class, called filtered.

A filtered colimit in general is a colimit of a functor D : 𝒟 ⟶ 𝒦 where 𝒟 is a small category that is filtered, i.e., such that every finite subcategory of 𝒟 admits a cocone in 𝒟. A functor preserving filtered colimits is called finitary. A monad is called finitary if its functor is finitary.

If 𝒦 has filtered colimits, then an object M is called finitely presentable if its homfunctor 𝒦 (M, −) : 𝒦 ⟶ Set is finitary.

2.5. Example.

1. A set is finitely presentable if and only if it is finite.

2. An algebra of a finitary variety is finitely presentable if and only if it is finitely presentable in the ordinary sense of universal algebra, i.e., if it is presented by finitely many finitary equations and finitely many generators.

A general functor F : 𝒟 ⟶ 𝒦 is called dense if its “tilde-conjugate” F̃ : 𝒦 ⟶ [𝒟^{op}, Set] defined by

F̃ : X ↦ 𝒦 (F −, X)

is fully faithful. We will use the concept of density even when the category 𝒟 is not small, since we will assume that the possibly illegitimate presheaf category [𝒟^{op}, Set] exists in some higher universe.

2.6. Definition. A cocomplete category with a small dense subcategory consisting of finitely presentable objects is called locally finitely presentable (l.f.p. for short).

2.7. Remark. L.f.p. categories are exactly the essential algebraic categories over sets, see, e.g., Chapter 3.D of [AR]. This means, roughly speaking, that l.f.p. categories encompass all categories of structures that are defined by equations over finitary partial operations with equationally defined domains. See Example 2.10 for some instances of this fact.

2.8. Notation. In what follows, 𝒦 will always denote an l.f.p. category and E : 𝒜 ⟶ 𝒦 will denote the full embedding of a small dense subcategory representing all finitely presentable objects. Objects of 𝒜 will be denoted by small letters n, m, etc.

It can be proved that E : 𝒜 ⟶ 𝒦 is in fact a free cocompletion of 𝒜 under filtered colimits.

2.9. Example. Suppose 𝕊 is a finitary monad on 𝒦 . The inclusion

A_{𝕊} : 𝒜_{𝕊} ⟶ 𝒦 ^{𝕊}

of the full subcategory spanned by 𝕊-algebras free on objects of 𝒜 is a dense functor. This is proved, e.g., in Theorem 6.9 in [Bi].

Similarly, the inclusion

K_{𝕊} : 𝒦_{𝕊} ⟶ 𝒦 ^{𝕊}

of the Kleisli category in 𝒦 ^{𝕊} is dense, see Example 4.3 of [D_{2}].

2.10. Example.

1. The category Set is l.f.p. As a small dense subcategory representing all finitely presentable objects we choose the category spanned by the sets n = {0, 1, …, n−1}, where n is a natural number.

2. A poset, considered as a category, is l.f.p. if and only if it is an algebraic lattice. Finitely presentable objects are called compact elements in this context.

3. Any finitary variety of universal algebras is l.f.p. As a small dense subcategory representing finitely presentable objects we can choose algebras, finitely presentable in the usual sense.

4. The category Pos of all posets and monotone maps is l.f.p. As a small dense category representing finitely presentable objects one can choose the category of finite posets. The category Pos is not a finitary variety but it is an example of an essentially algebraic category defined by partial operations, see Chapter 3.D of [AR].

5. The category Cat of all small categories and functors is l.f.p. As a small dense subcategory representing finitely presentable objects we can choose categories on finitely many objects subject to a finite set of commutativity conditions.

6. If 𝒦 is l.f.p., so is every functor category [𝒟, 𝒦 ], where 𝒟 is a small category. Thus, all categories [𝒟^{op}, Set] of presheaves are l.f.p.

In particular, the category

Fin(𝒦 , 𝒦 )

of finitary endofunctors of an l.f.p. category 𝒦 is l.f.p., since Fin(𝒦 , 𝒦 ) is equivalent to the functor category [𝒜 , 𝒦 ], because E : 𝒜 ⟶ 𝒦 is a free cocompletion under filtered colimits.

7. Given a finitary monad 𝕊 on an l.f.p. category 𝒦 , then the category 𝒦 ^{𝕊} is l.f.p. Recall from Example 2.9 that the inclusion A_{𝕊} : 𝒜_{𝕊} ⟶ 𝒦 ^{𝕊} is dense and 𝒜_{𝕊} clearly consists of finitely presentable objects in 𝒦 ^{𝕊}. Moreover, the category 𝒦 ^{𝕊} is cocomplete, being reflective in [𝒜_{𝕊}^{op}, Set]. See, e.g., Theorem 6.9 in [Bi].

Consequently, the category

Mnd_{fin}(𝒦 )

of all finitary monads on an l.f.p. category 𝒦 and monad morphisms is l.f.p. This is seen as follows:

(a) The obvious finitary forgetful functor

U : Mnd_{fin}(𝒦 ) ⟶ Fin(𝒦 , 𝒦 )

has a left adjoint given by a free monad F_{H} on a finitary endofunctor H.

(b) Moreover, the functor U is monadic. This means that there exists a (finitary!) monad 𝕊 on Fin(𝒦 , 𝒦 ) such that the category Mnd_{fin}(𝒦 ) is canonically equivalent to the category of 𝕊-algebras. (This fact is easily proved using Beck’s Theorem, see, e.g., Theorem 21.5.7 of [S].)

(c) Now use the fact that Fin(𝒦 , 𝒦 ) is l.f.p., hence Fin(𝒦 , 𝒦 )^{𝕊} (that is, the category of finitary monads on 𝒦 ) is l.f.p.

2.11. The Calculus of Finitary Monads. The calculus of finitary monads on l.f.p. categories was developed by Max Kelly and John Power in their paper [KP]. This beautiful and powerful technique allows one to say that finitary monads “are” indeed finitary algebraic theories on an l.f.p. category, i.e., that finitary monads can be presented by equations and operations of a suitable finitary signature. We recall the basic ideas now, all the details and results can be found in the paper cited above. We will heavily use the equivalence

Fin(𝒦 , 𝒦 ) ≃ [𝒜 , 𝒦 ]

see Example 2.10(6).

A finitary signature Σ is a collection

(Σ(n))_{n}

of objects of 𝒦 indexed by finitely presentable objects of 𝒦 and Σ(n) is the object of n-ary operations.

Every finitary signature Σ gives rise to a corresponding finitary polynomial endofunctor H_{Σ} given by

H_{Σ} : X ↦ ∐_{n} 𝒦 (En, X) • Σ(n)

where 𝒦 (En, X) • Σ(n) denotes the 𝒦 (En, X)-fold copower of Σ(n) and where the coproduct is taken over all finitely presentable objects in 𝒜. Intuitively, H_{Σ}X is the object of flat Σ-terms, i.e., Σ-terms of depth ≤ 1.

A Σ-algebra is an algebra for H_{Σ}, i.e., a pair (A, a), where a : H_{Σ}A ⟶ A is a morphism in 𝒦 (intuitively: the computation of flat Σ-terms in A). A homomorphism of Σ-algebras from (A, a) to (B, b) is a morphism h : A ⟶ B making the square

\xymatrix{H_{Σ}A \ar[r]^{H_{Σ}h} \ar[d]_{a} & H_{Σ}B \ar[d]^{b} \\ A \ar[r]_{h} & B}

commutative.

If we denote by 𝔽_{Σ} = (F_{Σ}, η^{Σ}, μ^{Σ}) the free monad on H_{Σ} (see Example 2.10(7)), it is straightforward to see that the category H_{Σ}-Alg of H_{Σ}-algebras and their homomorphisms is equivalent to the Eilenberg-Moore category 𝒦 ^{𝔽_{Σ}}.

Define the category of finitary signatures on 𝒦 and their homomorphisms as a functor category [|𝒜 |, 𝒦 ] (where |𝒜 | is the discrete category on objects of 𝒜) and denote it by

Sig(𝒦 )

Then we have a series of right adjoints

[figure: Mnd_{fin}(𝒦 ); U; Fin(𝒦 , 𝒦 ); V; Sig(𝒦 )]

where the left adjoint of U gives a free monad on a finitary endofunctor and the left adjoint of V forms a polynomial endofunctor of the given finitary signature.

Steve Lack proved in [L] that the composite V ·U : Mnd_{fin}(𝒦 ) ⟶ Sig(𝒦 ) is monadic (compare with Example 2.10(7)), yielding thus a canonical coequalizer presentation

\xymatrix{𝔽_{Γ} \ar[r]^{λ} \ar[r]_{ρ} & 𝔽_{Σ} \ar[r]^{c_{𝕊}} & 𝕊}  (2.8)

for every finitary monad 𝕊 on 𝒦 , where 𝔽_{Σ} and 𝔽_{Γ} are free monads on suitable signatures Σ and Γ.

What Max Kelly and John Power proved is that the category of Eilenberg-Moore alegbras 𝒦 ^{𝕋} is isomorphic to the full subcategory of 𝔽_{Σ}-algebras (A, a) (or, equivalently, Σ-algebras) satisfying the equation λ = ρ. The idea is to replace algebras for a monad by certain monad morphisms (see Remark 2.14 for the well-known instance of these ideas). This is done as follows:

For every pair A, B of objects in 𝒦 and every finitely presentable object n in 𝒜 define

⟨⟨A, B⟩⟩n = 𝒦 (En, A) ⋔ B

where 𝒦 (En, A) ⋔ B is the 𝒦 (En, A)-fold power of B in 𝒦 . Then the assignment n ↦ ⟨⟨A, B⟩⟩n clearly extends to a functor 𝒜 ⟶ 𝒦 . Thus ⟨⟨A, B⟩⟩ is a finitary endofunctor of 𝒦 if we identify Fin(𝒦 , 𝒦 ) with the functor category [𝒜 , 𝒦 ]. Clearly, the definition of ⟨⟨A, B⟩⟩ is functorial contravariantly in A and covariantly in B. Moreover, the following holds:

2.12. Proposition. Every functor ⟨⟨A, A⟩⟩ has a natural structure of a finitary monad and monad morphisms ǎ : 𝕋 ⟶ ⟨⟨A, A⟩⟩ correspond uniquely to Eilenberg-Moore algebra structures a : T A ⟶ A on A. Moreover, if α : 𝕊 ⟶ 𝕋 is a monad morphism, then the equality

(a · α_{A})ˇ = ǎ · α  (2.9)

holds.

If, for f : A ⟶ B, we form the pullback

\xymatrix{\{\{f, f\}\} \ar[r]^{π_{A}} \ar[d]_{π_{B}} & ⟨⟨A, A⟩⟩ \ar[d]^{⟨⟨A,f⟩⟩} \\ ⟨⟨B, B⟩⟩ \ar[r]_{⟨⟨f,B⟩⟩} & ⟨⟨A, B⟩⟩}  (2.10)

in Fin(𝒦 , 𝒦 ) then the following holds:

2.13. Proposition. {{f, f}} has canonically a structure of a finitary monad and there exists a monad morphism 𝕋 ⟶ {{f, f}} precisely when f carries a 𝕋-algebra homomorphism between the corresponding 𝕋-algebras.

Consider now the diagram

\xymatrix{𝔽_{Γ} \ar[r]^{λ} \ar[r]_{ρ} & 𝔽_{Σ} \ar[r]^{c_{𝕊}} \ar[dr] & 𝕊 \ar[d] \\  &  & ⟨⟨A, A⟩⟩}

to conclude that monad morphisms 𝕊 ⟶ ⟨⟨A, A⟩⟩ (i.e., 𝕊-algebras) correspond bijectively to monad morphisms 𝔽_{Σ} ⟶ ⟨⟨A, A⟩⟩ that coequalize the pair λ, ρ (i.e., to the Σ-algebras that satisfy the equations λ, ρ). Replacing ⟨⟨A, A⟩⟩ by {{f, f}} in the above diagram one obtains the corresponding bijection of hom-sets, proving that the category of 𝕊-algebras and their homomorphisms is equivalent to the category of Σ-algebras that satisfy λ = ρ and their homomorphisms.

2.14. Remark. In fact, the above calculus of monads is a generalization of a well known fact about actions of monoids: denote, for sets A, B, by ⟨⟨A, B⟩⟩ the set of all maps from A to B.

This definition is clearly functorial contravariantly in A and covariantly in B. Moreover, it is well-known that every set ⟨⟨A, A⟩⟩ carries a natural structure of a monoid w.r.t. composition. Furthermore, given any monoid 𝕋 = (T, e, ∗), there is an evident bijection between monoid homomorphisms from 𝕋 to ⟨⟨A, A⟩⟩ and monoid actions T × A ⟶ A (compare with Proposition 2.12).

If we define, for a map f : A ⟶ B, the set {{f, f}} as a pullback

\xymatrix{\{\{f, f\}\} \ar[r]^{π_{A}} \ar[d]_{π_{B}} & ⟨⟨A, A⟩⟩ \ar[d]^{⟨⟨A,f⟩⟩} \\ ⟨⟨B, B⟩⟩ \ar[r]_{⟨⟨f,B⟩⟩} & ⟨⟨A, B⟩⟩}

i.e., elements of {{f, f}} are pairs (h : A ⟶ A, k : B ⟶ B) such that f · h = k · f, then {{f, f}} becomes a monoid in a natural way. In fact, {{f, f}} is a submonoid of a product ⟨⟨A, A⟩⟩ × ⟨⟨B, B⟩⟩ via the map ⟨π_{A}, π_{B}⟩ (we will use a generalization of this fact in Corollary 5.5 below).

Moreover, to give a monoid homomorphisms from a monoid 𝕋 to {{f, f}} is to say that f : A ⟶ B is an equivariant map between the action of 𝕋 on A and B, respectively (compare with Proposition 2.13).

3. Sufficient Conditions for Density

3.1. Assumption. In the rest of the paper 𝒦 denotes a fixed l.f.p. category, E : 𝒜 ⟶ 𝒦 the inclusion of a small dense subcategory representing all finitely presentable objects of 𝒦 . By α : 𝕊 ⟶ 𝕋 we always denote a morphism of finitary monads on 𝒦 .

3.2. Definition. A monad morphism α : 𝕊 ⟶ 𝕋 is called dense if the restriction-along-α functor α_{∗} : 𝒦 ^{𝕋} ⟶ 𝒦 ^{𝕊} is fully faithful.

Since 𝒦 (and hence 𝒦 ^{𝕋}, see Example 2.10(7)) is cocomplete, the functor α_{∗} always has a left adjoint α^{∗} (see (2.7)) and by a general result on adjunctions, α_{∗} is fully faithful if and only if α^{∗} is dense (see, e.g., Proposition 17.2.6 of [S]). This motivated our choice of terminology.

In this section we mention various sufficient conditions for density of α that are mostly well-known and are often very easy to verify in practice. Most of the properties suggest that density of α is a kind of “epimorphism” condition, as, for example, the following trivial property:

3.3. Lemma. Dense monad morphisms compose and if the composite β · α is dense, so is β.

3.4. Lemma. Every pointwise epimorphic monad morphism is dense.

Proof. Consider the diagram

\xymatrix{SA \ar[r]^{Sh} \ar[d]_{α_{A}} & SB \ar[d]^{α_{B}} \\ T A \ar[r]^{T h} \ar[d]_{a} & T B \ar[d]^{b} \\ A \ar[r]_{h} & B}

where (A, a) and (B, b) are arbitrary 𝕋-algebras. If the perimeter of the above diagram commutes, so does the lower square since α_{A} is epi.

3.5. Remark. In fact, pointwise epimorphic α characterize abstractly Birkhoff subcategories of 𝒦 ^{𝕊}, see Theorem 3.3.4 of [M]. A Birkhoff subcategory of 𝒦 ^{𝕊} is one where we add equations to the presentation of 𝕊, see the theorem in [M] mentioned above. An example of a Birkhoff subcategory in groups is the subcategory of Abelian groups.

However, the full inclusion α_{∗} : Groups ⟶ Monoids (see Example 1.1(2)) is an example of a dense α that is not pointwise epimorphic.

Observe that by (2.5) every α_{A} is an 𝕊-homomorphism from (SA, μ_{A}^{S}) to α_{∗}(T A, μ_{A}^{T}).

3.6. Lemma. Suppose α_{m} : (Sm, μ_{m}^{S}) ⟶ α_{∗}(T m, μ_{m}^{T}) is an epimorphism in 𝒦 ^{𝕊} for every finitely presentable object m. Then α is dense.

Proof. We prove first that that the action of α_{∗} is a bijection on every hom-set of the form 𝒦 ^{𝕋}((T m, μ_{m}^{T}), (B, b)), where m is finitely presentable and (B, b) is an arbitrary 𝕋-algebra.

Let h : α_{∗}(T m, μ_{m}^{T}) ⟶ α_{∗}(B, b) be any 𝕊-homomorphism. The unique 𝕋-homomorph-ism extending the composite h · η_{m}^{T} : m ⟶ B is denoted by h′ : (T m, μ_{m}^{T}) ⟶ (B, b). We want to prove that α_{∗}(h′) = h. But this follows from the fact that the diagram

\xymatrix{(Sm, μ_{m}^{S}) \ar[r]^{α_{m}} & α_{∗}(T m, μ_{m}^{T}) \ar[r]^{h} \ar[r]_{α_{∗}(h′)} & α_{∗}(B, b)}

clearly commutes and from the assumption that α_{m} is an epimorphism in 𝒦 ^{𝕊}. Expressing every free 𝕋-algebra (T A, μ_{A}^{T}) as a filtered colimit

T f : (T m, μ_{m}^{T}) ⟶ (T A, μ_{A}^{T})

where f : m ⟶ A, we conclude that the action of α_{∗} is a bijection on every hom-set of the form 𝒦 ^{𝕋}((T A, μ_{A}^{T}), (B, b)), where A is arbitrary and (B, b) is an arbitrary 𝕋-algebra.

Finally, let us choose any 𝕊-homomorphism h : α_{∗}(A, a) ⟶ α_{∗}(B, b). Express (A, a) as a canonical coequalizer

\xymatrix{(T T A, μ_{T A}^{T}) \ar[r]^{μ_{A}^{T}} \ar[r]_{T a} & (T A, μ_{A}^{T}) \ar[r]^{a} & (A, a)}

in 𝒦 ^{𝕋} and consider the following commutative diagram

\xymatrix{α_{∗}(T T A, μ_{T A}^{T}) \ar[r]^{α_{∗}(μ_{A}^{T})} \ar[r]_{α_{∗}(T a)} & α_{∗}(T A, μ_{A}^{T}) \ar[r]^{α_{∗}(a)} \ar@{.>}[dr]_{α_{∗}(k′)} & α_{∗}(A, a) \ar[d]^{h} \\  &  & α_{∗}(B, b)}

We know that the composite h · α_{∗}(a) is of the form α_{∗}(k′) for some 𝕋-homomorphism k′ : (T A, μ_{A}^{T}) ⟶ (B, b) necessarily coequalizing the pair T a, μ_{A}^{T} : (T T A, μ_{T A}^{T}) ⟶ (T A, μ_{A}^{T}). Hence k′ induces a unique 𝕋-homomorphism h′ : (A, a) ⟶ (B, b) for which α_{∗}(h′) = h holds.

3.7. Example. The above lemma can be applied to the case of α_{∗} : Groups ⟶ Monoids, see Example 1.1(2), since the inclusion of a free monoid into a free group on the same (finite) set is an epimorphism of monoids.

3.8. Remark. It should be noted that the condition on α_{m} of Lemma 3.6 can be easily modified into a necessary and sufficient condition for density of α:

Say that α_{m} : (Sm, μ_{m}^{S}) ⟶ α_{∗}(T m, μ_{m}^{T}) is an α_{∗}-epimorphism in 𝒦 ^{𝕊} if from h·α_{m} = k ·α_{m} the equality h = k follows for any parallel pair h, k : α_{∗}(T m, μ_{m}^{T}) ⟶ α_{∗}(B, b) of 𝕊-homomorphisms.

Then α is dense if and only if every α_{m} is α_{∗}-epimorphism in 𝒦 ^{𝕊}.

For sufficiency, read the proof of Lemma 3.6. Conversely, if α is dense and if h · α_{m} = k · α_{m} holds for a parallel pair h, k : α_{∗}(T m, μ_{m}^{T}) ⟶ α_{∗}(B, b) of 𝕊-homomorphisms, then h = α_{∗}(h′) and k = α_{∗}(k′) for a unique parallel pair h′, k′ : (T m, μ_{m}^{T}) ⟶ (B, b) of 𝕋-homomorphisms. Observe that h′ = k′ holds, since both h′ and k′ extend the same morphism:

h′ · η_{m}^{T} = h · α_{m} · η_{m}^{S} = k · α_{m} · η_{m}^{S} = k′ · η_{m}^{T}

We conclude that h = k.

3.9. Lemma. Every regular epimorphism in Mnd_{fin}(𝒦 ) (especially, every split epimorphism) is dense.

Proof. Consider a coequalizer

\xymatrix{ℙ \ar[r]^{λ} \ar[r]_{ρ} & 𝕊 \ar[r]^{α} & 𝕋}

in Mnd_{fin}(𝒦 ). This coequalizer gives rise to an equalizer

\xymatrix{𝒦 ^{𝕋} \ar[r]^{α_{∗}} & 𝒦 ^{𝕊} \ar[r]^{λ_{∗}} \ar[r]_{ρ_{∗}} & 𝒦 ^{ℙ}}

of functors that commute with (faithful) forgetful functors. Thus, α_{∗} is fully faithful.

Recall that a monad 𝕊 is called idempotent if the underlying functor U^{𝕊} : 𝒦 ^{𝕊} ⟶ 𝒦 is fully faithful.

3.10. Lemma. A monad morphism α : 𝕊 ⟶ 𝕋 with 𝕊 idempotent is a dense morphism if and only if 𝕋 is idempotent.

Proof. The statement follows from the fact that U^{𝕊} · α_{∗} = U^{𝕋} holds, hence U^{𝕋} is fully faithful if and only if α_{∗} is fully faithful.

Recall that by A_{𝕊} : 𝒜_{𝕊} ⟶ 𝒦 ^{𝕊}, A_{𝕋} : 𝒜_{𝕋} ⟶ 𝒦 ^{𝕋}, resp., we denote the full dense subcategories of 𝕊-algebras, 𝕋-algebras, resp., spanned by algebras free on finitely presentable objects (see Example 2.9). Every monad morphism α : 𝕊 ⟶ 𝕋 then induces a functor

A_{α} : 𝒜_{𝕊} ⟶ 𝒜_{𝕋}  (3.1)

sending every 𝕊-algebra (Sn, μ_{n}^{S}) to (T n, μ_{n}^{T}) and every 𝕊-homomorphism h : (Sn, μ_{n}^{S}) ⟶ (Sm, μ_{m}^{S}) to a 𝕋-homomorphism (α_{m} · h · η_{n}^{S})^{∗} : (T n, μ_{n}^{T}) ⟶ (T m, μ_{m}^{T}). Here by upper star we denote the unique extension to a 𝕋-homomorphism.

Clearly, the above process can be performed for arbitrary free algebras, yielding a functor

K_{α} : 𝒦_{𝕋} ⟶ 𝒦_{𝕊}  (3.2)

3.11. Lemma. If the functor [A_{α}^{op}, Set] : [𝒜_{𝕋}^{op}, Set] ⟶ [𝒜_{𝕊}^{op}, Set] is fully faithful, then α is a dense monad morphism.

Proof. The square

\xymatrix{𝒦 ^{𝕋} \ar[r]^{Ã_{𝕋}} \ar[d]_{α_{∗}} & [𝒜_{𝕋}^{op}, Set] \ar[d]^{[A_{α}^{op},Set]} \\ 𝒦 ^{𝕊} \ar[r]_{Ã_{𝕊}} & [𝒜_{𝕊}^{op}, Set]}  (3.3)

is easily seen to commute (up to isomorphism). Its diagonal is fully faithful by assumption, thus, the functor α_{∗} is fully faithful.

3.12. Remark. Functors F : 𝒞 ⟶ 𝒟 between general small categories with [F^{op}, Set] fully faithful are called connected and they were characterized in [ABSV] as those for which the canonical morphism

∫ ^{C} 𝒟(D′, F C) × 𝒟(F C, D) ⟶ 𝒟(D′, D)

given by composition is an isomorphism.

4. Beth’s Definability Theorem

In this section we characterize dense monad morphisms in “Beth style” and give some connections between dense monad morphisms and the density of induced functors between Kleisli categories.

The following concept captures the notion of “explicit definability”.

4.1. Definition. We say that an n-tuple τ : n ⟶ T m of m-ary 𝕋-operations is 𝕊definable, if there exists an equation of the form

\xymatrix{m + n + p \ar[r]^{λ_{τ}} \ar[r]_{ρ_{τ}} & S(m + n + q)}

with p, q finitely presentable, such that

α_{∗}(A, a) ⊧ ∀x∀y (y = τ(x) ⇔ ∃t (λ_{τ}(x, y, t) = ρ_{τ}(x, y, t)))

holds for every 𝕋-algebra (A, a).

4.2. Example.

1. As mentioned in the introduction, inverses in groups are definable in the language of monoids. More precisely, every group (G, ∗, e, (−)^{−1}) satisfies the sentence

∀x∀y (y = x^{−1} ⇔ x ∗ y = e ∧ y ∗ x = e)

Thus, if 𝕊 and 𝕋 are the finitary monads on Set that correspond to the theory of monoids and groups, respectively, then (−)^{−1} : 1 ⟶ T 1 is 𝕊-definable.

2. Complements in Boolean algebras are definable in the language of distributive lattices having the least and the greatest elements: the sentence

∀x∀y (y = ¬x ⇔ (x ⊓ y = ⊥ ∧ x ⊔ y = ⊤))

is satisfied in every Boolean algebra (B, ⊓, ⊔, ⊥, ⊤, ¬(−)).

3. Greatest common divisors in Euclidean rings are definable in the language of rings: every Euclidean ring (R, +, ·, 0, 1, gcd(−, −)) satisfies the sentence

∀x∀x′∀y (y = gcd(x, x′) ⇔ ∃k∃k′∃a∃a′(x = k · y ∧ x′ = k′ · y ∧ y = a · x + a′ · x′))

4. Joins and meets in Boolean algebras are definable in the language of MV-algebras (see [C]): every Boolean algebra (B, ⊓, ⊔, ⊥, ⊤, ¬(−)) satisfies the following two sentences

\begin{matrix}∀x∀x′∀y (y = x ⊔ x′ ⇔ y = ¬(¬x ⊕ x′) ⊕ x′) \\ ∀x∀x′∀y (y = x ⊓ x′ ⇔ y = ¬(¬x ⊔ ¬x′)) \end{matrix}

5. Every n-tuple σ : n ⟶ Sm of m-ary 𝕊-operations is 𝕊-definable. Consider the equation λ_{σ}, ρ_{σ} : n ⟶ S(m + n) with

\xymatrix{λ_{σ} ≡ n \ar[r]^{σ} & Sm \ar[r]^{Sinl} & S(m + n)}

and

\xymatrix{ρ_{σ} ≡ n \ar[r]^{η_{n}^{S}} & Sn \ar[r]^{Sinr} & S(m + n)}

DENSE MORPHISMS OF MONADS  387

Then every 𝕊-algebra of the form α_{∗}(A, a) (indeed, every 𝕊-algebra) satisfies the sentence

∀x∀y (y = σ(x) ⇔ λ_{σ}(x, y) = ρ_{σ}(x, y))

as it is easily seen. The concept of 𝕊-definability allows us to characterize dense monad morphisms:

4.3. Theorem. The following are equivalent:

1. α : 𝕊 ⟶ 𝕋 is a dense monad morphism.

2. Every 𝕊-homomorphism α_{∗}(T k, μ_{k}^{T}) ⟶ α_{∗}(A, a), where k is finitely presentable, is a 𝕋-homomorphism (T k, μ_{k}^{T}) ⟶ (A, a).

3. Every n-tuple of m-ary 𝕋-operations is 𝕊-definable. Proof. That (1) implies (2) and (3) implies (1) is trivial. It remains to prove that (2) implies (3): Suppose an n-tuple τ : n ⟶ T m of m-ary 𝕋-operations is given. The plan of the proof is as follows: we exhibit first a “large” 𝕊-equation L_{τ}, R_{τ}, that will witness 𝕊-definability of τ and then we reduce it to a “small” 𝕊-equation λ_{τ}, ρ_{τ}, using finitarity of 𝕊 and 𝕋.

Define first an equation

\xymatrix{m + n + ST m \ar[r]^{L_{τ} =[L^{(i)},L^{(ii)},L^{(iii)}]} \ar[r]_{R_{τ} =[R^{(i)},R^{(ii)},R^{(iii)}]} & S(m + n + T m)}

with the following properties (where (A, a) is an arbitrary 𝕋-algebra):

(i) α_{∗}(A, a) ⊧ L^{(i)}(x, y, t) = R^{(i)}(x, y, t) if and only if t · η_{m}^{T} = x. (ii) α_{∗}(A, a) ⊧ L^{(ii)}(x, y, t) = R^{(ii)}(x, y, t) if and only if t · τ = y. (iii) α_{∗}(A, a) ⊧ L^{(iii)}(x, y, t) = R^{(iii)}(x, y, t) if and only if t is an 𝕊-homomorphism from

α_{∗}(T m, μ_{m}^{T}) to α_{∗}(A, a). The individual equations are defined as follows:

(i) Put

\xymatrix{L^{(i)} ≡ m \ar[r]^{η_{m}^{S}} & Sm \ar[r]^{Sinl} & S(m + n + T m) \\ R^{(i)} ≡ m \ar[r]^{η_{m}^{T}} & T m \ar[r]^{inr} & m + n + T m \ar[r]^{η_{m+n+T m}^{S}} & S(m + n + T m)}

Let (A, a) be any 𝕋-algebra and let [x, y, t] : m + n + T m ⟶ A be any morphism. Then the equations

[x, y, t]^{♯} · L^{(i)} = [x, y, t]^{♯} · Sinl · η_{m}^{S} = x^{♯} · η_{m}^{S} = x

and

[x, y, t]^{♯} · R^{(i)} = [x, y, t]^{♯} · η_{m+n+T m}^{S} · inr · η_{m}^{T} = [x, y, t] · inr · η_{m}^{T} = t · η_{m}^{T}

hold, thus, α_{∗}(A, a) ⊧ L^{(i)}(x, y, t) = R^{(i)}(x, y, t) if and only if t · η_{m}^{T} = x.

(ii) Put

\xymatrix{L^{(ii)} ≡ n \ar[r]^{inm} & m + n + T m \ar[r]^{η_{m+n+T m}^{S}} & S(m + n + T m) \\ R^{(ii)} ≡ n \ar[r]^{τ} & T m \ar[r]^{inr} & m + n + T m \ar[r]^{η_{m+n+T m}^{S}} & S(m + n + T m)}

Let (A, a) be any 𝕋-algebra and let [x, y, t] : m + n + T m ⟶ A be any morphism. Then the equations

[x, y, t]^{♯} · L^{(ii)} = [x, y, t]^{♯} · η_{m+n+T m}^{S} · inm = [x, y, t] · inm = y

and

[x, y, t]^{♯} · R^{(ii)} = [x, y, t]^{♯} · η_{m+n+T m}^{S} · inr · τ = [x, y, t] · inr · τ = t · τ

hold, thus, α_{∗}(A, a) ⊧ L^{(ii)}(x, y, t) = R^{(ii)}(x, y, t) if and only if t · τ = y.

(iii) Put

\xymatrix{L^{(iii)} ≡ ST m \ar[r]^{α_{T m}} & T T m \ar[r]^{μ_{m}^{T}} & T m \ar[r]^{inr} & m + n + T m \ar[r]^{η_{m+n+T m}^{S}} & S(m + n + T m) \\ R^{(iii)} ≡ ST m \ar[r]^{Sinr} & S(m + n + T m)}

Then the equations

[x, y, t]^{♯} ·L^{(iii)} = [x, y, t]^{♯} ·η_{m+n+T m}^{S} ·inr·μ_{m}^{T} ·α_{T m} = [x, y, t]·inr·μ_{m}^{T} ·α_{T m} = t·μ_{m}^{T} ·α_{T m}

and

[x, y, t]^{♯} · R^{(iii)} = [x, y, t]^{♯} · Sinr = a · α_{A} · St

hold, thus, α_{∗}(A, a) ⊧ L^{(iii)}(x, y, t) = R^{(iii)}(x, y, t) if and only if t is an 𝕊-homo-morphism from α_{∗}(T m, μ_{m}^{T}) to α_{∗}(A, a).

We proved so far that α_{∗}(A, a) ⊧ L_{τ}(x, y, t) = R_{τ}(x, y, t) if and only if t is the unique 𝕋-homomorphism from (T m, μ_{m}^{T}) to (A, a) (since α_{∗} is assumed to be bijective on homomorphisms from (T m, μ_{m}^{T}) to (A, a)) that extends x : m ⟶ A and satisfies t · τ = y (or, equivalently, the equality τ(x) = y holds).

Suppose that x, y is given and y = τ(x) holds, then it suffices to put t to be the extension of x. If x, y are given such that y ≠ τ(x), then there is no extension of x into a 𝕋-homomorphism t since this would imply y = τ(x).

We now reduce the “large” equation L_{τ}, R_{τ} to a finitary one. Consider all morphisms f : p ⟶ ST m with p finitely presentable and suppose that for every such f there exists a 𝕋-algebra (A_{f}, a_{f}) and a triple [x_{f}, y_{f}, t_{f}] : m + n + T m ⟶ A_{f} such that y_{f} ≠ τ(x_{f}) and the diagram

\xymatrix{m + n + p \ar[r]^{id+id+f} & m + n + ST m \ar[r]^{L_{τ}} \ar[r]_{R_{τ}} & S(m + n + T m) \ar[r]^{[x_{f} ,y_{f} ,t_{f}]^{♯}} & α_{∗}(A_{f}, a_{f})}

commutes. Since

∏_{f} α_{∗}(A_{f}, a_{f}) ≅ α_{∗}(∏_{f}(A_{f}, a_{f}))

holds, this shows that the unique induced morphism

[x, y, t]^{♯} : S(m + n + T m) ⟶ α_{∗}(∏_{f}(A_{f}, a_{f}))

coequalizes L_{τ}, R_{τ} and y ≠ τ(x) holds, a contradiction.

Therefore we may choose f : p ⟶ ST m with p finitely presentable such that the equation

\xymatrix{m + n + p \ar[r]^{id+id+f} & m + n + ST m \ar[r]^{L_{τ}} \ar[r]_{R_{τ}} & S(m + n + T m)}  (4.1)

does the same job as L_{τ}, R_{τ}. Express now S(m + n + T m) as a filtered colimit with the colimit cocone

S(id+id+g) : S(m+n+q) ⟶ S(m+n+T m), g : q ⟶ T m with q finitely presentable

and use the fact that m + n + p is finitely presentable to obtain the following factorization of (4.1)

[figure: m + n + p; id+id+f; m + n + ST m; S(m + n + q); S(id+id+g); λ_{τ}; ρ_{τ}; S(m + n + T m)] (4.2)

through a colimit. In this way we obtain the desired λ_{τ}, ρ_{τ}. Clearly, if [x, y, t]^{♯} coequalizes (4.1) then [x, y, t · g]^{♯} coequalizes λ_{τ}, ρ_{τ}. Conversely, if [x, y, t]^{♯} coequalizes λ_{τ}, ρ_{τ}, let t^{∗} : T m ⟶ A be the unique extension of x to a 𝕋-homomorphism. Then [x, y, t^{∗}]^{♯} coequalizes (4.1).

4.4. Remark.

1. The equivalence of (1) and (3) of the above theorem is indeed Beth’s Definability Theorem for finitary monads: the implication (1) ⇒ (3) says that every implicitly defined operation (i.e., one preserved by 𝕊-homomorphisms) is defined explicitly by a system of 𝕊-equations. The implication (3) ⇒ (1) is then the trivial part of Beth’s Definability Theorem: every explicitly defined operation is preserved by 𝕊homomorphisms.

2. Let us stress that the proof of (2) ⇒ (3) in Theorem 4.3 is non-constructive which makes it, in general, difficult to find the definability 𝕊-equation.

3. One can prove the equivalence of (1) and (3) in a more general setting, imposing no restriction on 𝒦 , 𝕊 and 𝕋 whatsoever. One has to require 𝕊-definability of every τ : X ⟶ T Y, where X and Y are arbitrary objects of 𝒦 . In proving (1) ⇒ (3) one defines an equation

\xymatrix{Y + X + ST Y \ar[r]^{L_{τ}} \ar[r]_{R_{τ}} & S(Y + X + T Y)}

in the same way as in the above proof. Of course, one cannot expect to reduce the above system to a “smaller” one.

4. We show in Example 4.8 below that one cannot weaken the condition (2) of the above theorem to the requirement that α_{∗} is fully faithful when restricted to 𝒜_{𝕋}, the category of 𝕋-algebras free on finitely presentable objects of 𝒦 .

4.5. Example. It is well-known (see [PS]) that the change-of-ring functor α_{∗} : T -Mod ⟶ S-Mod between the categories of left modules is fully faithful if and only if α : S ⟶ T is an epimorphism of rings with a unit. This fits into our framework since every ring S with a unit can be considered as a finitary monad by assigning (an underlying set of) a free left S-module S^{(X)} on X to every set X. Moreover, ring homomorphisms correspond then precisely to morphisms of the corresponding monads.

Observe that an n-tuple τ : n ⟶ T^{(m)} of m-ary 𝕋 operations is just a matrix (τ_{ij}) of elements of T having n rows and m columns. We will denote this matrix by τ again.

Suppose A is any left T -module and x : m ⟶ A, y : n ⟶ A are “vectors” of elements of A. Then τ(x) = y holds if and only if the system

τ · x = y

of linear equations holds in A.

Analogously, an 𝕊-equation

\xymatrix{m + n + p \ar[r]^{λ_{τ}} \ar[r]_{ρ_{τ}} & S^{(m+n+q)}}

consists of a pair λ_{τ}, ρ_{τ} of matrices over S having (m + n + p) rows and (m + n + q) columns.

Theorem 4.3 then gives us the following characterization of ring epimorphisms α : S ⟶ T:

For every pair n, m of natural numbers and for every (n × m)-matrix τ of elements of T there exist ((m + n + p) × (m + n + q))-matrices λ_{τ}, ρ_{τ} of elements of S, such that, for every left T -module A, and each pair x, y of vectors of A, the system

τ · x = y

of linear equations holds in A if and only if the system

λ_{τ} · ( \begin{matrix}x \\ y \\ t \end{matrix} ) = ρ_{τ} · ( \begin{matrix}x \\ y \\ t \end{matrix} )

has a solution t in A.

4.6. Example. Considerations similar to the previous example can be made to characterize epimorphisms of monoids.

If we identify a monoid S with a one-object category, then the category S-Act of left S-actions and equivariant maps can be identified with the presheaf category [S^{op}, Set].

Given a monoid homomorphism a : S ⟶ T, then the restriction-along-a functor [a^{op}, Set] : [T^{op}, Set] ⟶ [S^{op}, Set] is fully faithful if and only if a : S ⟶ T is an epimorphism of monoids, as proved in Example 3.13(3) of [BV].

Now every monoid S in sets defines a finitary monad 𝕊 on the category of sets by putting X ↦ S × X and, analogously, every monoid homomorphism a : S ⟶ T defines a monad morphism α : 𝕊 ⟶ 𝕋 having α_{X} = a × X : S × X ⟶ T × X as components. Moreover, the restriction-along-a functor is of the form α_{∗}, since the categories of left actions are precisely the categories of Eilenberg-Moore algebras for the respective monads. We conclude:

The monad morphism α is dense if and only if a is an epimorphism of monoids.

Identify every τ : n ⟶ T × m with an n-tuple (τ_{i}, j_{i}). Suppose that A is equipped with a left T -action denoted by ∘. Then for x : m ⟶ A and y : n ⟶ A the equality τ(x) = y holds if and only if the system of equations

y_{i} = τ_{i} ∘ x_{j_{i}}, i = 0, …, n − 1

holds in A. Now we can use Theorem 4.3 to characterize monoid epimorphisms in the style of Example 4.5.

Recall the functors A_{α} : 𝒜_{𝕊} ⟶ 𝒜_{𝕋} and K_{α} : 𝒦_{𝕊} ⟶ 𝒦_{𝕋} (see (3.1) and (3.2)).

4.7. Proposition. The following are equivalent:

1. α is a dense monad morphism.

2. The composite A_{𝕋} · A_{α} : 𝒜_{𝕊} ⟶ 𝒦 ^{𝕋} is a dense functor.

3. The composite K_{𝕋} · K_{α} : 𝒦_{𝕊} ⟶ 𝒦 ^{𝕋} is a dense functor.

Proof. To prove (1) ⇔ (2) observe that the diagonal of the square (3.3) is the functor { \atop A_{𝕋} · A_{α}}. It is fully faithful (i.e., A_{𝕋} · A_{α} is dense) if and only if α_{∗} is fully faithful, since the horizontal arrows of (3.3) are fully faithful (see Example 2.9).

The proof of (1) ⇔ (3) is analogous: instead of (3.3) one uses the commutative square

\xymatrix{𝒦 ^{𝕋} \ar[r]^{K̃_{𝕋}} \ar[d]_{α_{∗}} & [𝒦_{𝕋}^{op}, Set] \ar[d]^{[K_{α}^{op},Set]} \\ 𝒦 ^{𝕊} \ar[r]_{K̃_{𝕊}} & [𝒦_{𝕊}^{op}, Set]}  (4.3)

(which is even a bipullback, as proved by Fred Linton in [Li_{2}]).

4.8. Example. We give an example of a functor α_{∗} : 𝒦 ^{ℝ} ⟶ 𝒦 ^{𝔽} that is not fully faithful, although its restriction to 𝒦_{ℝ} is fully faithful.

Given a finitary endofunctor H : 𝒦 ⟶ 𝒦 , consider the free monad 𝔽 on H. Then it is easy to see that 𝒦 ^{𝔽} is isomorphic to the category H-Alg of H-algebras and their homomorphisms.

We define the full subcategory H-Alg_{it} of iterative H-algebras as follows: an algebra a : HA ⟶ A is iterative, if for any e : X ⟶ HX + A there is a unique e^{†} : X ⟶ A making the diagram

\xymatrix{X \ar[r]^{e^{†}} \ar[d]_{e} & A \\ HX + A \ar[r]_{He^{†}+A} & HA + A \ar[u]_{[a,A]}}

commutative. (See [AMV] for the motivation of this concept.)

It can be proved that H-Alg_{it} is reflective in H-Alg. Thus, there exist free iterative H-algebras, RA, on any object A. The monad ℝ of free iterative algebras, called the rational monad of H, is finitary and there is a canonical monad morphism α : 𝔽 ⟶ ℝ. The category 𝒦 ^{ℝ} is identified as the category of Elgot algebras in [AMV], i.e., structures (A, a, (−)^{†}) consisting of a H-algebra (A, a) and a mapping (−)^{†} : 𝒦 (X, HX + A) ⟶ 𝒦 (X, A) satisfying certain axioms. However, the functor α_{∗} : 𝒦 ^{ℝ} ⟶ 𝒦 ^{𝔽} is not fully faithful in general, although its restriction to 𝒦_{ℝ} is always fully faithful, see Example 4.3 of [AMV].

Detecting, when the restriction of α_{∗} to Kleisli category is fully faithful, is easy:

4.9. Proposition. The following are equivalent:

1. The restriction of α_{∗} to 𝒦_{𝕋} is fully faithful.

2. The functor K_{α} : 𝒦_{𝕊} ⟶ 𝒦_{𝕋} is dense.

Proof. Consider the diagram

[figure: 𝒦_{𝕋}; K_{𝕋}; 𝒦 ^{𝕋}; K̃_{𝕋}; α_{∗}; [𝒦_{𝕋}^{op}, Set]; [K_{α}^{op},Set]; Y; 𝒦 ^{𝕊}; K̃_{𝕊}; [𝒦_{𝕊}^{op}, Set]]

where the square is the diagram (4.3). The passage from 𝒦_{𝕋} to [𝒦_{𝕊}^{op}, Set] is the functor K̃_{α} and it is fully faithful if and only if α_{∗} · K_{𝕋} is fully faithful.

4.10. Remark. Proposition 4.9 and Example 4.8 form a counterexample to Proposition 5.1 of [D_{2}]:

Given a dense functor N : ℒ ⟶ 𝒦_{𝕋} the composite K_{𝕋}N : ℒ ⟶ 𝒦 ^{𝕋} is dense.

Were the above true, then α_{∗} : 𝒦 ^{𝕋} ⟶ 𝒦 ^{𝕊} would be fully faithful whenever its restriction to 𝒦_{𝕋} is fully faithful. This is seen as follows: Suppose that the restriction of α_{∗} to 𝒦_{𝕋} is fully faithful. By Proposition 4.9 we conclude that K_{α} is dense. By the above claim the composite K_{𝕋}K_{α} : 𝒦_{𝕊} ⟶ 𝒦 ^{𝕋} is dense. Thus, the diagonal { \atop K_{𝕋}K_{α}} of the square

\xymatrix{𝒦 ^{𝕋} \ar[r]^{K̃_{𝕋}} \ar[d]_{α_{∗}} & [𝒦_{𝕋}^{op}, Set] \ar[d]^{[K_{α}^{op},Set]} \\ 𝒦 ^{𝕊} \ar[r]_{K̃_{𝕊}} & [𝒦_{𝕊}^{op}, Set]}

is fully faithful. We proved that α_{∗} is fully faithful. By considering α : 𝔽 ⟶ ℝ of Example 4.8 we obtain a contradiction.

5. Position of Dense Monad Morphisms in the Category of Monads

In this section we locate dense monad morphisms as those in between the class of strong epimorphisms and the class of epimorphisms in the category

Mnd_{fin}(𝒦 )

of finitary monads on 𝒦 and their morphisms. The main result of this section, Theorem 5.4 below, then characterizes dense monad morphisms by a simple orthogonality condition. This is used for showing that dense monad morphisms are the “epis” of a factorization system on Mnd_{fin}(𝒦 ), see Proposition 5.8.

The following proposition answers in negative the first question of Exercise 3.3.6(d) in [M].

5.1. Proposition. α : 𝕊 ⟶ 𝕋 is an epimorphism of monads if and only if α_{∗} : 𝒦 ^{𝕋} ⟶ 𝒦 ^{𝕊} is injective on objects.

Proof. Form the cokernel of α in Mnd_{fin}(𝒦 ) and consider the unique connecting morphism τ : coker(α) ⟶ 𝕋:

[figure: 𝕊; α; α; 𝕋; inr; id; 𝕋; inl; id; coker(α); τ; 𝕋]  (5.1)

Then α is an epimorphism if and only if τ above is an isomorphism. Since τ is (always) a split epimorphism, it is dense by Lemma 3.9, hence

τ_{∗} : 𝒦 ^{𝕋} ⟶ 𝒦 ^{coker(α)}

is fully faithful.

It therefore suffices to prove that α_{∗} is injective on objects if and only if τ_{∗} is bijective on objects.

By Proposition 2.12 coker(α)-algebras are pairs ((A, a), (A, b)) of 𝕋-algebras with α_{∗}(A, a) = α_{∗}(A, b). Therefore α_{∗} is injective on objects if and only if coker(α)-algebras are pairs ((A, a), (A, a)) of 𝕋-algebras.

Hence α_{∗} is injective on objects if and only if τ_{∗} (or, equivalently, τ) is an isomorphism.

5.2. Corollary. Every dense monad morphism is an epimorphism.

Proof. Suppose α : 𝕊 ⟶ 𝕋 is dense and let α_{∗}(A, a) = α_{∗}(B, b). Then necessarily A = B and identity is a morphism from α_{∗}(A, a) to α_{∗}(A, b). Since α_{∗} is fully faithful, identity is a morphism from (A, a) to (A, b).

5.3. Example. It has been proved by John Isbell [I_{1}] that the monad morphism α : 𝕊 ⟶ 𝕋, where 𝕊 is the monad of semigroups and 𝕋 is the monad of monoids, is an epimorphism in Mnd_{fin}(Set). This can also easily be seen by employing Proposition 5.1, since the forgetful functor

α_{∗} : Monoids ⟶ Semigroups

is injective on objects. However, α_{∗} is not fully faithful, thus, the above α is an example of an epimorphism which is not dense in Mnd_{fin}(Set).

Recall from [K_{1}] that, in any category, a morphism a : A ⟶ B is called orthogonal to a morphism b : C ⟶ D, if for every commutative square

\xymatrix{A \ar[r]^{a} \ar[d]_{u} & B \ar[d]^{v} \\ C \ar[r]_{b} & D}

there exists a unique diagonal morphism d : B ⟶ C making both triangles commutative. The orthogonality characterization of dense monad morphisms is the following one:

5.4. Theorem. The following are equivalent:

1. α : 𝕊 ⟶ 𝕋 is dense.

2. α is orthogonal to every monad morphism of the form ⟨π_{A}, π_{B}⟩ : {{f, f}} ⟶ ⟨⟨A, A⟩⟩ × ⟨⟨B, B⟩⟩.

Proof. Consider the following diagram

\xymatrix{𝕊 \ar[r]^{α} \ar[d] & 𝕋 \ar[d]^{⟨ǎ,b̌⟩} \\ \{\{f, f\}\} \ar[r]_{⟨π_{A},π_{B}⟩} & ⟨⟨A, A⟩⟩ × ⟨⟨B, B⟩⟩}

in Mnd_{fin}(𝒦 ). Then the (necessarily unique) diagonal monad morphism 𝕋 ⟶ {{f, f}} witnesses precisely the fact that α_{∗} is fully faithful.

Recall from [K_{1}] that strong epimorphisms are defined as those morphisms that are orthogonal to every monomorphism. The above theorem has then the following corollary:

5.5. Corollary. Every strong epimorphism in Mnd_{fin}(𝒦 ) is dense.

Proof. Observe that every morphism of the form ⟨π_{A}, π_{B}⟩ : {{f, f}} ⟶ ⟨⟨A, A⟩⟩×⟨⟨B, B⟩⟩ is a monomorphism.

5.6. Example. We provide an example of a dense monad morphism that is not strong epimorphic.

We will use the fact that the category Fin(Set, Set) is equivalent to the category [Set_{fp}, Set], where E : Set_{fp} ⟶ Set is the inclusion of a small full subcategory representing finite sets.

First observe that regular epimorphisms in the category [Set_{fp}, Set] coincide with (pointwise) epimorphisms. Thus, the horizontal composite τσ = τK′ · Hσ = H′σ · τK : HK ⟶ H′K′ is a regular epimorphism for every pair τ : H ⟶ H′, σ : K ⟶ K′ of regular epimorphisms.

Observe further that the functor H ↦ F_{H} on Fin(Set, Set) which assigns to every finitary endofunctor H the underlying functor F_{H} of the free monad 𝔽_{H} on H preserves regular epimorphisms: for let τ : H ⟶ H′ be pointwise an epimorphism. Then we have a chain τ_{0}, τ_{1}, …, of connecting epimorphisms:

[figure: W_{0}; w_{0,1}; τ_{0}; W_{1}; w_{1,2}; τ_{1}; W_{2}; w_{2,3}; τ_{2}; …; w_{k−1,k}; W_{k}; w_{k,k+1}; τ_{k}; W_{k+1}; w_{k+1,k+2}; τ_{k+1}; …; W′_{0}; w′_{0,1}; W′_{1}; w′_{1,2}; W′_{2}; w′_{2,3}; …; w′_{k−1,k}; W′_{k}; w′_{k,k+1}; W′_{k+1}; w′_{k+1,k+2}; …]

where the horizontal chains have F_{H}, resp. F_{H′} as a colimit, i.e., W_{0} = W′_{0} = Id , W_{k+1} = HW_{k} + Id, W′_{k+1} = HW′_{k} + Id, and w_{0,1} = inr : Id ⟶ H + Id, w′_{0,1} = inr : Id ⟶ H′ + Id, w_{k+1,k+2} = Hw_{k,k+1} + id. The connecting morphisms are defined by putting τ_{0} = id : Id ⟶ Id and τ_{k+1} = ττ_{k} + id : W_{k+1} ⟶ W′_{k+1} and they are all pointwise epimorphisms. So is the induced connecting morphism F_{τ} : colim W_{k} ⟶ colim W′_{k}.

Thus, a monad morphism is a regular epimorphism in Mnd_{fin}(Set) if and only if it is a regular epimorphism as a natural transformation in Fin(Set, Set), see. e.g., Theorem 21.6.3(d) of [S].

Therefore regular epimorphisms in Mnd_{fin}(Set) are closed under composition and thus strong epimorphisms coincide with regular epimorphisms in Mnd_{fin}(Set) by Proposition 3.8 of [K_{1}].

We conclude that the full inclusion α_{∗} : Groups ⟶ Monoids is an example of a dense α such that α is not strong epimorphic. This follows from the fact that α is not (regular) epi in Fin(Set, Set).

Recall from, e.g., [FK] the following definition.

5.7. Definition. A factorization system (ℰ , ℳ) on a category 𝒦 consists of two classes of morphisms ℰ and ℳ such that the following three conditions are satisfied:

1. Both ℰ and ℳ contain all isomorphisms and are closed under composition.

2. Every morphism in 𝒦 can be factored as a morphism in ℰ followed by a morphism in ℳ.

3. For every commutative square

\xymatrix{A \ar[r]^{e} \ar[d]_{u} & B \ar[d]^{v} \\ C \ar[r]_{m} & D}

with e ∈ ℰ and m ∈ ℳ, there exists a unique diagonal morphism d : B ⟶ C making both triangles commutative.

Given a factorization system (ℰ , ℳ), it can be proved that elements of ℰ behave very much like epimorphisms and elements of ℳ are then the corresponding “monomorphisms”. We prove now that dense monad morphisms are epimorphisms in this broad sense:

5.8. Proposition. The class of dense monad morphisms is an “epi” part of a factorization system on Mnd_{fin}(𝒦 ).

Proof. Denote by ℋ the class of all morphisms of the form

⟨π_{A}, π_{B}⟩ : {{f, f}} ⟶ ⟨⟨A, A⟩⟩ × ⟨⟨B, B⟩⟩

Then (by Theorem 5.4) the class of dense morphisms is of the form ℋ ^{↑}, i.e., dense monad morphisms are exactly those orthogonal to the class ℋ . Form the class ℋ ^{↑↓}, i.e., ℋ ^{↑↓} is the class of all morphisms orthogonal to dense morphisms. Then the pair

(ℋ ^{↑}, ℋ ^{↑↓})

constitutes a prefactorization system on Mnd_{fin}(𝒦 ) in the sense of [FK]. To prove that it is in fact a factorization system, we only need to know that every monad morphism factors as a dense morphism followed by a morphism in ℋ ^{↑↓} (Corollary 2.2.2 of [FK]). This fact, however, follows immediately from Lemma 2.3.2 of [FK], since Mnd_{fin}(𝒦 ), being locally finitely presentable and well-powered, has intersections of arbitrary families of monomorphisms in ℋ ^{↑↓}.

We were not able to obtain an explicit characterization of morphisms in ℋ ^{↑↓}. However, we have:

Every monad morphism α : 𝕊 ⟶ 𝕋 such that α^{∗} : 𝒦 ^{𝕊} ⟶ 𝒦 ^{𝕋} reflects isomorphisms is in ℋ ^{↑↓}.

This follows from the fact that any left adjoint between sufficiently complete categories can be factored as a reflection onto a full subcategory followed by an isomorphism-reflecting left adjoint (see, e.g., Proposition 5.1 of [D_{1}]).

5.9. Open Problem. Are the “monos” that correspond to dense monad morphisms precisely those monad morphisms α for which α^{∗} reflects isomorphisms?

6. Possible Generalizations

The above results can be easily generalized in two ways:

1. All main results of this paper go through verbatim if one systematically replaces locally finitely presentable categories and finitary monads by locally 𝔻-presentable categories and 𝔻-accessible monads for a limit doctrine 𝔻, as introduced in [ABLR].

Besides an obvious generalization to λ-presentable categories and λ-accessible monads for an uncountable regular cardinal λ (see [GU]) we obtain thus, e.g., results for the interesting doctrine 𝔻 of finite products (replacing thus filtered colimits with sifted colimits).

2. One can also start with a symmetric monoidal closed category 𝒱 that is locally finitely presentable as a monoidal category (see [K_{3}]) and choose it as a base category for category theory enriched over 𝒱 , see [K_{2}]. An example of such a base category is the category Ab of Abelian groups and group homomorphisms. An Ab-category is then one that has Abelian groups as hom-objects and its composition maps are group homomorphisms.

Replacing systematically categories and functors by 𝒱 -categories and 𝒱 -functors one obtains the corresponding results on dense morphisms between 𝒱 -monads.

References

[ABSV] J. Adámek, R. El Bashir, M. Sobral and J. Velebil, On functors which are lax epimorphisms, Theor. Appl. Categ. 8 (2001), 509–521

[ABLR] J. Adámek, F. Borceux, S. Lack and J. Rosický, A classification of accessible categories, Jour. Pure Appl. Algebra 175 (2002), 7–30

[AMV] J. Adámek, S. Milius and J. Velebil, Elgot algebras, Logical Methods in Computer Science Vol. 2(5:4) (2006), 1–31

[AR] J. Adámek and J. Rosický, Locally Presentable and Accessible Categories, Cambridge University Press, 1994

[BV] R. El Bashir and J. Velebil, Simultaneously reflective and coreflective subcategories of presheaves, Theor. Appl. Cat., 10 (2002), 410–423

[Be] E. W. Beth, On Padoa’s method in the theory of definition, Indag. Math. 15 (1953), 330–339

[Bi] G. J. Bird, Limits in 2-categories of locally presented categories, Ph. D. Thesis, The University of Sydney, 1984

[C] C. C. Chang, Algebraic analysis of many-valued logics, Trans. Amer. Math. Soc. 88 (1958), 467–490

[D_{1}] B. J. Day, On adjoint-functor factorisation, in Category Seminar, Lecture Notes in Mathematics Vol. 420, Springer 1974, 1–19

[D_{2}] B. J. Day, Density presentations of functors, Bull. Austral. Math. Soc. 16 (1977), 427–448

[FK] P. J. Freyd and G. M. Kelly, Categories of continuous functors I, J. Pure Appl. Alg., 2 (1972), 169–191

[GU] P. Gabriel and F. Ulmer, Lokal präsentierbare Kategorien, Lecture Notes in Mathematics 221, Springer 1971 [I_{1}] J. R. Isbell, General functorial semantics, Amer. J. Math. XCIV (1972), 535–

594

[I_{2}] J. R. Isbell, Functional implicit operations, Israel J. Math. 15 (1973), 185–188

[I_{3}] J. R. Isbell, Generic algebras, Trans. Amer. Math. Soc 275.2 (1983), 497–510

[K_{1}] G. M. Kelly, Monomorphisms, epimorphisms and pull-backs, J. Aust. Math. Soc. IX (1969), 124–142

[K_{2}] G. M. Kelly, Basic Concepts of Enriched Category Theory, London Math. Soc. Lecture Notes Series 64, Cambridge Univ. Press, 1982, also available as TAC reprint via

         http://www.tac.mta.ca/tac/reprints/articles/10/tr10abs.html

[K_{3}] G. M. Kelly, Structures defined by finite limits in the enriched context I, Cahiers de Top. et Géom. Diff. XXIII (1982), 3–42

[KP] G. M. Kelly and A. J. Power, Adjunctions whose counits are coequalizers and presentations of enriched monads, J. Pure Appl. Alg., 89 (1993), 163–179

[L] S. Lack, On the monadicity of finitary monads, J. Pure Appl. Alg. 140 (1999), 65–73

[Li_{1}] F. E. J. Linton, Some aspects of equational categories, in Proceedings of the Conference on Categorical Algebra, La Jolla 1965 (eds. S. Eilenberg and S. MacLane), 84–94

[Li_{2}] F. E. J. Linton, An outline of functorial semantics, Lecture Notes in Mathematics Vol. 80, Springer 1969, 7-50

[M] E. G. Manes, Algebraic Theories, Graduate Texts in Mathematics, Springer, 1976

[PS] N. Popescu and T. Spircu, Quelques observations sur les épimorphismes plats (à gauche) d’anneaux, J. Algebra 16 (1970), 40–59

[S] H. Schubert, Categories, Springer-Verlag, 1972

[W] G. Wraith, Algebraic Theories, Aarhus University Lecture Notes No. 22, 1975

Department of Mathematics, University of Patras, Patras, Greece Faculty of Electrical Engineering, Czech Technical University, Prague, Czech Republic

Email: pkarazer@math.upatras.gr
velebil@math.feld.cvut.cz

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

ftp://ftp.tac.mta.ca/pub/tac/html/volumes/18/14/18-14.{dvi,ps,pdf}

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. Full text of the journal is freely available in .dvi, Postscript and PDF from the journal’s server at http://www.tac.mta.ca/tac/ and by ftp. It is archived electronically and in printed paper format.

Subscription information. Individual subscribers receive abstracts of articles by e-mail as they are published. 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 strongly encouraged. Articles should be submitted by e-mail directly to a Transmitting Editor. Please obtain detailed information on submission format and style files at http://www.tac.mta.ca/tac/.

Managing editor. Robert Rosebrugh, Mount Allison University: rrosebrugh@mta.ca

TEXnical editor. Michael Barr, McGill University: mbarr@barrs.org

Transmitting editors.

Richard Blute, Université d’ Ottawa: rblute@uottawa.ca Lawrence Breen, Université de Paris 13: breen@math.univ-paris13.fr Ronald Brown, University of North Wales: r.brown@bangor.ac.uk Aurelio Carboni, Università dell Insubria: aurelio.carboni@uninsubria.it Valeria de Paiva, Xerox Palo Alto Research Center: paiva@parc.xerox.com

Ezra Getzler, Northwestern University: getzler(at)math(dot)northwestern(dot)edu

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@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 Jiri Rosicky, Masaryk University: rosicky@math.muni.cz Brooke Shipley, University of Illinois at Chicago: bshipley@math.uic.edu 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