Theory and Applications of Categories, Vol. 13, No. 9, 2004, pp. 147–163.

COMPOSING PROPS

Dedicated to Aurelio Carboni on the occasion of his sixtieth birthday

STEPHEN LACK

Abstract. A PROP is a way of encoding structure borne by an object of a symmetric monoidal category. We describe a notion of distributive law for PROPs, based on Beck’s distributive laws for monads. A distributive law between PROPs allows them to be composed, and an algebra for the composite PROP consists of a single object with an algebra structure for each of the original PROPs, subject to compatibility conditions encoded by the distributive law. An example is the PROP for bialgebras, which is a composite of the PROP for coalgebras and that for algebras.

1. Introduction

1.1 Monads provide a formalism for describing structure borne by an object of a category; the resulting structures are called algebras. A distributive law in the sense of Beck [1] allows two such monads to be “composed”; an algebra for the composite monad consists of an algebra for each of the original monads, subject to certain compatibility conditions between the two algebra structures. The fundamental example is the structure of a ring, which involves an abelian group (the additive structure) and a monoid (the multiplicative structure) subject to the compatibility condition of distributivity. There is a distributive law between the monad for abelian groups and the monad for monoids, and the composite monad is precisely the monad for rings. Not all such compatibility conditions can be expressed in terms of a distributive law, but in practice very many do so.

1.2 In this paper we consider a different formalism for describing structure borne by an object of a category; in our case the category is supposed to be symmetric monoidal. We shall write ⊗ for the tensor product, I for the unit, and c for the symmetry, and write as if the monoidal structure were strict (this simplification is made legitimate by the coherence theorem for symmetric monoidal categories — see [9, Section VII.2]). The formalism, recalled below, is that of a PROP [8], or “one-sorted symmetric monoidal theory”. The structures on an object A involve morphisms A^{⊗m} → A^{⊗n}, called operations, between tensor powers of A, with these operations being subject to equations between derived such operations, built up out of the given operations using the symmetric monoidal category structure. Thus monoids (also known as algebras, and consisting of maps A⊗A → A and I → A subject to the usual associative and unit laws) are the algebras for a PROP, but so too are comonoids (also known as coalgebras; involving maps A → A ⊗ A and A → I). One can also consider an object A equipped with a monoid structure and a comonoid structure, subject to certain compatibility conditions: of course the most important case is that of bimonoids or bialgebras, but we shall also consider Carboni’s notion of separable algebra [3]. We shall define and study a notion of distributive law between PROPs and see that such distributive laws allow one to “compose” PROPs, and in particular that the bialgebras and the separable algebras are each the algebras for such composite PROPs.

Received by the editors 2003-08-07.

Published on 2004-12-05.

2000 Mathematics Subject Classification: 18D10, 18C10, 18D35.

Key words and phrases: symmetric monoidal category, PROP, monad, distributive law, algebra, bialgebra.

\begin{matrix}c \\ ◯ \end{matrix} Stephen Lack, 2004. Permission to copy for private use granted.

1.3 If something is a composite, then we might expect that it can be factorized into its constituent parts, and this point of view does turn out to be helpful in connection with composite PROPs. The fact that the PROP for bialgebras, described in [11], can be factorized as the PROP for comonoids followed by the PROP for monoids amounts to the fact that for a bialgebra A, any map A^{⊗m} → A^{⊗n} built up out of the basic structure maps can be factorized, in an essentially unique way, as a map A^{⊗m} → A^{⊗p} built up out the comonoid structure, followed by a map A^{⊗p} → A^{⊗n}, built up out of the monoid structure. For instance the composite

\xymatrix{A ⊗ A \ar[r]^{μ} & A \ar[r]^{δ} & A ⊗ A}

of the multiplication μ and the comultiplication δ, can be factorized as

\xymatrix{A ⊗ A \ar[r]^{δ⊗δ} & A ⊗ A ⊗ A ⊗ A \ar[r]^{1⊗c⊗1} & A ⊗ A ⊗ A ⊗ A \ar[r]^{μ⊗μ} & A ⊗ A}

and here all the comonoid structure comes before the monoid structure. This factorization is only “essentially unique” because the symmetry can be regarded as part of the comonoid structure or as part of the monoid structure, and extra symmetries can be artificially introduced into each side.

1.4 Before looking at PROPs, we shall first consider the case of PROs, which involve monoidal categories rather than symmetric monoidal categories. They are less expressive than PROPs, but many important structures can still be defined in terms of PROs, including monoids and comonoids, although not commutative monoids, cocommutative comonoids, or bialgebras. Although our main interest is in distributive laws between PROPs, it will be useful to have available the machinery of distributive laws between PROs, and the latter are also somewhat easier to describe, for the following reason. As observed by Street [13], one can consider monads not on a category but on an object of some bicategory, and the theory of distributive laws works perfectly for such “monads in a bicategory”. Moreover, PROs can be considered as monads in a certain bicategory Span(Mon) (of spans in the category of monoids), and we can then simply apply the general theory. PROPs can also be regarded as monads in a bicategory, as we shall see in Section 4 below, but the bicategory in question is somewhat more complicated.

1.5 There is a close analogy between PROs, PROPs, and Lawvere theories: Lawvere theories are the one-sorted finite product theories, PROPs are the one-sorted symmetric monoidal theories, while PROs are the one-sorted monoidal theories; here the “onesortedness” refers to the fact that the structure in question is borne by a single object, as opposed to such structures as a ring with a module over it.

1.6 The construction of PROPs using distributive laws is clearly closely related to their construction using generalized Q-constructions, as in [11], but we have chosen the approach presented here because of the flexibility provided by working with various bicategories of spans, and in order to make the connection with prior work on distributive laws.

1.7 The plan of the paper is as follows. In Section 2, we review the notions of PROPs, PROs, and their algebras. In Section 3, we look at the bicategories Span and Span(Mon), at the monads therein, and at distributive laws between such monads, and apply this to the case of PROs. In Section 4 we study distributive laws for PROPs, and in Section 5 we look at some examples of distributive laws between PROPs.

2. PROPs

2.1 In this section we recall the formal definitions of PROs and PROPs. A PRO is a strict monoidal category 𝕋 whose set of objects is the set of natural numbers, with tensor product given by addition. For an arbitrary strict monoidal category 𝒱 , an algebra of 𝕋 in 𝒱 is a strict monoidal functor from 𝕋 to 𝒱 . The image of a map ξ : m → n in 𝕋 will thus be a map A^{⊗m} → A^{⊗n} in 𝒱 , usually also denoted by ξ. (Algebras in non-strict monoidal categories can also be defined, but it is easier to do this in a slightly different manner, described below.) A morphism of algebras is a monoidal natural transformation. These algebras and their morphisms together constitute a category 𝕋-Alg, equipped with a forgetful functor 𝕋-Alg → 𝒱 given by evaluation at the object 1 of 𝕋.

