Theory and Applications of Categories, Vol. 24, No. 4, 2010, pp. 84–113.

MONADS AS EXTENSION SYSTEMS —NO ITERATION IS NECESSARY

F. MARMOLEJO AND R. J. WOOD

Abstract. We introduce a description of the algebras for a monad in terms of extension systems, similar to the one for monads given in [Manes, 1976]. We rewrite distributive laws for monads and wreaths in terms of this description, avoiding the iteration of the functors involved. We give a profunctorial explanation of why Manes’ description of monads in terms of extension systems works.

1. Introduction

For adjoint functors S ⊣ H, it has been well known since [Eilenberg & Moore, 1965] that monad structures on S are in bijective correspondence with comonad structures on H. Moreover, it is shown in [Eilenberg & Moore, 1965] that if (𝕊, ℍ) is a corresponding (monad, comonad) pair then the category of 𝕊-algebras is isomorphic to the category of ℍ coalgebras via a functor that identifies the forgetful functors. After [Street, 1972] it has been clear that these results of [Eilenberg & Moore, 1965] are actually part of the formal theory of monads, the definitions making sense in any 2-category and the theorems being provable in any suitably complete 2-category. It was acknowledged in [Lack & Street, 2002] that the formal theory of monads is easily adjusted to the greater generality of bicategories, although it suffices to prove most results in a general 2-category. Where possible we take the latter point of view in this paper.

The bijective correspondence of the nullary data

[figure: η: 1; S; ε: H; 1]

for monads and comonads is accomplished by a single application of taking mates with respect to the adjunction S ⊣ H (in any 2-category). For the binary components, it is useful to consider the correspondence of the data as a three-step mating process:

[figure: μ: SS; S; ξ: S; HS; λ: SH; H; δ: H; HH]

The second author gratefully acknowledges continuing financial support from the Canadian NSERC.

Received by the editors 2009-10-25 and, in revised form, 2010-04-01.

Transmitted by F. W. Lawvere. Published on 2010-04-03.

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

Key words and phrases: extension systems, monads, distributive laws, wreaths, profunctors.

\begin{matrix}c \\ ◯ \end{matrix} F. Marmolejo and R. J. Wood, 2010. Permission to copy for private use granted.

This leads us to contemplate not only monads 𝕊 = (S, η, μ), and comonads ℍ = (H, ε, δ) but also 3-tuples (S ⊣ H, η, ξ) and (S ⊣ H, ε, λ). For each of the latter two, it is a simple matter to determine three equations so that the correspondences of the data above extend to the resulting equational structures. We give such equations for an (S ⊣ H, η, ξ), which we then call an extension system, in Section 9. The experienced reader will see immediately how to prescribe equations making an (S ⊣ H, ε, λ) what we would call a lifting system, although we will say little, explicitly, about these. We will speak of ξ as an extension operator, which terminology has already been used, for a special case, in [Manes & Mulry, 2007].

Suppose that (S ⊣ H, η, ξ) is an extension system on an object C in a bicategory K. Then, for every A, B : T → C in K, we have the composite functions

K(T, C)(B, SA) → K(T, C)(B, HSA) → K(T, C)(SB, SA)

where the first factor is given by composition with ξA and the second by taking mates with respect to S ⊣ H. This composite, which we will call (−)^{𝕊}, satisfies equations, which we will give in Section 2, but no longer requires that S have a right adjoint in K. Accordingly, we generalize the definition of extension system to include the case where S does not necessarily have a right adjoint and show in Section 2 that, given η : 1_{C} → S : C → C in K, there is a bijective correspondence between monads (S, η, μ) and extension systems (S, η, (−)^{𝕊}).

In [Manes, 1976], Exercise 1.3, p. 32, monads in Cat were presented as extension systems in which the data η: 1_{C} → S: C → C on a category C required only that S be initially given as an object function |S|: |C| → |C| and η as a function defined on |C| with no a priori naturality requirement. We are able to analyse this simplification in Cat by considering the canonical embedding of Cat in Pro, the bicategory of profunctors. Here we use the fact that any category C is, in Pro, the Kleisli object for a canonical monad ℂ on |C|. We discuss this in Section 9. We remark that when considering extension systems in Cat, we can always regard the situation as taking place in Pro, where every functor in Cat has a right adjoint, and exploit the simpler form that extension systems take in the presence of a right adjoint.

We define algebras for an extension system and, interpolating the aforementioned theorem of [Eilenberg & Moore, 1965], show that if (S, η, μ) and (S, η, (−)^{𝕊}) correspond then the categories of algebras for each are isomorphic via an arrow that identifies the forgetful arrows. Thus we are able to think of extension systems and their algebras as no more than an alternate presentation for monads. However, there is an important overarching reason to consider monads in this way. Extension systems allow us to completely dispense with the iterates SS and SSS of the underlying arrow. No iteration is necessary. A moment’s reflection on the various terms of terms and terms of terms of terms that occur in practical applications suggest that this alone justifies the alternate approach. We give examples in Section 8.

We use the simplicity of the approach to further advance the general theory of monads with respect to composition of monads via both distributive laws, Sections 4 and 6, and wreaths, Sections 5 and 7. Here we are able to make use of alternate formulations of distributive laws first given in [Marmolejo, Rosebrugh, Wood, 2002]. In anticipation of further work, we note that extension systems in higher dimensional category theory provide an even more important simplification of monads. For even in dimension 2, some of the tamest examples are built on pseudofunctors that are difficult to iterate.

2. Extension systems in a 2-category

In the Introduction we motivated the idea of an extension system in terms of monad-like data with underlying arrow S: C → C in a 2-category, in the case that S is part of an adjunction S ⊣ H. However, it is the non-elementary definition, that we can state without the assumption of a right adjoint for S, that is most useful for our work. After a preliminary Definition and Lemma we take this as our starting point.

We work in a 2-category K. Let

[figure: C; D; E; S; U; T; ε]  (1)

be a 2-cell (in K). For any span of arrows (C, D) : T → C;D, pasting ε at S defines a family of functions

