Todd Trimble Towards a doctrine of operads

Contents

Introduction

The hope for this article is to give some general theory which would encompass various notions of operad found in the literature, including nonpermutative operads, permutative or symmetric operads, braided operads, cartesian operads, and others. Roughly speaking, all such cases involve types of monoidal doctrines which distribute over the doctrine of colimit cocompletion, from which general notions of plethysm, operad, and algebras over operads can be inferred.

I am not certain of the final shape of this article, so for the time being this article may look somewhat piecemeal.

Cartesian operads and Lawvere theories

This section explores a circle of ideas involving clones in universal algebra, a cartesian version of operads, Lawvere theories, and algebras or models over such. There is no doubt that all of this material has been known to the cognoscenti for decades (and accurately regarded as folklore), but it seems to be hard to find a convenient place where it is written down.

A subsidiary purpose of this section is to provide an abstract niche in which to show that the forgetful functor from the category of algebras for a Lawvere theory TT,

Mod(T,C)C,\mathbf{Mod}(T, C) \to C,

is monadic provided that CC is (say) cocomplete and cartesian closed (the only aspect of exponentiation needed is that finite products distribute over colimits); see theorem 3. This addresses a question raised on MathOverflow in reasonably satisfying generality. The development is “soft” and in fact rather tautological, the moves being little more than manipulations based on adjunctions and universal properties. For theorem 3 in particular, there is no need to invoke a technical monadicity theorem; in effect one just writes down the monad and verifies monadicity directly. (True, the development is high-level abstract nonsense, but readers whose taste tends more toward the concrete should encounter no difficulty in verifying the claims.)

Abstract context for cartesian operads

In what follows, a category with finite products will be called an FP category. A category with finite products and small colimits over which finite products distribute will be called a cartesian monoidally cocomplete (or cmc) category.

Proposition

The functor 1Fin op1 \to Fin^{op} that names the one-element set exhibits FinSet opFinSet^{op} as the free FP category generated by 11.

In other words, if CC and DD are FP categories and Prod(C,D)\mathbf{Prod}(C, D) denotes the category of functors that preserve finite products, then evaluation at the one-element set produces an equivalence

Prod(Fin op,D)D.\mathbf{Prod}(Fin^{op}, D) \stackrel{\sim}{\to} D.
Lemma

For an FP category CC, the monoidal product on Set C opSet^{C^{op}} given by the Day convolution induced from the cartesian monoidal product in CC is cartesian monoidal.

Proof

We have an evident sequence of isomorphisms

(FG)(c) = a,bF(a)×G(b)×C(c,a×b) a,bF(a)×G(b)×C(c,a)×C(b) ( aF(a)×C(c,a))×( bG(b)×C(c,b)) F(c)×G(c)\array{ (F \otimes G)(c) & = & \int^{a, b} F(a) \times G(b) \times C(c, a \times b) \\ & \cong & \int^{a, b} F(a) \times G(b) \times C(c, a) \times C(b) \\ & \cong & (\int^a F(a) \times C(c, a)) \times (\int^b G(b) \times C(c, b)) \\ & \cong & F(c) \times G(c) }

where the second line alone uses the cartesian monoidal structure on CC (using projection maps, etc.), and the rest uses the usual yoga of Day convolution for symmetric monoidal products and the Yoneda lemma.

Proposition

The cartesian monoidal structure on Set FinSet^{Fin} is cmc, and the functor 1Set Fin1 \to Set^{Fin} that names I=hom(1,):FinSetI = \hom(1, -): Fin \to Set (I=I = the inclusion functor) exhibits Set FinSet^{Fin} as the free cmc category generated by 11.

Given two cmc categories CC, DD, let [C,D][C, D] denote the category of finite-product-preserving cocontinuous functors from CC to DD. By the previous proposition we have, for each cmc category CC, an equivalence

[Set Fin,C]C[Set^{Fin}, C] \stackrel{\sim}{\to} C

given by evaluation at I:FinSetI: Fin \to Set. In particular, taking C=Set FinC = Set^{Fin}, we have an equivalence

Set Fin[Set Fin,Set Fin]Set^{Fin} \simeq [Set^{Fin}, Set^{Fin}]