2.2 An example is the strict monoidal category 𝔻 of finite ordinals and order-preserving maps (the “algebraicist’s simplicial category”), with tensor product being given by ordinal sum. The objects have the form n = {0 < 1 < … < n − 1}; the ordinal sum of two ordinals is their disjoint union, with all elements of the first ordinal deemed to be less than all elements of the second ordinal. An algebra of 𝔻 in a monoidal category 𝒱 is just a monoid in 𝒱 : the multiplication of the monoid is the image of the map 2 → 1 in 𝔻, and the unit is the image of the map 0 → 1; see [9, Section VII.5] for details.

2.3 A strict monoidal category can be seen either as a monoid in the monoidal category Cat of categories, or as an internal category in the category Mon of monoids. From the latter point of view, a PRO is precisely a category in Mon whose monoid of objects is the natural numbers.

A morphism of PROs is a strict monoidal functor which is the identity on objects; from the point of view of the previous paragraph this amounts to an internal functor in Mon which is the identity on objects. Thus there is a category PRO of PROs and their morphisms. Algebras for a PRO can be viewed as morphisms of PROs: given an object A in a monoidal category 𝒱 , not necessarily strict, there is a PRO ⟨A, A⟩ whose hom-sets are given by ⟨A, A⟩(m, n) = 𝒱 (A^{⊗m}, A^{⊗n}), with the composition and tensor product in ⟨A, A⟩ defined using the corresponding structures in 𝒱 . A morphism of PROs from 𝕋 to ⟨A, A⟩ is precisely a 𝕋-algebra with underlying object A. Algebra morphisms can be defined in a similar way. If f : A → B is a morphism in 𝒱 , there is a PRO {f, f} with hom-sets {f, f}(m, n) given by the pullback

\xymatrix{\{f, f\}(m, n) \ar[r] \ar[d] & 𝒱 (B^{⊗m}, B^{⊗n}) \ar[d]^{𝒱 (f^{⊗m},B^{⊗n})} \\ 𝒱 (A^{⊗m}, A^{⊗n}) \ar[r]_{𝒱 (A^{⊗m},f^{⊗n})} & 𝒱 (A^{⊗m}, B^{⊗n})}

in Cat. The projections of these pullbacks organize themselves into morphisms of PROs D : {f, f} → ⟨A, A⟩ and C : {f, f} → ⟨B, B⟩. Suppose now that A and B have 𝕋-algebra structures corresponding to PRO-morphisms P : 𝕋 → ⟨A, A⟩ and Q : 𝕋 → ⟨B, B⟩. Then f : A → B is a morphism of 𝕋-algebras if and only if the diagram

\xymatrix{𝕋(m, n) \ar[r]^{Q} \ar[d]_{P} & 𝒱 (B^{⊗m}, B^{⊗n}) \ar[d]^{𝒱 (f^{⊗m},B^{⊗n})} \\ 𝒱 (A^{⊗m}, A^{⊗n}) \ar[r]_{𝒱 (A^{⊗m},f^{⊗n})} & 𝒱 (A^{⊗m}, B^{⊗n})}

commutes, in which case the maps 𝕋(m, n) → {f, f}(m, n) induced by the universal property of the pullback {f, f}(m, n) organize themselves into a PRO-morphism F : 𝕋 → {f, f} with DF = P and CF = Q. Another point of view is that to make f : A → B into a morphism between some 𝕋-algebra structures on A and B is to give a PRO-morphism F : 𝕋 → {f, f}; one then finds the relevant 𝕋-algebra structures by looking at the PROmorphisms DF : T → ⟨A, A⟩ and CF : T → ⟨B, B⟩.

2.4 A PROP is simply a PRO which, as a monoidal category, is equipped with a symmetry. Since the set of objects of a PRO is just the natural numbers, this is essentially saying that the category “contains the permutations”; to express this more formally, we introduce the PRO ℙ which is the skeletal symmetric monoidal category of finite sets and bijections. The objects are as usual the natural numbers; there are morphisms from m to n only if m = n, in which case the set of such morphisms is the symmetric group on n elements. A PROP is now a PRO 𝕋 with a morphism of PROs J : ℙ → 𝕋; the symmetry isomorphism c : m + n → n + m in 𝕋 is the image under J of the permutation of m + n which interchanges first m elements with the last n. A morphism of PROPs is a morphism of PROs which commutes with the maps out of ℙ; in other words, the category PROP of PROPs and their morphisms is just the slice category ℙ/PRO.

2.5 For a symmetric strict monoidal category 𝒱 , an algebra in 𝒱 of the PROP 𝕋 is a symmetric strict monoidal functor from 𝕋 to 𝒱 , while a morphism of such algebras is a monoidal natural transformation. If 𝒱 is an arbitrary symmetric monoidal category (not necessarily strict) then for an object A of 𝒱 , the PRO ⟨A, A⟩ is canonically a PROP, and A becomes an algebra of 𝕋 when there is given a PROP morphism from 𝕋 to ⟨A, A⟩; similarly {f, f} is a PROP and can be used to define morphisms of algebras.

2.6 If we need to distinguish between a PROP 𝕋 and its underlying PRO, obtained by forgetting the symmetry, we write 𝕋_{0} for the latter. In particular, it is important to note that although every 𝕋-algebra is a 𝕋_{0}-algebra, the converse is false. On the other hand, there is no distinction between the corresponding notions of morphism, and the category of 𝕋-algebras is a full subcategory of the category of 𝕋_{0}-algebras.

3. Distributive laws for PROs

3.1 Given monads T = (T, μ, η) and S = (S, μ, η) on a category 𝒞, a distributive law [1] of T over S consists of a natural transformation λ : T S → ST satisfying various conditions; one way of expressing these conditions is that ST becomes a monad with multiplication and unit given by

\xymatrix{ST ST \ar[r]^{SλT} & SST T \ar[r]^{SSμ} & SST \ar[r]^{μT} & ST \\ 1 \ar[r]^{η} & S \ar[r]^{Sη} & ST.}

Street [13] showed that the whole theory of monads, distributive laws, Eilenberg-Moore objects, and so on, can be developed in the context of an arbitrary bicategory (actually Street worked with a 2-category, but the modifications for dealing with a bicategory are relatively minor, and in any case by the coherence theorem [10] for bicategories one can always replace a bicategory by a biequivalent 2-category). The “formal theory of monads” of [13] was further developed by Street and the author in [6].

We shall often work with bicategories with only one object; these are essentially the same thing as monoidal categories: the objects of the monoidal category are the 1-cells of the bicategory, and the tensor product becomes the composition of 1-cells. A monad in a one-object bicategory is the same thing as a monoid (or algebra) in the monoidal category. Thus we can consider monoids T = (T, μ, η) and S = (S, μ, η) with a distributive law λ : T ⊗ S → S ⊗ T, and this induces a monoid structure on S ⊗ T. The following is an immediate generalization of a result of Beck:

3.2. Proposition. There is a bijection between monoid maps S ⊗ T → R and pairs f : S → R and g : T → R of monoid maps making the diagram

\xymatrix{T ⊗ S \ar[r]^{g⊗f} \ar[dd]_{λ} & R ⊗ R \ar@{-->}[dr]^{m} \\  &  & R \\ S ⊗ T \ar[r]_{f⊗g} & R ⊗ R \ar@{-->}[ur]_{m}}