(−)_{D,C}^{#} : K(T, D)(D, SC) → K(T, E)(T D, UC)

whose effect on d in K(T, D)(D, SC) is the pasting composite

[figure: T; C; D; E; C; D; S; U; T; ε; d]

This 2-cell, whose full name is d_{D,C}^{#}, will often be written simply as d^{#}. The family of functions (−)_{D,C}^{#} respects whiskering at T, meaning that for any X: S → T,

d^{#}X = (dX)^{#}  (2)

and respects blistering at D, meaning that for any b: B → D: T → D,

(db)^{#} = d^{#} · T b  (3)

2.1. Definition. A pasting operator

(−)^{#} : K(T, D)(1, S) → K(T, E)(T, U)

is a family of functions

(−)_{D,C}^{#} : K(T, D)(D, SC) → K(T, E)(T D, UC)

which respects whiskering and blistering.

2.2. Lemma. For arrows S, T, U configured as is in (1), pasting operators

K(T, D)(1, S) → K(T, E)(T, U)

are in bijective correspondence with 2-cells T S → U.

Proof. Given a pasting operator (−)^{#} : K(T, D)(1, S) → K(T, E)(T, U), we have

(1_{S})_{S,1_{C}}^{#} : T S → U.

Moreover, it is easy to see that any d: D → SC arises by whiskering 1_{S} at C by C and blistering the result at SC by d. Thus any (−)^{#} : K(T, D)(1, S) → K(T, E)(T, U) is completely determined by (1_{S})_{S,1_{C}}^{#} and the latter can be any 2-cell T S → U. It follows that the assignment (−)^{#} ↦ (1_{S})_{S,1_{C}}^{#} is a bijection.

2.3. Definition. Let C be an object in a 2-category K. An extension system on C consists of an arrow S: C → C, a 2-cell η: 1_{C} → S, and a pasting operator

(−)^{𝕊}: K(T, C)(1, S) → K(T, C)(S, S)

that we call the 𝕊-extension operator. This data is subject to the following equations, for every C, B, A: T → C, f : B → SA, and g: C → SB,

η^{𝕊} = 1_{S},  (4)
\xymatrix{B \ar[r]^{ηB} \ar[dr]_{f} & SB \ar[d]^{f^{𝕊}} \\  & SA,}  (5)

and

\xymatrix{SC \ar[r]^{g^{𝕊}} \ar[dr]_{(f^{𝕊}g)^{𝕊}} & SB \ar[d]^{f^{𝕊}} \\  & SA.}  (6)

2.4. Theorem. For η: 1_{C} → S: C → C in a 2-category K, there is a bijective correspondence between extension systems (S, η, (−)^{𝕊}) and monads (S, η, μ).

Proof. By Lemma 2.2 we have a bijection between pasting operators (−)^{𝕊} and 2-cells μ: SS → S. Let (S, η, μ) be a monad. The correspondence of Lemma 2.2 provides f^{𝕊} = μA · Sf : SB → SA. Now (4) is one of the unit monad axioms, while (5) is

f^{𝕊} · ηB = μA · Sf · ηB = μA · ηSA · f = f

using the other unit monad axiom, and (6) is

f^{𝕊} · g^{𝕊} = μA · Sf · μB · Sg = μA · μSA · SSf · Sg = μA · SμA · SSf · Sg
= μA · S(μA · Sf · g) = (f^{𝕊} · g)^{𝕊}

using monad associativity; so that (S, η, (−)^{𝕊}) is an extension system.

On the other hand, if (S, η, (−)^{𝕊}) is an extension system, the correspondence of Lemma 2.2 provides μ = 1_{S}^{𝕊}. The first monad equation is μ · ηS = 1_{S}^{𝕊} · ηS = 1_{S} by (5). The second is μ · Sη = 1_{S}^{𝕊} · Sη = η^{𝕊} = 1_{S}, by (3) and (4). Monad associativity is given by

μ · Sμ = 1_{S}^{𝕊} · Sμ = μ^{𝕊} = (1_{S}^{𝕊})^{𝕊} = 1_{S}^{𝕊} · 1_{S^{2}}^{𝕊} = 1_{S}^{𝕊} · 1_{S}^{𝕊}S = μ · μS,

using (2), (3), and (6); so that (S, η, μ) is a monad.

From now on we do not need to distinguish between monads and extension systems. If (S, η, (−)^{𝕊}) and (S, η, μ) correspond, we write (S, η, (−)^{𝕊}) = 𝕊 = (S, η, μ) and use freely the equations relating both. Note too that, for b: B → D: T → C, we have

Sb = (ηD · b)^{𝕊},  (7)

which we leave as a simple exercise.

3. Algebras for extension systems

Notwithstanding the last paragraph, in the spirit of [Eilenberg & Moore, 1965], we give a definition of algebras for an extension system.

3.1. Definition. For (S, η, (−)^{𝕊}) an extension system on C and X an object, both in K, an (S, η, (−)^{𝕊})-algebra with domain X is a pair 𝔹 = (B, (−)^{𝔹}), where B: X → C and

(−)^{𝔹}: K(T, C)(1, B) → K(T, C)(S, B)

is a pasting operator that we call the 𝔹-extension operator, subject to the following equations, for every h: Y → BD and k: Z → SY : T → C,

\xymatrix{Y \ar[r]^{ηY} \ar[dr]_{h} & SY \ar[d]^{h^{𝔹}} \\  & BD,}  (8)

\xymatrix{SZ \ar[r]^{k^{𝕊}} \ar[dr]_{(h^{𝔹}·k)^{𝔹}} & SY \ar[d]^{h^{𝔹}} \\  & BD.}  (9)

A homomorphism p: (B, (−)^{𝔹}) → (A, (−)^{𝔸}) of (S, η, (−)^{𝕊})-algebras with domain X is a 2-cell p: B → A subject to the following equation, for every h: Y → BD,

\xymatrix{SY \ar[r]^{h^{𝔹}} \ar[dr]_{(pD·h)^{𝔸}} & BD \ar[d]^{pD} \\  & AD.}  (10)

It is easy to see that (S, η, (−)^{𝕊})-algebras with domain X and their homomorphisms form a category K(X, (C, (S, η, (−)^{𝕊})) equipped with a forgetful functor to K(X, C). We recall the (S, η, μ)-algebras with domain X as described in [Street, 1972] or [Marmolejo, 1997] and write K(X, (C, (S, η, μ))) for these.

3.2. Theorem. The categories K(X, (C, (S, η, (−)^{𝕊}))) and K(X, (C, (S, η, μ))) are isomorphic via a functor that identifies the forgetful functors.

Proof. By Lemma 2.2, pasting operators (−)^{𝔹}: K(T, C)(1, B) → K(T, C)(S, B) are in bijective correspondence with 2-cells β: SB → B. It suffices to show that the equations for algebras and their homomorphisms in either sense correspond to those in the other sense. Let (B, (−)^{𝔹}) be an (S, η, (−)^{𝕊})-algebra and consider (B, 1_{B}^{𝔹}), where 1_{B}^{𝔹} arises from (−)^{𝔹} as in Lemma 2.2. We have 1_{B}^{𝔹} · ηB = 1_{B} by (8), and

1_{B}^{𝔹} · S 1_{B}^{𝔹} = 1_{B}^{𝔹} · (ηB · 1_{B}^{𝔹})^{𝕊} = (1_{B}^{𝔹} · ηB · 1_{B}^{𝔹})^{𝔹} = (1_{B}^{𝔹})^{𝔹}
= 1_{B}^{𝔹} · (1_{SB})^{𝕊} = 1_{B}^{𝔹} · 1_{S}^{𝕊}B = 1_{B}^{𝔹} · μB,

by (7), (9), (8), (9) and (2). If p: (B, (−)^{𝔹}) → (A, (−)^{𝔸}) is a homomorphism of (S, η, (−)^{𝕊})- algebras then we have

1_{A}^{𝔸} · Sp = 1_{A}^{𝔸} · (ηA · p)^{𝕊} = (1_{A}^{𝔸} · ηA · p)^{𝔸} = p^{𝔸} = p · 1_{B}^{𝔹},

by (7), (9), (8), and (10), showing that we also have p: (B, (1_{B})^{𝔹}) → (A, (1_{A})^{𝔸}), a homomorphism of (S, η, μ)-algebras.

On the other hand, if (B, β) is an (S, η, μ)-algebra then, for h: Y → BD: Y → C,

define h^{𝔹} = SY [figure: Sh]SBD [figure: βD]BD. Now (8) is h^{𝔹}·ηY = βD·Sh·ηY = βD·ηBD·h = h, and (9) is

(h^{𝔹} · k)^{𝔹} = βD · SβD · S^{2}h · Sk = βD · μBD · S^{2}h · Sk
= βD · Sh · μY · Sk = h^{𝔹} · k^{𝕊}.

If p: (B, β) → (A, α) is an (S, η, μ)-homomorphism, then (p·h)^{𝔸} = α·Sp·Sh = p·β ·Sh = p · h^{𝔹} establishes (10) showing that we also have an (S, η, (−)^{𝕊})-homomorphism.

Thus we do not need to distinguish between (S, η, (−)^{𝕊})-algebras and (S, η, μ)-algebras and speak simply of 𝕊-algebras, freely using all the equations now at hand.

4. The 2-category Mnd(K)

Let K be a 2-category. Recall from [Street, 1972] that an object of the 2-category Mnd(K) consists of a pair (C, 𝕊) where C is an object of K and 𝕊 is a monad on C, that a 1-cell from (D, 𝕋) to (C, 𝕊) consists of a 1-cell F : D → C and a 2-cell λ: SF → F T in K such that the diagrams

\xymatrix{ & F \ar[dl]_{η_{S} F} \ar[dr]^{F η_{T}} &  & S^{2}F \ar[r]^{Sλ} \ar[d]_{μ_{S} F} & SF T \ar[r]^{λT} & F T^{2} \ar[d]^{F μ_{T}} \\ SF \ar[rr]_{λ} &  & F T & SF \ar[rr]_{λ} &  & F T}

commute, and that a 2-cell (F, λ) → (F′, λ′) : (D, 𝕋) → (C, 𝕊) consists of a 2-cell φ: F → F′ in K such that the diagram

\xymatrix{SF \ar[r]^{λ} \ar[d]_{Sφ} & F T \ar[d]^{φT} \\ SF′ \ar[r]_{λ′} & F′T}

commutes.

In the spirit of Proposition 3.4 in [Marmolejo, Rosebrugh, Wood, 2002] (where it is done for distributive laws), we have the following lemma.

4.1. Lemma. Given F : D → C, there is a bijection between 2-cells λ: SF → F T making (F, λ) : (D, 𝕋) → (C, 𝕊) a 1-cell of Mnd(K) and 2-cells α: SF T → F T making (F T, α) an 𝕊-algebra satisfying the equation

\xymatrix{SF T^{2} \ar[r]^{αT} \ar[d]_{SF μ_{T}} & F T^{2} \ar[d]^{F μ_{T}} \\ SF T \ar[r]_{α} & F T.}

Moreover, if under the given bijection λ and α correspond, given F : D → C, and λ′ and α′ correspond, given F′: D → C, then a 2-cell φ: F → F′ gives a 2-cell φ: (F, λ) → (F′, λ′) of Mnd(K) if and only if φT : F T → F′T is an 𝕊-homomorphism.

Proof. If we start with α, then λ = α · SF η_{T}. In the opposite direction, given λ, define α = F μ_{T} · λT.

Denote the 2-category implicitly defined by the above lemma with 1-cells (F, α) : (D, 𝕋) → (C, 𝕊) by Mnd′(K). Observe that the composition of 1-cells (G, β) : (E, 𝕌) → (D, 𝕋) and (F, α) : (D, 𝕋) → (C, 𝕊) is given by F G together with

\xymatrix{SF GU \ar[r]^{SF η_{T} GU} & SF T GU \ar[r]^{αGU} & F T GU \ar[r]^{F β} & F GU.}

4.2. Corollary. The correspondences above define an identity-on-objects isomorphism of 2-categories Mnd(K) → Mnd′(K), so that Mnd′(K) can be regarded as Mnd(K).

4.3. Theorem. Let 𝕋 = (T, η_{T} , (−)^{𝕋}) be a monad on D, and let 𝕊 = (S, η_{S}, (−)^{𝕊}) be a monad on C. A 1-cell in Mnd(K) from (D, 𝕋) to (C, 𝕊) can equivalently be defined as follows: (F, (−)^{λ}) : (D, 𝕋) → (C, 𝕊) where F : D → C, and (F T, (−)^{λ}) is an 𝕊-algebra, such that for every u: U → T V : X → D and h: X → F T U : X → C, the diagram

\xymatrix{SX \ar[r]^{h^{λ}} \ar[dr]_{(F u^{𝕋}·h)^{λ}} & F T U \ar[d]^{F u^{𝕋}} \\  & F T V}  (11)

commutes.

Furthermore, given (F, (−)^{λ}), (F′, (−)^{λ′}) : (D, 𝕋) → (C, 𝕊), then φ: F → F′ is a 2-cell in Mnd(K) if and only if φT : (F T, (−)^{λ}) → (F′T, (−)^{λ′}) is a morphism of 𝕊-algebras.

Proof. According to Theorem 3.2 we have that pasting operators (−)^{λ}: K(X, C)(1, F T) → K(X, C)(S, F T) that make (F T, (−)^{λ}) an 𝕊-algebra are in bijective correspondence with 2-cells α : SF T → F T that make (F T, α) an 𝕊-algebra. So we must show that the extra equation given in the statement of the theorem is satisfied if and only if the extra equation given in Lemma 4.1 is satisfied.

Given (F, (−)^{λ}) as in the statement of the theorem, we have that

α := (1_{F T})^{λ}: SF T → F T.

The extra equation is F μ_{T} ·αT = F (1_{T}^{𝕋})·(1_{F T^{2}})^{λ} = F (1_{T}^{𝕋})^{λ} = (1_{F T}^{λ} ·η_{S}F T ·F (1_{T}^{𝕋}))^{λ} = 1_{F T}^{λ} · (η_{S}F T · F (1_{T}^{𝕋}))^{𝕊} = α · SF μ_{T}. Thus (F, α) : (D, 𝕋) → (C, 𝕊) is a 1-cell in Mnd′(K).

In the opposite direction, assume that (F, α) : (D, 𝕋) → (C, 𝕊) is a 1-cell in Mnd′(K). Then for h: X → F T U : X → C we have that

h^{λ} := [figure: SX; SF T U; F T U.; Sh; αU]  (12)

For u: U → T V, the commutative diagram

\xymatrix{SX \ar[r]^{Sh} \ar[ddr]_{S(F (u^{𝕋})·h)} & SF T U \ar[r]^{αU} \ar[d]_{SF T u} & F T U \ar[d]^{F T u} \\  & SF T^{2}V \ar[r]_{αT V} \ar[d]^{SF μ_{T} V} & F T^{2}V \ar[d]^{F μ_{T} V} \\  & SF T V \ar[r]_{αV} & F T V}

gives us (11).

4.4. Remark. Observe that in the previous theorem we can obtain λ: ST → T S directly from the pasting operator (−)^{λ} as (F η_{T})^{λ} to obtain a 1-cell (F, λ) : (D, 𝕋) → (C, 𝕊) as described at the beginning of this section.

5. The 2-category EM(K)

Recall from [Lack & Street, 2002] that the 2-category EM(K) has the same objects and 1cells as Mnd(K), but the 2-cells (F, λ) → (F′, λ′) : (D, 𝕋) → (C, 𝕊) are 2-cells ρ: F → F′T in K such that the diagram

\xymatrix{SF \ar[r]^{λ} \ar[d]_{Sρ} & F T \ar[r]^{ρT} & F′T^{2} \ar[d]^{F′μ_{T}} \\ SF′T \ar[r]_{λ′T} & F′T^{2} \ar[r]_{F′μ_{T}} & F′T}

commutes.

5.1. Lemma. If under the bijection given in Lemma 4.1, λ and α correspond, given F : D → C, and λ′ and α′ correspond, given F′: D → C, then a 2-cell ρ: F → F′T is a 2-cell ρ: (F, λ) → (F′, λ′) of EM(K) if and only if the diagram

\xymatrix{SF T \ar[r]^{α} \ar[d]_{SρT} & F T \ar[r]^{ρT} & F′T^{2} \ar[d]^{F′μ_{T}} \\ SF′T^{2} \ar[r]_{α′T} & F′T^{2} \ar[r]_{F′μ_{T}} & F′T}

commutes.

We present the following description of the 2-cells in EM(K).

5.2. Theorem. Given 1-cells (F, (−)^{λ}), (F′, (−)^{λ′}) : (D, 𝕋) → (C, 𝕊) in EM(K), a 2-cell (F, (−)^{λ}) → (F, (−)^{λ′}) in EM(K) can be defined as an 𝕊-algebra morphism β: (F T, (−)^{λ}) → (F′T, (−)^{λ′}) such that for every u: U → T V : X → D, the diagram

\xymatrix{F T U \ar[r]^{βU} \ar[d]_{F u^{𝕋}} & F′T U \ar[d]^{F′u^{𝕋}} \\ F T V \ar[r]_{βV} & F′T V}

commutes.

Proof. Assume we have β: F T → F′T as in the statement of the theorem. Define

ρ = ( [figure: F; F T; F′T; F η_{T}; β] ).  (13)

The commutative diagram

\xymatrix{SF T \ar[dd]_{SF η_{T} T} \ar[dr]_{1_{SF T}} \ar[r]^{α} & F T \ar[ddr]^{1_{F T}} \ar[r]^{F η_{T} T} & F T^{2} \ar[r]^{βT} \ar[dd]^{F μ_{T}} & F T^{2} \ar[ddd]^{F′μ_{T}} \\  & SF T \ar[dr]_{α} \\ SF T^{2} \ar[ur]_{SF μ_{T}} \ar[r]_{αT} \ar[dr]_{SβT} & F T^{2} \ar[r]_{F μ_{T}} \ar[dr]_{βT} & F T \ar[dr]^{β} \\  & SF′T^{2} \ar[r]_{α′T} & F′T^{2} \ar[r]_{F′μ_{T}} & F′T}

gives us the equation in Lemma 5.1.

In the opposite direction, assume that ρ: (F, λ) → (F′, λ) : (D, 𝕋) → (C, 𝕊) satisfies the equation in Lemma 5.1. Define

β := [figure: (F T; F′T^{2}; F′T).; ρT; F′μ_{T}]  (14)

Then the commutative diagram

\xymatrix{SF T \ar[r]^{α} \ar[d]_{SρT} & F T \ar[r]^{ρT} & F′T^{2} \ar[d]^{F′μ_{T}} \\ SF′T^{2} \ar[r]^{α′T} \ar[dr]_{SF′μ_{T}} & F′T^{2} \ar[r]^{F′μ_{T}} & F′T \\  & SF′T \ar[ur]_{α′}}

tells us that β : (F T, α) → (F′T, α′) is a morphism of 𝕊-algebras, and for u: U → T V the commutative diagram

\xymatrix{F T U \ar[r]^{ρT U} \ar[d]_{F T u} & F′T^{2}U \ar[r]^{F′μ_{T} U} \ar[d]_{F′T^{2}u} & F′T U \ar[d]^{F′T u} \\ F T^{2}V \ar[r]^{ρT^{2}V} \ar[d]_{F μ_{T} V} & F′T^{3}V \ar[r]^{F′μ_{T} T V} \ar[d]_{F′T μ_{T} V} & F′T^{2}V \ar[d]^{F′μ_{T} V} \\ F T V \ar[r]_{ρT V} & F′T^{2}V \ar[r]_{F′μ_{T} V} & F′T V}

tells us that βV · F u^{𝕋} = F′u^{𝕋} · βU.

6. Distributive laws

We recall the characterization of distributive laws given in Proposition 3.5 of [Marmolejo, Rosebrugh, Wood, 2002].

6.1. Proposition. Given monads 𝕋 and 𝕊 on C in a 2-category K, there is a bijective correspondence between distributive laws λ: ST → T S of 𝕊 over 𝕋 and 𝕊-algebras α: ST S → T S that satisfy the commutativity of the diagrams

\xymatrix{ST S^{2} \ar[r]^{ST μ_{S}} \ar[d]_{αS} & ST S \ar[d]^{α} & S^{2} \ar[r]^{Sη_{T} S} \ar[d]_{μ_{S}} & ST S \ar[d]^{α} & ST^{2}S \ar[r]^{ST η_{S} T S} \ar[d]_{Sμ_{T} S} & ST ST S \ar[r]^{αT S} & T ST S \ar[r]^{T α} & T^{2}S \ar[d]^{μ_{T} S} \\ T S^{2} \ar[r]_{T μ_{S}} & T S, & S \ar[r]_{η_{T} S} & T S, & ST S \ar[rrr]_{α} &  &  & T S,}

given by λ ↦ (ST S [figure: λS]T S^{2} [figure: T μ_{S}]T S) with inverse α ↦ (ST [figure: ST η_{S}]ST S [figure: α]T S).

6.2. Theorem. Let 𝕋 = (T, η_{T} , (−)^{𝕋}) and 𝕊 = (S, η_{S}, (−)^{𝕊}) be monads on C. A distributive law of 𝕊 over 𝕋 can equivalently be given as follows. An 𝕊-algebra (T S, (−)^{λ}), such that

(T η_{S} · η_{T})^{λ} = η_{T} S,  (15)

and the commutativity of the diagram:

\xymatrix{SX \ar[r]^{h^{λ}} \ar[dr]_{((r^{λ})^{𝕋}·h)^{λ}} & T SU \ar[d]^{(r^{λ})^{𝕋}} \\  & T SV,}  (16)

for every h: X → T SU and r: U → T SV.

Proof. Assume (T S, (−)^{λ}) given with the stated properties. We show first that (T, (−)^{λ}) : (C, 𝕊) → (C, 𝕊) is a 1-cell in Mnd(K). Indeed, for u: U → SV we have

T (u^{𝕊}) = (η_{T} SV · u^{𝕊})^{𝕋} = ((T η_{S}V · η_{T} V)^{λ} · u^{𝕊})^{𝕋} = (((T η_{S}V · η_{T} V)^{λ} · u)^{λ})^{𝕋},

using (7), (15) and (9). Now a direct use of (16) produces (11).

The corresponding 2-cell α = 1_{T S}^{λ} is, according to Theorem 4.3, an 𝕊-algebra and it satisfies the first of the equations in Proposition 6.1. The second one is given by

α · Sη_{T} S = 1_{T S}^{λ} · (η_{S}T S · η_{T} S)^{𝕊} = (1_{T S}^{λ} · η_{S}T S · η_{T} S)^{λ} = (η_{T} S)^{λ}
= ((T η_{S} · η_{T})^{λ})^{λ} = (T η_{S} · η_{T})^{λ} · 1_{S}^{𝕊} = η_{T} S · μ_{S},

whereas the third is

α · Sμ_{T} S = 1_{T S}^{λ} · (η_{S}T S · μ_{T} S)^{𝕊} = (1_{T S}^{λ} · η_{S}T S · μ_{T} S)^{λ} = (μ_{T} S)^{λ} = (1_{T S}^{𝕋})^{λ}
= ((1_{T S}^{λ} · η_{S}T S)^{𝕋})^{λ} = (((1_{T S}^{λ})^{𝕋} · η_{T} ST S · η_{S}T S)^{𝕋})^{λ}
= ((1_{T S}^{λ})^{𝕋} · (η_{T} ST S · η_{S}T S)^{𝕋})^{λ} = ((1_{T S}^{λ})^{𝕋} · T η_{S}T S)^{λ}
= (((1_{T S}^{λ})^{𝕋})^{λ} · η_{S}T ST S · T η_{S}T S)^{λ} = ((1_{T S}^{λ})^{𝕋})^{λ} · (η_{S}T ST S · T η_{S}T S)^{𝕊}

= ((1_{T S}^{λ})^{𝕋})^{λ} · ST η_{S}T S = (1_{F T}^{λ})^{𝕋} · 1_{T ST S}^{λ} · ST η_{S}T S = α^{𝕋} · αT S · ST η_{S}T S = (1_{T S}^{𝕋} · η_{T} T S · α)^{𝕋} · αT S · ST η_{S}T S = 1_{T S}^{𝕋} · (η_{T} T S · α)^{𝕋} · αT S · ST η_{S}T S

= μ_{T} S · T α · αT S · ST η_{S}T S.

In the opposite direction, assume we have an 𝕊-algebra α: ST S → T S that satisfies the conditions of Proposition 6.1. Its corresponding pasting operator in h: X → T SU is given by

\xymatrix{SX \ar[r]^{Sh} & ST SU \ar[r]^{αU} & T SU,}

and produces a 1-cell (T, (−)^{λ}) : (C, 𝕊) → (C, 𝕊). Then

(T η_{S} · η_{T})^{λ} = α · ST η_{S} · Sη_{T} = α · Sη_{T} S · Sη_{S} = η_{T} S · μ_{S} · Sη_{S} = η_{T} S,

and for h: X → T SU and r: U → T SV, the commutative diagram

\xymatrix{SX \ar[r]^{Sh} \ar[ddddr]_{S((r^{λ})^{𝕋}·h)} & ST SU \ar[dd]^{ST Sr} \ar[rrr]^{αU} &  &  & T SU \ar[dd]^{T Sr} \\  &  &  & ST ST SV \ar@{-->}[dr]^{αT SV} \\  & ST ST SV \ar[r]_{ST η_{S} ST SV} \ar[d]_{ST αV} \ar[urr]^{1_{ST ST SV}} & ST S^{2}T SV \ar[d]_{ST SαV} \ar[r]_{αST SV} \ar@{-->}[ur]^{ST μ_{S} T SV} & T S^{2}T SV \ar[d]_{T SαV} \ar[r]_{T μ_{S} T SV} & T ST SV \ar[d]_{T αV} \\  & ST^{2}SV \ar[r]_{ST η_{S} T SV} \ar[d]^{Sμ_{T} SV} & ST ST SV \ar[r]_{αT SV} & T ST SV \ar[r]_{T αV} & T^{2}SV \ar[d]_{μ_{T} SV} \\  & ST SV \ar[rrr]_{αV} &  &  & T SV,}

tells us that (r^{λ})^{𝕋} · h^{λ} = ((r^{λ})^{𝕋} · h)^{λ}.

The proofs of the next two propositions are left to the reader.

6.3. Proposition. Given a distributive law λ of 𝕊 over 𝕋, the composite monad is given by 𝕋 ∘_{λ} 𝕊 = (T S, T η_{S} · η_{T} , ((−)^{λ})^{𝕋}).

There is also a result closer to “compatible structures”:

6.4. Proposition. Let 𝕊 and 𝕋 be monads on C. There is a bijection between distributive laws of 𝕊 over 𝕋 and monad structures (T S, T η_{S}·η_{T} , (−)^{(𝕋𝕊)}) on T S such that for every k: Y → SX, T (k^{𝕊}) = (η_{T} SX · k)^{(𝕋𝕊)}, and for every m: Y → T SX and h: X → T SU, h^{(𝕋𝕊)} = (h^{(𝕋𝕊)} · η_{T} SX)^{𝕋}, and the diagram

\xymatrix{T Y \ar[r]^{m^{𝕋}} \ar[dr]_{(h^{(𝕋𝕊)}·m)^{𝕋}} & T SX \ar[d]^{h^{(𝕋𝕊)}} \\  & T SU}

commutes.

7. Wreaths

Recall from [Lack & Street, 2002] that given a monad 𝕊 = (S, η, μ) on an object C of K and a 1-cell T : C → C, a wreath consists of 2-cells

σ: 1_{C} → T S, λ: ST → T S, ν: T^{2} → T S,

that satisfy the commutativity of the following diagrams:

\xymatrix{ & T \ar[dl]_{ηT} \ar[dr]^{T η} &  & S^{2}T \ar[r]^{Sλ} \ar[d]_{μT} & ST S \ar[r]^{λS} & T S^{2} \ar[d]^{T μ} \\ ST \ar[rr]_{λ} &  & T S & ST \ar[rr]_{λ} &  & T S}

\xymatrix{S \ar[rr]^{σS} \ar[d]_{Sσ} &  & T S^{2} \ar[d]^{T μ} & ST^{2} \ar[r]^{λT} \ar[d]_{Sν} & T ST \ar[r]^{T λ} & T^{2}S \ar[r]^{νS} & T S^{2} \ar[d]^{T μ} \\ ST S \ar[r]_{λS} & T S^{2} \ar[r]_{T μ} & T S & ST S \ar[rr]_{λS} &  & T S^{2} \ar[r]_{T μ} & T S}

\xymatrix{T \ar[r]^{T σ} \ar[ddr]_{T η} & T^{2}S \ar[d]^{νS} & T ST \ar[l]_{T λ} & T \ar[l]_{σT} \ar[ddll]^{T η} & T^{3} \ar[r]^{T ν} \ar[d]_{νT} & T^{2}S \ar[r]^{νS} & T S^{2} \ar[dd]^{T μ} \\  & T S^{2} \ar[d]^{T μ} &  &  & T ST \ar[d]_{T λ} \\  & T S &  &  & T^{2}S \ar[r]_{νS} & T S^{2} \ar[r]_{T μ} & T S}

7.1. Proposition. Let 𝕊 be a monad on C and T : C → C be a 1-cell in K. Fix a 2-cell σ: 1_{C} → T S. There is a bijective correspondence between pairs of 2-cells (λ: ST → T S, ν: T^{2} → T S) making (σ, λ, ν) a wreath, and pairs (α: ST S → T S, γ: T^{2}S → T S) such that (T S, α) is an 𝕊-algebra and the following diagrams commute:

\xymatrix{ST S^{2} \ar[r]^{αS} \ar[d]_{ST μ} & T S^{2} \ar[d]^{T μ} & S \ar[r]^{σS} \ar[d]_{Sσ} & T S^{2} \ar[d]^{T μ} & T^{2}S^{2} \ar[r]^{γS} \ar[d]_{T^{2}μ} & T S^{2} \ar[d]^{T μ} \\ ST S \ar[r]_{α} & T S, & ST S \ar[r]_{α} & T S, & T^{2}S \ar[r]_{γ} & T S,}

\xymatrix{T \ar[r]^{T σ} \ar[dr]_{T η} & T^{2}S \ar[d]^{γ} & T ST S \ar[r]^{T α} & T^{2}S \ar[d]^{γ} & ST ST S \ar[r]^{αT S} \ar[d]_{ST α} & T ST S \ar[r]^{T α} & T^{2}S \ar[d]^{γ} \\  & T S, & T S \ar[u]^{σT S} \ar[r]_{1_{T S}} & T S, & ST^{2}S \ar[r]_{Sγ} & ST S \ar[r]_{α} & T S,}

\xymatrix{T^{2}ST S \ar[r]^{γT S} \ar[d]_{T^{2}α} & T ST S \ar[r]^{T α} & T^{2}S \ar[d]^{γ} \\ T^{3}S \ar[r]_{T γ} & T^{2}S \ar[r]_{γ} & T S}

7.2. Theorem. Given a monad 𝕊 = (S, η, (−)^{𝕊}) on C in K and a 1-cell T : C → C, a wreath can be equivalently defined as follows:

1. A 2-cell σ: 1_{C} → T S in K.

2. A 1-cell (T, (−)^{s}) : (C, 𝕊) → (C, 𝕊) in Mnd(K).

3. A pasting operator (−)^{t}: K(X, C)(1, T S) → K(X, C)(T, T S).

4. For every A, (σA)^{t} = T ηA, and for every f : B → T SA, h: B → SA the diagrams

\xymatrix{B \ar[r]^{σB} \ar[d]_{h} & T SB \ar[d]^{T h^{𝕊}} & B \ar[r]^{σB} \ar[dr]_{f} & T SB \ar[d]^{(f^{s})^{t}} \\ SA \ar[r]_{(σA)^{s}} & T SA &  & T SA}  (17)

commute.

5. For every g: C → T SB, h: B → SA, k: C → B and f : B → T SA the diagrams

\xymatrix{T C \ar[r]^{g^{t}} \ar[dr]_{(T h^{𝕊}·g)^{t}} & T SB \ar[d]^{T h^{𝕊}} \\  & T SA}  (18)

commute.

6. For every f : B → T SA and g: C → T SB, the diagrams

\xymatrix{SC \ar[r]^{g^{s}} \ar[dr]_{((f^{s})^{t}g)^{s}} & T SB \ar[d]^{(f^{s})^{t}} & T C \ar[r]^{g^{t}} \ar[dr]_{((f^{s})^{t}g)^{t}} & T SB \ar[d]^{(f^{s})^{t}} \\  & T SA &  & T SA}  (19)

commute.

Proof. We know that 2-cells α: ST S → T S correspond to the pasting operators (−)^{s}, and that 2-cells γ: T^{2}S → T S correspond to the pasting operators (−)^{t} according to Lemma 2.2.

Assume that we have the conditions of the statement of the theorem. Then α = 1_{T S}^{s} and γ = 1_{T S}^{t}. We check that the conditions of Proposition 7.1 are satisfied. The fact that (T, (−)^{s}) : (C, 𝕊) → (C, 𝕊) is a 1-cell in Mnd(K) means, according to Theorem 4.3, that (T S, α) is an 𝕊-algebra and that the first of the diagrams in Proposition 7.1 commutes. The second is T μ · σS = T (1_{S}^{𝕊}) · σS = σ^{s} = (1_{T S}^{s} · ηT S · σ)^{s} = 1_{T S}^{s} · (ηT S · σ)^{𝕊} = α · Sσ, using (17). The third is T μ·γS = T (1_{S}^{𝕊})·1_{T S^{2}}^{t} = (T μ)^{t} = 1_{T S}^{t} ·T^{2}μ = γ ·T^{2}μ, using (18) and the fact that (−)^{t} respects blistering. The fourth is γ ·T σ = 1_{T S}^{t}·T σ = σ^{t} = T η using the fact that (−)^{t} respects blistering. The fifth is γ · T α · σT S = 1_{T S}^{t} · T (1_{T S}^{s}) · σT S = (1_{T S}^{s})^{t} ·σT S = 1_{T S}, using (17). The sixth is γ ·T α·αT S = (1_{T S}^{s})^{t} ·1_{T ST S}^{s} = ((1_{T S}^{s})^{t})^{s} = (α^{t})^{s} = (γ · T α)^{s} = (γ^{s} · ηT^{2}S · T α)^{s} = γ^{s} · (ηT^{2}S · T α)^{𝕊} = α · Sγ · ST α. And the last is γ · T α · γT S = α^{t} · 1_{T ST S}^{t} = (1_{T S}^{s})^{t} · 1_{T ST S}^{t} = ((1_{T S}^{s})^{t})^{t} = (α^{t})^{t} = (γ · T α)^{t} = γ^{t} · T^{2}α = γ · T γ · T^{2}α.

In the opposite direction assume we have σ: 1_{C} → T S, α: ST S → T S and γ: T^{2}S → T S that satisfy the conditions of Proposition 7.1. Then for f : B → T SA we have that f^{s} = αA · Sf, and f^{t} = γA · T f, that is, (−)^{s} is the pasting operator corresponding to α and (−)^{t} is the pasting operator corresponding to γ. The fact that (T S, α) is an 𝕊-algebra together with the first commutative diagram of Proposition 7.1 means that (T, (−)^{s}) : (C, 𝕊) → (C, 𝕊) is a 1-cell in Mnd(K). Now, (σA)^{t} = γA · T σA = T ηA, using the triangle from Proposition 7.1. Furthermore

T (h^{𝕊}) · σB = T μA · T Sh · σB = T μA · σSA · h = αA · SσA · h = (σA)^{s} · h,

using the second commutative diagram from Proposition 7.1, and

(f^{s})^{t} · σB = γA · T αA · T Sf · σB = γA · T αA · σT SA · f = f,

using the fifth commutative diagram of Proposition 7.1 give us (17). (18) is given by

T (h^{𝕊}) · g^{t} = T μA · T Sh · γB · T g = T μA · γSA · T^{2}Sh · T g
= γA · T^{2}μA · T^{2}Sh · T g = (T (h^{𝕊}) · g)^{t}

using the third commutative diagram from Proposition 7.1. Finally, the commutative diagrams

\xymatrix{SC \ar[dddr]_{S((f^{s})^{t}·g)} \ar[r]^{Sg} & ST SB \ar[r]^{αB} \ar[d]^{ST Sf} & T SB \ar[d]^{T Sf} & T C \ar[dddr]_{T ((f^{s})^{t}·g)} \ar[r]^{T g} & T^{2}SB \ar[r]^{γB} \ar[d]^{T^{2}Sf} & T SB \ar[d]^{T Sf} \\  & ST ST SA \ar[r]^{αT SA} \ar[d]_{ST αA} & T ST SA \ar[d]^{T αA} &  & T^{2}ST SA \ar[r]^{γT SA} \ar[d]_{T^{2}αA} & T ST SA \ar[d]^{T αA} \\  & ST^{2}SA \ar[d]^{SγA} & T^{2}SA \ar[d]^{γA} &  & T^{3}SA \ar[d]^{T γA} & T^{2}SA \ar[d]^{γA} \\  & ST SA \ar[r]_{αA} & T SA, &  & T^{2}SA \ar[r]_{γA} & T SA,}

give us (19).

8. Monads, algebras, distributive laws and wreaths in Cat

What we have been calling extension systems were first described by E. Manes as an alternative definition for monads on categories in [Manes, 1976]. Manes recognized, in giving a monad 𝕊 on a category C as an extension system, that a mere function |S|: |C| → |C| and a mere C-arrow valued function η, defined on |C| with no a priori naturality requirement, sufficed in the presence of an extension operator. Thus fewer axioms are required for extension systems on categories but we do have to show the naturality of the transformations that we introduce. However, formally it is very similar to what we have done so far in a general 2-category, and most of the proofs are similar to the proofs already given. Thus, in this section we present the precise statements for this important particular case and give the extra arguments necessary for the naturality of the various transformations. In the next section, we analyze the extra structure on Cat that enables the description of extension systems as functions, in terms of profunctors.

First we recall Exercise 1.3.12, page 32, of [Manes, 1976]:

8.1. Theorem. A monad 𝕊 on a category C can be defined as follows: A function |S|: |C| → |C|, for every A ∈ C, an arrow ηA: A → SA, and for every morphism f : B → SA in C, an 𝕊-extension f^{𝕊}: SB → SA subject to the axioms: for every A in C,

(ηA)^{𝕊} = 1_{SA},

for every f : B → SA in C and g: C → SB, the diagrams

\xymatrix{B \ar[r]^{ηB} \ar[dr]_{f} & SB \ar[d]^{f^{𝕊}} & SC \ar[r]^{g^{𝕊}} \ar[dr]_{(f^{𝕊}·g)^{𝕊}} & SB \ar[d]^{f^{𝕊}} \\  & SA, &  & SA}

commute.

Recall then that for ℓ: B → A, we can define S on ℓ by the formula Sℓ = (ηA · ℓ)^{𝕊}, and that this makes S: C → C a functor and η: 1_{C} → S a natural transformation. And the definition of μA is given by μA = 1_{SA}^{𝕊}.

8.2. Theorem. Given a monad 𝕊 = (S, η, (−)^{𝕊}) on the category C, an 𝕊-algebra can be defined as follows: 𝔹 = (B, (−)^{𝔹}), where B is an object of C, and (−)^{𝔹} assigns to every arrow of the form h: X → B in C, an extension h^{𝔹}: SX → B subject to the commutativity of the following diagrams (with h: X → B and y: Y → SX):

\xymatrix{X \ar[r]^{ηX} \ar[dr]_{h} & SX \ar[d]^{h^{𝔹}} & SY \ar[r]^{y^{𝕊}} \ar[dr]_{(h^{𝔹}y)^{𝔹}} & SX \ar[d]^{h^{𝔹}} \\  & B, &  & B.}

A morphism of 𝕊-algebras (B, (−)^{𝔹}) to (A, (−)^{𝔸}) can be defined as an arrow ℓ: B → A in C subject to the commutativity of the diagram (where h: X → B):

\xymatrix{SX \ar[r]^{h^{𝔹}} \ar[dr]_{(ℓ·h)^{𝔸}} & B \ar[d]^{ℓ} \\  & A.}

Proof. Given (B, (−)^{𝔹}) define the action by 1_{B}^{𝔹}: SB → B. On the other hand, given an 𝕊-algebra (B, β) and h: X → B in C, define h^{𝔹} = β · Sh.

8.3. Theorem. Let 𝕊 = (S, η_{S}, (−)^{𝕊}) and 𝕋 = (T, η_{T} , (−)^{𝕋}) be monads on the category C. A distributive law of 𝕊 over 𝕋 can be defined as follows. For every A in C an 𝕊algebra (T SA, (−)^{λ}) such that for every A in C, (T η_{S}A · η_{T} A)^{λ} = η_{T} SA, and for every f : B → T SA, (f^{λ})^{𝕋}: (T SB, (−)^{λ}) → (T SA, (−)^{λ}) is a morphism of 𝕊-algebras.

Proof. Given the conditions of the theorem define αA = 1_{T SA}^{λ}. We show that α: ST S → T S is natural. So take ℓ: B → A. Observe that

T Sℓ = (η_{T} SA · Sℓ)^{𝕋} = ((T η_{S}A · η_{T} A)^{λ} · (η_{S}A · ℓ)^{𝕊})^{𝕋}
= ((T η_{S}A · η_{T} A)^{λ} · η_{S}A · ℓ)^{λ})^{𝕋} = ((T η_{S}A · η_{T} A · ℓ)^{λ})^{𝕋}.

Thus

T Sℓ · αB = ((T η_{S}A · η_{T} A · ℓ)^{λ})^{𝕋} · 1_{T SB}^{λ} = (((T η_{S}A · η_{T} A · ℓ)^{λ})^{𝕋})^{λ} = (T Sℓ)^{λ}
= (1_{T SA}^{λ} · η_{S}T SA · T Sℓ)^{λ} = 1_{T SA}^{λ} · (η_{S}T SA · T Sℓ)^{𝕊} = αA · ST Sℓ,

and α is natural.

8.4. Theorem. Given a monad 𝕊 = (S, η, (−)^{𝕊}) on a category C and an endofunctor T : C → C, a wreath can be equivalently given as follows:

1. For every A in C, an arrow σA: A → T SA.

2. For every A, B in C, functions

\xymatrix{C(SB, T SA) & C(B, T SA) \ar[l]_{(−)^{s}} \ar[r]^{(−)^{t}} & C(T B, T SA)}

3. For every A, (T SA, (−)^{s}) is an 𝕊-algebra and T (h^{𝕊}) : (T SB, (−)^{s}) → (T SA, (−)^{s}) is a morphism of 𝕊-algebras for every h: B → SA. That is, the diagrams

\xymatrix{B \ar[r]^{ηB} \ar[dr]_{f} & SB \ar[d]^{f^{s}} & SC \ar[r]^{k^{𝕊}} \ar[dr]_{(f^{s}k)^{s}} & SB \ar[d]^{f^{s}} & SC \ar[r]^{g^{s}} \ar[dr]_{(T (h^{𝕊})g)^{s}} & T SB \ar[d]^{T (h^{𝕊})} \\  & T SA &  & T SA &  & T SA}  (20)

commute for every f : B → T SA, g: C → T SB, and k: C → SB.

4. For every A we have that (σA)^{t} = T ηA, and for every f : B → T SA, h: B → SA

the diagrams

\xymatrix{B \ar[r]^{σB} \ar[d]_{h} & T SB \ar[d]^{T (h^{𝕊})} & B \ar[r]^{σB} \ar[dr]_{f} & T SB \ar[d]^{(f^{s})^{t}} \\ SA \ar[r]_{(σA)^{s}} & T SA &  & T SA}  (21)

commute.

MONADS AS EXTENSION SYSTEMS —NO ITERATION IS NECESSARY  101

5. For every g: C → T SB, h: B → SA, k: C → B and f : B → T SA, the diagrams

\xymatrix{T C \ar[r]^{g^{t}} \ar[dr]_{(T (h^{𝕊})g)^{t}} & T SB \ar[d]^{T (h^{𝕊})} & T C \ar[r]^{T k} \ar[dr]_{(f·k)^{t}} & T B \ar[d]^{f^{t}} \\  & T SA &  & T SA}  (22)

commute.

6. For every f : B → T SA and g: C → T SB, the diagrams

\xymatrix{SC \ar[r]^{g^{s}} \ar[dr]_{((f^{s})^{t}g)^{s}} & T SB \ar[d]^{(f^{s})^{t}} & T C \ar[r]^{g^{t}} \ar[dr]_{((f^{s})^{t}g)^{t}} & T SB \ar[d]^{(f^{s})^{t}} \\  & T SA &  & T SA}  (23)

commute. Proof. For A ∈ C, take σA as given and define αA := 1_{T SA}^{s} and γA := 1_{T SA}^{t}. We show first that σ is natural. Take ℓ: B → A in A, then

T Sℓ · σB = T ((ηA · ℓ)^{𝕊}) · σB = (σA)^{s} · ηA · ℓ = σA · ℓ,

using (21) and (20). For the naturality of α we have:

T Sℓ · αB = T ((η_{S}A · ℓ)^{𝕊}) · 1_{T SA}^{s} = (T Sℓ)^{s} = (1_{T SA}^{s} · η_{S}T SA · T Sℓ)^{s}
= 1_{T SA}^{s} · (η_{S}T SA · T Sℓ)^{𝕊} = αA · ST Sℓ,

using the equations of (20). And for the naturality of γ we have T Sℓ · γB = T ((η_{S}A · ℓ)^{𝕊}) · 1_{T SB}^{t} = (T Sℓ)^{t} = γA · T^{2}Sℓ.

8.5. Example. Beck’s original example [Beck, 1969] has 𝕊 the free monoid monad and 𝕋 the free abelian group monad. Thus SA is the underlying set of the free monoid in A,

SA = {[a_{1}, …, a_{n}]|n ∈ ℕ, a_{j} ∈ A, j = 1, …, n},

η_{S} : A → SA is such that

η_{S}(a) = [a],

and for h: A → SB, we have that h^{𝕊}([a_{1}, …, a_{n}]) = h(a_{1}) ∼ h(a_{2}) ∼ ⋯ ∼ h(a_{n}), where ∼ denotes concatenation ([b_{1}, …, b_{k}] ∼ [c_{1}, …, c_{ℓ}] = [b_{1}, …, b_{k}, c_{1}, …, c_{ℓ}]). On the other hand, T A is the underlying set of the free group with A generators. Thus the elements of T A are formal sums

∑_{a∈A} n_{a} · a

with n_{a} ∈ ℤ for every a ∈ A, and only a finite number of the n_{a} are non-zero. η_{T} A: A → T A is such that

η_{T} A(c) = 1 · c,

and for k: A → T B, k^{𝕋}: T A → T B is

k^{𝕋} (∑_{a∈A} n_{a} · a) = ∑_{a∈A} n_{a}k(a),

where this last sum is taken in the abelian group T B.

Now, T SB has a monoid structure given by

( ∑_{w∈SB} m_{w} · w) ∗ ( ∑_{w∈SB} n_{w} · w) = ∑_{w∈SB} ( ∑_{u∼v=w} m_{u}n_{u}) · w.

Thus, given f : A → T SB, we define f^{λ} the unique monoid morphism f^{λ}: SA → T SB such that

\xymatrix{A \ar[r]^{η_{S} A} \ar[dr]_{f} & SA \ar[d]^{f^{λ}} \\  & T SB}

commutes. That is, f^{λ}([a_{1}, …, a_{n}]) = f(a_{1}) ∗ f(a_{2}) ∗ ⋯ ∗ f(a_{n}). Let g: C → T SB and take [c_{1}, …, c_{n}] ∈ SC. Assume that g(c_{i}) = ∑_{w∈SB} k_{w}^{(i)} · w for i = 1, …, n. Then

((f^{λ})^{𝕋}g)^{λ}([c_{1}, …, c_{n}]) = ( ∑_{w∈SB} k_{w}^{(1)}f^{λ}(w)) ∗ ⋯ ∗ ( ∑_{w∈SB} k_{w}^{(n)}f^{λ}(w)) .

On the other hand

(f^{λ})^{𝕋}(g^{λ}([c_{1}, …, c_{n}])) = ∑_{w∈SB} ( ∑_{w_{1}∼···∼w_{n}=w} k_{w_{1}}^{(1)} ⋯ k_{w_{n}}^{(n)}) f^{λ}(w).

It takes just a moment to realize that to see that these are the same, it suffices to show that the operation ∗ distributes over the addition in T SA, but this is easy.

Then the calculation

(η_{T} SA · η_{S}A)^{λ}([a_{1}, …, a_{n}]) = η_{T} SA · η_{S}A(a_{1}) ∗ ⋯ ∗ η_{T} SA · η_{S}A(a_{n})
= (1 · [a_{1}]) ∗ ⋯ ∗ (1 · [a_{n}])
= 1 · [a_{1}, …, a_{n}]
= η_{T} SA([a_{1}, …, a_{n}])

shows that we have a distributive law.

We have that λA = (T η_{S}A)^{λ}: ST A → T SA,

λA ([∑_{a∈A} n_{a}^{(1)} · a, …, ∑_{a∈A} n_{a}^{(r)} · a]) = T η_{S}A (∑_{a∈A} n_{a}^{(1)} · a) ∗ ⋯ ∗ T η_{S}A (∑_{a∈A} n_{a}^{(r)} · a)

= (∑_{a∈A} n_{a}^{(1)} · [a]) ∗ ⋯ ∗ (∑_{a∈A} n_{a}^{(r)} · [a])

= ∑_{[a_{1},...,a_{r}]} n_{a_{1}}^{(1)} ⋯ n_{a_{r}}^{(r)} · [a_{1}, …, a_{r}]

as expected.

8.6. Example. Another example from [Beck, 1969] has 𝕋 arbitrary on C with coproducts, and 𝕊 the constants monad. (It is done for the category of sets in Beck’s paper but it works in the given context.) That is, take a fixed object C in C, define for every A, SA = A + C, η_{S}A = i_{A}: A → A + C the canonical injection of the first summand, and for h: A → SB define h^{𝕊}: SA → SB as the unique arrow such that the diagram

\xymatrix{A \ar[r]^{η_{S} A} \ar[dr]_{h} & A + C \ar[d]^{h^{𝕊}} & C \ar[dl]^{i_{C}} \ar[l]_{i_{C}} \\  & B + C}

commutes.

Given f : A → T SB = T (B + C), define f^{λ} : A + C → T SB as the unique arrow that makes the diagram

\xymatrix{A \ar[r]^{η_{S} A} \ar[dr]_{f} & A + C \ar[d]^{f^{λ}} & C \ar[l]_{i_{C}} \ar[d]^{i_{C}} \\  & T (B + C) & B + C \ar[l]^{η_{T} (B+C)}}

commute. The commutative diagram

\xymatrix{A \ar[r]^{η_{S} A} \ar[d]_{η_{S} A} & A + C \ar[d]^{(η_{T} (A+C)·η_{S} A)^{λ}} & C \ar[l]_{i_{C}} \ar[d]^{i_{C}} \\ A + C \ar[r]_{η_{T} (A+C)} & T (A + C) & A + C \ar[l]^{η_{T} (A+C)}}

tells us that (η_{T} (A + C) · η_{S}A)^{λ} = η_{T} (A + C). For h: A → SB and g: B → T (D + C), the commutative diagram

\xymatrix{A \ar[r]^{η_{S} A} \ar[dr]_{h} \ar[ddr]_{g^{λ}h} & A + C \ar[d]^{h^{𝕊}} & C \ar[l]_{i_{C}} \ar[d]^{i_{C}} \ar[dl]^{i_{C}} \\  & B + C \ar[d]^{g^{λ}} & D + C \ar[dl]^{η_{T} (D+C)} \\  & T (D + C)}

tells us that (g^{λ} · h)^{λ} = g^{λ} · h^{𝕊}. And the commutative diagram

\xymatrix{A \ar[r]^{η_{S} A} \ar[dr]_{f} \ar[ddr]_{(g^{λ})^{𝕋}f} & A + C \ar[d]^{f^{λ}} &  & C \ar[ll]_{i_{C}} \ar[dl]_{i_{C}} \ar[dd]^{i_{C}} \\  & T (B + C) \ar[d]_{(g^{λ})^{𝕋}} & B + C \ar[l]_{η_{T} (B+C)} \ar[dl]^{g^{λ}} \\  & T (D + C) &  & D + C \ar[ll]^{η_{T} (D+C)}}

tells us that ((g^{λ})^{𝕋} · f)^{λ} = (g^{λ})^{𝕋} · f^{λ}. Therefore we have a distributive law, where λA: ST A → T SA is the unique arrow that makes the diagram

\xymatrix{T A \ar[r]^{i_{T A}} \ar[dr]_{T i_{A}} & T A + C \ar[d]^{λA} & C \ar[l]_{i_{C}} \ar[d]^{i_{C}} \\  & T (A + C) & A + C \ar[l]^{η_{T} (A+C)}}

commute.

8.7. Example. Another example from [Beck, 1969] is to take a monoid M and the monad 𝕄 it defines on Set. That is, to every set A we assign the set M × A, η_{M} A: A → M ×A is η_{M} (a) = (e, a), where e is the unit element of M, and for f = ⟨f_{1}, f_{2}⟩: B → M ×A we define

f^{𝕄}(m, b) = (m ∗ f_{1}(b), f_{2}(b))

where ∗: M × M → M is the multiplication of the monoid. It is clear that f^{𝕄} · η_{M} B = f, and if g = ⟨g_{1}, g_{2}⟩: C → M × B and (m, c) ∈ M × C, we have that

f^{𝕄}(g^{𝕄}(m, c)) = f^{𝕄}(m ∗ g_{1}(c), g_{2}(c)) = ((m ∗ g_{1}(c)) ∗ f_{1}g_{2}(c), f_{2}g_{2}(c)),

whereas (f^{𝕄}g)^{𝕄}(m, c) = (m ∗ (g_{1}(c) ∗ f_{1}g_{2}(c)), f_{2}g_{2}(c)), so g^{𝕄}f^{𝕄} = (g^{𝕄}f)^{𝕄}. Given any monad 𝕋 on Set and f : A → T (M × B) define f^{λ}: M × A → T (M × B) as

f^{λ}(m, a) = T (m ∗ (−) × B)(f(a)).

By the naturality of η_{T}, we have

(η_{T} (M × A) · η_{M} A)^{λ}(m, a) = T (m ∗ (−) × A)((η_{T} (M × A) · η_{M} A)(a))
= (T (m ∗ (−) × A) · η_{T} (M × A))(e, a)
= η_{T} (M × A)(m ∗ (−) × A)(e, a)
= η_{T} (M × A)(m, a).

Furthermore (f^{λ}·η_{M} A)(a) = f^{λ}(e, a) = T (e∗(−)×B)(f(a)) = f(a). For g = ⟨g_{1}, g_{2}⟩: C → M × A and (m, c) ∈ M × C we have

(f^{λ}g^{𝕄})(m, c) = f^{λ}(g^{𝕄}(m, c)) = f^{λ}(m ∗ g_{1}(c), g_{2}(c)) = T (m ∗ g_{1}(c) ∗ (−) × A)(f(g_{2}(c)))
= T (m ∗ (−) × A)(T (g_{1}(c) ∗ (−) × A)(f(g_{2}(c))))
= T (m ∗ (−) × A)((f^{λ}g)(c)) = (f^{λ}g)^{λ}(m, c).

It is not hard to show that for any m ∈ M, f^{λ} ∘ (m ∗ (−) × B) = T (m ∗ (−) × A) ∘ f^{λ}. Then for h: C → T (M × A) and (m, c) ∈ M × C we have

((f^{λ})^{𝕋}h)^{λ}(m, c) = (T (m ∗ (−) × A) · (f^{λ})^{𝕋})(h(c))
= ((η_{T} (M × A) · (m ∗ (−) × A))^{𝕋} · (f^{λ})^{𝕋})(h(c))
= (((η_{T} (M × A) · (m ∗ (−) × A))^{𝕋} · f^{λ})^{𝕋})(h(c))
= ((T (m ∗ (−) × A) · f^{λ})^{𝕋})(h(c)) = (f^{λ} · (m ∗ (−) × B))^{𝕋}(h(c))
= ((f^{λ})^{𝕋} · η_{T} (M × B) · (m ∗ (−) × B))^{𝕋}(h(c))
= ((f^{λ})^{𝕋} · T (m ∗ (−) × B))(h(c)) = ((f^{λ})^{𝕋} · h^{λ})(m, c).

We thus have a distributive law of 𝕄 over 𝕋.

8.8. Example. An example taken from [Varacca, 2003] has the monad ℙ on Set of finite non-empty subsets, whose structure is given by, for any set X, P X = {X_{0} ⊆ X|X_{0} finite non-empty}, η_{P} X: X → P X is η_{P} X(x) = {x}, and for any function f : Y → P X, f^{ℙ}(Y_{0}) = ⋃_{y∈Y_{0}} f(y).

On the other hand we have the monad 𝕍 on Set of indexed valuations, whose structure is given as follows. For a set X, V (X) has as elements equivalent classes of spans [figure: K; X; (0, ∞); χ; r] in Set with K finite, and the given span is equivalent to the span

[figure: K′; X; (0, ∞); χ′; r′] iff there is a bijection κ: K → K′ such that the diagram

[figure: K; X; (0, ∞); K′; χ; r; χ′; r′; κ]

commutes. The arrow η_{V} X: X → V (X) is such that the span associated to x ∈ X is

[figure: 1; X.; (0, ∞); ⌜x⌝; ⌜1⌝]

Take a function f : Y → V (X). For y ∈ Y denote the span f(y) by [figure: K_{y}; X.; (0, ∞); χ^{y}; r^{y}]

Define f^{𝕍}: V (Y) → V (X) on the span [figure: J; Y; (0, ∞); ψ; q] as the span

[figure: ∐_{j∈J} K_{ψ(j)}; X,; (0, ∞); χ; r]

where r and χ are the unique functions such that the diagram

\xymatrix{(0, ∞) \ar[d]_{q(j)·−} & K_{ψ(j)} \ar[l]_{r^{ψ(j)}} \ar[d]_{inc_{j}} \ar[dr]^{χ^{ψ(j)}} \\ (0, ∞) & ∐_{j∈J} K_{ψ(j)} \ar[l]^{r} \ar[r]_{χ} & X}

commutes for every i ∈ I. Thus for k ∈ K_{ψ(j)} we have χ(k) = χ^{ψ(j)}(k) and r(k) = q(j) · r^{ψ(j)}(k).

It is clear that f^{𝕍} ∘ η_{V} Y = f, and for g: Z → V (Y) write g(z) as

[figure: J_{z}; Y.; (0, ∞); ψ^{z}; q^{z}]  (24)

Then f^{𝕍}g^{𝕍} on the span [figure: I; Z; (0, ∞); ζ; p] is the span

[figure: ∐ ; j∈∐_{i∈I} J_{ζ(i)} K_{ψ^{ζ(i)}(j)}; X,; (0, ∞); χ; r]

where for a k ∈ K_{ψ(j)} with j ∈ J_{ζ(i)} we have

ξ(k) = ξ^{ψ^{ζ(i)}(j)}(k) and r(k) = p(i) · q^{ζ(i)}(j) · r^{ψ^{ζ(i)}(j)}(k).

On the other hand, (f^{𝕍}g)^{𝕍} on the same span gives us

[figure: ∐_{i∈I} ∐_{j∈J_{ζ(i)}} K_{ψ^{ζ(i)}(j)}; X; (0, ∞); χ′; r′]

where for a k ∈ K_{ψ^{ζ(i)}(j)} with j ∈ J_{ζ(i)} and i ∈ I we have

ξ′(k) = ξ^{ψ^{ζ(i)}(j)}(k) and r′(k) = p(i) · q^{ζ(i)}(j) · r^{ψ^{ζ(i)}(j)}(k).

Then the canonical isomorphism

[figure: ∐ ; j∈∐_{i∈I} J_{ζ(i)} K_{ψ^{ζ(i)}(j)}; ∐_{i∈I} ∐_{j∈J_{ζ(i)}} K_{ψ^{ζ(i)}(j)}; ≃]

shows that these spans are the same element of V (X). That is, the diagram

\xymatrix{V (Z) \ar[r]^{g^{𝕍}} \ar[dr]_{(f^{𝕍}g)^{𝕍}} & V (Y) \ar[d]^{f^{𝕍}} \\  & V (X)}

commutes. We have then shown that we have a monad 𝕍.

We now give the distributive law. Take h: Y → P (V (X)), and take a span

[figure: J; Y.; (0, ∞); ψ; q]

For every choice function ℓ: J → ⋃_{j∈J} h(ψ(j)) (that is, ℓ(j) ∈ h(ψ(j))), if ℓ(j) is the span

[figure: K_{j}; X,; (0, ∞); χ^{j}; r^{j}]

for j ∈ J, we form the span S(ℓ, q, ψ) as

[figure: ∐_{j∈J} K_{j}; X,; (0, ∞); χ; r]

where for k ∈ K_{j} we define χ(k) = χ^{j}(k) and r(k) = q(j) · r^{j}(k). We define

h^{λ}((q, ψ)) = {S(ℓ, q, ψ)|ℓ: J → ⋃_{j∈J} h(ψ(j)) is a choice function}.

We show that this defines a distributive law of 𝕍 over ℙ. We must show first that this definition of h^{λ} produces a structure of 𝕍-algebra on P (V (X)). We know that η_{V} Y (y) = (⌜1⌝, ⌜y⌝). Then a choice function ℓ: 1 → h(y) is simply to pick an element in h(y). Then S(ℓ, ⌜1⌝, ⌜y⌝) is this chosen element, thus h^{λ} ∘ η_{V} Y = h.

Then a typical element in h^{λ}(g^{𝕍}( [figure: I; Z)); (0, ∞); ζ; p] is formed as follows. Assume g(z) is given by (24) for every z ∈ Z. Then for every i ∈ I and every j ∈ J_{ζ(i)} we take an element

[figure: K_{ij}; X; (0, ∞); χ^{ij}; r^{ij}]

in h(ψ^{ζ(i)}(j)). Then the element of h^{λ}(g^{𝕍}(p, ζ)) is

\xymatrix{(0, ∞) & ∐_{(i,j)∈∐_{i∈I} J_{ζ(i)}} K_{ij} \ar[l]^{r} \ar[r]_{χ} & X,}

where for k ∈ K_{ij}, χ(k) = χ^{ij}(k) and r(k) = q^{ζ(i)}(j) · r^{ij}(k).

On the other hand, a typical element of (h^{λ}g^{𝕍})^{λ}(p, ζ) is formed as follows. For every i ∈ I and j ∈ J_{ζ(i)} take an element

[figure: K_{ij}; X; (0, ∞); χ^{ij}; r^{ij}]

in h(ψ^{ζ(i)}(j)). Then the element is formed as

\xymatrix{(0, ∞) & ∐_{i∈I} ∐_{j∈J_{ζ(i)}} K_{ij} \ar[l]^{r′} \ar[r]_{χ′} & X,}

where for k ∈ K_{ij} (j ∈ J_{ζ(i)}) we have that χ′(k) = χ^{ij}(k) and r′(k) = p(i) · q^{ζ(i)}(j) · r^{ij}(k).

The canonical isomorphism ∐_{i∈I} ∐_{j∈J_{ζ(i)}} K_{ij} → ∐_{(i,j)∈∐_{i∈I} J_{ζ(i)}} K_{ij} then tell us that h^{λ}g^{𝕍} = (h^{λ}g)^{λ}.

The condition (η_{P} V (X) · η_{V} X)^{λ} = η_{P} V (X) is easy, since there is only one possible choice function for a given element in V (X).

Finally, take k: Z → P (V (Y)) and h: Y → P (V (X)). We must check that (h^{λ})^{P} k^{λ} =

((h^{λ})^{ℙ}k)^{λ}. Take [figure: I; Z; (0, ∞); ζ; p] in V (Z). Then a typical element of ((h^{λ})^{P} k^{λ})(p, ζ)

is formed as follows: for every i ∈ I chose a span [figure: J_{i}; Y; (0, ∞); ψ^{i}; q^{i}] in k(ζ(i)), then

for every j ∈ J_{i} choose a span [figure: K_{ij}; X; (0, ∞); χ^{ij}; r^{ij}] in h(ψ^{i}(j)); then the element in question is

[figure: ∐_{(i,j)∈∐_{i∈I} J_{i}} K_{ij}; X; (0, ∞); χ; r]

where for k ∈ K_{ij}, (j ∈ J_{i}) we have χ(k) = χ^{ij}(k) and r(k) = p(i) · q^{i}(j) · r^{ij}(k). On the other hand, a typical element in ((h^{λ})^{P} k)^{λ}(p, ζ) is formed as follows: for every

i ∈ I we take a span [figure: J_{i}; Y; (0, ∞); ψ^{i}; q^{i}] in k(ζ(i)), then for every j ∈ J_{i} we take a

span [figure: K_{ij}; X; (0, ∞); χ^{ij}; r^{ij}] in h(ψ^{i}(j)); then the element in question is

[figure: ∐_{i∈I} ∐_{j∈J_{i}} K_{ij}; X; (0, ∞); χ′; r′]

where for k ∈ K_{ij}, (j ∈ J_{i}) we have χ′(k) = χ^{ij}(k) and r′(k) = p(i) · q^{i}(j) · r^{ij}(k). Therefore, (h^{λ})^{P} k^{λ} = (h^{λ}k)^{λ}. Thus we have a distributive law.

Compare with the proof given in [Varacca, 2003].

8.9. Example. This one is taken from [Manes & Mulry, 2007]. Let 𝕊 be the free monoid monad (described in example 8.5) and let 𝕋 the submonad of 𝕊 of nonempty words:

T A = {[a_{1}, …, a_{n}]|n ∈ ℕ\{0}, a_{j} ∈ A, j = 1, …, n},

for any set A. Give T SA the following binary operation

[U_{1}, …, U_{k}] ∗ [V_{1}, …, V_{ℓ}] = [U_{1}, …, U_{k−1}, U_{k} ∼ V_{1}, V_{2}, …, V_{ℓ}]

where U_{1}, …, U_{k}, V_{1}, …, V_{ℓ} are elements of SA, and ∼ denotes concatenation. It is immediate to see that T SA with this operation is a monoid. Therefore, if for an f : B → T SA we define f^{λ}: SA → T SA such that

f^{λ}([a_{1}, …, a_{n}]) = f(a_{1}) ∗ ⋯ ∗ f(a_{n}),

we obtain an 𝕊-algebra (T SA, ( )^{λ}). Now, for [a_{1}, …, a_{k}] ∈ SA we have

(T η_{S}A · η_{T} A)^{λ}([a_{1}, …, a_{k}]) = [[a_{1}]] ∗ ⋯ ∗ [[a_{k}]] = [[a_{1}, …, a_{k}]] = η_{T} SA([a_{1}, …, a_{k}]).

Finally we must show that for f : B → T SA, (f^{λ})^{𝕋}: T SB → T SA is a monoid morphism with respect to the operation ∗ on both, T SB and T SA. Let [U_{1}, …, U_{k}], [V_{1}, …, V_{ℓ}] ∈ T SB. Then

\begin{matrix}(f^{λ})^{𝕋}([U_{1}, …, U_{k}] ∗ [V_{1}, …, V_{ℓ}]) = (f^{λ})^{𝕋}([U_{1}, …, U_{k−1}, U_{k} ∼ V_{1}, V_{2}, …, V_{ℓ}]) \\ = f^{λ}(U_{1}) ∼ ⋯ ∼ f^{λ}(U_{k−1}) ∼ f^{λ}(U_{k} ∼ V_{1}) ∼ f^{λ}(V_{2}) ∼ f^{λ}(V_{ℓ}) \end{matrix}

and

(f^{λ})^{𝕋}([U_{1}, …, U_{k}]) ∗ (f^{λ})^{𝕋}([V_{1}, …, V_{ℓ}])
= (f^{λ}(U_{1}) ∼ ⋯ ∼ f^{λ}(U_{k})) ∗ (f^{λ}(V_{1}) ∼ ⋯ ∼ f^{λ}(V_{ℓ}))
= f^{λ}(U_{1}) ∼ ⋯ ∼ (f^{λ}(U_{k}) ∗ f^{λ}(V_{1})) ∼ ⋯ ∼ f^{λ}(V_{ℓ}).

Since it direct to see that f^{λ}(U_{k}) ∗ f^{λ}(V_{1}) = f^{λ}(U_{k} ∼ V_{1}), we have a distributive law of 𝕊 over 𝕋.

8.10. Example. We close our set of examples with a wreath from [Lack & Street, 2002]. Take a short exact sequence in the category of groups

1 → A → E → G → 1.

For g ∈ G and a ∈ A denote the action of g on a by a^{g} = g^{−1}ag ∈ A, and let ρ: G×G → A be a normalized cocycle corresponding to the extension. Let 𝔸 be the monad on Set determined by the group A (as described in example 8.7, there for a monoid M), and take the functor T = G×−: Set → Set. For the wreath define σX: X → G×A×X such that σA(x) = (e, e, x), and for f = ⟨f_{1}, f_{2}, f_{3}⟩: Y → G × A × X, define f^{s}: A → G × A × X as

f^{s}(a, y) = (f_{1}(y), a^{f_{1}(y)} · f_{2}(y), f_{3}(y)),

and f^{t}: G × Y → G × A × X as

f^{t}(g, y) = (g · f_{1}(y), ρ(g, f_{1}(y)) · f_{2}(y), f_{3}(y)).

We only verify that the last condition from Theorem 8.4 is satisfied and leave the rest to the reader. We have that

(f^{s})^{t}(g, a, y) = (g · f_{1}(y), ρ(g, f_{1}(y)) · a^{f_{1}(y)} · f_{2}(y), f_{3}(y)).

Thus for ℓ = ⟨ℓ_{1}, ℓ_{2}, ℓ_{3}⟩: Z → G × A × X we have that (f^{s})^{t}(ℓ^{t}(g, z)) is

(g · ℓ_{1}(z) · f_{1}ℓ_{3}(z), ρ(g · ℓ_{1}(y), f_{1}ℓ_{3}(z)) · (ρ(g, ℓ_{1}(z)) · ℓ_{2}(z))^{f_{1}ℓ_{3}(z)} · f_{2}ℓ_{3}(z), f_{3}ℓ_{3}(z)),

whereas ((f^{s})^{t}ℓ)^{t}(g, z) is

(g · ℓ_{1}(z) · f_{1}ℓ_{3}(z), ρ(g, ℓ_{1}(z) · f_{1}ℓ_{3}(z) · ρ(ℓ_{1}(z), f_{1}ℓ_{3}(z)) · ℓ_{2}(z)^{f_{1}ℓ_{3}(z)} · f_{2}ℓ_{3}(z), f_{3}ℓ_{3}(z)).

The fact that they are equal follows from the cocycle condition

ρ(g · h, k) · ρ(g, h)^{k} = ρ(g, h · k)ρ(h, k)

for g, h, k ∈ G.

9. Extension systems in the bicategory of profunctors

In the Introduction we also mentioned extension systems of the form (φ, ψ: S ⊣ H, η, ξ) on an object C in a 2-category K. We recall that η: 1_{C} → S: C → C and that ξ: S → HS is to be the mate of a 2-cell μ: SS → S so that explicitly we have

\xymatrix{ξ = (S \ar[r]^{φS} & HS^{2} \ar[r]^{Hμ} & HS)}

and

\xymatrix{μ = (S^{2} \ar[r]^{Sξ} & SHS \ar[r]^{ψS} & S).}

We begin this section by reconciling our two usages of the term extension system.

9.1. Lemma. The data (S, η, μ) constitute a monad if and only if the data (φ, ψ: S ⊣ H, η, ξ) satisfy the following three equations:

\xymatrix{1 \ar[r]^{η} \ar[dr]_{φ} & S \ar[d]^{ξ} & S^{2} \ar[r]^{Sξ} & SHS \ar[d]^{ψS} & S^{2} \ar[r]^{Sξ} & SHS \ar[r]^{ψS} \ar[d]_{ξHS} & S \ar[d]^{ξ} \\  & HS, & S \ar[u]^{ηS} \ar[r]_{1_{S}} & S, &  & HSHS \ar[r]_{HψS} & HS.}  (25)

Proof. Apply S to the first of these equations and post-compose the result with ψS. From the definition of μ this gives the monad equation μ · Sη = 1_{S}. Conversely, given μ · Sη = 1_{S}, the mate 1_{C} → HS with respect to the given adjunction of 1_{S} is φ while that of μ · Sη is Hμ · HSη · φ = Hμ · φS · η = ξ · η, from the definition of ξ. The second of the equations given above is immediately the monad equation μ · ηS = 1_{S} and conversely. Starting with the third equation, apply S− and note the commutativity of each of the three squares pasted west or south of the result, as shown in the diagram below. From the definition of μ, the outer square gives the associativity equation μ · Sμ = μ · μS.

\xymatrix{S^{3} \ar[r]^{S^{2}ξ} \ar[d]_{SξS} & S^{2}HS \ar[r]^{SψS} \ar[d]_{SξHS} & S^{2} \ar[d]^{Sξ} \\ SHS^{2} \ar[r]^{SHSξ} \ar[d]_{ψS^{2}} & SHSHS \ar[r]_{SHψS} \ar[d]_{ψSHS} & SHS \ar[d]^{ψS} \\ S^{2} \ar[r]^{Sξ} & SHS \ar[r]^{ψS} & S.}

Finally, starting with μ · Sμ = μ · μS, get the third equation of the statement from

[figure: S^{2}; HS^{3}; HS^{2}; SHS^{2}; HS^{2}HS^{2}; HSHS^{2}; HS^{2}; SHS; HS^{2}HS; HSHS; HS; S^{2}; SHS^{2}; S; SHS; HS^{2}; φS^{2}; SφS; 1_{S^{2}}; SφS; HμS; HS^{2}φS; HSμ; HSφS; 1_{HS^{2}}; φSHS^{2}; SHμ; HμHS^{2}; HS^{2}Hμ; HψS^{2}; HSHμ; Hμ; φSHS; HμHS; HψS; μ; ψS^{2}; SHμ; φS; ψS; Hμ]

Now recall, from [Borceux, 1994] say, the bicategory Pro of categories, profunctors, and equivariant 2-cells. There is a pseudofunctor (−)_{∗}: Cat → Pro which is the identity on objects and takes a functor F : X → A to the profunctor with F_{∗}(A, X) = A(A, F X). For any parallel pair of functors F, G: X → A, there is a bijection between equivariant 2-cells F_{∗} → G_{∗} and natural transformations F → G. That is, (−)_{∗} is locally fully faithful. Most importantly, for any functor F, there is an adjunction F_{∗} ⊣ F^{∗} in Pro, where F^{∗}(X, A) = A(F X, A). It follows that to describe a monad (S, η, μ) in Cat via an extension system, we can either use the general theory of the bulk of this paper or avail ourselves of the adjunction S_{∗} ⊣ S^{∗} in Pro and proceed using the elementary definition provided by the data of Lemma 9.1, subject to the equations (25).

Now, note that in Pro the composite S^{∗}S_{∗} : C → C has S^{∗}S_{∗}(B, A) = C(SB, SA) so that to give a two cell ξ: S_{∗} → S^{∗}S_{∗} in Pro is to give an equivariant family of functions (ξ_{B,A})_{B,A} taking arrows B → SA to SB → SA, whose effect is denoted, as usual, f ↦ f^{𝕊}. Equivariance of ξ in the variable B means that, for all g: C → B, we have (fg)^{𝕊} = f^{𝕊}·Sg, which is just the blister equation (3) of Section 2. Equivariance of ξ in the variable A means that, for all u: A → X, we have (Su · f)^{𝕊} = Su · f^{𝕊} which follows easily from (6). The point here is that when the data for the elementary definition is expanded in Pro, it amounts to the same data required for the non-elementary definition in Cat. This reconciles our usage of the term extension system in both cases.

In Section 8, we remarked that Manes’ original presentation of monads in Cat does not require that S: C → C be given as a functor nor that η: 1_{C} → S be given as a natural transformation. It is interesting to note that the bicategory Pro also provides a venue to discuss this simplification, in terms of the formal theory of monads. For any category C, write |C| for the set of objects of C regarded as a discrete category. In Pro we have, on the object |C|, the monad ℂ where ℂ(B, A) = C(B, A). The canonical, identity on objects, functor K: |C| → C admits an (op)action of ℂ that we call κ: K_{∗}ℂ → K_{∗}. The (C, A) component of this action, ∑_{B∈|C|} K_{∗}(C, B) × ℂ(B, A) → K_{∗}(C, A) is determined by the C(C, B) × C(B, A) → C(C, A) which are given by the composition of C.

The profunctor K_{∗}, together with κ, exhibits C as the Kleisli object in Pro for the monad ℂ. Moreover, the equivalence mediated by this data restricts to functors, in the sense that to give a functor F : C → D is to give a functor F̂: |C| → D together with an action F̂_{∗}ℂ → F̂_{∗}. Similarly, to give a natural transformation τ : F → G: C → D is to give a natural transformation τ̂: F̂ → Ĝ: |C| → D that respects the actions. An action F̂_{∗}ℂ → F̂_{∗} has a mate ℂ → F̂^{∗}F̂_{∗}. The two action equations translate to make ℂ → F̂^{∗}F̂_{∗} a morphism of monads on |C| and conversely.

In the case of the data given originally by Manes, we have in these terms: η: K → Ŝ: |C| → C and now the requisite morphism of monads ℂ → Ŝ^{∗}Ŝ_{∗} is given by the composite

\xymatrix{ℂ = K^{∗}K_{∗} \ar[r]^{K^{∗}η_{∗}} & K^{∗}Ŝ_{∗} \ar[r]^{(−)^{𝕊}} & Ŝ^{∗}Ŝ_{∗}}

— the monad morphism equations arising from two of those satisfied by the extension operator (−)^{𝕊}.

References

Jon Beck. Distributive laws. Lecture Notes in Mathematics 80, (1969), 119-140.

F. Borceux. Handbook of Categorical Algebra. Cambridge University Press, 1994.

S. Eilenberg and J. Moore, Adjoint functors and triples. Illinois J. Math. 9 (1965), 381-398.

Stephen Lack and Ross Street, The formal theory of monads II. Journal of pure and applied algebra 175 (2002) 234-265.

E. G. Manes. Algebraic Theories. Springer-Verlag, 1976.

Ernie Manes and Philip Mulry, Monad compositions I: general constructions and recursive distributive laws. Theory and Applications of Categories, Vol. 18, 2007, No. 7, pp 172-208.

F. Marmolejo, R. D. Rosebrugh and R. J. Wood, A basic distributive law. J. Pure and Appl. Algebra 168 (2002) 209-226.

F. Marmolejo, Doctrines whose structure forms a fully faithful adjoint string. Theory and Applications of Categories, Vol 3, No. 2, 1999, pp. 24-44.

R. H. Street, The formal theory of monads. J. Pure and Appl. Algebra 2 (1972) 149-168.

D. Varacca. Probability, nondeterminism and concurrency: two denotational models for probabilistic computation. PhD Dissertation, BRICS PhD School, 2003.

Instituto de Matemáticas Universidad Nacional Autónoma de México Área de la Investigación Científica, Circuito Exterior, Ciudad Universitaria Coyoacán 04510, México, D.F. México

Department of Mathematics and Statistics, Dalhousie University Chase Building, Halifax, Nova Scotia, Canada B3H 3J5

Email: quico@matem.unam.mx
      rjwood@mathstat.dal.ca

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/24/4/24-04.{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: barr@math.mcgill.ca

Assistant TEX editor. Gavin Seal, Ecole Polytechnique Fédérale de Lausanne:

gavin seal@fastmail.fm

Transmitting editors.

Clemens Berger, Université de Nice-Sophia Antipolis, cberger@math.unice.fr 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: ronnie.profbrown (at) btinternet.com Aurelio Carboni, Università dell Insubria: aurelio.carboni@uninsubria.it Valeria de Paiva, Cuill Inc.: valeria@cuill.com Ezra Getzler, Northwestern University: getzler(at)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 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 Tom Leinster, University of Glasgow, T.Leinster@maths.gla.ac.uk 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