so that the monoidal product on the right side given by endofunctor composition transfers across the equivalence to a monoidal product on Set FinSet^{Fin}. This monoidal product is denoted \odot. The monoidal unit is II.

Definition

A cartesian operad is a monoid in the monoidal category (Set Fin,,I)(Set^{Fin}, \odot, I).

Concrete description of cartesian operads

We give a more concrete description of cartesian operads, beginning with a more concrete description of the equivalences

CProd(Fin op,C)[Set Fin,C]C \simeq \mathbf{Prod}(Fin^{op}, C) \simeq [Set^{Fin}, C]

for a cmc category CC. The first equivalence takes an object cc to the product-preserving functor c˜:Fin opC:nc n\tilde{c}: Fin^{op} \to C: n \mapsto c^n. This in turn is mapped, by the second equivalence, to the functor c^:Set FinC\hat{c}: Set^{Fin} \to C that takes a weight F:FinSetF: Fin \to Set to the corresponding weighted colimit of c˜\tilde{c}:

c^(F) nFinF(n)c˜(n)= nFinF(n)c n.\hat{c}(F) \coloneqq \int^{n \in Fin} F(n) \cdot \tilde{c}(n) = \int^{n \in Fin} F(n) \cdot c^n.

Of course, the inverse equivalence [Set Fin,C]C[Set^{Fin}, C] \to C just the evaluation at the object I=hom(1,)I = \hom(1, -) of Set FinSet^{Fin}.

We thus have a formula for the monoidal product \odot on Set FinSet^{Fin}:

FG= nFinF(n)G n.F \odot G = \int^{n \in Fin} F(n) \cdot G^n.

A cartesian operad consists of

satisfying monoid axioms. By the Yoneda lemma, the unit uu is given by an element eM(1)e \in M(1). The multiplication mm consists of a natural transformation

nM(n)M nM\int^n M(n) \cdot M^n \to M

which in turn consists of maps

m n,k:M(n)×M(k) nM(k)m_{n, k}: M(n) \times M(k)^n \to M(k)

natural in the argument “kk” (for kk-element sets) and dinatural in nn.

The maps m n,km_{n, k} take on a more operad-like appearance if we take advantage of cartesian structure: if k=k 1++k nk = k_1 + \ldots + k_n is a coproduct decomposition in FinFin (dual to a product decomposition in Fin opFin^{op}), with summand inclusion maps denoted i j:k jki_j: k_j \to k (dual to projection maps; cf. the proof of lemma 1), then we have composites

M(n)×M(k 1)××M(k n)1×M(i 1)××M(i n)M(n)×M(k)××M(k)=M(n)×M(k) nm n,kM(k),M(n) \times M(k_1) \times \ldots \times M(k_n) \stackrel{1 \times M(i_1) \times \ldots \times M(i_n)}{\to} M(n) \times M(k) \times \ldots \times M(k) = M(n) \times M(k)^n \stackrel{m_{n, k}}{\to} M(k),

that is to say, maps

M(n)×M(k 1)××M(k n)M(k 1++k n);M(n) \times M(k_1) \times \ldots \times M(k_n) \to M(k_1 + \ldots + k_n);

this makes the connection with operads clear.

In the literature on universal algebra, the usual term for a cartesian operad is “clone” (or rather, one usually speaks of the clone of an algebraic theory, which we are repackaging here as a cartesian operad). The following is taken from Gould, definition 1.2.1,

Definition

A clone consists of

  • A sequence of sets M(0),M(1),M(2),M(0), M(1), M(2), \ldots;

  • For every n,kn, k \in \mathbb{N}, a function = n,k:M(n)×M(k) nM(k)\bullet = \bullet_{n, k} \colon M(n) \times M(k)^n \to M(k);

  • For each nn \in \mathbb{N}, elements π 1,n,,π n,nM(n)\pi_{1, n}, \ldots, \pi_{n, n} \in M(n)