commute, where m denotes the multiplication of the monoid R. The bijection sends the pair (f, g) to the map m(f ⊗ g) : S ⊗ T → R along the bottom of the diagram.

3.3 The case of monads in the bicategory Span was studied in detail by Rosebrugh and Wood in [12], where the name set-mat was used rather than Span. An object of Span is just a set, while a morphism from X to Y consists of a set E with functions d : E → X and c : E → Y. A 2-cell from (E, d, c) to (E′, d′, c′) consists of a morphism E → E′ compatible with the maps into X and Y. The 1-cells are composed by pullback; with the evident compositions of 2-cell this gives a bicategory. A monad in Span consists of a set X, an endomap of X in the form of a set E with functions d, c : E → X, an associative multiplication m : E ×_{X} E → E, with a unit X → E; in other words, a monad in Span is precisely a category. A distributive law between two such monads allows one to “compose” the corresponding categories. The “composite” category can be factorized into its constituent parts, and this amounts to giving a certain sort of “strict” factorization system on the category, as is explained in [12]. In these strict factorization systems, there are as usual two subcategories ℰ and ℳ, and every arrow has a unique factorization (not just unique up to isomorphism) as an ℰ followed by an ℳ. This uniqueness means however that only the identities are contained in both ℰ and ℳ, not all the isomorphisms. Thus a strict factorization system in this sense is not (strictly speaking!) a factorization system, although it does induce one when one closes ℰ and ℳ under composition with isomorphisms.

3.4 Given any category 𝒞 with pullbacks one can construct the bicategory Span(𝒞) of spans in 𝒞, consider monads in it, and distributive laws between them. We shall use the symbol ⊗ to denote composition in Span(𝒞). Just as in the case 𝒞 = Set, a monad in Span(𝒞) is precisely an internal category in 𝒞. Once again, distributive laws between such monads allow one to “compose” the corresponding categories, and such composite categories have a strict factorization system, in the evident 𝒞 -internal sense. (The possibility of working in Span(𝒞) rather than Span was pointed out already in [12].)

3.5 Here we are interested in the case 𝒞 = Mon. The forgetful functor U : Mon → Set preserves finite limits, and so induces a homomorphism of bicategories Span(U) : Span(Mon) → Span(Set), which takes monads to monads (by taking a strict monoidal category to its underlying category), distributive laws to distributive laws, and so on.

As we have seen, a monad in Span(Mon) is a category in Mon, and a PRO is such a category whose monoid of objects is ℕ; in other words, a monad in Span(Mon) on the object ℕ. We shall write 𝒩 for the monoidal category Span(Mon)(ℕ, ℕ) of spans of monoids from ℕ to ℕ, with tensor product given by composition. Then the category PRO of PROs is just the category of monoids in 𝒩 . We define a distributive law between PROs to be a distributive law between the corresponding monads in Span(Mon); that is, between the corresponding monoids in 𝒩 .

3.6 In the notation of [12], a distributive law in Span between categories ℰ and ℳ with the same set of objects involves giving, for each m : A → B in ℳ and e : B → C in ℰ, an object e_{λ}m, a morphism e_{ε}m : A → e_{λ}m in ℰ, and a morphism e_{μ}m : e_{λ}m → B in ℳ satisfying various conditions. The maps e_{μ}m and e_{ε}m will give the factorization in the composite category of the composite em : A → C.

If 𝕋 and 𝕊 are PROs, and L : 𝕋⊗𝕊 → 𝕊⊗𝕋 is a distributive law, we adapt slightly the notation of [12]: given σ : m → n in 𝕊 and τ : n → p in 𝕋, we write σ_{𝕋}τ : m → σ_{L}τ and σ_{𝕊}τ : σ_{L}τ → p for the induced maps. As we saw above, the homomorphism of bicategories Span(U) : Span(Mon) → Span takes distributive laws to distributive laws, and so a distributive law between PROs induces a distributive law between their underlying categories. Conversely, a distributive law between the underlying categories of two PROs is a distributive law of PROs if and only if the operations σ_{L}τ, σ_{𝕋}τ and σ_{𝕊}τ are compatible with the monoidal structure:

3.7. Theorem. A distributive law between PROs 𝕋 and 𝕊 consists of a distributive law L : 𝕋 ⊗ 𝕊 → 𝕊 ⊗ 𝕋 between their underlying categories, for which

(σ ⊗ σ′)_{L}(τ ⊗ τ′) = (σ_{L}τ) ⊗ (σ′_{L}τ′)
(σ ⊗ σ′)_{𝕊}(τ ⊗ τ′) = (σ_{𝕊}τ) ⊗ (σ′_{𝕊}τ′)
(σ ⊗ σ′)_{𝕋}(τ ⊗ τ′) = (σ_{𝕋}τ) ⊗ (σ′_{𝕋}τ′).

As usual, a distributive law induces a composite monad, and this composite monad has a strict factorization system, where the two subcategories are actually strict monoidal subcategories. Thus a strict factorization system on a PRO is nothing but a strict factorization system on its underlying category, for which the two subcategories are closed under the tensor product:

3.8. Theorem. A PRO ℝ is the composite 𝕊 ⊗ 𝕋 of PROs 𝕊 and 𝕋 if and only if 𝕊 and 𝕋 are subcategories of ℝ, closed under the tensor product, and every map in ℝ has a unique factorization as a map in 𝕋 followed by a map in 𝕊.

3.9 We now turn to 𝕊 ⊗ 𝕋-algebras, and show that they have the expected description, closely analogous to that of [1]. By Proposition 3.2 we can describe PRO-morphisms from 𝕊⊗𝕋 to an arbitrary PRO ℝ; we apply this in the case ℝ = ⟨A, A⟩ to obtain a description of the algebras for 𝕊⊗𝕋. Recall that an ℝ-algebra structure on A is just a PRO morphism from ℝ to ⟨A, A⟩, and that we use the same name for the morphism m → n in ℝ and the induced map A^{⊗m} → A^{⊗n} in the monoidal category 𝒱 .

3.10. Proposition. If 𝕊 ⊗ 𝕋 is a composite PRO induced by a distributive law L : 𝕋⊗𝕊 → 𝕊⊗𝕋, then an 𝕊⊗𝕋-algebra structure on A consists of an 𝕊-algebra structure on A and a 𝕋-algebra structure on A subject to the condition that

\xymatrix{A^{⊗m} \ar[r]^{σ} \ar[d]_{σ_{𝕋}τ} & A^{⊗n} \ar[d]^{τ} \\ A^{⊗q} \ar[r]_{σ_{𝕊}τ} & A^{⊗p}}

commutes for all σ : m → n in 𝕊 and τ : n → p in 𝕋, where q denotes σ_{L}τ.

3.11 In order to describe the morphisms of 𝕊⊗𝕋-algebras, we use the case ℝ = {f, f} of Proposition 3.2. To make f into a morphism of 𝕊⊗𝕋-algebras is to give a PRO-morphism F : 𝕊 ⊗ 𝕋 → {f, f} that is, to give PRO-morphisms F^{𝕊} : 𝕊 → {f, f} and F^{𝕋} : 𝕋 → {f, f} rendering commutative

\xymatrix{𝕋 ⊗ 𝕊 \ar[r]^{F^{𝕋}⊗F^{𝕊}} \ar[dd]_{L} & \{f, f\} ⊗ \{f, f\} \ar@{-->}[dr]^{M} \\  &  & \{f, f\}. \\ 𝕊 ⊗ 𝕋 \ar[r]_{F^{𝕊}⊗F^{𝕋}} & \{f, f\} ⊗ \{f, f\} \ar@{-->}[ur]_{M}}

By the universal property of the pullbacks defining {f, f}, commutativity of this diagram can be tested by composing with the projections D : {f, f} → ⟨A, A⟩ and C : {f, f} → ⟨B, B⟩. The resulting diagrams are

\xymatrix{𝕋 ⊗ 𝕊 \ar[r]^{(DF^{𝕋})⊗(DF^{𝕊})} \ar[dd]_{L} & ⟨A, A⟩ ⊗ ⟨A, A⟩ \ar@{-->}[dr]^{M} \\  &  & ⟨A, A⟩ \\ 𝕊 ⊗ 𝕋 \ar[r]_{(DF^{𝕊})⊗(DF^{𝕋})} & ⟨A, A⟩ ⊗ ⟨A, A⟩ \ar@{-->}[ur]_{M}}

and a corresponding one for C; commutativity of these diagrams is part of the fact that A and B are 𝕊 ⊗ 𝕋-algebras, and so we have:

3.12. Proposition. If 𝕊 ⊗ 𝕋 is a composite PRO induced by a distributive law L : 𝕋 ⊗ 𝕊 → 𝕊 ⊗ 𝕋, and A and B have 𝕊 ⊗ 𝕋-algebra structures, then a morphism f : A → B is a morphism of 𝕊 ⊗ 𝕋-algebras if and only if it is a morphism of 𝕊-algebras and of 𝕋-algebras.

As warned, there are relatively few interesting examples of distributive laws between PROs (although there will be plenty of examples of distributive laws between PROPs). There are two cases worth mentioning though; both will be referred to again in Section 5.

3.13. Example. Recall that 𝔻 is the PRO of finite ordinals, and that its algebras are the monoids. As a category, 𝔻 has a well-known factorization system given by the surjections and the injections; since there are no non-identity isomorphisms this is actually a strict factorization system. Thus the category 𝔻 is a composite of the corresponding subcategories 𝔻_{e} and 𝔻_{m}, via a distributive law. Furthermore, these subcategories are closed under the tensor product, so they are themselves PROs, the distributive law is a distributive law of PROs, and the PRO 𝔻 is the composite of the PROs 𝔻_{e} and 𝔻_{m}. An algebra for 𝔻_{e} in 𝒱 is a semigroup — that is, an object A with an associative multiplication m : A ⊗ A → A — while an algebra for 𝔻_{m} is an I-pointed object — that is, an object A with an arbitrary map i : I → A. The compatibility condition between the 𝔻_{e}-structure and the 𝔻_{m}-structure says precisely that i is a unit for the semigroup, so that A is in fact a monoid. A morphism in 𝒱 is of course a morphism of monoids if and only if it preserves the multiplication and the unit — that is, if and only if it is a morphism of 𝔻_{e}-algebras and of 𝔻_{m}-algebras.

3.14. Example. The second example involves a distributive law L : ℙ ⊗ 𝔻 → 𝔻 ⊗ ℙ, defined as follows. A morphism in ℙ ⊗ 𝔻 from m to n is a pair (π, φ), where φ : m → n is an order-preserving map and π is a permutation of n. The image under L of (π, φ) will be a pair (φ_{𝔻}π, φ_{ℙ}π), where φ_{ℙ}π is a permutation of m and φ_{𝔻}π : m → n is an order-preserving map. The permutation may be specified by saying that, for i, j ∈ m, we have (φ_{ℙ}π)(i) < (φ_{ℙ}π)(j) if and only if either πφi < πφj or φi = φj and i < j. We now define φ_{𝔻}π : m → n to be the unique morphism rendering commutative

\xymatrix{m \ar[r]^{φ} \ar[d]_{φ_{ℙ}π} & n \ar[d]^{π} \\ m \ar[r]_{φ_{𝔻}π} & n,}

and observe that φ_{𝔻}π is order-preserving. A routine calculation verifies that the equations for a distributive law hold, and so that 𝔻 ⊗ ℙ becomes a PRO. In fact the canonical map ℙ → 𝔻 ⊗ ℙ makes 𝔻 ⊗ ℙ into a PROP, whose algebras are the monoids. The full subcategory of 𝔻 ⊗ ℙ consisting of the objects n with n > 0 was studied in [7, Section 6.1]. It is isomorphic to a category described in [5, p. 191] and in [11]: in the isomorphic category a morphism from m to n consists of a function f : m → n equipped with a total order on each of the fibres. Both categories were described in [4], where the maps ℙ(n, n) × 𝔻(m, n) → 𝔻(m, n) × ℙ(m, m) were informally called a “distributive law”. We shall return to 𝔻 ⊗ ℙ as a PROP in Section 5 below.

3.15 There is a subcategory ℂ of ℙ consisting of only those permutations of n = {0 < 1 < … < n − 1} generated by the cycle (01 … n − 1), but this subcategory is not closed under tensor product. The distributive law ℙ ⊗ 𝔻 → 𝔻 ⊗ ℙ of categories restricts to a distributive law ℂ ⊗ 𝔻 → 𝔻 ⊗ ℂ, but this is not a distributive law of PROs. The full subcategory of the composite category 𝔻 ⊗ ℂ consisting of the objects n with n > 0, was studied in [7, Section 6.1], in connection with cyclic homology. We shall not consider it further.

4. Distributive laws for PROPs

4.1 In this section we come to distributive laws for PROPs. Given PROPs 𝕋 and 𝕊, and a distributive law between their underlying PROs 𝕋_{0} and 𝕊_{0}, one obtains a composite PRO 𝕊_{0} ⊗ 𝕋_{0}. The problem is that this has two PROP structures, given by the maps ℙ → 𝕋_{0} → 𝕊_{0} ⊗ 𝕋_{0} and ℙ → 𝕊_{0} → 𝕊_{0} ⊗ 𝕋_{0}, since we have included the symmetry of 𝕊 and that of 𝕋 whereas really these two should be identified. In this case the correct notion of composite will be given by the coequalizer (in PRO) of these two maps ℙ → 𝕊_{0} ⊗ 𝕋_{0}.

4.2 The example of bialgebras, discussed in the introduction, is typical: one doesn’t know whether to regard the symmetry maps as being part of the monoid structure or as part of the comonoid structure. There is a further complication in that, in this case and many others, one does not even have a distributive law of the underlying PROs, but only some sort of “relaxed distributive law”, in a sense related to, but not the same as, that of [12, Section 5]. Rather than work with relaxed distributive laws, we take the approach outlined in the following paragraph. This approach could clearly be adapted to give an alternative treatment of (non-strict) factorization systems to that in [12, Section 5] or [6, Example 3.5]. This alternative approach would involve profunctors between groupoids rather than spans between sets.