such that

  • For fM(i)f \in M(i), g 1,,g iM(j)g_1, \ldots, g_i \in M(j), and h 1,,h jM(k)h_1, \ldots, h_j \in M(k),

    f(g 1(h 1,,h j),,g i(h 1,,h j))=(f(g 1,,g i))(h 1,,h j);f \bullet (g_1 \bullet (h_1, \ldots, h_j), \ldots, g_i \bullet (h_1, \ldots, h_j)) = (f \bullet (g_1, \ldots, g_i)) \bullet (h_1, \ldots, h_j);
  • For f 1,,f nM(k)f_1, \ldots, f_n \in M(k),

    π i,n(f 1,,f n)=f i;\pi_{i, n} \bullet (f_1, \ldots, f_n) = f_i;
  • For fM(n)f \in M(n),

    f(π 1,n,,π n,n)=f.f \bullet (\pi_{1, n}, \ldots, \pi_{n, n}) = f.

To extract a functor M:FinSetM: Fin \to Set from such data, define M(f):M(m)M(n)M(f): M(m) \to M(n), for a function f:{1,,m}{1,2,,n}f: \{1, \ldots, m\} \to \{1, 2, \ldots, n\} between finite sets, by the formula

M(f)(ϕ)ϕ(π f(1),n,,π f(m),n).M(f)(\phi) \coloneqq \phi \bullet (\pi_{f(1), n}, \ldots, \pi_{f(m), n}).

The unit eM(1)e \in M(1) is given by π 1,1\pi_{1, 1}. It is not hard to verify that under these definitions, MM is functorial and m:MMMm: M \odot M \to M (as assembled from the maps m n,k= n,km_{n, k} = \bullet_{n, k}) is natural. The first equation in the definition of clone expresses the associativity of mm.

Induced monads

Each cartesian operad (M:FinSet,u:IM,m:MMM)(M: Fin \to Set, u: I \to M, m: M \odot M \to M) induces a monad on any cmc category CC, as follows. By definition of cartesian operad, we have an induced monad

()M:Set FinSet Fin(-) \odot M: Set^{Fin} \to Set^{Fin}

that is cocontinuous and preserves finite products. It follows that we have a an induced monad

[Set Fin,C][()M,1 C][Set Fin,C][Set^{Fin}, C] \stackrel{\; \; \; [(-) \odot M, 1_C]\; \; \; }{\to} [Set^{Fin}, C]

which may be transferred across the equivalence C[Set Fin,C]C \simeq [Set^{Fin}, C] to give a monad M CM_C on CC. Following the constructions above, M CM_C sends an object cc to the object named by the composite

1ISet Fin()MSet Finc^C1 \stackrel{I}{\to} Set^{Fin} \stackrel{\; (-) \odot M\; }{\to} Set^{Fin} \stackrel{\hat{c}}{\to} C

which boils down to the weighted colimit

nFinM(n)c n.\int^{n \in Fin} M(n) \cdot c^n.
Definition

An MM-algebra in CC is an algebra over the monad M CM_C.

Endomorphism operads

If CC is an FP category and cc is an object of CC, there is a tautological cartesian operad attached to cc, familiarly known as an “endomorphism operad”. Concretely, this is the functor FinSetFin \to Set whose value at nOb(Fin)n \in Ob(Fin) is

Endo c(n)hom C(c n,c)Endo_c(n) \coloneqq \hom_C(c^n, c)

and where the operadic multiplication maps

Endo c(n)×Endo c(m) nEndo c(m)Endo_c(n) \times Endo_c(m)^n \to Endo_c(m)

are given intuitively by substituting or plugging in nn mm-ary operations f 1,,f n:c mcf_1, \ldots, f_n: c^m \to c into an nn-ary function f:c ncf: c^n \to c, to produce an mm-ary operation. More formally, one forms the composite

c mf 1,,f nc nfc.c^m \stackrel{\; \; \langle f_1, \ldots, f_n \rangle \; \; }{\to} c^n \stackrel{f}{\to} c.

It is not difficult to calculate that this does indeed give a cartesian operad. It’s even easier to just believe this without even bothering to calculate! (From a logical standpoint, one could argue that since this is just an assertion of equational or FP logic, it suffices to verify the claim just in the case C=SetC = Set, since we can invoke the Yoneda embedding [which preserves and reflects FP logic] and then just argue pointwise. And of course everyone and his uncle knows it’s true in the case C=SetC = Set.)

However, these facts can also be cleanly deduced on abstract grounds. Each object cc of a cmc category CC corresponds to a cocontinuous product-preserving map

c^:Set FinC\hat{c}: Set^{Fin} \to C