4.3 Let 𝒩 be a monoidal category with colimits, preserved by tensoring on either side, and let ℙ be a fixed monoid in 𝒩 . There is a category 𝒫 of left ℙ-, right ℙ-bimodules, and this category is itself monoidal via a tensor product ⊗_{ℙ} given by “tensoring over ℙ”: the tensor product of bimodules A and B is given by the coequalizer

\xymatrix{A ⊗ ℙ ⊗ B \ar[r]^{ρ⊗B} \ar[r]_{A⊗λ} & A ⊗ B \ar[r] & A ⊗_{ℙ} B}

where λ is the left action of ℙ on B and ρ is the right action of ℙ on A. For purely formal reasons, the category Mon(𝒫) of monoids in 𝒫 is equivalent to the slice category ℙ/Mon(𝒩 ) of monoids in 𝒩 under the monoid ℙ. We apply this in the case 𝒩 = Span(Mon)(ℕ, ℕ) — the monoidal category of spans of monoids from ℕ to ℕ, with tensor product given by composition of spans. As we have seen, a monoid in ℕ is precisely a PRO, while a monoid with a monoid map out of ℙ is precisely a PROP. Thus the category PROP of PROPs may be seen as the category Mon(𝒫) of monoids in 𝒫. We now define a distributive law of PROPs to be a distributive law of monoids in 𝒫: that is, a morphism 𝕋 ⊗_{ℙ} 𝕊 → 𝕊 ⊗_{ℙ} 𝕋 of ℙ,ℙ-bimodules, satisfying the usual equations for distributive laws.

4.4 The description of the previous paragraph may be recast in the following terms. There is a bicategory Prof(Mon) whose objects are the internal categories in Mon, and whose morphisms are the internal profunctors (or modules). The monoidal category ℙ may be regarded as a category in Mon, and so as an object of Prof(Mon). A ℙ,ℙbimodule, in the sense of the previous paragraph, is just a morphism in Prof(Mon) from ℙ to ℙ. Thus a PROP is precisely a monad in the bicategory Prof(Mon) on the object ℙ.

4.5 The interpretation of a composite PROP 𝕊 ⊗_{ℙ} 𝕋 in terms of strict factorization systems is more complicated, since there is no reason in general why the maps 𝕊 → 𝕊⊗_{ℙ}𝕋 and 𝕋 → 𝕊 ⊗_{ℙ} 𝕋 should be injective, and so we cannot suppose that 𝕊 and 𝕋 constitute subcategories. As an extreme example, consider the case where 𝕊 is ℙ, and 𝕋 is the chaotic category ℕ_{ch} on ℕ; then 𝕊 ⊗ 𝕋 ≅ ℙ ⊗_{ℙ} ℕ_{ch} ≅ ℕ_{ch}, so that 𝕊 → 𝕊 ⊗_{ℙ} 𝕋 is the map ℙ → ℕ_{ch} which sends all permutations of n to the same map.

For simplicity, we focus our attention on the case where the maps 𝕊 → 𝕊 ⊗_{ℙ} 𝕋 and 𝕋 → 𝕊 ⊗_{ℙ} 𝕋 are injective; this seems to cover the examples of interest.

4.6. Theorem. Let ℝ be a PROP, and let 𝕊 and 𝕋 be subcategories of ℝ containing all the objects and all the symmetry isomorphisms, and closed under tensoring. Suppose that every map ρ in ℝ can be represented as a composite ρ = στ with σ in 𝕊 and τ in 𝕋, and that if ρ = σ′τ′ is another such representation, then there is a permutation π with τ = τ′π and πσ = σ′. Then ℝ is the composite of 𝕊 and 𝕋 via a distributive law L : 𝕋 ⊗_{ℙ} 𝕊 → 𝕊 ⊗_{ℙ} 𝕋.

Proof. Given σ : m → n in 𝕊 and τ : n → p in 𝕋, factorize the composite τσ : m → p in ℝ as τ_{𝕋}σ : m → τ_{L}σ (in 𝕋) followed by τ_{𝕊}σ : τ_{L}σ → p (in 𝕊). The object τ_{L}σ is uniquely determined, while the pair (τ_{𝕊}σ, τ_{𝕋}σ) is determined as a morphism of 𝕊⊗_{ℙ}𝕋. The uniqueness of factorizations up to the action of ℙ also guarantees that this defines a map L : 𝕋 ⊗_{ℙ} 𝕊 → 𝕊 ⊗_{ℙ} 𝕋. The equations for the distributive law follow from the associativity of composition in ℝ. The inclusions 𝕊 → ℝ and 𝕋 → ℝ induce, by Proposition 3.2, a map 𝕊 ⊗_{ℙ} 𝕋 → ℝ in PROP. This is full by the existence of factorizations, faithful by the uniqueness (modulo the actions of ℙ) of factorizations, and is the identity on objects, so is an isomorphism.

Just as in the case of PROs, we have:

4.7. Proposition. If 𝕊 ⊗_{ℙ} 𝕋 is a composite PROP induced by a distributive law L : 𝕋 ⊗_{ℙ} 𝕊 → 𝕊 ⊗_{ℙ} 𝕋, then an 𝕊 ⊗_{ℙ} 𝕋-algebra structure on A consists of an 𝕊-algebra structure on A and a 𝕋-algebra structure on A subject to the condition that

\xymatrix{A^{⊗m} \ar[r]^{σ} \ar[d]_{σ_{𝕋}τ} & A^{⊗n} \ar[d]^{τ} \\ A^{⊗q} \ar[r]_{σ_{𝕊}τ} & A^{⊗p}}

commutes for all σ : m → n in 𝕊 and τ : n → p in 𝕋, where q denotes σ_{L}τ.

4.8. Proposition. If 𝕊 ⊗_{ℙ} 𝕋 is a composite PROP induced by a distributive law L : 𝕋 ⊗_{ℙ} 𝕊 → 𝕊 ⊗_{ℙ} 𝕋, and A and B have 𝕊 ⊗_{ℙ} 𝕋-algebra structures, then a morphism f : A → B is a morphism of 𝕊 ⊗_{ℙ} 𝕋-algebras if and only if it is a morphism of 𝕊-algebras and of 𝕋-algebras.

5. Examples

In this section we look at examples of distributive laws between PROPs. Most of the PROPs were also described in [11].

5.1 Let 𝔽 be the skeletal category of finite sets, equipped with the monoidal structure given by disjoint union, and with the usual symmetry. This is a PROP whose algebras in a monoidal category 𝒱 are the commutative monoids in 𝒱 . We shall see below how 𝔽 participates in various composite PROPs, but it is also itself a composite PROP, in a manner very similar to that in which the PRO 𝔻 for monoids is a composite PRO. The category 𝔽 has subcategories 𝔽_{e} and 𝔽_{m} consisting of the surjections and the injections. These are closed under tensor product (disjoint union) and every arrow in 𝔽 has an essentially unique factorization as a surjection followed by an injection. By Theorem 4.6, the PROP 𝔽 is the composite 𝔽_{m}⊗_{ℙ}𝔽_{e} of 𝔽_{e} and 𝔽_{m}. The 𝔽_{e}-algebras are the commutative semigroups, and the 𝔽_{m}-algebras are the I-pointed objects.