which is left adjoint to the functor CSet FinC \to Set^{Fin} obtained by “currying” the functor

Fin×Chom(c˜(),)Set.Fin \times C \stackrel{\; \; \hom(\tilde{c}(-), -)}{\to} Set.

This observation is very old, going back to the 1958 paper Kan. It applies equally well if we replace CC by the cmc category Set C opSet^{C^{op}} (where we now need only that CC is a finite-product category) and replace cc by the hom-functor C(,c)C(-, c). For in that case, it follows easily from the Yoneda lemma that the curryed (curried?) functor is nothing but

Set c˜ op:Set C opSet FinSet^{\tilde{c}^{op}} \colon Set^{C^{op}} \to Set^{Fin}

(note this is well-defined – and no need to worry over the fact that Set C opSet^{C^{op}} is not locally small; we just need CC to be locally small to apply the Yoneda lemma).

In other words, we have an adjoint pair

(C(,c)^:Set FinSet C op)(Set c˜ op:Set C opSet Fin)(\widehat{C(-, c)}: Set^{Fin} \to Set^{C^{op}}) \; \dashv \; (Set^{\tilde{c}^{op}}: Set^{C^{op}} \to Set^{Fin})

where both the left and right adjoint are manifestly (small-)cocontinuous and finite-product-preserving. Their composite yields a monad, i.e., a monoid in the endofunctor category [Set Fin,Set Fin][Set^{Fin}, Set^{Fin}] of cocontinuous, product-preserving functors. This in turn gives a cartesian operad

Set c˜ opC(,c)=C(c˜,c):FinSet,Set^{\tilde{c}^{op}} \circ C(-, c) = C(\tilde{c}, c): Fin \to Set,

and it is nothing but the endomorphism operad attached to cc (we could take it as the abstract definition of the endomorphism operad).

Morphisms to the endomorphism operad

Theorem

Let CC be a cmc category, and let MM be a cartesian operad. Then algebra structures ξ:M C(c)c\xi: M_C(c) \to c over the monad M CM_C are in canonical bijection with morphisms of cartesian operads MEndo cM \to Endo_c.

Once again, this result is entirely expected for anyone familiar with ordinary operad theory. Roughly speaking, an M CM_C-algebra structure ξ:M C(c)c\xi: M_C(c) \to c is given by a collection of maps

M(n)c ncM(n) \cdot c^n \to c

which corresponds to a collection of morphisms

ϕ n:M(n)hom(c n,c)=Endo c(n)\phi_n: M(n) \to \hom(c^n, c) = Endo_c(n)

and the claim is that the conditions that ξ\xi be an algebra structure correspond exactly to the conditions that the ϕ n\phi_n constitute a morphism of cartesian operads.

This follows from a routine but slightly tedious calculation, or from a more abstract argument which we now give. According to our abstract definition of the endomorphism operad, a morphism MEndo cM \to Endo_c of cartesian operads corresponds exactly to a morphism of monoids in Set Fin,Set Fin]Set^{Fin}, Set^{Fin}],

()MSet c˜ opC(,c)^,(-) \odot M \to Set^{\tilde{c}^{op}} \circ \widehat{C(-, c)},

or in other words a morphism of monads MUF- \odot M \to U F (where UU here denotes the right adjoint Set c˜ opSet^{\tilde{c}^{op}} and FF the left adjoint hom(,c)^\widehat{\hom(-, c)}).

Generally speaking, there are a couple of equivalent ways of viewing a morphism of monads TUFT \to U F:

where “action” has the usual meaning (involving a unit axiom and an associativity axiom). This is another very old observation, going back in this case to the 1965 paper of Eilenberg and Moore. If we choose the right action, then in the case at hand we are led to a natural transformation of the form

Set Fin ()M Set Fin C(,c)^ C(,c)^ Set C op\array{ Set^{Fin} & \stackrel{\; \; (-) \odot M \; \; }{\to} & Set^{Fin} \\ & _\mathllap{\widehat{C(-, c)}} \searrow ^\mathrlap{\swArrow} & \downarrow _\mathrlap{\widehat{C(-, c)}} \\ & & Set^{C^{op}} }

i.e., a transformation