5.2 The opposite 𝔽^{op} of 𝔽 is also a PROP; its algebras are the cocommutative comonoids. It is a composite 𝔽_{e}^{op} ⊗_{ℙ} 𝔽_{m}^{op}.

5.3 A morphism in 𝔽 ⊗ 𝔽^{op} from m to n consists of morphism p → m and p → n in 𝔽; that is, of a span in 𝔽. The spans

\xymatrix{ & p \ar[dl]_{α} \ar[dr]^{β} &  &  & p′ \ar[dl]_{α′} \ar[dr]^{β′} \\ m &  & n & m &  & n}

become equal in 𝔽 ⊗_{ℙ} 𝔽^{op} if there is a map π : p → p′ with α′π = α and δπ = β (of course this implies that p = p′) in other words if the spans are isomorphic as 1-cells in the bicategory Span(𝔽) of spans in 𝔽. Similarly, a morphism in 𝔽^{op} ⊗ 𝔽 from m to n is a cospan in 𝔽, and we can obtain from it a span by forming the pullback.

\xymatrix{ & p \ar[dl]_{β_{1}} \ar[dr]^{α_{1}} \\ m \ar[dr]_{α} &  & n \ar[dl]^{β} \\  & q}  (∗)

This defines a map 𝔽^{op} ⊗𝔽 → 𝔽⊗𝔽^{op} which, by the usual pasting properties of pullbacks, induces a map 𝔽^{op} ⊗_{ℙ} 𝔽 → 𝔽 ⊗_{ℙ} 𝔽^{op} satisfying the equations for a distributive law. Thus we obtain a composite PROP 𝔽 ⊗_{ℙ} 𝔽^{op}; it is the classifying category [2] of the bicategory Span(𝔽), obtained by identifying isomorphic 1-cells, and then throwing away the 2-cells. We may calculate the algebras of 𝔽 ⊗_{ℙ} 𝔽^{op} using Proposition 4.7. An algebra for 𝔽⊗_{ℙ}𝔽^{op} should consist of an object A with an 𝔽^{op}-algebra structure (a cocommutative comonoid structure) and an 𝔽-algebra structure (commutative monoid structure) subject to a compatibility condition for each morphism in 𝔽^{op} ⊗_{ℙ} 𝔽; in other words, for each pullback as in (∗) above. For a map α : m → n in 𝔽 we write, as usual, α for the corresponding structure map A^{⊗m} → A^{⊗n} of an 𝔽-algebra A, but we write α^{∗} : A^{⊗n} → A^{⊗m} for the corresponding structure map of an 𝔽^{op}-algebra. The compatibility condition amounts to commutativity of the diagram

\xymatrix{ & A^{⊗p} \ar[dr]^{β_{1}} \\ A^{⊗m} \ar@{-->}[ur]^{α_{1}^{∗}} \ar[dr]_{α} &  & A^{⊗n} \\  & A^{⊗q} \ar@{-->}[ur]_{β^{∗}}}

for each pullback diagram (∗) in 𝔽. Since every such diagram is a coproduct of diagrams in which q = 1, it will suffice to consider the case q = 1. By an inductive argument a further reduction is possible to the cases where m and n are either 2 or 0. If m = n = 2 and q = 1, then the resulting commutativity condition is

\xymatrix{ & A^{⊗4} \ar[rr]^{A⊗c⊗A} &  & A^{⊗4} \ar[dr]^{μ⊗μ} \\ A^{⊗2} \ar[ur]^{δ⊗δ} \ar[drr]_{μ} &  &  &  & A^{⊗2} \\  &  & A \ar[urr]_{δ}}

which is the usual condition that δ : A → A ⊗ A preserve the multiplication. The remaining three conditions can be similarly described, and we conclude that the 𝔽⊗_{ℙ}𝔽^{op}- algebras are precisely the commutative and cocommutative bialgebras; by Proposition 4.8 the 𝔽 ⊗_{ℙ} 𝔽^{op}-morphisms are likewise the bialgebra morphisms: that is, the maps which preserve both the algebra/monoid and the coalgebra/comonoid structure.

An alternative description of this PROP is given in [11]: it is (isomorphic to) the category of finitely generated free commutative monoids. The isomorphism is easily understood: to give a span

\xymatrix{ & p \ar[dl]_{α} \ar[dr]^{β} \\ m &  & n}

in 𝔽 is, up to isomorphism, to give the cardinality of each fibre of the map p → m × n, which in turn is to give a function m × n → ℕ. Finally this may be viewed as a function m → ℕ^{n} or as a homomorphism ℕ^{m} → ℕ^{n} of (free, finitely generated) commutative monoids.

5.4 Next we consider cospans rather than spans. A cospan in 𝔽 is the same as a map in 𝔽^{op}⊗𝔽, and the isomorphism classes of cospans in 𝔽 are the maps in 𝔽^{op}⊗_{ℙ}𝔽. Composition of cospans via pushout defines a distributive law 𝔽 ⊗_{ℙ} 𝔽^{op} → 𝔽^{op} ⊗_{ℙ} 𝔽 and the resulting composite category 𝔽^{op} ⊗_{ℙ} 𝔽 is the classifying category of the bicategory of cospans in 𝔽. Once again an algebra for 𝔽^{op} ⊗_{ℙ} 𝔽 will be an object A with a commutative monoid structure and a cocommutative comonoid structure, subject to compatibility conditions: there will be a condition for every pushout in 𝔽. This time it suffices to consider just two pushouts:

\xymatrix{ & 1 + 1 \ar[dl]_{∇} \ar[dr]^{∇} &  &  & 1 + 1 + 1 \ar[dl]_{∇+1} \ar[dr]^{1+∇} \\ 1 \ar[dr]_{1} &  & 1 \ar[dl]^{1} & 1 + 1 \ar[dr]_{∇} &  & 1 + 1 \ar[dl]^{∇} \\  & 1 &  &  & 1}

and the corresponding commutativity conditions are

\xymatrix{ & A ⊗ A \ar[dr]^{μ} &  &  & A ⊗ A ⊗ A \ar[dr]^{A⊗μ} \\ A \ar[ur]^{δ} \ar[rr]_{1} &  & A & A ⊗ A \ar[ur]^{δ⊗A} \ar[dr]_{μ} &  & A ⊗ A \\  &  &  &  & A \ar[ur]_{δ}}

which are precisely axioms (U) and (D) of [3], so that the 𝔽^{op} ⊗_{ℙ} 𝔽-algebras are precisely the commutative separable algebras of [3].

5.5 In Example 3.14 we saw how to construct a composite PRO 𝔻 ⊗ ℙ, and that the canonical map ℙ → 𝔻⊗ℙ made this into a PROP. By Proposition 3.10, an algebra for the PRO (𝔻 ⊗ ℙ)_{0} consists of an object A in a symmetric monoidal category, with 𝔻-algebra and ℙ-algebra structures on A satisfying a compatibility condition. A 𝔻-algebra structure is a monoid structure; a ℙ-algebra structure involves an isomorphism π : A^{⊗n} → A^{⊗n} for each permutation π of n. The (𝔻 ⊗ ℙ)_{0}-algebra A is a 𝔻 ⊗ ℙ-algebra if and only if the isomorphisms π : A^{⊗n} → A^{⊗n} are those induced by the symmetry. The compatibility condition is then a consequence of the naturality of the symmetry isomorphisms, and so the algebras of the PROP are just the monoids; similarly, the algebra morphisms are the monoid morphisms.

There are also distributive laws of PROs ℙ ⊗ 𝔻_{m} → 𝔻_{m} ⊗ ℙ and ℙ ⊗ 𝔻_{e} → 𝔻_{e} ⊗ ℙ inducing composite PROs 𝔻_{m} ⊗ℙ and 𝔻_{e} ⊗ℙ, and these have canonical PROP structures. Moreover, tensoring over ℙ with a free ℙ-module behaves in the usual way, and we have 𝔻_{m} ⊗ ℙ ⊗_{ℙ} 𝔻_{e} ⊗ ℙ ≅ 𝔻_{m} ⊗ 𝔻_{e} ⊗ ℙ ≅ 𝔻 ⊗ ℙ, and the PROP 𝔻 ⊗ ℙ is indeed the composite of 𝔻_{m} ⊗ ℙ and 𝔻_{e} ⊗ ℙ via a distributive law of PROPs.

5.6 Just as 𝔻 ⊗ ℙ is the PROP for monoids, so (𝔻 ⊗ ℙ)^{op} ≅ ℙ^{op} ⊗ 𝔻^{op} ≅ ℙ ⊗ 𝔻^{op} is the PROP for comonoids. It is a composite of the PROPs ℙ ⊗ 𝔻_{e}^{op} and ℙ ⊗ 𝔻_{m}^{op}, via a distributive law of PROPs (the “opposite” of the distributive law in the previous paragraph).

5.7 There is a distributive law L : 𝔽^{op} ⊗𝔻 → 𝔻⊗𝔽^{op} of PROs, which makes 𝔻⊗𝔽^{op} into a composite PRO. A morphism in 𝔽^{op} ⊗ 𝔻 from m to n is a pair (f, φ), where φ : m → p is order-preserving and f : n → p is arbitrary. One now forms the pullback

\xymatrix{q \ar[r]^{ψ} \ar[d]_{g} & n \ar[d]^{f} \\ m \ar[r]_{φ} & p}  (∗∗)

in Set, where q is given the unique ordering for which ψ is order-preserving and g is order-preserving on the fibres of ψ. In other words, for elements i and j of q, we have i ≤ j if and only if qi < qj or both qi = qj and i ≤ j. We now define L(f, φ) to be (ψ, g): the distributive law axioms are easily verified, and so 𝔻⊗𝔽^{op} becomes a PRO. It becomes a PROP via the PROP structure ℙ → 𝔽^{op} of 𝔽^{op} and the canonical map 𝔽^{op} → 𝔻 ⊗ 𝔽^{op}. An object A of a symmetric monoidal category 𝒱 becomes a (𝔻 ⊗ 𝔽^{op})_{0}-algebra if it is both a 𝔻-algebra and a 𝔽_{0}^{op}-algebra, and the usual compatibility conditions hold; it is a 𝔻 ⊗ 𝔽^{op}-algebra if the 𝔽_{0}^{op}-algebra is in fact an 𝔽^{op}-algebra. A 𝔻-algebra is a monoid, an 𝔽^{op}-algebra is a cocommutative comonoid, and compatibility involves a condition for each square (∗∗); but since each such square is a coproduct of squares with p = 1 it suffices to consider this case. Very much as in Section 5.3 above, these conditions reduce to the condition that A be a bialgebra. One analyzes the algebra morphisms similarly, and deduces that 𝔻 ⊗ 𝔽^{op} is the PROP for cocommutative bialgebras.

We have described the PRO (𝔻⊗𝔽^{op})_{0} in terms of a distributive law 𝔽_{0}^{op}⊗𝔻 → 𝔻⊗𝔽_{0}^{op}, but 𝔻 ⊗ 𝔽^{op} is also a composite PROP, via a distributive law

𝔽^{op} ⊗_{ℙ} (𝔻 ⊗ ℙ) → (𝔻 ⊗ ℙ) ⊗_{ℙ} 𝔽^{op} ≅ 𝔻 ⊗ 𝔽^{op}

of PROPs; we omit the details.

In [11] an alternative description of the PROP for cocommutative bialgebras was given: it is the opposite of the category of finitely generated free monoids.

5.8 Similarly, one can construct the PROP for commutative bialgebras as a composite PRO 𝔽 ⊗ 𝔻^{op} made into a PROP via the PROP structure of 𝔽, or as a composite PROP 𝔽 ⊗_{ℙ} (ℙ ⊗ 𝔻^{op}), or as the category of finitely generated free monoids.

5.9 Our final example concerns the PROP for bialgebras (not necessarily commutative or cocommutative). Not surprisingly, this will involve a distributive law between the PROP 𝔻 ⊗ ℙ for monoids/algebras and the PROP ℙ ⊗ 𝔻^{op} for comonoids/coalgebras, with the resulting composite being (𝔻⊗ℙ)⊗_{ℙ}(ℙ⊗𝔻^{op}) ≅ 𝔻⊗ℙ⊗𝔻^{op}. To describe the distributive law, we first describe a map L_{0} : 𝔻^{op} ⊗ 𝔻 → 𝔻 ⊗ ℙ ⊗ 𝔻^{op}. A morphism m → n in 𝔻^{op} ⊗ 𝔻 is a pair (ψ, φ), consisting of order-preserving maps φ : m → p and ψ : n → p. We form the pullback

\xymatrix{q \ar[d]_{ψ′} \ar[r]^{f} & n \ar[d]^{ψ} \\ m \ar[r]_{φ} & p}

in Set, and equip q with the unique order for which ψ′ is order-preserving and f is orderpreserving on the fibres of ψ′. There is now a unique factorization of f as a permutation π followed by an order-preserving map φ′ : q → n, with the property that ψ′π^{−1} is orderpreserving on the fibres of φ′. We now define L_{0}(ψ, φ) to be the morphism (φ′, π, ψ′) : m → n in 𝔻 ⊗ ℙ ⊗ 𝔻^{op}. The resulting morphism L_{0} : 𝔻^{op} ⊗ 𝔻 → 𝔻 ⊗ ℙ ⊗ 𝔻^{op} determines a unique morphism ℙ ⊗ 𝔻^{op} ⊗ 𝔻 ⊗ ℙ → 𝔻 ⊗ ℙ ⊗ 𝔻^{op} of ℙ,ℙ-bimodules; that is, a map L : (ℙ ⊗ 𝔻) ⊗_{ℙ} (𝔻^{op} ⊗ ℙ) → (𝔻^{op} ⊗ ℙ) ⊗_{ℙ} (ℙ ⊗ 𝔻) of ℙ,ℙ-bimodules, and this turns out to be a distributive law of PROPs.