nM(n)C(,c) nC(,c)\int^n M(n) \cdot C(-, c)^n \to C(-, c)

satisfying action axioms.

Cartesian operads are equivalent to Lawvere theories

Definition

Let MM be a cartesian operad. The prop of MM is the category Prop(M)\mathbf{Prop}(M) whose objects are natural numbers 0,1,2,0, 1, 2, \ldots and whose hom-sets are defined by the formula

Prop(M)(n,m)=M(n) m\mathbf{Prop}(M)(n, m) = M(n)^m

The unit 1 n:1M(n) n1_n: 1 \to M(n)^n is given by the nn-tuple

M(i 1)(e),,M(i n)(e)\langle M(i_1)(e), \ldots, M(i_n)(e) \rangle

where i j:1ni_j: 1 \to n in FinFin names the element j{1,,n}j \in \{1, \ldots, n\}. The composition

M(m) k×M(n) mM(n) kM(m)^k \times M(n)^m \to M(n)^k

takes a pair (f 1,,f k)M(m) k(f_1, \ldots, f_k) \in M(m)^k, (g 1,,g m)M(n) m(g_1, \ldots, g_m) \in M(n)^m to the element (h j) 1jkM(n) k(h_j)_{1 \leq j \leq k} \in M(n)^k given by

h j=f j(g 1,,g m).h_j = f_j \bullet (g_1, \ldots, g_m).
Proposition

Prop(M)\mathbf{Prop}(M) has finite products, where the product of two objects m,nm, n is m+nm+n, where the product projections π m:m+nm\pi_m: m+n \to m, π n:m+nn\pi_n: m+n \to n are defined by

π m=(M(i 1)(e),,M(i m)(e))M(m+n) m,π n=(M(i m+1)(e),,M(i m+n)(e))M(m+n) n.\pi_m = (M(i_1)(e), \ldots, M(i_m)(e)) \in M(m+n)^m, \qquad \pi_n = (M(i_{m+1})(e), \ldots, M(i_{m+n})(e)) \in M(m+n)^n.

With this structure, Prop(M)\mathbf{Prop}(M) is a Lawvere theory.

Example

For the endomorphism operad Endo cEndo_c of a finite-product category, the homs of Prop(Endo c)\mathbf{Prop}(Endo_c) are given by hom(n,m)=C(c n,c m)\hom(n, m) = C(c^n, c^m), with compositions given by composition in CC.

Theorem

There is an equivalence between the category of cartesian operads and the category of Lawvere theories,

CartOpLawTh,CartOp \to LawTh,

taking a cartesian operad MM to Prop(M)\mathbf{Prop}(M).

For the inverse equivalence LawThCartOpLawTh \to CartOp: if TT is a Lawvere theory (with product-preserving map i:Fin opTi: Fin^{op} \to T on the category of finite cardinals and functions giving an isomorphism between object sets), we get a functor hom T(i(),1):FinSet\hom_T(i(-), 1): Fin \to Set which carries a structure of cartesian operad, which we will denote as Op(T)\mathbf{Op}(T).

Under the identification of cartesian operads with clones, this theorem is well-known and goes back to Lawvere’s thesis. See for instance theorem 1.5.5 of Gould.

Categories of algebras over a cmc category

Let CC be a cmc category, and let TT be a Lawvere theory. The cartesian operad Op(T)\mathbf{Op}(T) induces a monad MM on CC, as in definition 3. The category of models of TT is by definition the category of product-preserving functors

Mod(T,C)=Prod(T,C).Mod(T, C) = \mathbf{Prod}(T, C).
Theorem

The forgetful functor Mod(T,C)=Prod(T,C)CMod(T, C) = \mathbf{Prod}(T, C) \to C obtained by evaluating at 1Ob(T)1 \in Ob(T) is monadic, via an equivalence Mod(T,C)MMod(T, C) \simeq M-AlgAlg.

Proof overview

Using the development above, we have equivalences between

  • Product-preserving functors TCT \to C with underlying object cc;

  • Morphisms of Lawvere theories TProp(Endo c)T \to \mathbf{Prop}(Endo_c);

  • Morphisms of cartesian operads Op(T)Endo c\mathbf{Op}(T) \to Endo_c (theorem 2);

  • Algebra structures M(c)cM(c) \to c of the monad M:CCM: C \to C induced from Op(T)\mathbf{Op}(T) (theorem 1).

It is straightforward to check that transformations ϕ\phi between product preserving functors TCT \to C, uniquely induced from the component at 1Ob(T)1 \in Ob(T) given by a map f=ϕ 1:cdf = \phi_1: c \to d in CC, correspond precisely to such f:cdf: c \to d that are MM-algebra maps.

Sketch of a general theory of operads

The development given above for cartesian operads can be carried out analogously for other sorts of operads, perhaps along the following lines.

Let D:CatCatD: Cat \to Cat be a 2-monad on the 2-category of locally small categories lying over the 2-monad MonMon whose pseudo-algebras are monoidal categories, so that there is a given 2-monad morphism j:MonDj: Mon \to D. We probably want to assume DD is a strict 2-monad and jj is a strict 2-monad morphism, even though we will deal with pseudo-algebras over such. Possibly we also want to assume that jj is essentially surjective on objects and even an isomorphism on objects (although that could be considered “evil”), or better, that jj is eso and faithful. (Cf. ternary factorization systems on CatCat.) Roughly speaking, this would mean that the only type constructor on DD is given by a binary symbol \otimes, representing a monoidal product, but the monoidal product can be enhanced by other structural data.

We will also suppose that DD comes equipped with a distributive law

θ:DPPD\theta: D P \to P D

that is compatible with the usual distributive law MonPPMonMon P \to P Mon on which Day convolution is based. With the distributive law θ\theta, which we could view as an enhanced Day convolution, we get an accompanying 2-monad structure on PDP D.

Examples of such DD include

to name just a few.

DD-operads

Under our assumptions, the free PDP D-algebra on one generator is PD(1)=Set D(1) opP D(1) = Set^{D(1)^{op}}, and for any PDP D-algebra CC there is an equivalence

[Set D(1) op,C]C[Set^{D(1)^{op}}, C] \stackrel{\sim}{\to} C

where [C,E][C, E] denotes the category of PDP D-algebra maps. In particular, for C=Set D(1) opC = Set^{D(1)^{op}}, we have an equivalence

[Set D(1) op,Set D(1) op]Set D(1) op[Set^{D(1)^{op}}, Set^{D(1)^{op}}] \simeq Set^{D(1)^{op}}

so that the monoidal structure on the left given by endofunctor composition may be transferred across the equivalence to give a monoidal category structure on Set D(1) opSet^{D(1)^{op}}, playing the role of plethysm appropriate to the doctrine DD. The monoidal product will be denoted D\odot_D, and the monoidal unit I DI_D; here I D=hom(,i(1)):D(1) opSetI_D = \hom(-, i(1)): D(1)^{op} \to Set where i:1D(1)i: 1 \to D(1) is the generator.

Definition

A DD-operad is a monoid in the monoidal category (Set D(1) op, D,I D)(Set^{D(1)^{op}}, \odot_D, I_D).

Towards an explicit description of DD-operads

The objects of D(1)D(1) may be considered as abstract arities. If CC is a DD-algebra and cc is an object of CC, then it may be suggestive to write c ac^a for the value of an arity aOb(D(1))a \in Ob(D(1)) under the unique DD-algebra map D(1)CD(1) \to C carrying the generator 1D(1)1 \to D(1) to cc. Then we have a coend formula for the DD-plethysm product of two DD-species F,G:D(1) opSetF, G: D(1)^{op} \to Set:

F DG= aD(1)F(a)G aF \odot_D G = \int^{a \in D(1)} F(a) \cdot G^a

and accordingly one can write out a relatively “concrete” description of the structure of a DD-operad.

Of course D(1)D(1) has an underlying monoidal category (by pulling back the DD-algebra structure along j:MonDj: Mon \to D), so that arities may be tensored; it is suggestive to write a+ba + b for the monoidal product of arities a,ba, b.

Induced monads

If MM is a DD-operad, then the PDP D-algebra map

() DM:Set D(1) opSet D(1) op(-) \odot_D M: Set^{D(1)^{op}} \to Set^{D(1)^{op}}

carries a monad structure, and it follows that for any PDP D-algebra CC

References

Revised on April 27, 2013 at 00:36:53 by Todd Trimble