An algebra for the composite PROP consists of an object A of a symmetric monoidal category 𝒱 , equipped with a ℙ ⊗ 𝔻-algebra (monoid) structure and a 𝔻^{op} ⊗ ℙ-algebra (comonoid) structure, satisfying a compatibility condition for each diagram

\xymatrix{ & q \ar[rr]^{π} \ar[dl]_{ψ′} &  & q \ar[dr]^{φ′} \\ m \ar[drr]_{φ} &  &  &  & n \ar[dll]^{ψ} \\  &  & p}

as above. Once again, it suffices to consider the case p = 1, and the compatibility condition becomes

\xymatrix{ & (A^{⊗n})^{⊗m} \ar[rr]^{π} &  & (A^{⊗m})^{⊗n} \ar@{-->}[dr]^{μ_{m}^{n}} \\ A^{⊗m} \ar@{-->}[ur]^{δ_{n}^{m}} \ar[drr]_{μ_{m}} &  &  &  & A^{⊗n} \\  &  & A \ar[urr]_{δ_{n}}}

where μ_{m} : A^{⊗m} → A denotes the unique map built up out of μ and η using tensoring and composition (but not symmetry isomorphisms), while δ_{n} : A → A^{⊗n} denotes the unique map built up out of δ and ε. The cases where m and n are either 2 or 0 are precisely the conditions in the definition of bialgebra; the remaining cases are then a consequence. One then deduces that 𝔻 ⊗ ℙ ⊗ 𝔻^{op} is the PROP for bialgebras. An alternative description was given in [11].

References

[1] J. Beck, Distributive laws, in: Seminar on Triples and Categorical Homology Theory, Lecture Notes Math. Vol. 80, Springer, Berlin, 1969, pp. 119–140.

[2] J. Bénabou, Introduction to bicategories, in Reports of the Midwest Category Seminar, Lecture Notes Math. Vol. 47, Springer, Berlin, 1967, pp. 1–77.

[3] A. Carboni, Matrices, relations, and group representations, J. Alg. 136:497–529, 1991.

[4] B.J. Day and R.H. Street, Abstract substitution in enriched categories, J. Pure Appl. Alg. 179:49–63, 2003.

[5] B.L. Feigin and B.L. Tsygan, Additive K-theory, in K-theory, Arithmetic, and Geometry, Lecture Notes Math. Vol. 1289, Springer, Berlin, 1987, pp. 97–209.

[6] Stephen Lack and R. Street, The formal theory of monads II, J. Pure Appl. Alg. 175:243–265, 2002.

[7] Jean-Louis Loday, Cyclic Homology, Grundlehren der Mathematischen Wissenschaften Vol. 301, Springer, Berlin 1992.

[8] S. Mac Lane, Categorical algebra, Bull. Amer. Math. Soc. 71:40–106, 1965.

[9] S. Mac Lane, Categories for the Working Mathematician, Graduate Texts in Mathematics Vol. 5, Springer, Berlin-New York, 1971.

[10] S. Mac Lane and R. Paré, Coherence for bicategories and indexed categories, J. Pure Appl. Algebra 37:59–80, 1985.

[11] Teimuraz Pirashvili, On the PROP corresponding to bialgebras, Cahiers Top. Géom. Diff. Cat. XLIII, 2002.

[12] R. Rosebrugh and R.J. Wood, Distributive laws and factorization, J. Pure Appl. Alg. 175:327–353, 2002.

[13] R.H. Street, The formal theory of monads, J. Pure Appl. Alg. 2:149–168, 2002

School of Quantitative Methods and Mathematical Sciences University of Western Sydney Locked Bag 1797 Penrith South DC NSW 1797 Australia

Email: s.lack@uws.edu.au

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

mous ftp at ftp://ftp.tac.mta.ca/pub/tac/html/volumes/13/9/13-09.{dvi,ps}

THEORY AND APPLICATIONS OF CATEGORIES (ISSN 1201-561X) will disseminate articles that significantly advance the study of categorical algebra or methods, or that make significant new contributions to mathematical science using categorical methods. The scope of the journal includes: all areas of pure category theory, including higher dimensional categories; applications of category theory to algebra, geometry and topology and other areas of mathematics; applications of category theory to computer science, physics and other mathematical sciences; contributions to scientific knowledge that make use of categorical methods.

Articles appearing in the journal have been carefully and critically refereed under the responsibility of members of the Editorial Board. Only papers judged to be both significant and excellent are accepted for publication.

The method of distribution of the journal is via the Internet tools WWW/ftp. The journal is archived electronically and in printed paper format.

Subscription information. Individual subscribers receive (by e-mail) abstracts of articles as they are published. Full text of published articles is available in .dvi, Postscript and PDF. Details will be e-mailed to new subscribers. To subscribe, send e-mail to tac@mta.ca including a full name and postal address. For institutional subscription, send enquiries to the Managing Editor, Robert Rosebrugh,

rrosebrugh@mta.ca.

Information for authors. The typesetting language of the journal is TEX, and L^{A}TEX2e is the preferred flavour. TEX source of articles for publication should be submitted by e-mail directly to an appropriate Editor. They are listed below. Please obtain detailed information on submission format and style files from the journal’s WWW server at http://www.tac.mta.ca/tac/. You may also write to tac@mta.ca to receive details by e-mail.

Editorial board.

Michael Barr, McGill University: barr@barrs.org, Associate Managing Editor Lawrence Breen, Université Paris 13: breen@math.univ-paris13.fr Ronald Brown, University of Wales Bangor: r.brown@bangor.ac.uk Jean-Luc Brylinski, Pennsylvania State University: jlb@math.psu.edu Aurelio Carboni, Università dell Insubria: aurelio.carboni@uninsubria.it Valeria de Paiva, Palo Alto Research Center: paiva@parc.xerox.com Martin Hyland, University of Cambridge: M.Hyland@dpmms.cam.ac.uk P. T. Johnstone, University of Cambridge: ptj@dpmms.cam.ac.uk G. Max Kelly, University of Sydney: maxk@maths.usyd.edu.au Anders Kock, University of Aarhus: kock@imf.au.dk Stephen Lack, University of Western Sydney: s.lack@uws.edu.au F. William Lawvere, State University of New York at Buffalo: wlawvere@buffalo.edu Jean-Louis Loday, Université de Strasbourg: loday@math.u-strasbg.fr Ieke Moerdijk, University of Utrecht: moerdijk@math.uu.nl Susan Niefield, Union College: niefiels@union.edu Robert Paré, Dalhousie University: pare@mathstat.dal.ca Robert Rosebrugh, Mount Allison University: rrosebrugh@mta.ca, Managing Editor Jiri Rosicky, Masaryk University: rosicky@math.muni.cz James Stasheff, University of North Carolina: jds@math.unc.edu Ross Street, Macquarie University: street@math.mq.edu.au Walter Tholen, York University: tholen@mathstat.yorku.ca Myles Tierney, Rutgers University: tierney@math.rutgers.edu Robert F. C. Walters, University of Insubria: robert.walters@uninsubria.it R. J. Wood, Dalhousie University: rjwood@mathstat.dal.ca